HW2 | 5.1

[npk]

Hello,

Wouldn't it be better if the the classification boundary is of the form wx+b=0 ? The condition y<x,w> >=(1 - epsilon) implies the line always passed through the origin.

Thanks!

[Junier Oliva]

I'm not sure I follow your question. What exactly is the problem?

Thanks,

Junier

--
http://alex.smola.org/teaching/cmu2013-10-701 (course website)
http://www.youtube.com/playlist?list=PLZSO_6-bSqHQmMKwWVvYwKreGu4b4kMU9 (YouTube playlist)
---
You received this message because you are subscribed to the Google Groups "10-701 Spring 2013 CMU" group.
To unsubscribe from this group and stop receiving emails from it, send an email to 10-701-spring-201...@googlegroups.com.
To post to this group, send email to 10-701-spri...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Krikamol Muandet]

you can always incorporate b by using

w' = [w 1]

x' = [x b]

then w'x' = wx + b

Krik

--
http://alex.smola.org/teaching/cmu2013-10-701 (course website)
http://www.youtube.com/playlist?list=PLZSO_6-bSqHQmMKwWVvYwKreGu4b4kMU9 (YouTube playlist)
---
You received this message because you are subscribed to the Google Groups "10-701 Spring 2013 CMU" group.
To unsubscribe from this group and stop receiving emails from it, send an email to 10-701-spring-201...@googlegroups.com.
To post to this group, send email to 10-701-spri...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

--

Krikamol Muandet
PhD Student                                                   
Max Planck Institute for Intelligent Systems            
Spemannstrasse 38, 72076 Tübingen, Germany      
Telephone: +49-(0)7071 601 554
http://www.kyb.mpg.de/~krikamol

[Silvia Liu]

Hi Krik and Junier,

I think b is incorporated as,

w' =[w,b]

x' = [x,1]

so that w' is unknown, waiting be minimized; and x' is known, by adding an additional feature with value 1.

Another question is, usually the primal has to subject to

y_i [ <w, x_i> + b] >= 1- \xi

but there is no 'b' in this problem... so I think we simplify b=0 here (Because the last feature for x not equals to 1)

Am i correct?

Thanks!

Best Wishes,

Silvia

(Shuchang Liu)

[Krikamol Muandet]

Hi Silvia,

Yes, you are right. b should be in w, instead of x. Thanks.

Krik

[Junier Oliva]

No, do not assume b is zero. As you stated, use:

w' =[w,b]

x' = [x,1]

Thanks,

Junier

[Yitong Zhou]

So if take w0 and x0 into consideration, should the dual problem also changes? The alpha's dimensions are the total number of x_i vectors, has nothing to do with the dimensions of x_i, so where should the b be put in, in the dual problem case?

在 2013年2月18日星期一UTC-5下午1时55分35秒，Junier写道：

To unsubscribe from this group and stop receiving emails from it, send an email to 10-701-spring-2013-cmu+unsub...@googlegroups.com.

To post to this group, send email to 10-701-spri...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

--

Krikamol Muandet
PhD Student                                                   
Max Planck Institute for Intelligent Systems            
Spemannstrasse 38, 72076 Tübingen, Germany      
Telephone: +49-(0)7071 601 554
http://www.kyb.mpg.de/~krikamol

--
http://alex.smola.org/teaching/cmu2013-10-701 (course website)
http://www.youtube.com/playlist?list=PLZSO_6-bSqHQmMKwWVvYwKreGu4b4kMU9 (YouTube playlist)
---
You received this message because you are subscribed to the Google Groups "10-701 Spring 2013 CMU" group.

To unsubscribe from this group and stop receiving emails from it, send an email to 10-701-spring-2013-cmu+unsub...@googlegroups.com.

To post to this group, send email to 10-701-spri...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

--

Best Wishes,

Silvia

(Shuchang Liu)

--
http://alex.smola.org/teaching/cmu2013-10-701 (course website)
http://www.youtube.com/playlist?list=PLZSO_6-bSqHQmMKwWVvYwKreGu4b4kMU9 (YouTube playlist)
---
You received this message because you are subscribed to the Google Groups "10-701 Spring 2013 CMU" group.

To unsubscribe from this group and stop receiving emails from it, send an email to 10-701-spring-2013-cmu+unsub...@googlegroups.com.

[Krikamol Muandet]

Hi Yitong,

It does not really matter how you parametrize w because b will not appear in the dual problem. If you derive the dual form of SVM using the standard formulation, you will see that

w = \sum \alpha_i.y_i.x_i

