1 Written Questions

Answer the following questions in the template provided. Then upload your solutions to Gradescope. You may use L^AT_EX or print the template and hand-write your answers then scan it in. Failure to use the template may result in a penalty. There are 52 points and 12 questions. 1.1 Semantic Segmentation

Figure 1.1: Input Image Figure 1.2: Image Segmentation

Let’s assume we have a 4 x 4 grid consisting of RGB pixels. Our task is to perform image segmentation, ie assign a label to each pixel from the set {foreground,background}. Intuitively, neighboring pixels should have similar values in y, i.e. pixels associated with a mountain should form one continuous blob. This knowledge can be naturally modeled via a Potts model which consists of potentials φ(y_i,x) that encode the likelihood that any given pixel is from our subject and pairwise potentials φ(y_i,y_j) which will encourage adjacent y’s to have the same value with high probability. If visualized as a graphical model, we would have a node for each pixel and an edge for each pair of pixels that are touching vertically or horizontally but not diagonally. We will refer to these sets as V and E respectively.

As seen in class, solving this task corresponds to finding y such that

yˆ = argmax_y log_w p(y|x)

= argmaxyXwT φ(xj,yj) + X wT φ(yj,yk)

j j,k∈E

NOTE: This is not the same model used in the programming section. We will provide the set-up for that separately.

1.2 MAP Inference with Integer Linear Programming

In this section, we will formulate our problem as an Integer Linear Program (ILP) and use it to predict the segmentation of a small patch of our image. For convenience, denote the background class with 0 and the foreground class with 1. Furthermore suppose we have variables α and β that we will be optimizating over. Let α_i(y) represent an indictator function that is one when pixel i is labeled class y. Let β_ij(y_n,y_m) represent an indicator function that is one when pixel i is set to class y_n and pixel j is set to class y_m.

First we will need to translate our requirements into a constraint set.

1. (2 points) Short answer: Write constraints on the variables α_i(y) such that each pixel i is assigned one and only one class y.
2. (4 points) Short answer: Write constraints on the variables β_ij(y_n,y_m) such that pixels i and j are consistently applied to the same classes y_n and y_m in the pairwise potentials. Note that this will only be defined over ij pairs in our edge set E.
3. (2 points) Shortanswer: Using the score functions and goal defined above, write an ILP that represents our constraint set and objective such that if solved we would have a solution to our image segmentation task.

Suppose we had the following unary feature functions:

φ₁(yellow pixel,background) = 1 φ₂(yellow pixel,foreground) = 2 φ₃(brown pixel,foreground) = 3 φ₄(brown pixel,background) = 0

In addition suppose we had the following non-zero pairwise feature functions:

φ₅(background,background) = 1 φ₆(foreground,background) = 2 φ₇(background,foreground) = 0 φ₈(foreground,foreground) = 1

Image Patch Segmentation

Figure 1.3: Extracted Image Patch and Segmentation

4. (7 points) Short answer: In this question we will walk through the process of solving the ILP for the 1 × 2 patch in the upper left hand corner of our image shown in figure 3. Assume an initial weight vector w = [1,1,1,…1].
   • What are the scores assigned by the model for all possible y configurations shown below?

	Yellow Background	Yellow Foreground
Brown Background	2	4
Brown Foreground	4	6

• What are the settings of variable α that solves the above ILP?
• What would be the updated weight vector w after running one iteration of structured perceptron?

5. (5 points) Short answer: Assume the same set-up as seen in question 4. Also assume an initial weight vector w = [1,1,1,…1] and the Hamming loss as l.
   • What are the loss augmented scores for all possible y configurations shown below?

	Yellow Background	Yellow Foreground
Brown Background	3	6
Brown Foreground	4	7

• What would be the updated weight vector w after running one iteration of structured SVM?

1.3 Loss-Augmented Inference and Learning

1. (1 point) Select all that apply: Structured Perceptron differs from Structured SVM in? Training Inference 2 Evaluation
2. (4 points) Suppose you are given an MRF’s factor graph G = (C,ψ,y) consisting of a set of factors C, potential functions ψ, and variables y ∈ Y, where Y is the output space. Each factor c ∈ C touches a subset of the variables y. The probability distribution defined by this graph decomposes multiplicatively according to the factors:

Further, you are given a loss function that decomposes additively according to the factors:

`(y<sup>∗</sup>,yˆ) = <sup>X</sup>`_c(^y_c^∗,yˆ_c)

c∈C

Show that you can define a new factor graph G⁰ (with the same factors and variables as G, but different potential functions ψ⁰) such that the most probable assignment to yˆ⁰ , argmax_y∈Y p_G0(y) solves the loss-augmented MAP inference problem for G with loss `.

1.4 Empirical Questions

The following questions should be completed after you work through the programming portion of this assignment (Section 2).

1. (12 points) Report the mean IOU and pixel accuracy scores for all models. For this question, you should run the FCN for 2 epochs and the linear SVM and structured SVM for 3 epochs each. Round each value to two significant figures

Model	Mean IOU	Pixel Accuracy
FCN (Train)
FCN (Test)	0.44	0.67
FCN+l-SVM (Train)
FCN+l-SVM (Test)	0.40	0.61
FCN+s-SVM (Train)
FCN+s-SVM (Test)	0.41	0.75

2. (10 points) Plot training and testing curves for the hinge loss (FCN+l-SVM) and structured hinge loss (FCN+s-SVM) respectively over 3 epochs. Note: Your plot must be machine generated.
3. (3 points) For any image of your choice from the test set, plot the labels predicted by FCN, FCN+lSVM and FCN+s-SVM as grayscale images. Use the visualization function provided in the code to plot images. Do you see any remarkable differences between the model predictions?
4. (1 point) Multiple Choice: Did you correctly submit your code to Autolab?

Yes

No

2. (1 point) Numerical answer: How many hours did you spend on this assignment?.