Starting from:
$24.99
CS769 Assignment 2 Solution
The following are the policies regarding this assignment.
2. Use Latex (online platforms such as overleaf) for writing theory questions.
3. Submit the assignment as a zip file containing latex source, and PDF file.
Questions
Let there be a graph G with V vertices and E edges. Comment on the modularity of the following functions and give reasons.
1. Let I(V1) = set of edges with at least one end point in V1, V1 ∈ V (G). Then |I| is?
2. Let cut(V1) = set of all branches with only one endpoint in V1, V1 ∈ V (G). Then |cut| is?
3. |I(V1)| + |cut(V1)| is?
4. Let B = (VL,VR,E). Let EL(X) = set of all vertices in VR adjacent only to vertices in X, X ∈ VL. ER is defined similarly on subsets of VR. Then |EL|, |ER| are?
Let Ω be a universal set and A,B ⊆ Ω. For a monotone submodular f, submodular mutual information between the sets A,B denoted by If(A;B) is defined as If(A;B) ≜ f(A) + f(B) − f(A ∪ B).
1. What would the expression for of If(A1;A2;...;Ak)?
2. Show that If(A;B) ≥ 0 and If(A;B|C) ≥ 0
3. Show that min(f(A),f(B)) ≥ If(A;B) ≥ f(A ∩ B)
4. Show that min(f(A|C),f(B|C)) ≥ If(A;B|C) ≥ f(A ∩ B|C)
5. Show that If(A;B) can be lower bounded by f(A)−Pj∈AB f(j|B) ≤ If(A;B) and upper bounded by If(A;B) ≤ f(A) − Pj∈AB f(j|Ω j) ≤ f(A). Are upper/lower bounds submodular?
We have a regression function for the variable x, given by fˆ(x) = βˆ0 + βˆ1x. There are n instances. The coefficients βˆ0 and βˆ1 are obtained by solving the given optimization problem -:
n
βˆ0,βˆ1 = argminβ0,β1 Xwi(x)(yi − β0 − β1xi)2
i=1
where the weight factors wi(x) do not depend on either of the coefficients.
1. Show that the above function can be written in the form -: (1)
(y − Ba)⊤g(x)(y − Ba) (2)
where y = [y1 y2 ··· yn]⊤, a = [β0 β1]⊤, B = [1 x1; 1 x2; ··· 1 xn], and g(x) is a diagonal matrix whose diagonal entries are the weights wi(x).
2. Using the formulation above, show that fˆ(x) is a linear combination of y. In other words, fˆ(x) = , where hi(x) is some function over x. Clearly mention what hi(x) is.
1. In this part of the problem, you are provided with two sets of files - ‘gset 1.txt‘ and ‘rep.txt‘. The former contains the ground set of points (whose subset we want) and the latter contains the target set of points (whose representation we want). Each line of a file represents an (x,y)-coordinate.
(a) First, plot the data from both sets of files using differing colors. Legends and axis should be present and labelled properly.
Then, plot the observations using the functions given below for optimal set budget of size 10. Use the naive greedy algorithm and make sure to plot points from the optimal set obtained in a different color. Report the order in which the points were picked up by your algorithm -: (b) Facility Location
(c) Graph Cut with varying parameter λ
(d) Set Cover
(e) Disparity Sum
(a) Plot the ground set and query set data using different colors.
Further, plot the summarization results obtained using the following submodular mutual information functions in a similar manner to the previous part. The optimal set budget continues to be 10 -:
(b) Log-determinant Mutual Information
(c) Concave over Modular
Recall that the Prox operator of a function h for some argument z is
proxh(z) = argmin
Compute the Prox operator for h(x) defined as h(x) = 0 if 0 ≤ x ≤ θ (for some fixed θ > 0 ) and h(x) = 100 for any other value of x.
Often, in optimization problems in machine learning, we have a simple constraint requiring that parameters lie in a particular interval. Such optimization problems can be effectively solved using the projected gradient descent algorithm discussed in the class.
Derive the exact projection operation of the projected gradient descent algorithm, for the following optimization problem which has the simplest form of such an interval constraint:
minx∈ℜ f(x)
subject to x ≤ r and x ≥ l
for some fixed given scalars l < r ∈ ℜ and for some machine learning convex loss function f(x). You can use the Karush-Kuhn-Tucker (KKT) conditions for deriving the projection step.
Show that the 3-way submodular mutual information If(A;B;C) ≥ 0 if If(A;B) is submodular in A for a fixed set B. Similarly show that, If(A;B;C) ≤ 0 if If(A;B) is supermodular in A for a fixed set B.
Given a monotone submodular function f, does the inequality: If(A1;A2;··· ;Ak) ≤ min(f(A1),··· ,f(Ak)) always hold for any k ∈ N ?
2. Use Latex (online platforms such as overleaf) for writing theory questions.
3. Submit the assignment as a zip file containing latex source, and PDF file.
Questions
Let there be a graph G with V vertices and E edges. Comment on the modularity of the following functions and give reasons.
1. Let I(V1) = set of edges with at least one end point in V1, V1 ∈ V (G). Then |I| is?
2. Let cut(V1) = set of all branches with only one endpoint in V1, V1 ∈ V (G). Then |cut| is?
3. |I(V1)| + |cut(V1)| is?
4. Let B = (VL,VR,E). Let EL(X) = set of all vertices in VR adjacent only to vertices in X, X ∈ VL. ER is defined similarly on subsets of VR. Then |EL|, |ER| are?
Let Ω be a universal set and A,B ⊆ Ω. For a monotone submodular f, submodular mutual information between the sets A,B denoted by If(A;B) is defined as If(A;B) ≜ f(A) + f(B) − f(A ∪ B).
1. What would the expression for of If(A1;A2;...;Ak)?
2. Show that If(A;B) ≥ 0 and If(A;B|C) ≥ 0
3. Show that min(f(A),f(B)) ≥ If(A;B) ≥ f(A ∩ B)
4. Show that min(f(A|C),f(B|C)) ≥ If(A;B|C) ≥ f(A ∩ B|C)
5. Show that If(A;B) can be lower bounded by f(A)−Pj∈AB f(j|B) ≤ If(A;B) and upper bounded by If(A;B) ≤ f(A) − Pj∈AB f(j|Ω j) ≤ f(A). Are upper/lower bounds submodular?
We have a regression function for the variable x, given by fˆ(x) = βˆ0 + βˆ1x. There are n instances. The coefficients βˆ0 and βˆ1 are obtained by solving the given optimization problem -:
n
βˆ0,βˆ1 = argminβ0,β1 Xwi(x)(yi − β0 − β1xi)2
i=1
where the weight factors wi(x) do not depend on either of the coefficients.
1. Show that the above function can be written in the form -: (1)
(y − Ba)⊤g(x)(y − Ba) (2)
where y = [y1 y2 ··· yn]⊤, a = [β0 β1]⊤, B = [1 x1; 1 x2; ··· 1 xn], and g(x) is a diagonal matrix whose diagonal entries are the weights wi(x).
2. Using the formulation above, show that fˆ(x) is a linear combination of y. In other words, fˆ(x) = , where hi(x) is some function over x. Clearly mention what hi(x) is.
1. In this part of the problem, you are provided with two sets of files - ‘gset 1.txt‘ and ‘rep.txt‘. The former contains the ground set of points (whose subset we want) and the latter contains the target set of points (whose representation we want). Each line of a file represents an (x,y)-coordinate.
(a) First, plot the data from both sets of files using differing colors. Legends and axis should be present and labelled properly.
Then, plot the observations using the functions given below for optimal set budget of size 10. Use the naive greedy algorithm and make sure to plot points from the optimal set obtained in a different color. Report the order in which the points were picked up by your algorithm -: (b) Facility Location
(c) Graph Cut with varying parameter λ
(d) Set Cover
(e) Disparity Sum
(a) Plot the ground set and query set data using different colors.
Further, plot the summarization results obtained using the following submodular mutual information functions in a similar manner to the previous part. The optimal set budget continues to be 10 -:
(b) Log-determinant Mutual Information
(c) Concave over Modular
Recall that the Prox operator of a function h for some argument z is
proxh(z) = argmin
Compute the Prox operator for h(x) defined as h(x) = 0 if 0 ≤ x ≤ θ (for some fixed θ > 0 ) and h(x) = 100 for any other value of x.
Often, in optimization problems in machine learning, we have a simple constraint requiring that parameters lie in a particular interval. Such optimization problems can be effectively solved using the projected gradient descent algorithm discussed in the class.
Derive the exact projection operation of the projected gradient descent algorithm, for the following optimization problem which has the simplest form of such an interval constraint:
minx∈ℜ f(x)
subject to x ≤ r and x ≥ l
for some fixed given scalars l < r ∈ ℜ and for some machine learning convex loss function f(x). You can use the Karush-Kuhn-Tucker (KKT) conditions for deriving the projection step.
Show that the 3-way submodular mutual information If(A;B;C) ≥ 0 if If(A;B) is submodular in A for a fixed set B. Similarly show that, If(A;B;C) ≤ 0 if If(A;B) is supermodular in A for a fixed set B.
Given a monotone submodular function f, does the inequality: If(A1;A2;··· ;Ak) ≤ min(f(A1),··· ,f(Ak)) always hold for any k ∈ N ?
1 file (1.5MB)
