Cosine Similarity Measure According to a Convex Cost Function

Osman Günay, Cem Emre Akbas, A. Enis ÇetinarXiv 2014 · arXiv · OpenReview

Abstract

In this paper, we describe a new vector similarity measure associated with a convex cost function. Given two vectors, we determine the surface normals of the convex function at the vectors. The angle between the two surface normals is the similarity measure. Convex cost function can be the negative entropy function, total variation (TV) function and filtered variation function. The convex cost function need not be differentiable everywhere. In general, we need to compute the gradient of the cost function to compute the surface normals. If the gradient does not exist at a given vector, it is possible to use the subgradients and the normal producing the smallest angle between the two vectors is used to compute the similarity measure.

Introduction

In machine learning and signal processing, the inner product is the fundamental tool for measuring similarity. Standard cosine similarity measures the angle between two vectors, effectively treating the underlying space as flat and uniform. However, data often possesses intrinsic structures that a "flat" measure ignores. For example, in image processing, the "Total Variation" (smoothness) of a signal might be more informative than its raw values.

While Bregman divergences (like KL-divergence) allow for the incorporation of convex cost functions into distance metrics, they are not angular metrics and do not always behave intuitively in classification tasks like Nearest Neighbor. This paper introduces a novel vector similarity measure called the Bregman angle. By "lifting" vectors into a higher-dimensional space defined by the geometry of a convex cost function (e.g., entropy or Total Variation), this method can distinguish between data points that traditional cosine or Euclidean measures might find identical.

Methodology

The core concept involves taking two vectors, $\mathbf{x}_1$ and $\mathbf{x}_2$, and a convex cost function $f(\mathbf{x})$. Instead of comparing the vectors directly, we analyze the surface normals of the function $f$ at those points.

Lifting to $N+1$ Dimensions

For a vector in $N$-dimensional space, the surface normal is defined in $(N+1)$ dimensions. The normal vector $\mathbf{e}$ is constructed using the gradient of the function: $\mathbf{e} = [\nabla f(\mathbf{x}), -1]$. The similarity $C(\mathbf{x}_1, \mathbf{x}_2)$ is then defined as the cosine of the angle between these two surface normals.

Geometric interpretation of the Bregman angle: surface normals $e_1, e_2$ of a convex function $f(x)$ at points $x_1, x_2$ define the similarity angle $\theta$.

Handling Non-Differentiability

If the cost function is not differentiable (e.g., Total Variation), the framework utilizes subgradients. The subgradient that produces the smallest angle between the two vectors is selected to ensure a robust similarity measure. Additionally, a "tangent-based" version is proposed, which applies standard cosine similarity specifically to the gradient vectors of the cost function.

Experimental Setup

The proposed measure was evaluated on two distinct datasets:

  1. UCI Gesture Phase Segmentation Dataset: Contains 1,747 instances of hand gestures with 18 attributes. A two-class subset (202 instances) was used for classification testing.
  2. KTH-TIPS Database: A texture recognition dataset with 800 images across 10 classes. Features were extracted using Dual-Tree Complex Wavelet Transforms (DT-CWT) and HSV histograms.

Results and Discussion

The researchers employed a 1-Nearest Neighbor (1-NN) classifier to compare the Bregman angle against standard metrics.

Performance Comparison

  • Gesture Recognition: The Bregman Angle with Total Variation (TV) achieved 99.0% accuracy, outperforming standard Cosine Similarity (98.0%) and the Entropy-based Bregman Angle (97.5%).
  • Texture Classification: The Bregman Angle using an $\ell_2$-norm cost function matched standard Cosine Similarity at 95.0%.

Geometric Insights

A key advantage of the Bregman angle is its ability to break linear inseparability. Traditional cosine similarity cannot distinguish between points that lie on the same line originating from the origin. The Bregman angle overcomes this because the surface normals of a convex function change even if the vectors are collinear.

Comparison of similarity measures for collinear samples. While standard cosine similarity remains constant, the proposed measures vary, allowing for discrimination.

By choosing different convex functions $f(\mathbf{x})$, the space is effectively "warped" to highlight specific features. For instance, using Negative Entropy makes the measure sensitive to the distribution of values within the vector. The success of TV in gesture data suggests that transitions between elements are more informative than absolute values in that domain.

Conclusion

The Bregman angle provides a flexible framework for similarity measurement by incorporating the geometry of convex cost functions. While it shows superior performance in specific domains like gesture recognition, challenges remain. Calculating gradients or subgradients increases computational complexity compared to simple dot products. Furthermore, selecting the optimal convex function for a given dataset currently lacks a formal framework, and the measure can be sensitive to input scaling relative to the function's curvature. Future work will focus on automating function selection and optimizing computational efficiency for high-dimensional data.

Summary updated

Abstract

In this paper, we describe a new vector similarity measure associated with a convex cost function. Given two vectors, we determine the surface normals of the convex function at the vectors. The angle between the two surface normals is the similarity measure. Convex cost function can be the negative entropy function, total variation (TV) function and filtered variation function. The convex cost function need not be differentiable everywhere. In general, we need to compute the gradient of the cost function to compute the surface normals. If the gradient does not exist at a given vector, it is possible to use the subgradients and the normal producing the smallest angle between the two vectors is used to compute the similarity measure.
BibTeX
@misc{gunay2014cosine,
  author = {Osman Günay and Cem Emre Akbas and A. Enis Çetin},
  title = {{Cosine Similarity Measure According to a Convex Cost Function}},
  year = {2014},
  eprint = {1410.6093},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1410.6093},
}
Figure