Machine Problem #7 Solution

Note: The assignment will be autograded.  It is important that  you do not use additional libraries, or change the provided functions input  and output.

 

Part 1:  Setup

 

•  Remove connect to a EWS machine.

 

ssh (netid)@remlnx.ews.illinois.edu

 

 

•  Load python  module, this will also load pip and virtualenv

 

module load python/3.4.3

 

 

•  Reuse the virtual  environment from mp1.

 

source ~/cs446sp_2018/bin/activate

 

 

•  Copy mp7 into your svn directory,  and change directory  to mp7.

 

cd ~/(netid)

svn cp https://subversion.ews.illinois.edu/svn/sp18-cs446/_shared/mp7 . cd mp7

 

 

•  Install  the requirements  through  pip.

 

pip install -r requirements.txt

 

 

•  Prevent svn from checking in the data  directory.

 

svn propset svn:ignore data .

 

Part 2:  Exercise

In this exercise we will build a structured prediction model that,  given several noisy samples Iˆ of some image I , learns a model that  attempts to recover the  image I .  To simplify the problem,  we will be representing  each pixel of the images as binary  values {0, 1} (you can

think  of these as representing  black/white).

 

The model for this function  will be a linear markov random  field represented  by a grid graph whose nodes represent the pixels in an image and whose edges connect pairs of adjacent

 

 

 

1

 

 

pixels. For a graph with n nodes, the specific scoring function used will be the following:

 

n

F (w, x1, . . . , xn , y1 , . . . , yn ) = X φu(w, xi , yi ) +   X


 

 

φpw (w, yi , yj )

i=1


(i,j)∈pairs

 

where w = [wu, wpw ] are the linear weights for the model, xi  represents  the observation  at pixel i, yi  represents  the hidden “true”  value of pixel i, Φu  is the unary  potential  function, and Φpw  is the pairwise potential  function.  The potential  functions are:

 

φu(w, xi , yi ) = wufu(xi , yi )

φpw (w, yi , yj ) = wpw fpw (yi , yj )

 

where fu and fpw  are feature functions of the form

 

fu(xi , yi ) = 1[xi  = yi ]

fpw (yi , yj ) = 1[yi  = yj ]

 

 

 

where 1[·] is the indicator  function returning  1 if the argument is true and 0 if the argument is false.  These feature  functions  attempt to enforce the  predictions  for the  true  values to be similar to the observations  (in the case of fu) and for neighboring nodes to have similar values (in the case of fpw ).

 

Inference  for this  model consists  of finding the  variable  assignments  (y1 , . . . , yn )  that maximizes the  scoring function.   Since exact  inference is slow, we will use an approximate greedy inference algorithm  that  computes  a set of beliefs br (yr ) ∈ {0, 1}, where br (yr ) = 1 indicates  an assignment  of region to the  value yr .  More specific details  for this  algorithm can be found in the code file linear mrf.py .

 

We will use the following learning objective, which is derived from the general framework for learning  presented  in the lecture  by taking  the limit as    approaches  0, replacing exact inference with our approximation, setting  C = 0, and ignoring the task-loss term:

 

   n

min X

w


X X bi (yi )φu(w, xi , yi )

i∈D


i=1 yi ∈{0,1}

+   X   X


X b(i,j)(yi , yj )φpw (w, yi , yj )

(i,j)∈pairs yi ∈{0,1} yj ∈{0,1}

!

 

− F (w, x(i), y(i) )

 

 

 

The model code template  is found in  linear mrf.py . The overall structure is provided (including  the  implementation of the  train/test loops) along with  the  function  interfaces with detailed  required functionality, which you will be required  to implement.  Specifically, you will be required to implement the following functions:

 

 

•  get unary features

 

•  get pairwise features

 

•  calculate unary potentials

 

•  calculate pairwise potentials

 

•  build training obj

 

•  inference itr

 

•  calculate local score

 

•  check convergence

 

•  get pairwise beliefs

 

The file main.py has also been provided, which allows you to run training/testing on a few provided sample images.

 

Part 3:  Writing Tests

In  test.py we have provided  basic test-cases.   Feel free to write more.  To test  the code,

run

 

nose2

 

 

 

Part 4:  Submit

Submitting the code is equivalent to committing  the code. This can be done with the follow

command:

 

svn commit -m "Some meaningful comment here."

 

 

Lastly, double check on your browser that  you can see your code at

 

https://subversion.ews.illinois.edu/svn/sp18-cs446/(netid)/mp7/