深度度量学习(一)向量、距离与变换

Jun 22, 2019


原创:岐山凤鸣,转载请注明本站域名

觉得不错不妨star/follow一下我的Github

参考:

Kulis, Brian. (2012). Metric Learning: A Survey. Foundations and Trends in Machine Learning. 5. 10.1561/2200000019. 

前言

开这个系列前我是很纠结的,一方面因为这篇综述实在是我啃过的最难的一篇了,也没有什么中文的说明,关于度量学习并没有统一的学习框架和模式,我用了一个多月的时间才勉强看完,勉强能够理解里面的一些东西。

另一方面里面涉及到大量的数学相关的表达,有些表达因为专业视野限制的原因我可能表达不准,所以理解的私货会比较多,也可能有偏差。

但我依然觉得这部分十分的重要,深度学习发展的今天,它的数学基础是很宏大的,而度量学习刚好是对于深度特征方面一个非常抽象又重要的内容,很多Loss函数、对比方法的原理都源自于此。

当然也有很多水文随便改了改里面的算法(笑)

另外一个层面具备很重要的意义,如今很多人称深度学习已经变成了调包侠学习,当然提出这种说法的很多都是涉入不深的学生。一些在顶会上很有影响力的文章,一般都配备有相关的代码,里面也是调用的框架,我写了这么多年代码,里面的水平我认为是很高的,除非你觉得你能很轻松三四天就完全复刻出来,而且各种功能都齐全。除了主体的那一部分算法思路外,一般这些代码里涉及大量端到端的工程,以及比较精细的度量这块。举个栗子,依然是我最喜欢的那个InsightFace的代码仓库,我认为想看懂都是有些复杂的。里面有一个地方我之前做过博文,那就是Verification,不过做的不够精细。在这方面如果对矩阵、空间、线性变换和非线性变换理解不够透彻的话,很容易产生偏差,当然也会看不懂。

在脱离学术界后,进入工业界,很多情况都不是清洗干净的数据,专为研究意义而生的资源和流程,这种情况更考验一个人的综合素质。

所以继续学习数学,学习度量学习,以及现代的深度度量学习,都是非常有意义的。

关于这个系列会做的有些久,里面涵盖的内容会非常的广,这篇只是一个开头,一个序言和前置的概念,之后同样也会开一个repo去存点代码资源(从度量工具 到 测评工具 到 具体的度量学习的一些案例)。

向量,Vector

度量学习是基于线性代数的,因为度量学习要考虑度量的是什么,对谁进行度量。在我们研究的这一块,度量学习主要度量的是距离,是一个Distance,度量的对象是【空间】里的向量。所以向量是一切的基础,空间也是由向量的域构成,所以度量学习的开端便是向量。

向量在三种学科里有三种意义,物理学意义、计算机科学意义和数学上的意义。而度量学习要考虑的主要是后两者的意义,数学上的意义提供理论基础,计算机科学意义提供实验方案。

  • 物理学意义:带方向的标量,例如力、速度、位移、动量、冲量等,均是一个带方向的标量。
  • 计算机科学意义:一个带顺序的数组,其中a[i]和a[j]的含义不一样,也不能随意替换。
  • 数学上的意义:用来描述空间的代数,主要考虑它的加法和乘法,即

直截了当的说向量和空间的关系,对二维平面来讲,想象一个直角坐标系,横坐标, 纵坐标,我们对这个空间里任意一点的描述是,它的含义是,其中是直角坐标系上的一个正交基底,那么实际上对于这个二维空间里所有的点,任意一个地方,都可以用来表示。实际上哪怕不是正交基底,只是一个线性不相关(Linearly Independent,即不共线)的一对基底,都能描述出这整个二维空间。

同理进行拓展,从二维到高维空间,只要有d个线性不相关的d维向量,那么整个空间便能够进行具现,我们也可以通过一个d维向量或数组,表示空间内任意的某个点。

这个是对线性空间一个比较粗浅的理解,深入理解一点可以从抽象代数角度来理解。

