My Math Forum  

Go Back   My Math Forum > College Math Forum > Linear Algebra

Linear Algebra Linear Algebra Math Forum


Thanks Tree4Thanks
  • 1 Post By akerman
  • 1 Post By Country Boy
  • 1 Post By zylo
  • 1 Post By zylo
Reply
 
LinkBack Thread Tools Display Modes
November 11th, 2015, 12:08 PM   #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
Thanks from zylo
akerman is offline  
 
November 12th, 2015, 06:53 AM   #2
Math Team
 
Joined: Jan 2015
From: Alabama

Posts: 2,822
Thanks: 750

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.
Thanks from akerman
Country Boy is offline  
November 12th, 2015, 08:51 AM   #3
Senior Member
 
Joined: Mar 2015
From: New Jersey

Posts: 1,175
Thanks: 90

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/(|x||y|)=costheta

6) The best I could come up with is:
f(x)=min|x|
f(y)=min|y|
f(x).f(y)=min(x||y|)

I found this interesting as a problem in pure math given definitions; as such, Linear Algebra is the best fit.
Thanks from akerman
zylo is offline  
November 13th, 2015, 05: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 05:55 AM.
akerman is offline  
November 13th, 2015, 08:41 AM   #5
Senior Member
 
Joined: Mar 2015
From: New Jersey

Posts: 1,175
Thanks: 90

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.
Thanks from akerman
zylo is offline  
Reply

  My Math Forum > College Math Forum > Linear Algebra

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
Multi-information based feature selection alexmosc Applied Math 0 July 2nd, 2015 02:52 AM
Feature of binomials McPogor Number Theory 4 September 27th, 2013 08:03 AM





Copyright © 2017 My Math Forum. All rights reserved.