数学基础

凸分析

凸集的一些结论

定义： 当集合A Tutorial on Distancce Metric Learning - 图1 和任意A Tutorial on Distancce Metric Learning - 图2，满足条件A Tutorial on Distancce Metric Learning - 图3x%2B%5Clambda%20y%3A%5Clambda%5Cin%20%5B0%2C1%5D%7D%5Csubset%20K#card=math&code=%5Bx%2Cy%5D%20%3D%20%7B%281-%5Clambda%29x%2B%5Clambda%20y%3A%5Clambda%5Cin%20%5B0%2C1%5D%7D%5Csubset%20K&id=SACxR)时，集合A Tutorial on Distancce Metric Learning - 图4是一个凸集。

从这个定义中可以得知，任何一个非空的、是闭集的凸集，对于其边界的任何一个点我们都可以得到一个超平面，且该超平面满足以下特性：

  • 该闭凸集仅仅与这个超平面相较于一个点
  • 该闭凸集完全处于空间中该超平面划分的一侧

定义：设A Tutorial on Distancce Metric Learning - 图5是一个线性映射，A Tutorial on Distancce Metric Learning - 图6，则A Tutorial on Distancce Metric Learning - 图7%3D%5Calpha%5C%7D#card=math&code=P%3D%5C%7Bx%20%5Cin%20%5Cmathbb%7BR%7D%5Ed%3AT%28x%29%3D%5Calpha%5C%7D&id=mzLRV)是一个超平面。针对该超平面A Tutorial on Distancce Metric Learning - 图8，定义

A Tutorial on Distancce Metric Learning - 图9%5Cgeq%20%5Calpha%5C%7D%20%5C%5C%0AP%5E-%3D%5C%7Bx%5Cin%20%5Cmathbb%7BR%7D%5Ed%3AT(x)%5Cleq%20%5Calpha%5C%7D%0A#card=math&code=P%5E%2B%3D%5C%7Bx%5Cin%20%5Cmathbb%7BR%7D%5Ed%3AT%28x%29%5Cgeq%20%5Calpha%5C%7D%20%5C%5C%0AP%5E-%3D%5C%7Bx%5Cin%20%5Cmathbb%7BR%7D%5Ed%3AT%28x%29%5Cleq%20%5Calpha%5C%7D%0A&id=q61eL)

此时，如果A Tutorial on Distancce Metric Learning - 图10，且满足A Tutorial on Distancce Metric Learning - 图11或A Tutorial on Distancce Metric Learning - 图12二者之一，我们则将超平面A Tutorial on Distancce Metric Learning - 图13称作是对于集合A Tutorial on Distancce Metric Learning - 图14一个支撑超平面，同时称呼在A Tutorial on Distancce Metric Learning - 图15和A Tutorial on Distancce Metric Learning - 图16之间包含A Tutorial on Distancce Metric Learning - 图17的半空间为支撑半空间。

定理1 支撑超平面定理

  1. 如果A Tutorial on Distancce Metric Learning - 图18是一个闭凸集，则对于任何一个A Tutorial on Distancce Metric Learning - 图19，对于K有一个支撑超平面A Tutorial on Distancce Metric Learning - 图20使得A Tutorial on Distancce Metric Learning - 图21
  2. 在A Tutorial on Distancce Metric Learning - 图22的任何一个闭合的真凸集是其所有支撑半空间的交。
  3. A Tutorial on Distancce Metric Learning - 图23是一个非空闭集，则A Tutorial on Distancce Metric Learning - 图24是凸集当且仅当对于任意的A Tutorial on Distancce Metric Learning - 图25有一个支撑超平面A Tutorial on Distancce Metric Learning - 图26且A Tutorial on Distancce Metric Learning - 图27

这个定理的意义在于针对任何一个在A Tutorial on Distancce Metric Learning - 图28内的闭凸集和一个在A Tutorial on Distancce Metric Learning - 图29的点，我们均可以在这个闭凸集内找到一个针对该点最近的点，并且这个最近的点是唯一的，这也就是说针对那个给定的点，有一个在给定的闭凸集上的投影。

定理2 Convex Projection

