
Linear Algebra Linear Algebra Math Forum 
 LinkBack  Thread Tools  Display Modes 
November 11th, 2015, 11:08 AM  #1 
Newbie Joined: Nov 2015 From: london Posts: 3 Thanks: 1  kernel properties and feature maps
I am preparing myself for maths exam and I am really struggling with kernels. I have following six kernels and I need to prove that each of them is valid and derive feature map. 1) K(x,y) = g(x)g(y), g:R^d > R With this one I know it is valid but I don't know how to prove it. Also is g(x) a correct feature map? 2) K(x,y) = x^T * D * y, D is diagonal matrix with no negative entries With this one I am also sure that it is valid but I have no idea how to prove it or derive feature map For the following four I don't know anything. 3) K(x,y) = x^T * y  (x^T * y)^2 4) K(x,y) =$\prod_{i=1}^{d} x_{i}y_{i}$ 5) cos(angle(x,x')) 6) min(x,x'), x,x' >=0 Please help me as I am very struggling with kernel methods and if you could please provide as much explanation as possible 
November 12th, 2015, 05:53 AM  #2 
Math Team Joined: Jan 2015 From: Alabama Posts: 2,647 Thanks: 680 
I thought I knew a little Linear Algebra but I have no idea what a "feature map" is! Looking it up in Wikipedia, it appears that what you are talking about is not really linear algebra but rather "learning algorithms" in computer science. You might do better posting this in the "Computer Science" thread.

November 12th, 2015, 07:51 AM  #3 
Senior Member Joined: Mar 2015 From: New Jersey Posts: 1,134 Thanks: 88 
Looked up definitions in https://en.wikipedia.org/wiki/Kernel_method Definitions: Let X be a data set, x and y belong to X. k:XxX>R is a kernel if k(x,y)=f(x).f(y) (inner product) f is called a feature map, f:X>V 1) Satisfies Definition. Any g:R^n>R is a correct feature map 2) f(x)=x^T D^1/2 f(y)=y^T D^1/2 where D^1/2 has diagonal elements equal to sqrt of diagonal elenents of D. 3) The best I could come up with is: f(x)=x1,x2,x.x f(y)=y1,y2,y.y f(x).f(y)=x.y+x^2y^2 I don't think there is an answer, but I give this to illustrate thr thinking. 4) f(x)=x1x2x3 f(y)=y1y2y3 f(x).f(y)=x1y1x2y2x3y3 5) f(x)=x/x f(y)=y/y f(x).f(y)=xy/(xy)=costheta 6) The best I could come up with is: f(x)=minx f(y)=miny f(x).f(y)=min(xy) I found this interesting as a problem in pure math given definitions; as such, Linear Algebra is the best fit. 
November 13th, 2015, 04:49 AM  #4 
Newbie Joined: Nov 2015 From: london Posts: 3 Thanks: 1 
Thanks Zylo for your comprehensive answer and just to clarify? Do I understand it correctly that? 1) Is a valid kernel 2) Is a valid kernel 3) Is not a valid kernel 4) Is a valid kernel 5) Is a valid kernel 6) Is a valid kernel Also Zylo do you think your workings are enough to satisfy proof of each kernel? I know it is a bit of an abstract knowledge and thats why I find it difficult to grasp. Last edited by akerman; November 13th, 2015 at 04:55 AM. 
November 13th, 2015, 07:41 AM  #5 
Senior Member Joined: Mar 2015 From: New Jersey Posts: 1,134 Thanks: 88 
3) $\displaystyle x\cdot y=x_{1}y_{1}+x_{2}y_{2}\\ (x\cdot y)^{2}=x_{1}^{2}y_{1}^{2}+x_{2}^{2}y_{2}^{2}+2x_{1 }y_{1}x_{2}y_{2} $ Because of the symmetry in x and y: $\displaystyle (x\cdot y)^{2}=f'(x)\cdot f'(y)$ where $\displaystyle f'(x)=x_{1}^{2},x_{2}^{2},\sqrt{2}x_{1}x_{2}\\ f'(y)=y_{1}^{2},y_{2}^{2},\sqrt{2}y_{1}y_{2} $ the complete solution is then: f(x)=x,f'(x) f(y)=y,f'(y), f(x).f(y)=x.y+(x.y)^2 The solution applies for any number of components because of the symmetry of $\displaystyle (x.y)^{2}$ in $\displaystyle x_{i}$ and $\displaystyle y_{i}$. The OP has a minus sign which is impossible, the x.y terms are all positive. (a,b,c).(e,f.g)=ae+bf+cg unless f(x)=x.if'(x) f(y)=y.if'(y), in which case: f(x).f(y)=x.y(x.y)^2 With that 1)5) are valid and proven. I can't do 6). The actual math is straight forward but requires definition of dot and matrix product. The abstraction resides in the definition of kernel, but that's no more abstract than any definition in the most advanced algebra text. The real difficulty comes in "seeing" things, as in 3). The really hard part is understanding the relation of the math to Computer Science. I read one sentence about that in the wicki article, gave up, and went straight for definition of kernel, which fortunately was intelligible. If you have to understand the broader "meaning" of kernel, my sympathies and good luck. I undertook this problem to apply my impression that all you needed to do a math problem was all the relevant definitions, regardless of the subject or previous exposure (sadly generally not true for me). In conclusion, what are the first three steps in attacking a math problem: 1) Definition 2) Definition 3) Definition I notice your OP didn't start with a definition, but that's because you were trying to get to the basic definitions by understanding the subject, a much, much, more difficult approach. I took the easy way out. I'm a mechanical engineer, so I can't understand anything if I can't see it. 

Tags 
feature, kernel, maps, properties 
Search tags for this page 
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Multiinformation based feature selection  alexmosc  Applied Math  0  July 2nd, 2015 01:52 AM 
Feature of binomials  McPogor  Number Theory  4  September 27th, 2013 07:03 AM 