6.824 Artificial Intelligence, Fall 1992 Problem Set 3

Due: Beginning of class Wednesday, October 7

Problem 1. (25 points) This problem is on Hidden Markov Models. Consider a hidden Markov model λ with four internal state a_{1}, a_{2}, a_{3} and b and two external symbols a and b. We assume that if the internal state is either a_{1}, a_{2}, or a_{3} then the external symbol is always a and if the internal state is b then the external symbol is always b. We also assume that the state transition probability matrix is determined by four numbers A_{1}, A_{2}, A_{3} and B. A_{1} is the probability that when the machine is in state a_{1} then the next machine state remains a_{1}. A_{2}, A_{3} and B are the analogous “no change” probabilities for states a_{2}, a_{3} and b respectively. If the machine does change state it must change from an “a” state to a “b” state or vice versa, e.g., there is no chance of a transition from a_{1} to a_{2}. When the machine changes from state b to one of the a states all three a states are equally likely. Initially all four states are equally likely.

Part a. Let D be a sequence of k_{1} a’s then k_{2} b’s then k_{3} a’s then k_{4} b’s then k_{5} a’s and finally k_{6} b’s. Define a sequence S of k_{1} +k_{2} +k_{3} +k_{4} +k_{5} +k_{6} internal states and values for A_{1}, A_{2}, A_{3}, and B such that P_{r}(S|λ ∧ D) is maximized (λ is the hidden Markov model determined by A_{1}, A_{2}, B_{1} and B_{2}).

Part b. State transitions between the states a_{1}, a_{2} and a_{3} are not allowed in the above model. Is this property stable under Baum-Welch reestimation? In other words, if we use Baum-Welch reestimation to construct a new model, will this new model allw transitions between different a states? Explain your answer.

Part c. The model you constructed in part a generates the external symbols deterministically — only one external symbol is possible for a given internal state. Is this property preserved by Baum-Welch reestimation?

Part d. Describe a sequence of external symbols such that Baum-Welch reestimation starting from the above model would move to a model where the transition from the b to an a state does not give the a states equal probability. Explain your answer.

Problem 2. This problem is on the use of MAP in vision. It would be a good idea to read this problem before reading Well’s paper since the example given here might make the general formalism in the paper clearer. Suppose that we have “features” that are corners, i.e., places where two edges meet such as that shown below.

A corner can be represented by four numbers <x, y, Θ, Ψ> as shown below (in the figure Θ and Ψ are called angle1 and angle2).

Suppose that we are looking for a square in some image. A square has four corners so we have a model vector

M = {M_{1}, M_{2}, M_{3}, M_{4}}

where each M_{i} is a model corner <x_{M_{i}}, y_{M_{i}}, Θ_{M_{i}}, Ψ_{M_{i}}>. We will take a pose of the triangle to be a translation plus a rotation. A pose can therefore be specified by three numbers <x, y, Δ> where Δ is a (counter clockwise) rotation angle.

part a. Give an expression for the angle P (M_{i}, β) where M_{i} is a model angle and β is a pose as specified above. P (M_{i}, β) consists of four numbers that specify how the model angle M_{i} appears under the pose β.

Now assume that a set of angles is generated by running a feature detection algorithm (an angle detector) on an image. Let <Y_{1}, …, Y_{n}> be the set of angles detected in a given image. Each Y_{i} consists of four numbers — the four numbers that specify an angle. Let Γ be the tuple <Γ_{1}, …, Γ_{n}> where Γ_{i} is an interpretation of angle Y_{i}. Each Γ_{i} is one of the four model angles M_{j} or the special “unassigned” symbol ⊥. We assume that if Γ_{i} is M_{j} then under pose β we have that Y_{i} is P (M_{j}, β), as defined in part a, plus Gaussian noise. Assume that the noise in each of the four numbers specifying Y_{i} incorporates noise independent of the noise in the other components and the noise in each component has zero mean and variance σ_{p} for noise in positions and σ_{a} for noise in angles.

Part b. Give an expression for

P_{r}(Y_{i}|Γ, β)

as a function of the three values specifying β, the four values in the model angle Γ_{i}, and the noise variances σ_{p} and σ_{a}. Your answer should be consistent with the equations in Well’s paper.