对非空闭凸集A Tutorial on Distancce Metric Learning - 图30，对于任何一个点A Tutorial on Distancce Metric Learning - 图31，均有唯一的点A Tutorial on Distancce Metric Learning - 图32和A Tutorial on Distancce Metric Learning - 图33%3Dd(x%2Cx_0)#card=math&code=d%28x%2CK%29%3Dd%28x%2Cx_0%29&id=rI1PX)，这里我们定义到集合A Tutorial on Distancce Metric Learning - 图34的距离是：

A Tutorial on Distancce Metric Learning - 图35%3Dinf%5C%7Bd(x%2Cy)%3Ay%5Cin%20K%5C%7D%0A#card=math&code=d%28x%2CK%29%3Dinf%5C%7Bd%28x%2Cy%29%3Ay%5Cin%20K%5C%7D%0A&id=ntxrH)

其中，A Tutorial on Distancce Metric Learning - 图36%5C%7D#card=math&code=inf%5C%7Bd%28x%2Cy%29%5C%7D&id=ipTkI)指的是所有满足条件的A Tutorial on Distancce Metric Learning - 图37#card=math&code=d%28x%2Cy%29&id=DZVOf)的取值的下界。点A Tutorial on Distancce Metric Learning - 图38被称作A Tutorial on Distancce Metric Learning - 图39在A Tutorial on Distancce Metric Learning - 图40上的投影，记作A Tutorial on Distancce Metric Learning - 图41#card=math&code=P_K%28x%29&id=R5CC7)

函数A Tutorial on Distancce Metric Learning - 图42也A Tutorial on Distancce Metric Learning - 图43#card=math&code=x%20%5Cmapsto%20P_K%28x%29&id=pOjc7)所定义，被称作在A Tutorial on Distancce Metric Learning - 图44上的投影。

同时，对于A Tutorial on Distancce Metric Learning - 图45，半空间A Tutorial on Distancce Metric Learning - 图46%2Cy-P_K(x)%5Cright%20%5Crangle%20%5Cleq%200%5C%7D#card=math&code=%5C%7B%20y%20%5Cin%20%5Cmathbb%7BR%7D%5Ed%3A%5Cleft%20%5Clangle%20x-P_K%28x%29%2Cy-P_K%28x%29%5Cright%20%5Crangle%20%5Cleq%200%5C%7D&id=u1EOa)是在A Tutorial on Distancce Metric Learning - 图47#card=math&code=P_K%28x%29&id=TO9m7)对A Tutorial on Distancce Metric Learning - 图48的支撑半空间。

优化方法

针对可导且无约束的函数，采用梯度进行优化。对于带有凸条件的凸函数，采用梯度下降迭代获得的A Tutorial on Distancce Metric Learning - 图49可能并不在可行域中，但当约束条件是闭凸的，则我们可以使用投影映射到可行域中。

综述

一句话来总结DML的方法，那就是：

寻找一种可以使得相似的数据更加接近、不相似的数据相聚更远的距离度量

目前已经证明，DML对于在小中型的数据集上十分有效，但对于大量数据的处理一直是它的局限性。今年已经有许多针对该局限性进行改正的算法。

根据DML算法的目标可以对其进行分类，其目标主要有：

维数约简、改进分类器的距离度量或者基于信息论进行。

选用DML的原因：

根据人的直觉，距离可以被用来衡量事物之间的相似性。而将这一直觉迁移到机器学习领域，那就是设计一种可以从数据集中基于数据之间所体现的相似度来进行学习的算法。而为了衡量这一相似性，就很有必要来引入距离这一个概念，距离可以被用来作为相似度衡量的依据。而我们需要从无穷多的距离选项中选择最适合的那一个。此时，DML应运而生。DML可以获得数据的特征与关系，这是一般的距离指标比如欧氏距离所不具备的能力。

马氏距离

首先给出一些定义：

定义1 设A Tutorial on Distancce Metric Learning - 图50为一个非空集合，而在A Tutorial on Distancce Metric Learning - 图51上的距离或者度量就是一个映射A Tutorial on Distancce Metric Learning - 图52，并且该映射满足以下条件：

  1. 一致性：对于每一A Tutorial on Distancce Metric Learning - 图53，均有A Tutorial on Distancce Metric Learning - 图54%3D0%20%5CLongleftrightarrow%20x%3Dy#card=math&code=d%28x%2Cy%29%3D0%20%5CLongleftrightarrow%20x%3Dy&id=LmZmG)
  2. 对称性：对于每一A Tutorial on Distancce Metric Learning - 图55，均有A Tutorial on Distancce Metric Learning - 图56%3Dd(y%2Cx)#card=math&code=d%28x%2Cy%29%3Dd%28y%2Cx%29&id=Czc6Y)
  3. 三角不等性：对于每一A Tutorial on Distancce Metric Learning - 图57，均有A Tutorial on Distancce Metric Learning - 图58%5Cleq%20d(x%2Cy)%2Bd(y%2Cz)#card=math&code=d%28x%2Cz%29%5Cleq%20d%28x%2Cy%29%2Bd%28y%2Cz%29&id=KNFO0)

