5.2 Using markov random fields for election prediction  (Page 3/5)

The energy of a given assignment is equal to $e^{\theta ·\mu }$ , where $\theta$ is a vector of parameters and $\mu$ is a vector of indicator functions, i.e. 1 means on, 0 means off. Below, we define these notions exactly [link] .

                $\theta =\left(\begin{array}{c}{\theta }_1\left(x_1\right)\\ {\theta }_1\left(x_2\right)\\ .\\ .\\ .\\ {\theta }_1\left(x_K\right)\\ {\theta }_2\left(x_1\right)\\ .\\ .\\ .\\ {\theta }_2\left(x_K\right)\\ {\theta }_3\left(x_1\right)\\ .\\ .\\ .\\ {\theta }_N\left(x_K\right)\\ {\theta }_{E_{1_1},E_{1_2}}(x_1,x_1)\\ {\theta }_{E_{1_1},E_{1_2}}(x_1,x_2)\\ .\\ .\\ .\\ {\theta }_{E_{1_1},E_{1_2}}(x_1,x_K)\\ {\theta }_{E_{1_1},E_{1_2}}(x_2,x_1)\\ .\\ .\\ .\\ {\theta }_{E_{1_1},E_{1_2}}(x_K,x_K)\\ {\theta }_{E_{2_1},E_{2_2}}(x_1,x_1)\\ .\\ .\\ .\\ {\theta }_{E_{M_1},E_{M_2}}(x_K,x_K)\end{array}\right)$                                $\mu =\left(\begin{array}{c}{\mu }_1\left(x_1\right)\\ {\mu }_1\left(x_2\right)\\ .\\ .\\ .\\ {\mu }_1\left(x_K\right)\\ {\mu }_2\left(x_1\right)\\ .\\ .\\ .\\ {\mu }_2\left(x_K\right)\\ {\mu }_3\left(x_1\right)\\ .\\ .\\ .\\ {\mu }_N\left(x_K\right)\\ {\mu }_{E_{1_1},E_{1_2}}(x_1,x_1)\\ {\mu }_{E_{1_1},E_{1_2}}(x_1,x_2)\\ .\\ .\\ .\\ {\mu }_{E_{1_1},E_{1_2}}(x_1,x_K)\\ {\mu }_{E_{1_1},E_{1_2}}(x_2,x_1)\\ .\\ .\\ .\\ {\mu }_{E_{1_1},E_{1_2}}(x_K,x_K)\\ {\mu }_{E_{2_1},E_{2_2}}(x_1,x_1)\\ .\\ .\\ .\\ {\mu }_{E_{M_1},E_{M_2}}(x_K,x_K)\end{array}\right)$

• $K$ = Total Number of Possible States (Assumed to be the same for each node here, though this isn't necessarily true)
• $N$ = Total Number of Nodes
• $M$ = Total Number of Edges
• $x_k$ = State k
• $E_{m_1}$ = The first of two nodes connected by edge m
• $E_{m_2}$ = The second of two nodes connected by edge m
• ${\theta }_n\left(x_k\right)$ = The level of energy gained by node n being in state k
• ${\theta }_{E_{m_1},E_{m_2}}(x_j,x_k)$ = The level of energy gained by the two nodes connected by edge m being in states j and k, respectively
• ${\mu }_n\left(x_k\right)$ = 1 if node n is in state k, 0 if not.
• ${\mu }_{E_{m_1},E_{m_2}}(x_j,x_k)$ = 1 if the two nodes connected by edge m are in states j and k, respectively. 0 otherwise.

It can be seen that $D=$ length of $\theta =$ length of $\mu =N*K+M*K^2$ . In general, we are interested in maximizing the amount of energy over the network (also known as maximum a posteriori inference). Since the exponential is monotonic, this is equivalent to maximizing the following binary program [link] :

The first two constraints ensure consistency between the edge indicator functions and the nodal indicator functions. The third constraint ensures that each node takes exactly one state.

Colorado counties as a markov random field

We consider each of the 64 counties of Colorado to be a node. Two counties are connected by an edge if they are geographically adjacent (see figure 2). The state of a county is the percentage of its voters in 2012 who will vote for Barack Obama (precisely it's the number of voters voting for Obama divided by the number of voters voting for Obama or Romney). For computational efficiency, we cut these percentages off at 20 and 79. In order to use this Markov Network to predict the 2012 election, we must know the model parameters, $\theta$ .

Learning the model parameters

In order to learn the model parameters, we examine presidential elections from 1960 to 2008. We note that 1960 was chosen somewhat arbitrarily but roughly represents the end of an old political era. The historical observations (call them ${\xi }_1,\cdots ,{\xi }_{13}$ ) are used in a Maximum Likelihood Estimation. This optimization problem searches for the most likely model parameters given the observed data:

Technically, our equation above gives the log -likelihood of a set of parameters $\theta$ , but this is unimportant since the logarithm is a monotonic function. $Z\left(\theta \right)$ is the partition function, i.e. the sum over all possible outcomes given a set of parameters, $\theta$ .