Those points with \alpha_i > 0 are the support vectors and satisfy y_i(w.x_i - b) = 1. Then, we can derive b as

b = w.x_i - y_i    (or you can average over all support vectors)  

So once you solve for \alpha, the offset b can be obtained. The same idea also applies soft-margin SVM.

Krik

[Premkumar]

Thank you, Kirk, Junier and Silvia. My question is now answered.

Premkumar

[Jiaji Zhou]

Hi, shall we also assume that for various kernels the bias term is also grouped?

To unsubscribe from this group and stop receiving emails from it, send an email to 10-701-spring-2013-cmu+unsubscri...@googlegroups.com.

To post to this group, send email to 10-701-spri...@googlegroups.com.

For more options, visit https://groups.google.com/groups/opt_out.
 
 

--

Krikamol Muandet
PhD Student                                                   
Max Planck Institute for Intelligent Systems            
Spemannstrasse 38, 72076 Tübingen, Germany      
Telephone: +49-(0)7071 601 554
http://www.kyb.mpg.de/~krikamol

--
http://alex.smola.org/teaching/cmu2013-10-701 (course website)
http://www.youtube.com/playlist?list=PLZSO_6-bSqHQmMKwWVvYwKreGu4b4kMU9 (YouTube playlist)
---
You received this message because you are subscribed to the Google Groups "10-701 Spring 2013 CMU" group.

To unsubscribe from this group and stop receiving emails from it, send an email to 10-701-spring-2013-cmu+unsubscri...@googlegroups.com.

To post to this group, send email to 10-701-spri...@googlegroups.com.

For more options, visit https://groups.google.com/groups/opt_out.
 
 

--

Best Wishes,

Silvia

(Shuchang Liu)

--
http://alex.smola.org/teaching/cmu2013-10-701 (course website)
http://www.youtube.com/playlist?list=PLZSO_6-bSqHQmMKwWVvYwKreGu4b4kMU9 (YouTube playlist)
---
You received this message because you are subscribed to the Google Groups "10-701 Spring 2013 CMU" group.

To unsubscribe from this group and stop receiving emails from it, send an email to 10-701-spring-2013-cmu+unsubscri...@googlegroups.com.

To post to this group, send email to 10-701-spri...@googlegroups.com.

For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Silvia Liu]

Hi Junier, Krik and Yitong,

I just want to make sure whether I'm in the right track for the dual form question (Q5.2).

After we get \alpha, we do not need to calculate w (or b).

Instead we can use support vector expansion

predictedY= sign( \sum \alpha_i y_i k(xi, testX) )

to get the predicted value, right?

Also for the parameter 'b' problem, we could add 1 to each x value as the third feature.

Correct me if there is anything wrong.

Another question is how to implement kernel into primal form (Q5.1)?

Does it means it has to subject to

yi <\phi(xi),w> >= 1 - \xi

But how could we know \phi(xi) only given a specific kernel function?

Thanks!

Silvia

[Junier Oliva]

You may refer to slide 72 for the bias term:
http://alex.smola.org/teaching/cmu2013-10-701/slides/5_SVM.pdf

Thanks,

Junier

To unsubscribe from this group and stop receiving emails from it, send an email to 10-701-spring-201...@googlegroups.com.

[Junier Oliva]

You may define $b$ as the average of $(y_{k}-\sum_{i=1}^{n}\alpha_{i}y_{i}\Phi(x_{i})^{T}\Phi(x_{k}))$ for all $k$ that satisfy $0<\alpha_{k}<C$.

See slide 72 for more details on the decision function http://alex.smola.org/teaching/cmu2013-10-701/slides/5_SVM.pdf

-Junier

To unsubscribe from this group and stop receiving emails from it, send an email to 10-701-spring-201...@googlegroups.com.

[Rittika]

Hi Junier,

For question 5, the assignment asks us to compare the dual and primal forms of SVM and says we only need to try RBF for the dual form.

1) Doesn't that imply we have to use kernels in the primal form (I find this highly contradictory, given the nature of the two forms)? If not, how do implement the linear and polynomial versions of the primal form? do we simply change the loss function? Even then, don't we need the 'kernel' parameter to decide which loss function to use? Anyway, I thought slack variables were introduced in the primal form to deal with non-linear data?

2) For the dual form, once we have calculated  w and b, do we calculate y as y= sign(wx +b), where x is from the test set?

I am really sorry, if these questions have been asked before but I am extremely confused.

Thank you very much for your patience.

--
Rittika

[Junier Oliva]

Hi.