而有序对A Tutorial on Distancce Metric Learning - 图59#card=math&code=%28X%2Cd%29&id=LQdNC)被称为度量空间。

而当一个映射A Tutorial on Distancce Metric Learning - 图60仅仅满足上述条件的2与3，并并将条件置换成A Tutorial on Distancce Metric Learning - 图61%3D0#card=math&code=d%28x%2Cx%29%3D0&id=DBj4W)，我们称其为伪距离。伪距离具有以下三个特性：

  1. 非负性：对于每一A Tutorial on Distancce Metric Learning - 图62，均有A Tutorial on Distancce Metric Learning - 图63%5Cgeq%200#card=math&code=d%28x%2Cy%29%5Cgeq%200&id=nl4Rs)
  2. 反向三角不等行：对于每一A Tutorial on Distancce Metric Learning - 图64，均有A Tutorial on Distancce Metric Learning - 图65-d(y%2Cz)%7C%5Cleq%20d(x%2Cz)#card=math&code=%7Cd%28x%2Cy%29-d%28y%2Cz%29%7C%5Cleq%20d%28x%2Cz%29&id=Qvded)
  3. 广义三角不等性：对于A Tutorial on Distancce Metric Learning - 图66，有A Tutorial on Distancce Metric Learning - 图67%5Cleq%20%5Csum%7Bi%3D1%7D%5E%7Bn-1%7Dd(x_i%2Cx%7Bi%2B1%7D)#card=math&code=d%28x1%2Cx_n%29%5Cleq%20%5Csum%7Bi%3D1%7D%5E%7Bn-1%7Dd%28xi%2Cx%7Bi%2B1%7D%29&id=FJmLE)

在n维欧氏空间中，马氏距离是十分重要的。为了定义马氏距离需要定义一些数学概念：

我们使用A Tutorial on Distancce Metric Learning - 图68来表示维度为A Tutorial on Distancce Metric Learning - 图69的矩阵的集合，使用A Tutorial on Distancce Metric Learning - 图70来表示A Tutorial on Distancce Metric Learning - 图71维的半正定矩阵的集合。

此时可以给出马氏距离的定义：

取A Tutorial on Distancce Metric Learning - 图72且A Tutorial on Distancce Metric Learning - 图73，针对矩阵A Tutorial on Distancce Metric Learning - 图74的马氏距离A Tutorial on Distancce Metric Learning - 图75可以被表示为：

A Tutorial on Distancce Metric Learning - 图76

当A Tutorial on Distancce Metric Learning - 图77满秩时，马氏距离是一个真正的距离，当其不满秩时，是一个伪距离。而取A Tutorial on Distancce Metric Learning - 图78为单位阵A Tutorial on Distancce Metric Learning - 图79时，马氏距离就变成了欧氏距离了。针对马氏距离有特性：

  1. 同质性:对于每一A Tutorial on Distancce Metric Learning - 图80，均有A Tutorial on Distancce Metric Learning - 图81%3D%7Ca%7Cd(x%2Cy)#card=math&code=d%28ax%2Cay%29%3D%7Ca%7Cd%28x%2Cy%29&id=t9mE8)
  2. 平移不变性：对于每一A Tutorial on Distancce Metric Learning - 图82，均有A Tutorial on Distancce Metric Learning - 图83%3Dd(x%2Bz%2Cy%2Bz)#card=math&code=d%28x%2Cy%29%3Dd%28x%2Bz%2Cy%2Bz%29&id=TigRe)

有些时候也使用马氏距离的平方来指代马氏距离，因为这样便于编程计算。

有关DML的描述

首先给出一些定义：

使用A Tutorial on Distancce Metric Learning - 图84来指代数据集，数据集我们通常是已经拥有的。在数据集上的相似性度量的表示如下：

