6.824 Artificial Intelligence, Fall 1992 Problem Set 2

Due: Beginning of class Wednesday, September 29

Problem 1 This problem is on the backpropagation learning procedure. There are many kinds of parameterized “networks”. Consider a linear sum of n inputs defined by

N(x_{1}, …, x_{n}) = ∑_{1≤i≤n} a_{i}x_{i}

We now define another function M of n inputs by computing a polynomial in N. More specifically we define M(x⃗) as follows

M(x⃗) = b_{0} + b_{1}[N(x⃗) + b_{2}[N(x⃗) + b_{3}N(x⃗)]]

Assume that you are given the parameters a_{i} and b_{j} that define the function M and a single input output pair <x⃗, y>. Give a gradient descent procedure for computing a small change in the network parameters a_{i} and b_{j} that reduces the error on this input output pair. Explain how your procedure can be used as an “on line” method of training this network to simulate a desired function.

Problem 2. This problem is about the Bayesian inference approach to concept learning. We consider an instance space where each instance assigns Boolean values to n attributes x_{1}, …, x_{n}. We consider the space of all concepts definable by Boolean expressions over these features. For example, x_{1} ∧ ¬x_{2} is the concept that is true of all instances that assign x_{1} the value T and x_{2} the value F.

In this problem we will define a probability distribution over concepts using a stochastic context free grammar. A normal (nonstochastic) context free grammar is defined by symbols that are divided into terminal symbols and nonterminal symbols plus a set of productions each of which has the form

X → s_{1}s_{2} … s_{n}

where X is a nonterminal and each s_{i} is a symbol, either terminal or nonterminal. The productions are rewrite rules for replacing nonterminal symbols by other strings. For example, consider the following grammar.

X → aXb

X → c In the above grammar X is a nonterminal symbol and a, b, and c are terminal symbols. By selecting between the above two productions for rewriting X, the symbol X can be rewritten to c, or acb or aacbb or any string of the form a^{n}cb^{n}. For any context free grammar and any nonterminal symbol X in that grammar, the set of strings of terminal symbols that can be generated from X using the productions of the language is called the language generated by X. The symbol F in the following context free grammar generates all the Boolean concepts over the attributes x_{1}, … x_{n}.

F → (F ∧ F)
F → (F ∨ F)
F → L
L → (¬A)
L → A
A → x_{1}
⋮
A → x_{n}

A stochastic context free grammar is a context free grammar in which each production is associated with a real number in the interval [0, 1] and such that for each nonterminal symbol X the sum of the weights of the productions from X is 1. The above grammar can be converted to a stochastic context free grammar by adding weights to the above productions as follows.

F →^{\frac{1}{3}} (F ∧ F)

F →^{\frac{1}{3}} (F ∨ F)

F →^{\frac{1}{3}} L

L →^{\frac{1}{2}} (¬A)

L →^{\frac{1}{2}} A

A →^{\frac{1}{n}} x_{1}

⋮

A →^{\frac{1}{n}} x_{n}

We can now define a random process for rewriting nonterminals in which every time a nonterminal symbol is rewritten we select a production for that nonterminal in such a way that the probability of selecting a given production equals the given weight of that production. In any grammar where each nonterminal generates a nonempty language this process determines a probability distribution over the strings in the language generated by each nonterminal symbol (the sum of the probabilities of all strings in the language equals 1). The above grammar determines a probability distribution over Boolean formulas.

Suppose that we are trying to learn a target concept where the target concept has been generated independently at random using the above grammar. After the target concept has been selected, instances for on which the concept is true are selected at random, giving each instance on which the concept is true equal probability. Let Ψ_{1} be the formula (f_{1} ∧ f_{2}) and let Ψ_{2} be the formula (f_{1} ∧ (f_{2} ∧ f_{3})). Suppose that we are given a data sequence D consisting of k instances such that both Ψ_{1} and Ψ_{2} are true of every instance in D. For what values of k and n is P_{r}(Ψ_{1}|D) larger than P_{r}(Ψ_{2}|D)? Justify your answer.

Problem 3. This problem is on the maximum entropy assumption. Consider a wheel such as those used on game shows. This wheel has three possible outcomes numbered 1, 2, and 3. Suppose that we are told that the wheel is biased so that the expected value on any spin is 1.5 (if all three numbers where equally likely the expected value would be 2). Give a numerical approximation to the maximum entropy probability distribution over the three possible outcomes subject to the constraint that the expected value is 1.5.

Problem 4. This problem is also on the maximum entropy assumption. Consider three propositions P, Q and R. In the maximum entropy distribution on the truth assignments to these propositions, what is the probability that P is true? Now suppose that we are given the constraint that P_{r}(R|P) = 0. What is the probability that P is assigned true in the maximum entropy distribution satisfying this constraint?