Ch 3 Inner product Hilbert space
不1 Inner Product
Norms give only metrics ie measuring the distance of two vectors
However in many applications the angel of two vectors matter
For example two images xy the same
showing scene with different lights
For simplicity we may assume say y⼆ 点 x 皆恐品㷀尘品学劁
Then ⼩川 占⽐11 or not small
but x y are from the same scene
We use inner product for angel of two vectors
x
y
Definition A function NXV [Link] called an inner product
on the vector Space Voter Rif
⽐ EV 化 Do and 化 D 0 x 0
cxxtpxz 以 ⼆ 义 化 Dtp 佑 y EMER X X ya
化 y 似
Remark l By20 and 30 化 州 内 ⼆ 义化 以 [Link] 怎杀器 品
Therefore Co is a bilinearfunction it
n it is linear
with respect to one of the variable with the otherfixed
z For inner product of vector spaces on G we onlyneed to
change to
化y MT Where T stands
for complexconjugate
Example Ii R is a vector space We can define an inner product as
y [Link] nyn wherex 㓹 and ⽕愿
⼆
xy
Example 2 Another inner product in R is as follows
Let HER be a symmetric positive definite spd
Recall Spd means AEA and TAX 0 Uxto
Then x y不⼆ 姢y defines an inner product in R because
化 ⼒ A TAX 20 and 化 㚳 0 XTo
[Link]
ka
xxitytpxy
x化 DA t DA
也 以仁 妚 y AyjEyix _yTAFM.DA
[Link]
Example 3 i RMM is a vector space over R
[Link]
[Link]
lj i i
traa AT3
tracelBTA
This is an inner product on R
MM
Example 4 For two infinite sequences
G ai i 1，2，3
b bi ⼼ 2了
Then
Gb
⼆
点 abi defines an inner product
Example5 In Cain we can define an inner product as
A9 fff M9lxidx.V [Link]
3.2 Roperties of inner product orthogonality
CauchySchwartz Inequity
If ⼈ 7 is an inner product on V then for any X y EV
[Link] [Link]
y 0 Then obviously
2
1化州 140 12 0 E 0 似
It remains to prove the inequality with y to
Let ⼊ER be an arbitrary number
0⼆ 化⼗⼒ 从 ⼩ ⼆ 化 [Link] AM
⼆ 化 P 12 Xx y t Ng y
Thus
题 以⼗ 如
主产品
以 ER
Since y to Ky 0
So fM a quadratic function of ⼊ that takes nonnegative values only
There is at most one root of the quadraticfunction it bits
2
So 划
以
2
4例
sax
[Link]
yy
0
Lol errs
at most one real root
So hi 4 a CEO
2
Next when the equality holds true [Link] x_x yy
if y 0 then obviously y XX where 仁 0
if Ho there is exactly one real root of fa
⺕ a unique
MR N Ly ⼗ ⼆⼊ 化 以 ⼗ 化 D 0
化 ⼗刈 xtxy 0 M 0 x_x y with ㄨ ⼊
2
showthat if Day
Finally we kxyory [Link] ay
By direct calculation
2 2
x_x y G以 例 以 xyy ⼆ 例 刘 y y
2 2 2
y xx x义 x D Gx Pax ㄨ
⽹
With the CauchySchwartzinequity we can show that
Called norm induced
仙
[Link] ⽕ 0
by the innerproduct
Proof 10 1⽐11 ⼼ 220 and1啡 化 x ㄨ 0
收州 xxx 是 化州 兰 凶 化11
化 州 1122 [Link] a 以
⼆ Note that CauchySchwartz
化114114114 2 x 以 becomes
EM 141 Hit 2 化1111911
Xx yN EM 111911
[Link] 図
We call the norm M1 三 化
[Link]
Cauchy
Sahwartzisrestatda_rgkx.ME
lXlllMllLrExamplel
lR with inner product x y 划
The induced norm is
化仁 化 沝 ⼆ 世如 ⼆ 点啡 ⼆ 化112
Example 2 N with inner product 化 以 仁 XI y where A is SPD
The induced norm is
⽐你 也 x 也有妒 京 aijxij
Example 3 The pnorm in R
Mlp P 2 are not induced by inner products
Example 4 i R with inner product
A 137 ⼆ 点Qjbij
The induced norm is
II All AT 吾们 三 侧个 the Frobenius norm
Angles in inner product spaces
The equality is attained if and only if x and y
are aligned exactly which should have the least and
Therefore we use the ratio of the two sides of Cauchy
Schwartz ㄑ监
化11 Mll
to qnantitize the closeness to exact alignment Hence to
define the angles between x and y
when ㄨ 刈 with no
从上
1 x
化1111411 y
Sina X and y are in the same direction
It is naturally to define 化y 0
When
[Link]
⼆
⼗ ⼀⼀
侧 侧 x y
Since x and y are in the opposite direction
it is naturally to define ㄑ 化 y 不
We define
cos xy
巡
化1111911
or equivalently ㄑ业
Lay arc cos
化1111411
This definition coincides with the above two cases and the
vectors in R2 or 1123 equipped with the standard inner product
Orthogonality Let V be an inner product space
When the angleof X and
y is ⾄ we call they are
orthogonal denoted
[Link]
[Link]
when XU they are least relevant
Pythagoras theorem Let X y be two vectors in an inner product space
If XI y then IT ㄐ 112 1⽐112 1 11丱
X
x 14 ㄨ 4
[Link] they
proof My 112
以ㄨ y以
侧 411丱 曲
halleGram law Ux y EH ⼀
an inner product space
My 11411划⽔ 2化1142119112
proof My 1141以 丱
州 [Link]
⼆ 化 如 tag ⽕⽕ tag y tax yx [Link] 例
211卌⼗211叭 ⽹
Hilbertspaaittg
A Hilbert Space is
qlmppedandrtkmrmisindadrbytuinurpro
[Link]
a Banach space in which an
Vector spaces
inner product is
Ün
Example Ii R with inner product
化y xg
is a Hilbert space
Example 2 R with inner product
化y A TAY where A is an Spd mix
is a Hilbert space The norm on this space is
11 㚳 4百⽔
Example 3 i R with inner product 伯 13 trace约73
is a Hilbert space
infinite sequence
a is an
Example 4 i h a
Haha to and
with inner Product b
⼼ bi
is a Hilbert space
Example 5i Can b with inner product
b
G9 hbfcxigcydx
is NOT a Hilbert space because it is not complete
To complete Cab了 under the norm 11.11 4 咋
we need to extend the Riemannian integral to the so called Lebesgue
integral and the resulting Hilbert space is Ela b
In the following we will consider calculus on Hilbert Banach spaces
3.3 Case Study kernel trick Kernel K means
The K means will not work for the following examples
i
i ii
fit cc ii 呩
iii iii i
Recall in want to X ⽕ 从 ER
a chastening group
⼀
we
into K groups
The K means algorithm works like i
Initialize Z 2 ⼀
Zk
step Ii Given Z ⼆ ⼀
Zk update the groups G ⼀
[Link]
foreach Xi assign Ci the group that Xi belongsto by
a argminllxi
[Link]
𠮩
Then
Gj ikij for Fl 了 K
step 2 i Given Gi Gk update their representsby
Ziījī 意 for Fl K
ˋ
2
To modify K means to those curved data sets in R
we use a transform to incur re the data sets in a Hilbert
space
Let 0 i N N
i Ni 中以 1
i
Xj
ins 中的
ji
Rn H
1
01⽐⻔ is calledthefeature of Xi
中 is called thefeature map
Called the feature space
It is
Then we apply k means to 中⼼ 中如 中则 in H
Let Zi Zk be the representative vectors in H
step Ii Given Z
⼆
[Link]
0KXi
[Link] ZjH2 i 1；3
step 2 Given Gl
NandGj
filCi j3
⼀⼀
Gk
j l 2 k
Zj ⼆
点 意中 划
Repeat
However finding the feature map of is not easy because
中 depends on the shape of X ⽕
⼀
从 which generally is
very complicated
Thgooduwsisthatitrg
Thereisnoneedtoknowolexplitksm
This is seen as in below
First of all since we care only the groups of X 从
we only need to know G
⼀
Gk The representatives
Z Zk are only internediate
Therefore we can eliminate Zi Zk in the K means algorithm
囖 2in
囖
Now only Dino hes the feature mapping f
Since His a Hilbert space we can expand the
norm in 10 by
11中⽐
以前 新州12
4 ⽐以前 㷉 如 ⽐以前 㷉 𠴕
4侧 中以
前 意件 侧 䖰
⼗ 伙划
赢点意 中咱
We see that
[Link]
onhginnerproductsin
Therefore
[Link]
kernel trick
Instead ofdefining中的 explicitly we define a kernel function Kay
嚣管 簪 器器 您 int
imiiiiilhtlese
it violateswith 4 以 灿 20
Which function Kay can be an inner product 化 ⽕ for
some feature mapping 中
First of all inner productproperly
t
K X⻔ 4 ⽐1 叫 ⼆ 件们 中化 ⼆ KM x
We say KC i is symmetric if Kay key x for all X yERI
Secondly let y ⽕ ym be m vectors in R then
for any 𨰝ERM C
CĚC 恻 Èci 中 州 20 By innerproductproperty
On the other hand
焦⽟中以1 Ěa 炽 歌 中侧 意 伙 州
inner
TEÈÈ
product
Cig 伙则 中以
By ⼆
点 Ě [Link]
properly
KM⽣ Kgym
C 𨶹 炽 1 C 20 ⽐ER
⼮品则 Kam别 ⼀
您
In other words the matrix F is symmetric positive semidefinite
We say a function ⼮ ⼩ R XR R is symmetric positive
semidefinite if i
i kcx 以 ⼆ KM x Ex y ER
ii For any m and any vectors y ⼼ 不 ER the matrix
KM⽣ Kgym
𨶹 炽
⼮品则 Kam别 ⼀
您别
is symmetric positive semi definite
Mercer's theorem tells us that If a kernel function Kc i
is
Symmetric positive semi definite then there exists a feature map
of such that kcxin 4 x 𤘘
Some popular kernels
Kay ㄨ可 如仁 X No transform
Kay ⽔ polynomial kernels
Kay e
等
化
Gaussian kernel
kernel k means algorithm
choose a kernel function KC
Initialize Gin Gi G by e.g one step of K means
Set
噝 仙 鱲 新 低则
管𢦀
update G 后 ⼀
Gk by
G if CB for Fl 2 K
⼀
go back and repeat
The kernel K means works for some datasets for which
K means
fail
Example i
iii 只
i
ii
化
If we use Gaussian kernel [Link] e 等
then I Xilk
Kai E 52 1
so all 中以⼩ 中必以 are on unit sphere in H
⼆ 0 if NXi Xjlhislarge
[Link] lifllxi xjlhissmdl
[Link] lxi1，4Nj are orthogonal in H if 伈 灿 large
中以1 中的1 in H
if Nixjll small
Therefore
n
ii 7
㘥
i
ii
th
Rn
It
frwgl
Thus K means works for this data set
3.4 Case Study i Metric Learning
Given a set of vectors Xi Xz
⼀
不 ER and
given information that certain pairs of them are similar dissimilar
S Xi Xj ES if Xi and Xj are similar
Di Xi Xj ED if Xi and Xj are dissimilar
Can we find a distance metric such that
similar points are chose to each other
and dissimilar points are far away from each other
reorganizethem
i
similar
蓏 i
dissimilar So the similarities are measured
blank unknown by the distance Then we can
巡 您简 infer [Link] are similar
以 are dissimilar
Potential applications
Supervised clustering
Given a dataset with partial clustering information
soo Similar lie in thesame
cluster
_dissimilar lie in different
clusters
Metric learning Lie find a distance
a cluster the points under the learned distance metric
Representation
There are many different forms of norms even in Rn
Candidate forms of norms
on
p normllxllp [Link] 㗦 P 21
This class of norms is too small because there is only
one parameter p in the definition of these norms
norms induced
by the A inner product
HXHA 化 DA
2
TAX
where AER is an SPD matrix
This class of norms are parame tried by an nxn
so
matrix A that contains enough parameters In 2 parameters
We use this class of norms as candidate norms for
our distance metric learning
Then
find a distance metric 7 Find SPD manx AER
⼀
an
and the distance metric is MA
Remarks
The SPDness of A is usually relaxed to
A is symmetric positive semi_definite SPD
Correspondingly the resuming norm will NOT satish
MIA Ko and other conditions in the
definition of norms are satisfied thus MA with
SPSDA is NOTexactly a norm but a pseudo norm
Given X y EN the disauce induced by MA
llx [Link] A cop
is also known as [Link] distance
Evaluation Which A is the best for metric learning
For di Xj ES their distance is small ie
[Link]
11xi
赢
For Xi Xj ED their distance is large ice
化所 作 颂
So we
赢 的
find the best
227 AER is the sense of
三
Min [Link] 为你
h
AERrn Xi xjl
[Link]
ON equivalently we solve
min 伈 为作
[Link]
is SPSD n
伈 不䢳 1
st
赢
Optimization
The optimization is introduced later