Learning Distance Functions using Equivalence Relations
Learning Distance Functions using Equivalence Relations
复制标题
DOI：
--
复制
发表时间：
2003-08
期刊：
影响因子：
--
通讯作者：
Aharon Bar-Hillel;T. Hertz;N. Shental;D. Weinshall
中科院分区：
文献类型：
--
作者：
Aharon Bar-Hillel;T. Hertz;N. Shental;D. Weinshall
我们使用“相似”点组形式的辅助信息来解决学习距离度量的问题。我们建议使用 RCA 算法，这是一种简单而有效的算法，用于学习完整排序的 Mahalanobis 度量（Shental 等人，2002）。我们首先证明 RCA 获得了一个有趣的优化问题的解决方案，该问题建立在信息论的基础上。如果允许马哈拉诺比斯矩阵是奇异的，我们证明费舍尔线性判别式和 RCA 是相同标准下的最优降维算法。然后，我们展示了这个优化问题如何与另一个最近的度量学习算法（Xing et al., 2002）优化的标准相关，该算法使用相同类型的辅助信息。我们凭经验证明，与替代算法类似，使用 RCA 算法学习距离度量可以显着提高聚类性能。由于 RCA 算法比替代算法更高效且更具成本效益，因为它仅使用数据的封闭形式表达式，因此它似乎是学习全秩马哈拉诺比斯距离的更好选择。
We address the problem of learning distance metrics using side-information in the form of groups of "similar" points. We propose to use the RCA algorithm, which is a simple and efficient algorithm for learning a full ranked Mahalanobis metric (Shental et al., 2002). We first show that RCA obtains the solution to an interesting optimization problem, founded on an information theoretic basis. If the Mahalanobis matrix is allowed to be singular, we show that Fisher's linear discriminant followed by RCA is the optimal dimensionality reduction algorithm under the same criterion. We then show how this optimization problem is related to the criterion optimized by another recent algorithm for metric learning (Xing et al., 2002), which uses the same kind of side information. We empirically demonstrate that learning a distance metric using the RCA algorithm significantly improves clustering performance, similarly to the alternative algorithm. Since the RCA algorithm is much more efficient and cost effective than the alternative, as it only uses closed form expressions of the data, it seems like a preferable choice for the learning of full rank Mahalanobis distances.