当两对数据A Tutorial on Distancce Metric Learning - 图85与A Tutorial on Distancce Metric Learning - 图86相似时，使用A Tutorial on Distancce Metric Learning - 图87来表示这一相似的数据对构成的的集合：

A Tutorial on Distancce Metric Learning - 图88%5Cin%20X%5Ctimes%20X%5C%7D%0A#card=math&code=S%3D%5C%7B%28x_i%2Cx_j%29%5Cin%20X%5Ctimes%20X%5C%7D%0A&id=tLNxE)

当两对数据A Tutorial on Distancce Metric Learning - 图89与A Tutorial on Distancce Metric Learning - 图90不相似时，使用A Tutorial on Distancce Metric Learning - 图91来表示这一相似的数据对构成的的集合：

A Tutorial on Distancce Metric Learning - 图92%5Cin%20X%5Ctimes%20X%5C%7D%0A#card=math&code=D%3D%5C%7B%28x_i%2Cx_j%29%5Cin%20X%5Ctimes%20X%5C%7D%0A&id=pmqAD)

当数据A Tutorial on Distancce Metric Learning - 图93，相比于A Tutorial on Distancce Metric Learning - 图94而和A Tutorial on Distancce Metric Learning - 图95更加相似时，使用A Tutorial on Distancce Metric Learning - 图96表示这一三元组的集合：

A Tutorial on Distancce Metric Learning - 图97%5Cin%20X%5Ctimes%20X%5Ctimes%20X%5C%7D%0A#card=math&code=R%3D%5C%7B%28x_i%2Cx_j%2Cx_l%29%5Cin%20X%5Ctimes%20X%5Ctimes%20X%5C%7D%0A&id=eJ90B)

为了在数据集和上述的三个相似条件约束的情况下最优化距离取值集合A Tutorial on Distancce Metric Learning - 图98，设置一个损失函数A Tutorial on Distancce Metric Learning - 图99并需要解决一个最优化问题来获得最小的距离：

A Tutorial on Distancce Metric Learning - 图100%0A#card=math&code=min_%7Bd%5Cin%5CDelta%7Dl%28d%2CS%2CD%2CR%29%0A&id=nheb0)

而在有标签的监督学习的情形下，A Tutorial on Distancce Metric Learning - 图101与A Tutorial on Distancce Metric Learning - 图102可以被改写成如下形式：

A Tutorial on Distancce Metric Learning - 图103%5Cin%20X%5Ctimes%20X%3Ay_i%3Dy_j%5C%7D%0A%5Cnewline%0AD%3D%5C%7B(x_i%2Cx_j)%5Cin%20X%5Ctimes%20X%20%3A%20y_i%5Cneq%20y_j%5C%7D%0A#card=math&code=S%3D%5C%7B%28x_i%2Cx_j%29%5Cin%20X%5Ctimes%20X%3Ay_i%3Dy_j%5C%7D%0A%5Cnewline%0AD%3D%5C%7B%28x_i%2Cx_j%29%5Cin%20X%5Ctimes%20X%20%3A%20y_i%5Cneq%20y_j%5C%7D%0A&id=IVeEO)

同样的，在一定范围内的本地DML可以将A Tutorial on Distancce Metric Learning - 图104改写成一个更进一步的形式：

A Tutorial on Distancce Metric Learning - 图105%5Cin%20X%5Ctimes%20X%3Ay_i%3Dy_j%20%5Cquad%20and%20%5Cquad%20x_i%5Cin%20U(x_i)%5C%7D%0A#card=math&code=S%3D%5C%7B%28x_i%2Cx_j%29%5Cin%20X%5Ctimes%20X%3Ay_i%3Dy_j%20%5Cquad%20and%20%5Cquad%20x_i%5Cin%20U%28x_i%29%5C%7D%0A&id=TsuRp)

这里，A Tutorial on Distancce Metric Learning - 图106#card=math&code=U%28x_i%29&id=to9io)指代的是数据A Tutorial on Distancce Metric Learning - 图107附近的数据，也就是一个靠近A Tutorial on Distancce Metric Learning - 图108的数据的集合，这样的集合是在DML学习之前使用一些先验信息获得的，比如使用标准的相似性度量。针对A Tutorial on Distancce Metric Learning - 图109这一几何也加上约束A Tutorial on Distancce Metric Learning - 图110也可以帮助区分一些特殊的情况。

尽管DML可以被用于非数字的数据集上，但用在数字型的数据集上效果更好。