定义一个非空集合X,X里包含的元素为向量,增加元素的加法和数乘(scale),即对属于X里的任意元素均能进行,使得进行运算后的元素也属于X,这样形成的代数系统即为线性空间,满足一系列性质。当然这个空间的维度是由其中线性不相关的向量数量决定的。

这个线性空间<X, 加法,数乘>,往往一般满足不了我们的需求,所以很多时候要对其进行增广。

最广泛的一种增广是增加一个内积运算,也就是在原有空间<X, 加法, 数乘>上增加内积空间,变成<X, 加法, 数乘, 内积>。

内积也是两个向量的二元运算,对向量来说,,加入*为矩阵乘法,同样可以写为

增加内积空间后可以定义出很多的性质,比如向量直接的角度,共轭对称性等。最直接的一个性质就是可以定义出正交向量。

对d维度线性空间+内积空间<X, 加法, 数乘, 内积>,取其中n个向量,若满足n已经达到最大即,且其中任意两两向量满足,且向量的模都相同,那么这n(d)个向量便是线性无关的该空间的正交基底,由这些正交基底线性组合得到的线性空间,和我们这个线性空间是同构的,但也有一个特殊的名字和很多特殊的性质,这个便是欧几里得空间。

我们平时接触的平面直角坐标系,三维直角坐标系,均是欧几里得空间的度量方式。之后说的很多的度量空间,也都是基于欧几里得空间。

上面的都说清楚后,下面才能开始距离Distance的讨论。

距离,Distance

假设在一个数轴上,有甲和乙两个人,位置分别在a和b,那么他们之间距离多少?

这是一道小学数学题,凭直觉我们都知道是,那么问题是,我们如何进行更mathematical的语言去描述这个东西呢?

我们假设对这个一维欧几里得空间,取其中单位长度向量作为基底,那么整个空间都可以采用来表达,对甲来说,他所处位置为a,即将进行scale a倍后的向量的终点位置,同理乙为,这次再进行,那么对于来说,它的模即为我们通俗来说的距离,它的方向,即为相对基底来说的方向。

那么扩展高维欧几里得空间,对于二维来说,同样假如甲在(3, 4)的位置,乙在(9, -10)的位置,我们同样对这两个向量作减法,得到的向量的模即为我们通俗的欧几里得距离,方向是甲相对乙的方向。

这里我们有个很直观的印象,那就是对向量a和向量b的在欧几里得空间的距离,我们通常认为是a和b的模,取直观的公式写法便是

那么这个距离有什么含义,我们一般理解在高维空间中,向量之间距离越近,则代表它们越相似。

度量学习中,最重要的一部分,便是对于原始向量来说,能否找到或者学习到一个映射f,使得计算出的能够满足一些我们想要的性质。同理对于这个d,我们能否找到一个更符合其性质的度量面和距离度量方法,而不仅仅满足于高维欧几里得距离。

当然上述对度量学习的定义中有一点问题,那便是我们要寻找的是映射f,最终要使得d满足一些关系,这是否说明这一定是带监督的学习呢?是否如果不带监督,那么无法学习到好的f?事实上有的时候是可以不带监督的,比如降维,可以理解成一个线性变换P,对原始的式子变成,这也是一个形式的度量学习。

对于带监督的度量学习,一种很常用的模式便是,对向量对象,我们已知希望让x和y在度量空间里相比x和z更近,这种常常用于聚类或者分类中,而这类是我们更想解决的问题,所以大多数度量学习中,我们focus on带监督的问题。

变换,Transformation

对于一个欧几里得空间中的两个向量,我们计算其距离为

在很多的线性问题中,我们希望增加一个统一的线性变换G,得到学习到的距离,即

那么,什么是线性变换?

实际上,如果线性变换和非线性变换弄不明白,是很难弄懂CNN里面那堆东西的,当然弄不明白也不妨碍你调包(笑)。我继续简单说一下我自己的理解,要理解Linear Transformation和Non-Linear Transformation,我们逃不开对于矩阵的描述。

