Artificial Intelligence Homework #5 Solution

Problem 1 (SVM) – 6 Points: For this problem, you will be investigating the properties of the Support Vector Machine (SVM). The following graph shows points with two possible labels, i.e., + or −.

10 







5







5    10

    (a) (2 points) What is the maximum (hard) margin separating line for the above graph and what is the margin? No need to formally prove that it is the maximum margin, but briefly describe how you know it is maximum.

    (b) (2 points) Is this separating line still optimal when using a soft margin classifier? Why or why not?

    (c) (2 points) We mentioned in class that SVM can be made to generate non-linear classification boundaries as well using the so-called Kernel tricks. In essence, the idea is to transform all points x to φ(x) via a transformation function φ, and the transformed points become separable. To exercise this idea, this question asks you to describe a data transformation in close-form φ(x) : X → V that would allow the data shown in the following graph to become linearly separable (V can be d-dimensional for any d).


Problem 2 (Linear Regression and Linear Program) – 4 Points: In this problem, we will examine linear regression with absolute value loss and see how to solve it using linear programs.

    (a) (2 point) Before studying regression, we examine a simpler question to learn some useful ideas. The trick you need to figure out is to convert the problem of minimizing absolute value function into maximizing a linear function. In particular, show how to convert the following optimization problem into a linear program (LP).
minx1,x2
|2x1 − x2
|
subject to
x1 + x2 ≥
5

x2 ≤ 2


Note that this is not an LP since absolute value function is not a linear function.

    (b) (2 points) Show how to cast the optimization problem of linear regression with respect to the absolute value loss function, l(hθ(fi), yi) = |hθ(fi)−yi|, as a linear program; namely, show how to write the problem

m
X
min    |θT f(i) − y(i)|
θ
i=1

as a linear program.


Solution 2:



Problem 3 (Nash Equilibrium) – 5 Points: In this problem, you will learn to master the rock-paper-scissor game. Recall that the game has the following payoff structure where each utility (x, y) means the row player receives x and the column player receives y.


Rock
Paper
Scissor
Rock
(0,
0)
(-1,
1)
(1,
-1)
Paper
(1,
-1)
(0,
0)
(-1,
1)
Scissor
(-1,
1)
(1,
-1)
(0,
0)

Table 1: Payoffs of the Rock-Paper-Scissor Game


    (a) (2 point) Prove that each player picks one of {Rock, P aper, Scissor} uni-formly at random is a Nash equilibrium. Moreover, prove that this is the only Nash equilibrium.

    (b) (3 points) Consider the situation where the column player is forbidden to play Scissor (equivalently, the last column of the above payoff matrix is deleted). What is the Nash equilibrium of this new variant of the game.

Problem 4 (Mechanism Design) – 5 Points: With the graduation time approaching, many students will sell their stuffs. Assume you have to sell your used car. You have two potential buyers who are interested in your car. One of them is your close friend and he has told you that he values your car at $4000. The other potential buy is unknown to you and you only know that his value is drawn from a uniform distribution between $3000 and $6000.

You are considering using one of the following two mechanisms to sell you car.

    (a) (2 points) If you use a second-price auction to sell your used car, what will be your expected revenue at equilibrium?

    (b) If you use a posted-price mechanism to sell your car, consider the following cases:

        (1) (1 point) If you post a fixed price $5000, what will be your expected revenue?
        (2) (2 points) What will be the optimal reserve price for you to post if you want to maximize your expected revenue at equilibrium?

Solution 4:































6