基于马尔可夫链的期望到达时间距离学习

发布时间：2019-02-11 12:52

【摘要】：随着移动互联网的高速发展和智能设备的广泛普及,各类图像和文本数据在以前所未有的速度迅速膨胀,基于大数据的各种机器学习应用正在蓬勃发展。围绕机器学习算法中常用的距离度量技术,本文主要做了以下几个工作。第一,传统的马氏距离度量的学习目标是学习一个对称半正定的矩阵,将数据特征投影到新的特征空间之后计算距离,它隐式度量了特征之间的二阶关系,但当数据特征之间存在高阶相关性时,马氏距离度量的效果就不甚理想。本文基于马尔可夫链中期望到达时间的概念,提出了一种新的距离度量方法——期望到达时间距离。它利用了马尔可夫链中状态转移的时间序列关系,隐式度量了特征之间的高阶相关性。第二,在期望到达时间距离度量中,一个合适的概率转移矩阵T对算法性能的影响至关重要。为了从训练数据中利用类别的判别信息自动学习到T,本文提出了基于梯度下降的优化算法LED。之后,为了解决优化算法复杂度过高、训练效率低的缺点,提出了在增量学习的设定下的一种效率优化算法LED-SGD。它利用了学习过程中矩阵低秩更新的特性,极大的降低了算法的复杂度,提高了训练效率。第三,本文在三个图像数据集和两个文本数据集上将期望到达时间度量算法与5个前沿的马氏距离度量算法进行了对比实验,证明了期望到达时间度量算法相对于传统马氏距离度量算法的优越性。同时,在图像与文本数据集上分别进行了可理解性实验,证明了通过LED算法学到的概率转移矩阵T,在一定程度上捕捉到了数据中蕴含的语义信息。
[Abstract]:With the rapid development of mobile Internet and the widespread popularity of intelligent devices, all kinds of images and text data are expanding rapidly at an unprecedented speed, and various machine learning applications based on big data are booming. Focusing on the commonly used distance measurement techniques in machine learning algorithms, this paper mainly does the following work. First, the learning goal of the traditional Markov distance metric is to learn a symmetric positive semidefinite matrix and calculate the distance after projecting the data features into a new feature space, which implicitly measures the second-order relationship between the features. However, when there is high order correlation between data features, the effect of Markov distance measurement is not satisfactory. Based on the concept of expected arrival time in Markov chain, a new distance measurement method is proposed in this paper, which is expected arrival time distance. It makes use of the time series relation of state transition in Markov chain and measures the high order correlation between features implicitly. Secondly, a suitable probability transfer matrix T plays an important role in the measurement of the expected time of arrival (DOA). In order to learn from training data automatically by using classification discriminant information, an optimization algorithm based on gradient descent, LED., is proposed in this paper. Then, in order to solve the shortcomings of high complexity and low training efficiency of the optimization algorithm, an efficiency optimization algorithm, LED-SGD., is proposed under the setting of incremental learning. It takes advantage of the low rank update of matrix in the learning process, greatly reduces the complexity of the algorithm and improves the training efficiency. Thirdly, in this paper, three image data sets and two text data sets are compared with the Mahalanobis distance measurement algorithm and the expected arrival time measurement algorithm. It is proved that the expected arrival time measurement algorithm is superior to the traditional Markov distance measurement algorithm. At the same time, the understandability experiments on the image and text data sets show that the probability transfer matrix T, which is learned by the LED algorithm, captures the semantic information contained in the data to a certain extent.
【学位授予单位】：南京大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP391.41;TP181

【相似文献】