赞
踩
论文地址:https://cs.nju.edu.cn/zhouzh/zhouzh.files/publication/icml09miGraph.pdf
论文出发点:包中的实例非独立同分布 (non-I.I.D.)
设计的两种方法:
1)MIGraph:明确将每个包映射为无向图 (undirected graph),并设计一种graph kernel来区分正包和负包;
2)miGraph:通过affinity matrix来隐式地构建图,并设计一种相应的graph kernel。
本文的符号表如下:
符号 | 含义 |
---|---|
X \mathcal{X} X | 实例空间 |
S = { ( X 1 , Y 1 ) , ⋯ , ( X i , Y i ) , ⋯ , ( X N , Y N ) } \mathcal{S} = \{ (X_1, Y_1), \cdots, (X_i, Y_i), \cdots, (X_N, Y_N) \} S={(X1,Y1),⋯,(Xi,Yi),⋯,(XN,YN)} | 给定训练集 |
X i = { x i 1 , ⋯ , x i j , ⋯ , x i , n i } ⊆ X X_i = \{ \mathbf{x}_{i1}, \cdots, \mathbf{x}_{ij}, \cdots, \mathbf{x}_{i, n_i} \} \subseteq \mathcal{X} Xi={xi1,⋯,xij,⋯,xi,ni}⊆X | 包 |
Y i ∈ Y = { − 1 , + 1 } Y_i \in \mathcal{Y} = \{ -1, +1 \} Yi∈Y={−1,+1} | 包标签 |
x i j = [ x i j 1 , ⋯ , x i j l , ⋯ , x i j d ] ′ \mathbf{x}_{ij} = [x_{ij1}, \cdots, x_{ijl}, \cdots, x_{ijd}]' xij=[xij1,⋯,xijl,⋯,xijd]′ | x i j ∈ X \mathbf{x}_{ij} \in \mathcal{X} xij∈X | 实例 |
y i j y_{ij} yij | 实例标签 |
x i j l x_{ijl} xijl | 属性值 |
N N N | 训练集大小 |
n i n_i ni | 包大小 |
d d d | 属性值个数 |
包的标签确定如下:
Y
i
=
{
+
1
,
∃
g
∈
{
1
,
⋯
,
n
i
}
,
st.
y
i
g
=
+
1
;
−
1
,
otherwise.
(1*)
Y_i =
1)如下图所示 (图片来自原论文并简单处理),假设每张图对应一个包,每个用矩形框出的部分 (patch)对应一个实例,且同一颜色的patch是相似的。
2)如果每个patch看作是独立的样本,则上图可以抽象为下图 (图片来自原论文)。这种情况下,这三个包是相似的,因为他们拥有同样数量且相似的实例。
3)如果考虑每个patch的关系,那么前两个包则更为相似:
步骤如下:
1)为每个包构建
ϵ
\epsilon
ϵ-graph1:
I)对于每一个包
X
i
X_i
Xi,其中的实例看作是一个节点 (node);
II)计算每两个node之间的的距离 (暂时记作d);
III)如果某两个node之间的距离小于预设的阈值
ϵ
\epsilon
ϵ,则两者之间建立边界 (edge);
IV)edge的权重表示两个node之间的亲密度 (affinity),实验中初始化为非零距离的归一化倒数;
2)涉及已分类的 (categorical)属性时,使用VDM (value differene metric)2作为补充:
I)假设属性的前
j
j
j个是categorical,余下的
(
d
−
j
)
(d - j)
(d−j)个是归一化为
[
0
,
1
]
[0, 1]
[0,1]的连续值;
II)使用以下距离来计算两个实例
x
1
\mathbf{x}_1
x1和
x
2
\mathbf{x}_2
x2的距离:
d
=
(
∑
h
=
1
j
V
D
M
(
x
1
,
h
,
x
2
,
h
)
+
∑
h
=
j
+
1
d
∣
x
1
,
h
,
x
2
,
h
∣
2
)
1
2
.
(2*)
d = (\sum^j_{h = 1} {VDM} (\mathbf{x}_{1, h}, \mathbf{x}_{2, h}) + \sum^d_{h = j + 1} {| \mathbf{x}_{1, h}, \mathbf{x}_{2, h} |}^2)^{\frac{1}{2}}. \tag{2*}
d=(h=1∑jVDM(x1,h,x2,h)+h=j+1∑d∣x1,h,x2,h∣2)21.(2*)
III)数值
z
1
z_1
z1和
z
2
z_2
z2的VDM距离表示如下:
V
D
M
(
z
1
,
z
2
)
=
∑
c
=
1
C
∣
N
Z
,
z
1
,
c
N
Z
,
z
1
−
N
Z
,
z
2
,
c
N
Z
,
z
2
∣
2
,
(1)
{VDM} (z_1, z_2) = \sum^C_{c = 1} \bigg| \frac{N_{Z, z_1, c}}{N_{Z, z_1}} - \frac{N_{Z, z_2, c}}{N_{Z, z_2}} \bigg |^2, \tag{1}
VDM(z1,z2)=c=1∑C∣∣∣∣NZ,z1NZ,z1,c−NZ,z2NZ,z2,c∣∣∣∣2,(1) 其中
N
Z
,
z
N_{Z,z}
NZ,z表示持有
z
z
z的
Z
Z
Z的长度,
N
Z
,
z
,
c
N_{Z, z, c}
NZ,z,c表示持有
z
z
z的
Z
Z
Z中数值属于第
c
c
c类的数量,
C
C
C表示类别数。
理解:这里的
Z
Z
Z代表实例
x
x
x的前j个值组成的向量 (暂时记作
x
∗
x^*
x∗),
N
Z
,
z
=
j
N_{Z, z} = j
NZ,z=j。
疑问:这里的类别指的是什么?
一种猜测是按照某种方式将
x
∗
x^*
x∗中的值分为
C
C
C类,则
N
Z
,
z
,
c
N_{Z, z, c}
NZ,z,c表示当前数值所属类别的数值数。
3)将训练包映射为图的集合,并以此构建分类器。
I)例1:使用kNN、图形距离 (graph edit distance) 3来构建分类器;
2)例2:设置一种图核、带核的分类器如SVM。
4)MIGraph使用3)中例二的方法,其图核的思想如下图 (图片来自原论文),即通过节点核和边界核来计算两个包之间的相似性:
给定两个包
X
i
X_i
Xi和
X
j
X_j
Xj,并将其看作为图:
G
h
(
{
x
h
u
}
u
=
1
n
h
,
{
e
h
v
}
v
=
1
m
h
)
G_h (\{ \mathbf{x}_{hu}\}^{n_h}_{u = 1}, \{ \mathbf{e}_{hv}\}^{m_h}_{v = 1})
Gh({xhu}u=1nh,{ehv}v=1mh),其中
n
h
n_h
nh和
m
h
m_h
mh分别是
G
h
G_h
Gh中节点和边界的个数,则图核定义如下:
k
G
(
x
i
,
x
j
)
=
∑
a
=
1
n
i
∑
b
=
1
n
j
k
n
o
d
e
(
x
i
a
,
x
j
b
)
+
∑
a
=
1
m
i
∑
b
=
1
m
j
k
e
d
g
e
(
e
i
a
,
e
j
b
)
,
(2)
k_G (\mathbf{x}_i, \mathbf{x}_j) = \sum^{n_i}_{a = 1} \sum^{n_j}_{b = 1} k_{node} ( \mathbf{x}_{ia}, \mathbf{x}_{jb}) + \sum^{m_i}_{a = 1} \sum^{m_j}_{b = 1} k_{edge} ( \mathbf{e}_{ia}, \mathbf{e}_{jb}), \tag{2}
kG(xi,xj)=a=1∑nib=1∑njknode(xia,xjb)+a=1∑mib=1∑mjkedge(eia,ejb),(2)其中
k
n
o
d
e
k_{node}
knode和
k
e
d
g
e
k_{edge}
kedge是正半定核 (positive semidefinite kernels)。
为了避免数值问题,
k
G
k_G
kG标准化如下:
k
G
(
x
i
,
x
j
)
=
k
G
(
x
i
,
x
j
)
k
G
(
x
i
,
x
i
)
k
G
(
x
j
,
x
j
)
.
(3)
k_G (\mathbf{x}_i, \mathbf{x}_j) = \frac{k_G (\mathbf{x}_i, \mathbf{x}_j)}{\sqrt{k_G (\mathbf{x}_i, \mathbf{x}_i)}\sqrt{k_G (\mathbf{x}_j, \mathbf{x}_j)}}. \tag{3}
kG(xi,xj)=kG(xi,xi)
kG(xj,xj)
kG(xi,xj).(3)
k
n
o
d
e
k_{node}
knode和
k
e
d
g
e
k_{edge}
kedge的定义方式多样,以下用Gaussian RBF核4对
k
n
o
d
e
k_{node}
knode进行定义:
k
n
o
d
e
(
x
i
a
,
x
j
b
)
=
exp
(
−
γ
∥
x
i
a
−
x
j
b
∥
2
)
.
(4)
k_{node} (\mathbf{x}_{ia}, \mathbf{x}_{jb}) = \exp (- \gamma \parallel \mathbf{x}_{ia} - \mathbf{x}_{jb} \parallel^2). \tag{4}
knode(xia,xjb)=exp(−γ∥xia−xjb∥2).(4)
k
e
d
g
e
k_{edge}
kedge的定义与式 (4)类似,只是将
x
i
j
\mathbf{x}_{ij}
xij替换为
e
i
j
\mathbf{e}_{ij}
eij。
目前的关键问题是如何定义特征向量来描述边界:
边界用于连接包
X
i
X_i
Xi中的两个节点
x
i
u
\mathbf{x}_{iu}
xiu和
x
i
v
\mathbf{x}_{iv}
xiv,将其定义为
[
d
u
,
p
u
,
d
v
,
p
v
]
′
[d_u, p_u, d_v, p_v]'
[du,pu,dv,pv]′,其中
d
u
d_u
du表示
x
i
u
\mathbf{x}_{iu}
xiu与其他节点相连接的边界数量,需要注意的是已通过将其除以
X
i
X_i
Xi中的边界总数来进行归一化;
d
v
d_v
dv的定义与
d
u
d_u
du类似;
p
u
p_u
pu定义如下:
p
u
=
w
u
v
/
∑
w
u
,
∗
.
(3*)
p_u = w_{uv} / \sum w_{u, *}. \tag{3*}
pu=wuv/∑wu,∗.(3*)其中
w
u
v
w_{uv}
wuv表示连接
x
i
u
\mathbf{x}_{iu}
xiu和
x
i
v
\mathbf{x}_{iv}
xiv的权重;
w
u
,
∗
w_{u, *}
wu,∗表示
x
i
u
\mathbf{x}_{iu}
xiu与其他相连接节点的权重之和;
p
v
p_v
pv的定义与
p
u
p_u
pu类似。
如公式 (2),
k
G
k_G
kG是一个正定核 (positive definite kerne),显然,
k
G
k_G
kG满足图核定义所需考虑的四个主要性质5
且可以用于任意的图,不足之处在于时间复杂度为
O
(
n
i
n
j
+
m
i
m
j
)
O (n_in_j + m_im_j)
O(ninj+mimj)。对此,“我们”提出了一种更为简单高效的核,即miGraph。
对于包 X i X_i Xi中的两个实例之间的距离,“我们“可以通过构建关联矩阵 W i W^i Wi (affinity matrix)来计算。例如,如果两个实例 x i a \mathbf{x}_{ia} xia和 x i u \mathbf{x}_{iu} xiu之间的距离小于给定阈值 δ \delta δ, W i W^i Wi的第 a a a行第 u u u列元素 w a u i w^i_{au} waui将设置为1,反之为0。
本文中,距离的度量使用Gaussian距离,
δ
\delta
δ设置为包中的平均距离:
给定两个包
X
i
X_i
Xi和
X
j
X_j
Xj,分别包含
n
i
n_i
ni和
n
j
n_j
nj个实例实例,则图核的定义如下:
k
g
(
X
i
,
X
j
)
=
∑
a
=
1
n
i
∑
b
=
1
n
j
W
i
a
W
j
b
k
(
x
i
a
,
x
j
b
)
∑
a
=
1
n
i
W
i
a
∑
b
=
1
n
j
W
j
b
,
(5)
k_g (X_i, X_j) = \frac{\sum \limits^{n_i}_{a = 1}\sum \limits^{n_j}_{b = 1} W_{ia} W_{jb} k (\mathbf{x}_{ia}, \mathbf{x}_{jb})}{\sum \limits^{n_i}_{a = 1} W_{ia} \sum \limits^{n_j}_{b = 1} W_{jb}}, \tag{5}
kg(Xi,Xj)=a=1∑niWiab=1∑njWjba=1∑nib=1∑njWiaWjbk(xia,xjb),(5)其中
W
i
a
=
1
/
∑
u
=
1
n
i
w
a
u
i
W_{ia} = 1 / \sum^{n_i}_{u = 1} w^i_{au}
Wia=1/∑u=1niwaui,
W
j
b
=
1
/
∑
v
=
1
n
j
w
b
v
j
W_{jb} = 1 / \sum^{n_j}_{v = 1} w^j_{bv}
Wjb=1/∑v=1njwbvj,
k
(
x
i
a
,
x
j
b
)
k (\mathbf{x}_{ia}, \mathbf{x}_{jb})
k(xia,xjb)的定义类似于式 (4)。
k
g
k_g
kg应满足以下原则:
W
i
a
=
{
1
,
W
i
=
I
;
1
/
n
i
,
W
i
=
E
;
1
/
n
i
a
,
W
i
=
C
,
(4*)
W_{ia} =
显然
k
g
k_g
kg的时间复杂度为
O
(
n
i
n
j
)
O (n_in_j)
O(ninj)
数据集类型 | 实验类型 | 实验结果展示 |
---|---|---|
benchmark数据集 | 10次10CV | 分类精度 + 标准差 |
image categorization | 5次随机划分(数据集的每一个类别随机二划分,实验类型为one-against-one) | 95%置信区间 |
text categorization | 10次10CV | 分类精度 + 标准差 |
regression (artificial) | LOO | 平方损失 |
Tenenbaum, J. B., de Silva, V., & Langford, J. C. (2000). A global geometric framework for nonlinear dimensionality reduction. Science, 290, 2319–2323. ↩︎
Stanfill, C., & Waltz, D. (1986). Toward memory-based reasoning. Comm. ACM, 29, 1213–1228. ↩︎
Neuhaus, M., & Bunke, H. (2007). A quadratic programming approach to the graph edit distance problem. Proc. 6th IAPR Workshop on Graph-based Represent. in Patt. Recogn. (pp. 92–102). ↩︎
Gärtner, T. (2003). A survey of kernels for structured data. SIGKDD Explorations, 5, 49–58. ↩︎
Borgwardt, K. M., & Kriegel, H.-P. (2005). Shortest-path kernels on graphs. Proc. 5th IEEE Intl. Conf. Data Min. (pp. 74–81). ↩︎
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。