最適輸送理論(OT: Optimal Transport)
距離空間†
距離空間とは，距離の構造にあたる「距離関数」を備えた集合のこと。
距離関数(distance function)、距離計量(distance metric)とは†
集合X上の函数 d: X × X → R （ここで、R は実数全体の成す集合）が距離函数であるとは、x, y, z を X の任意の元として、以下の条件をすべて満たす
- d(x, y) ≥ 0 （非負性 non-negativity）
- d(x, y) = 0 if and only if x = y （同一律 reflexivity）
- d(x, y) = d(y, x) （対称律 symmetry）
- d(x, z) ≤ d(x, y) + d(y, z) （劣加法性あるいは三角不等式 triangle inequality）
距離計量†
- Minkowski (Lp) distance
- Manhattan distance/City block distabce(L1)
- Euclidian distance (L2)
- Chessboard distance/Chebyshev distance (Loo, infinity})
- Jaccard distance
- Hausdorff distance
- earth mover's distance
- Mahalanobis metric, d_M(x,y)=sqrt{(x-y)^TM(x-y)}
- Fréchet distance:dis bet. curves, trajectories, prob. distributions
非計量距離(類似性・非類似性)†
- fractional Lp distances
- cosine measure
- Jeffrey-divergence
- k-median distance
- partial Hausdorff distance (pHD)
- (dynamic) time warping distance (DTW)
- longest common subsequence(LCSS)
- Kullback-Leibler divergence
- Bregman divergence/distance
- user-defined similarity measure
学習・動的距離†
- dynamic preference
- multi-metric (dynamic combinations of metrics),
Distance Metric Learning†
Metric learning is the task of learning a distance function over objects. Distance Metric learning is to learn a distance metric for the input space of data from a given collection of pair of similar/dissimilar points that preserves the distance relation among the training data.
Kernel Methods†
In pattern analysis, the general task is to find and study general types of relations (for example clusters, rankings, principal components, correlations, classifications) in datasets. Kernel methods require only a user-specified kernel, i.e., a similarity function over pairs of data points in raw representation, instead explicitly transforming raw representation into feature vector representations.
参考文献†
- T. Skopal, Unified Framework for Fast Exact and Approximate Search in Dissimilarity Spaces, ACM TODS 2007 pp.1-45
- 佐藤 竜馬，最適輸送入門
- 太田 慎一，最適輸送理論とその周辺
![[PukiWiki]](/ksuwiki/assets/skin/ksu/ksuwiki01.jpg "[PukiWiki]")