ITML及复现

Reference

Paper: Information-Theoretic-Metric-Learning

http://metric-learn.github.io/metric-learn/

Intro

这是度量学习的一个方法, 根据给定已标注样本数据集, 学习一个马氏度量的协方差矩阵的逆, 用相对熵衡量损失.

Problem Formulation

给定点集${\{x_1,\dots,x_n\}},x_i\in\R^d$, 我们希望找到一个正定矩阵$\mathbf A$, 用来定义一个马氏距离(平方, 为方便, 下文不指出这一点)

对于两个点, 我们希望用马氏距离的来度量它们的相似性或相异性, 马氏距离越小, 它们就越相似. 如果两个点的马氏距离大于或小于上下阈值, 我们就说它们是相似的或相异的.

这种约束对于许多半监督学习问题是输入, 也可以应用于一个有分类标记的样本集, 只需要使得相同类的实例距离较小, 反之较大.

所以, 现在的问题是我们需要学习一个正定矩阵$A$, 来计算一组点之间的马氏距离. 通常来说, 这样学习距离可以提高KNN算法的精度, 或将半监督学习问题纳入distance-based clus- tering algorithm算法.

在许多情况中, 马氏距离是已知的, 比如数据分布符合高斯分布, 样本集的协方差矩阵的逆就可以作为$A$. 在某些情况下, 欧式距离也能很好地工作(对应马氏距离$A$是一个单位矩阵).

我们现在设$A$是我们想要的矩阵, 我们将马氏距离用$A_0$参数化. 我们通过自然信息论方法衡量$A$与$A_0$的差异. 我们注意到由于高斯分布函数以马氏距离的平方为参数, 所以马氏距离和高斯分布存在一个简单的双射关系. (不失一般性, 我们可以假设高斯分布有均值$\mu$). 我们可以这样表示它们的双射关系, $Z$为单位化约束, $A^{-1}$是分布的协方差矩阵.

然后通过KL散度衡量$A$与$A_0$的差异.

KL散度提供了很好的衡量两个马氏距离差异的方法.

设$S$是相似点的下标对的集合, $D$是不相似点的下标对对的集合. 我们的度量学习问题为

在上述公式中的约束是简单的, 但是, 我们可以对公式稍作变形, 来适应其他约束情况, 比如相对接近性约束. (Schutz & Joachims, 2003)事实上, ITML可以合并任意线性约束.

Algorithm

Metric Learning as LogDet Optimization

LogDet divergence: $\phi(X)=-log(detX)$, $X$是一个正定矩阵的锥.

两个多变量高斯分布的微分相对熵可以表示为均值向量间的马氏距离和协方差矩阵的logdet divergence的凸组合. (Davis & Dhillon, 2006)

LogDet divergence也被称为Stein’s loss, 它是具有尺度不变性(James & Stein, 1961).

尺度不变性意味着它在任何特征空间的缩放后都保持不变.

设$S$为可逆线性变换, 则

因此, 原度量学习问题可以转化为如下的LogDet优化问题

为了防止上述问题不存在解, 我们加一个松弛变量. 设$c(i,j)$表示第(i,j)的约束的序号, 设$\xi$为松弛向量, 初始值为$\xi_0$.(它对应相似约束部分等于u, 相异约束部分等于l)

1543631365871

(未完待续)

实验

算法部分涉及到凸优化理论, 我看得并不明白, 只能先搁置了, 可能后续得学一些凸优化的理论.

幸好在github找到了已经实现好的python库, 我可以跳过算法实现, 直接实验.

四维点集的两个维度

原始样本

1543716106221

坐标变换后

1543716151115

On Extend_Yale_B

1543717833107

一共38类64张.

直接将图片缩放成了32*32

实验中的几个超参数

  • 使用KNN, k = 4
  • 置信区间为95%
  • 随机选取$c^2$对样本, 其中c为种类数(论文推荐的约束数目为$20c^2$, 但由于计算时间太长, 就没这样做)

在训练集上的测试

坐标变换前(欧式距离)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
>          0.0       0.57      1.00      0.73        64
> 1.0 0.69 0.95 0.80 64
> 2.0 0.71 0.78 0.75 64
> 3.0 0.70 0.94 0.80 64
> 4.0 0.83 0.97 0.89 64
> 5.0 0.74 0.92 0.82 64
> 6.0 0.63 0.81 0.71 64
> 7.0 0.69 0.95 0.80 64
> 8.0 0.87 0.94 0.90 64
> 9.0 0.84 0.72 0.77 64
> 10.0 0.98 0.84 0.91 64
> 11.0 0.95 0.92 0.94 64
> 12.0 0.98 0.91 0.94 64
> 13.0 1.00 0.89 0.94 64
> 14.0 0.79 0.75 0.77 64
> 15.0 0.91 0.83 0.87 64
> 16.0 0.90 0.95 0.92 64
> 17.0 0.96 0.86 0.91 64
> 18.0 0.80 0.89 0.84 64
> 19.0 1.00 0.81 0.90 64
> 20.0 0.95 0.88 0.91 64
> 21.0 0.94 0.80 0.86 64
> 22.0 1.00 0.86 0.92 64
> 23.0 0.95 0.83 0.88 64
> 24.0 1.00 0.88 0.93 64
> 25.0 1.00 0.91 0.95 64
> 26.0 1.00 0.92 0.96 64
> 27.0 0.98 0.84 0.91 64
> 28.0 0.96 0.83 0.89 64
> 29.0 0.98 0.88 0.93 64
> 30.0 0.98 0.95 0.97 64
> 31.0 0.89 0.80 0.84 64
> 32.0 0.90 0.83 0.86 64
> 33.0 0.92 0.91 0.91 64
> 34.0 1.00 0.70 0.83 64
> 35.0 0.93 0.83 0.88 64
> 36.0 0.92 0.88 0.90 64
> 37.0 1.00 0.91 0.95 64
>
> micro avg 0.87 0.87 0.87 2432
> macro avg 0.89 0.87 0.87 2432
> weighted avg 0.89 0.87 0.87 2432
>