在初等代数里,我们描述一个简单的映射,可以采用 来描述,这里x存在定义域,y存在一个值域,它的直观几何意义是二维空间里的一条直线,对x来说,它的定义域表示一个由向量线性组合的数轴空间,同理y也是。说到这里,你可能有一些对空间的感觉了,我们对x和y进行推广,从线性数轴到线性空间里,那么原本的映射变成了:

$ \vec y = A \vec x$

这里和x和y均成为了一个向量,这里出现了矩阵A,和初等中的k不同,A变成了一个矩阵,其实非常好理解。

想象一个二维欧几里得空间,里面你定义的矩阵A假设是:

[1  0
 0  1]

假设向量x为,变换后得到的,是不是没有发生变化,那如果我们把A变成:

[2  0
 0  1]

得到的,没错,这就是线性变换,对x而言,它自己观测自己的位置是基于原始空间默认的基底,而对于y来讲,y是基于x的,并不是基于原始空间的基底,我们为其设置一系列基底(矩阵A的所有列向量)后,y在原始空间中观测的位置会发生变化,实际上空间并没有变,只是向量发生了位移或者拉伸。

那么线性变换最重要的性质就是保持了几何上的一系列不变。一条直线线性变换后依然是一条直线,一个矩形线性变换后还是矩形。

回到之前,我们为了进行学习距离,线性问题里一般对x和y采用线性变换后的距离,即,G即为学习的变换参数,根据距离上的监督我们更新G的值,使其得到的距离更满足我们想要的。所以为了方便优化,我们常常令G为平方后的满秩矩阵,解决带半定矩阵约束的凸优化问题。当然这段听不懂没关系,后面的博文我会比较详细的分析和代码分析。

上述均是对于线性变换,对x采用线性变换G后变为Gx,不过是让原本向量x的位置在原本空间里发生了个位移或者拉伸。那么有时候我们非常需要对空间结构进行改变,例如在欧几里得空间上聚类,往往无法非常很好的划分大量的类的空间,举个栗子吧。

对于100个类别,我们的目标是在空间上划分100个区域,去让我们的每个向量根据监督的类别,划分到相应的区域。在这个问题下,我们如何形式化描述这100个类别。有同学采用0-99的数字来标,即映射到数轴上,这样有个严重的问题那就是第0类到第1类,和第0类到第99类产生了非常大的距离差别,我们更期望不同的类与类之间能够满足独立性。这里我们往往对欧几里得空间进行非线性变换,到一个想要的空间,这种问题一般采用的非线性变换为Softmax,这个有时间再说吧。

所以非线性变换一般都是根据一些需求来做一些非常符合需求的空间,比如Sigmoid、tanh在两边梯度接近0,中间地区具有较高的梯度;比如ReLU能够只保留值为正的激活部位,这些非线性变换都对灵活性,拟合性能进行了很大的提高。

那么一般怎么描述非线性变换,很简单,对空间进行扭曲即可,扭曲的方法可以直接对欧几里得空间的坐标轴进行扭曲,例如二维欧几里得空间中,对基底i和j进行一个非线性映射,那么原始的变成了,这里对坐标轴的描述可以采用核函数,这里对学过SVM的同学来说一定不陌生。当然除了核函数描述非线性变换以外,标题既然为深度度量学习,一些得到的目标空间,有时候是深度网络根据目标构建出来的。

后续

上述的三部分均为度量学习的基础,度量学习也主要从两个部分下手,线性度量和非线性度量。非线性度量要更难以想象和理解。对于一些具体的方法和案例,除了线性代数相关的空间想象,还有很多是基于统计学规律,其中有很多方法其实已经被归类进统计机器学习。

所以学习度量学习,不仅是对过往数学知识的回顾和归纳,也是一次很好的实践和应用,后续结合代码一起来解决,我想是一件非常好的事情。

觉得有用的话就follow/star一下我的Github吧!