以成本導向標籤嵌入法解決多標籤分類問題

Abstract

在解決多標籤分類(Multi-label Classification)的方法當中，標籤嵌入法(Label Embedding)是一系列常見且重要的演算法。標籤嵌入法同時考量全部標籤之間的關係，並得到更好的分類表現。不同的多標籤分類應用通常會使用不同的成本計算方式來衡量演算法的分類表現，但是目前的標籤嵌入演算法都只考慮少數幾種、甚至只有一種成本計算方式，因此這些演算法在未考慮到的成本計算方式上的表現就會不如預期。為了解決這個問題，本論文提出了成本導向標籤嵌入演算法(Cost-sensitive Label Embedding with Multidimensional Scaling)。此演算法利用多維標度法(Multidimensional Scaling)找出標籤的嵌入向量(Embedded Vectos)，再將成本計算方式的資訊嵌入到嵌入向量彼此之間的距離，最終的預測結果會透過所預測的嵌入向量以及我們設計的最近距離解碼函數(Nearest-neighbor Decoding Function)得出。由於嵌入向量隱含了成本計算方式的資訊，所以預測結果是成本導向的，在不同的成本計算方式上都能夠得到好的分類表現。雖然嵌入向量彼此之間的距離是對稱的，不過所提出的演算法不但能夠處理對稱式成本計算方式，也能處理非對稱式成本計算方式。除此之外，我們為所提出的演算法的提供了理論保證，最後再用大量的實驗結果來驗證所提出的演算法的確能夠在不同的成本計算方式上表現得比現有的標籤嵌入法以及成本導向演算法還要好。

Label embedding (LE) is an important family of multi-label classification algorithms that digest the label information jointly for better performance. Different real-world applications evaluate performance by different cost functions of interest. Current LE algorithms often aim to optimize one specific cost function, but they can suffer from bad performance with respect to other cost functions. In this paper, we resolve the performance issue by proposing a novel cost-sensitive LE algorithm that takes the cost function of interest into account. The proposed algorithm, cost-sensitive label embedding with multidimensional scaling (CLEMS), approximates the cost information with the distances of the embedded vectors using the classic multidimensional scaling approach for manifold learning. CLEMS is able to deal with both symmetric and asymmetric cost functions, and effectively makes cost-sensitive decisions by nearest-neighbor decoding within the embedded vectors. Theoretical results justify that CLEMS achieves the cost-sensitivity and extensive experimental results demonstrate that CLEMS is significantly better than a wide spectrum of existing LE algorithms and state-of-the-art cost-sensitive algorithms across different cost functions.