坐标变换后(马氏距离)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
>          0.0       1.00      1.00      1.00        64
> 1.0 1.00 1.00 1.00 64
> 2.0 1.00 1.00 1.00 64
> 3.0 1.00 1.00 1.00 64
> 4.0 1.00 1.00 1.00 64
> 5.0 1.00 1.00 1.00 64
> 6.0 1.00 1.00 1.00 64
> 7.0 1.00 1.00 1.00 64
> 8.0 1.00 1.00 1.00 64
> 9.0 1.00 1.00 1.00 64
> 10.0 1.00 1.00 1.00 64
> 11.0 1.00 1.00 1.00 64
> 12.0 1.00 1.00 1.00 64
> 13.0 1.00 1.00 1.00 64
> 14.0 1.00 1.00 1.00 64
> 15.0 1.00 1.00 1.00 64
> 16.0 1.00 1.00 1.00 64
> 17.0 1.00 1.00 1.00 64
> 18.0 1.00 1.00 1.00 64
> 19.0 1.00 1.00 1.00 64
> 20.0 1.00 1.00 1.00 64
> 21.0 1.00 1.00 1.00 64
> 22.0 1.00 1.00 1.00 64
> 23.0 1.00 1.00 1.00 64
> 24.0 1.00 1.00 1.00 64
> 25.0 1.00 1.00 1.00 64
> 26.0 1.00 1.00 1.00 64
> 27.0 1.00 1.00 1.00 64
> 28.0 1.00 1.00 1.00 64
> 29.0 1.00 1.00 1.00 64
> 30.0 1.00 1.00 1.00 64
> 31.0 1.00 1.00 1.00 64
> 32.0 0.96 1.00 0.98 64
> 33.0 0.97 0.98 0.98 64
> 34.0 1.00 0.98 0.99 64
> 35.0 1.00 0.98 0.99 64
> 36.0 1.00 0.98 0.99 64
> 37.0 1.00 0.98 0.99 64
>
> micro avg 1.00 1.00 1.00 2432
> macro avg 1.00 1.00 1.00 2432
> weighted avg 1.00 1.00 1.00 24322
>

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
import matplotlib.pyplot as plt
from PIL import Image
import numpy as np

def read_img(src, grey=True):
im = Image.open(src);
im_l = im.convert('L').resize((48,48))
im_arr = np.array(im_l)
# 也可以用 np.asarray(im)
# 区别是 np.array() 是深拷贝,np.asarray() 是浅拷贝
# im = Image.fromarray(np.uint8(im_arr))
# im.show()
return im_arr.reshape((1,-1));

def show_img(im_arr):
im = Image.fromarray(np.uint8(im_arr.reshape((48, 48))))
plt.imshow(im)

import os
image_dir = "/mnt/data/Source/MachineLearning/Synergistic Generic Learning/Extend_Yale_B/"
path_list = os.listdir(image_dir)
path_list.sort()
file_list = []
for path in path_list:
file_list.append(image_dir + path)


img_data = np.empty((0,2304))
for img_src in file_list:
img_arr = read_img(img_src)
img_data = np.append(img_data, values=img_arr, axis=0)
print(img_data.shape)


np.save('data.npy', img_data)
# Load images data
img_data = np.load('data.npy')
img_data.shape

# get v_s
v_s = np.empty((0,2304))
for i in range(38):
c_i = np.zeros((1, 2304))
for j in range(64):
c_i += img_data[64*i+j]/64
v_s = np.append(v_s, values=img_data[64*i]-c_i, axis=0)
print(v_s.shape)
for i in range(7):
plt.subplot(7, 10, i*10+1)
plt.imshow(Image.fromarray(np.uint8(v_s[i].reshape((48, 48)))))
plt.axis('off')
for j in range(9):
plt.subplot(7, 10, i*10+2+j)
plt.imshow(Image.fromarray(np.uint8(img_data[i*64+j].reshape((48, 48)))))
plt.axis('off')
plt.show()

import metric_learn

X = img_data
c = 38
t = 64
(n,d) = X.shape
Y = np.zeros((n))
for i in range(c):
for j in range(t):
Y[i*t+j]=i


itml = metric_learn.ITML_Supervised(convergence_threshold=c*c)
X_itml = itml.fit_transform(X, Y)
M = itml.metric()
L = itml.transformer()
np.save('X_itml.npy', X_itml)
np.save('M.npy', M)
np.save('L.npy', L)


X_itml = np.load('X_itml.npy')
M = np.load('M.npy')
L = np.load('L.npy')

print(M.shape)
print(X_itml.shape)


from sklearn import neighbors
from sklearn import metrics


model_1 = neighbors.KNeighborsClassifier(n_neighbors=4)
model_1.fit(X_itml,Y)
print(model_1)

predicted_1 = model_1.predict(X_itml)
print(metrics.classification_report(Y,predicted_1))

tmp_c = 32
for i in range(0,63):
new_img = np.mean([X[tmp_c*t + i,:],X[tmp_c*t+ i+1,:]], axis=0)
pre = model_1.predict([new_img.dot(L.T)])
print(pre)
文章目录
  1. 1. Reference
  2. 2. Intro
  3. 3. Problem Formulation
  4. 4. Algorithm
    1. 4.1. Metric Learning as LogDet Optimization
  5. 5. 实验
    1. 5.1. 四维点集的两个维度
    2. 5.2. On Extend_Yale_B
      1. 5.2.1. 在训练集上的测试
  6. 6. 代码
|