1) For linear kernel, you know how to solve this using the primal (it is the vanilla primal problem). For the polynomial kernel, you have to think about what what induced feature space \Phi(x) you are working in. Then solve the primal problem where your features are \Phi(X)

2) You can directly classify using dual vars

You may define $b$ as the average of $(y_{k}-\sum_{i=1}^{n}\alpha_{i}y_{i}\Phi(x_{i})^{T}\Phi(x_{k}))$ for all $k$ that satisfy $0<\alpha_{k}<C$.

See slide 72 for more details on the decision function http://alex.smola.org/teaching/cmu2013-10-701/slides/5_SVM.pdf

-Junier

[Jingkun Gao]

Hi Junier,

I have a question of defining b. If we define b like this, when we calculate the accuracy, we need to calculate the value for each test point using Y_{test} = (\sum^m_{i=1} \alpha_i * y_i * Kernel(X_i,X_test)) + b, then let it equal 1 if Y_{test}>=0, let it equal -1 if Y_{test}<0. But b here is only an average calculated from effective \alpha, while Y_{test} is calculated from all of the \alpha s. I think this won't influence figure but will kind of influence the accuracy. Is it normal if we get a very low accuracy like 40% using the definition of b like this?

Thanks,

Jingkun 

To unsubscribe from this group and stop receiving emails from it, send an email to 10-701-spring-2013-cmu+unsubscri...@googlegroups.com.

To post to this group, send email to 10-701-spri...@googlegroups.com.

For more options, visit https://groups.google.com/groups/opt_out.
 
 

--

Krikamol Muandet
PhD Student                                                   
Max Planck Institute for Intelligent Systems            
Spemannstrasse 38, 72076 Tübingen, Germany      
Telephone: +49-(0)7071 601 554
http://www.kyb.mpg.de/~krikamol

--
http://alex.smola.org/teaching/cmu2013-10-701 (course website)
http://www.youtube.com/playlist?list=PLZSO_6-bSqHQmMKwWVvYwKreGu4b4kMU9 (YouTube playlist)
---
You received this message because you are subscribed to the Google Groups "10-701 Spring 2013 CMU" group.

To unsubscribe from this group and stop receiving emails from it, send an email to 10-701-spring-2013-cmu+unsubscri...@googlegroups.com.

To post to this group, send email to 10-701-spri...@googlegroups.com.

For more options, visit https://groups.google.com/groups/opt_out.
 
 

--

Best Wishes,

Silvia

(Shuchang Liu)

--
http://alex.smola.org/teaching/cmu2013-10-701 (course website)
http://www.youtube.com/playlist?list=PLZSO_6-bSqHQmMKwWVvYwKreGu4b4kMU9 (YouTube playlist)
---
You received this message because you are subscribed to the Google Groups "10-701 Spring 2013 CMU" group.

To unsubscribe from this group and stop receiving emails from it, send an email to 10-701-spring-2013-cmu+unsubscri...@googlegroups.com.

To post to this group, send email to 10-701-spri...@googlegroups.com.

For more options, visit https://groups.google.com/groups/opt_out.
 
 

--

Krikamol Muandet
PhD Student                                                   
Max Planck Institute for Intelligent Systems            
Spemannstrasse 38, 72076 Tübingen, Germany      
Telephone: +49-(0)7071 601 554
http://www.kyb.mpg.de/~krikamol

--

Best Wishes,

Silvia

(Shuchang Liu)

--
http://alex.smola.org/teaching/cmu2013-10-701 (course website)
http://www.youtube.com/playlist?list=PLZSO_6-bSqHQmMKwWVvYwKreGu4b4kMU9 (YouTube playlist)
---
You received this message because you are subscribed to the Google Groups "10-701 Spring 2013 CMU" group.

To unsubscribe from this group and stop receiving emails from it, send an email to 10-701-spring-2013-cmu+unsub...@googlegroups.com.

To post to this group, send email to 10-701-spri...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

--
http://alex.smola.org/teaching/cmu2013-10-701 (course website)
http://www.youtube.com/playlist?list=PLZSO_6-bSqHQmMKwWVvYwKreGu4b4kMU9 (YouTube playlist)
---
You received this message because you are subscribed to the Google Groups "10-701 Spring 2013 CMU" group.
To unsubscribe from this group and stop receiving emails from it, send an email to 10-701-spring-2013-cmu+unsub...@googlegroups.com.
To post to this group, send email to 10-701-spri...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

--
Rittika

[Junier Oliva]

Defining Y_{test} like that sounds correct.

-Junier

To unsubscribe from this group and stop receiving emails from it, send an email to 10-701-spring-201...@googlegroups.com.