Learning Expected Hitting Time Distance By Markov Chain

With the rapid development of mobile Internet and the widespread popularity of intelligent devices,various types of images and text data are expanding in an unprecedented speed.Thus,many big-data based machine learning application are booming.In the theme of distance metric technology commonly used in machine learning algorithm,this paper has done the following work:1.The target of traditional Mahalanobis metric is to learn a symmetric semi-definite matrix and to calculate the distance after projecting the feature into the new feature space.It implicitly measures the second-order relation between the features,but when high-order feature relationships between different features exist,Mahalanobis Distance metric's effect is not ideal.Based on the concept of expected hitting time of Markov chain,this paper comes up with a novel distance metric method——Expected Hitting Time Distance.It implicitly makes use of the time-series relationships which is a kind of high-order interactions between state transitions2.In the expected hitting time distance metric,a suitable transition probability matrix T is critical to the performance of algorithm.In order to learn the probability matrix T from the training data using the supervised information,this paper proposes an optimization algorithm based on gradient descent,LED.Then,in order to solve the shortcomings of LED algorithm with high complexity and low training efficiency,an efficiency algorithm LED-SGD is proposed in incremental learning configuration.It uses the property of low rank update in the learning process,which greatly reduces the complexity of the algorithm and improves the training efficiency.3.This paper compares the expected hitting time distance metric algorithm with five state of art Mahalanobis distance metric algorithms on three image data sets and two text data sets.It is proved that the expected hitting time distance metric algorithm is superior to traditional Mahalanobis distance metric algorithms.At the same time,comprehensible experiments are carried out on the image and text data sets respectively.It is proved that the probability matrix T learned by the LED algorithm captures the semantic information contained in the data.