Label Distribution Learning from Logical Label

LDL is a new machine learning paradigm that constructs a model to predict the label distribution of samples. At first, LDL were achieved through problem transformation that transforms LDL into a set of single label learning problems such as PT-SVM, PT-Bayes Geng (2016), or through algorithm adaptation that adopts the existing machine learning algorithms to LDL, such as AA-kNN and AA-BP Geng (2016). SA-IIS Geng (2016) is the first model that specially designed for LDL, whose objective function is a mixture of maximum entropy loss Berger et al. (1996) and KL-divergence. Based on SA-IIS, SA-BFGS Geng (2016) adopts BFGS to optimize the loss function, which is faster than SA-IIS. Sparsity conditional energy label distribution learning (SCE-LDL) Yang et al. (2016) is a three-layer energy-based model for LDL. In addition, SCE-LDL is improved by incorporating sparsity constraints into the objective function. To reduce feature noise, latent semantics encoding for LDL (LSE-LDL) Xu et al. (2019) converts the original data features into latent semantic features, and removes some irrelevant features by feature selection. LDL forests (LDLFs) Shen et al. (2017) is based on differentiable decision trees and may be combined with representation learning to provide an end-to-end learning framework. LDL by optimum transport (LDLOT) Zhao and Zhou (2018) builds an objective function using the optimal transport distance measurement and label correlations. $\textit{L}^{2}$ Liu et al. (2021a) is the first attempt to combine LE and LDL into a unified model, utilizing the manifold structure of samples and label correlations to learn the prediction model.

The above mentioned LDL methods all assume that in the training set, each sample is annotated with label distribution. However, precisely annotating the LDs for the training samples is extremely costly and time-consuming. On the contrary, many datasets annotated by logical labels are readily available. To this end, LE was proposed, which aims to convert the logical labels of samples in training set to LDs. GLLE Xu et al. (2021) is the first LE algorithm, which assumes that the LDs of two instances are similar to each other if they are similar in the feature space. LEMLL Shao et al. (2018) adopts the local linear embedding technique to evaluate the relationship of samples in the feature spaces. Generalized label enhancement with sample correlations (gLESC) Zheng et al. (2023) tries to obtain the sample correlations from both of the feature and the label spaces. Bidirectional label enhancement (BD-LE) Liu et al. (2021b) takes the reconstruction errors from the label distribution space to the feature space into consideration.

All of these LE methods and LE loss of $\textit{L}^{2}$ Liu et al. (2021a) can be generally formulated as

$$\small\min_{\mathbf{W}}||\mathbf{XW}-\mathbf{Y}||_{F}^{2}+\phi(\mathbf{XW},\mathbf{X}),$$

(1)

where $\mathbf{X}$ and $\mathbf{Y}$ are the feature matrix and logical label matrix, $\|\cdot\|_{F}$ denotes the Frobenius of a matrix, $\mathbf{W}\in\mathbb{R}^{m\times c}$ builds a linear mapping from features to logical labels, and $\phi(\mathbf{XW},\mathbf{X})$ models the geometric structure of samples, which is used to assist LD recovery. After minimizing Eq. (1), those methods usually normalize $\mathbf{XW}$ as the recovered LD.

Although those LE methods have achieved great success, they still suffer from the following limitations. Firstly, the fidelity term that minimizes the distance between the recovered LD (i.e., $\mathbf{XW}$) and the logical label $\mathbf{Y}$ is inappropriate because the logical labels are annotated as the same value, and the linear mapping will not differentiate the description degrees for different labels. Besides, the Frobenius norm is also not the best choice to measure the difference between two distributions. Secondly, Eq. (1) doesn’t consider the physical restriction of the label distribution, i.e., $\forall i,\textbf{0}\leq\boldsymbol{d}_{i}\leq\boldsymbol{y}_{i},\sum_{l}d^{l}_{\boldsymbol{x}_{i}}=1$. Although those methods perform a post-normalization to satisfy those constraints, they may assign positive description degrees to some negative logical labels. Furthermore, to predict the LD for unseen samples, those methods need to first perform LE and then carry out an existing LDL algorithm. The step-wise manner does not consider potential connections between LE and LDL.

Eq. (7) has two variables, we solve it by an alternative and iterative process, i.e., update $\mathbf{W}$ with fixed $\mathbf{D}$, and then update $\mathbf{D}$ with fixed $\mathbf{W}$.

1) Update W When $\mathbf{D}$ is fixed, the optimization problem (7) with respect to $\mathbf{W}$ is formulated as

$\displaystyle\underset{\mathbf{W}}{\min}$

$\displaystyle\rm{KL}(\mathbf{D},\mathbf{P})+\gamma||\mathbf{W}||_{F}^{2}.$

(8)

Expanding the KL-divergence and substituting $P_{ij}$ in Eq. (5) into Eq. (8), we obtain the objective function of $\mathbf{W}$ as

	$\displaystyle T(\mathbf{W})=$	$\displaystyle\sum_{i}{\rm ln}\sum_{j}\exp\left(\sum_{k}X_{ik}W_{kj}\right)+\gamma||\mathbf{W}||_{\rm{F}}^{2}$		(9)
		$\displaystyle-\sum_{i,j}D_{ij}\sum_{k}X_{ik}W_{kj}.$

Eq. (9) is a convex problem, we use gradient descent algorithm to update $\mathbf{W}$, where the gradient is expressed as

	$\displaystyle\dfrac{\partial\ T\left(\mathbf{W}\right)}{\partial\ W_{kj}}=$	$\displaystyle\sum_{i}\dfrac{\exp\left(\sum_{k}X_{ik}W_{kj}\right)X_{ik}}{\sum_{j}\exp\left(\sum_{k}X_{ik}W_{kj}\right)}-\sum_{i}D_{ij}X_{ik}$		(10)
		$\displaystyle+2\gamma W_{kj}.$

2) Update D With fixed $\mathbf{W}$, the optimization problem (7) regarding $\mathbf{D}$ is formulated as

		$\displaystyle\underset{\mathbf{D}}{\min}\ \rm{KL}(\mathbf{D},\mathbf{P})+\alpha\rm{tr}\left(\mathbf{D}\mathbf{G}\mathbf{D}^{T}\right)+\beta||\mathbf{D}||_{F}^{2}$		(11)
		$\displaystyle\text{s.t.}\ \textbf{0}\leq\mathbf{D}\leq\mathbf{Y},\mathbf{D}\mathbf{1}_{c}=\mathbf{1}_{n}.$

Eq. (11) involves multiple constraints and diverse losses, we introduce an auxiliary variable $\mathbf{B}=\mathbf{D}\in\mathbb{R}^{n\times c}$ to simplify it, and the corresponding augmented Lagrange equation becomes

		$\displaystyle\underset{\mathbf{D},\mathbf{B}}{\min}\ \rm{KL}(\mathbf{D},\mathbf{P})+\alpha\rm{tr}\left(\mathbf{D}^{T}\mathbf{G}\mathbf{D}\right)+\beta||\mathbf{D}||_{F}^{2}$		(12)
		$\displaystyle+\left<\mathbf{\Phi},\mathbf{B}-\mathbf{D}\right>+\frac{\tau}{2}||\mathbf{B}-\mathbf{D}||^{2}_{F}$
		$\displaystyle\text{s.t.}\ \textbf{0}\leq\mathbf{B}\leq\mathbf{Y},\mathbf{B}\mathbf{1}_{c}=\mathbf{1}_{n},$

where $\mathbf{\Phi}\in\mathbb{R}^{n\times c}$ is the Lagrange multiplier, and $\tau$ is parameter to introduce the augmented equality constraint. Eq. (12) can be minimized by solving the following sub-problems iteratively.

a) $\mathbf{D}$-subproblem: Removing the irrelated terms regarding $\mathbf{D}$, the $\mathbf{D}$-subproblem of Eq. (12) becomes

	$\displaystyle\underset{\mathbf{D}}{\min}\ U\left(\mathbf{D}\right)$	$\displaystyle=\rm{KL}(\mathbf{D},\mathbf{P})+\alpha\rm{tr}\left(\mathbf{D}^{T}\mathbf{G}\mathbf{D}\right)+\beta||\mathbf{D}||_{F}^{2}$		(13)
		$\displaystyle+\left<\mathbf{\Phi},\mathbf{B}-\mathbf{D}\right>+\frac{\tau}{2}||\mathbf{B}-\mathbf{D}||^{2}_{F},$

then its gradient regarding $\mathbf{D}$ can be expressed as:

$\displaystyle\dfrac{\partial\ U\left(\mathbf{D}\right)}{\partial\ D_{ij}}=\begin{cases}1+\ln{D_{ij}}-\ln{P_{ij}}+\alpha(\mathbf{G}^{T}+\mathbf{G})\mathbf{D}\\ +2\beta\mathbf{D}-\Phi+\tau(\mathbf{D}-\mathbf{B}),&\text{if }D_{ij}\neq 0\\ 0,&\text{if }D_{ij}=0.\\ \end{cases}$

(14)

b) $\mathbf{B}$-subproblem: When $\mathbf{D}$ is fixed, the problem (12) can be written as

		$\displaystyle\underset{\mathbf{B}}{\min}\ \left<\mathbf{\Phi},\mathbf{B}-\mathbf{D}\right>+\frac{\tau}{2}||\mathbf{B}-\mathbf{D}||^{2}_{F}$		(15)
		$\displaystyle\text{s.t.}\ \textbf{0}\leq\mathbf{B}\leq\mathbf{Y},\mathbf{B}\mathbf{1}_{c}=\mathbf{1}_{n}.$

Let $\hat{\boldsymbol{b}}=[\boldsymbol{b}_{1}^{T};\boldsymbol{b}_{2}^{T};\cdots;\boldsymbol{b}_{n}^{T}]\in\mathbb{R}^{nc}=vec(\mathbf{B})$, where $\boldsymbol{b}_{i}$ is the $i$-th row of $\mathbf{B}$ and $vec(\cdot)$ is the vectorization operator. Then, the problem (15) is equivalent to:

		$\displaystyle\underset{\hat{\boldsymbol{b}}}{\min}\ \hat{\boldsymbol{b}}^{T}\mathbf{\Sigma}\hat{\boldsymbol{b}}-\left(2\hat{\boldsymbol{d}}^{T}+\frac{2}{\tau}\hat{\boldsymbol{\phi}}^{T}\right)\hat{\boldsymbol{b}}$		(16)
		$\displaystyle\text{s.t.}\ \mathbf{0}_{nc}\leq\hat{\boldsymbol{b}}\leq\hat{\boldsymbol{y}},\sum_{j=c(i-1)+1}^{ci}\hat{\boldsymbol{b}}_{j}=1\ \left(\forall\ 0\leq i\leq n\right),$

in which $\hat{\boldsymbol{d}}$, $\hat{\boldsymbol{\phi}}$ and $\hat{\boldsymbol{y}}$ represent $vec(\mathbf{D})$, $vec(\mathbf{\Phi})$ and $vec(\mathbf{Y})$, respectively, and $\hat{\boldsymbol{b}}_{j}$ is the $j$-th element of $\hat{\boldsymbol{b}}$. Eq. (16) is a quadratic programming (QP) problem that can be solved by off-the-shelf QP tools.

The detailed solution to update $\mathbf{D}$ in Eq. (11) is summarized in Algorithm 1 and the pseudo code of DLDL is finally presented in Algorithm 2. In this paper, we initialize $\mathbf{W}$ as an identity matrix and initialize $\mathbf{D}$ according to the method in Wang et al. (2023).

In this section, we first provide Rademacher complexity for DLDL, which is a commonly used tool for comprehensive analysis of data-dependent risk bounds.

Definition 1. Let $\mathcal{H}$ be a family of functions mapping from $\mathcal{X}$ to [0,1] and $\mathcal{S}$ be a set of fixed samples with size $n$. Then, the empirical Rademacher complexity of $\mathcal{H}$ with respective to $\mathcal{S}$ is defined as

$$\small\widehat{\mathcal{R}}_{S}(\mathcal{H})=\mathbb{E}_{\boldsymbol{\sigma}}\left[\sup_{h\in\mathcal{H}}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}h\left(x_{i}\right)\right].$$

(17)

Lemma 1. Let $\mathcal{H}$ be a family of functions. For a loss function $\ell$ upper bounded by $\Theta$, then for any $\delta>0$, with probability at least $1-\delta$, for all $h\in\mathcal{H}$ such that

$\displaystyle\mathcal{L}(h)\leq\mathcal{L}_{S}(h)+\widehat{\mathcal{R}}_{S}(\ell\circ\mathcal{H})+3\Theta\sqrt{\frac{\log 2/\delta}{2n}},$

(18)

where $\mathcal{L}(h)$ and $\mathcal{L}_{S}(h)$ are the generalization risk and empirical risk with respective to h.

Theorem 1. The KL-divergence loss function $\ell$ can be written as $\rm{KL}(\mathbf{D},\mathbf{P})$, where $\mathbf{D}\in\mathbb{R}^{n\times c}$ and $\mathbf{P}\in\mathbb{R}^{n\times c}$ are the recovered LD matrix and the prediction matrix respectively, in which $\mathbf{P}$ can be expressed by the prediction weight matrix $\mathbf{W}\in\mathbb{R}^{m\times c}$. Let $\mathcal{H}=\mathbf{D}\times\mathbf{W}$ represent the family of functions for DLDL, with functions $(\mathbf{D},\mathbf{W})\in\mathcal{H}$. Our algorithm further encourages the complexity of $\mathbf{W}$ and the rank of $\mathbf{D}$ are upper bounded by $\epsilon_{1}$ and $\epsilon_{2}$ respectively, i.e., $||\mathbf{W}||_{F}\leq\epsilon_{1}$ and $rank(\mathbf{D})\leq\epsilon_{2}$. According to Definition 1, the Rademacher complexity of DLDL with KL-divergence loss $\ell$ is upper bounded as follows:

$\displaystyle\widehat{\mathcal{R}}_{S}(\ell\circ\mathcal{H})\leq\dfrac{\epsilon_{2}\sqrt{cm\cdot{\exp{(m|X_{max}\epsilon_{1}}|)}/{\exp{(-m|X_{min}\epsilon_{1}|)}}}}{\sqrt{n}},$

(19)

in which $X_{max}$, $X_{min}$ are the maximum and minimum element in the feature matrix $\mathbf{X}$ respectively.

The proof is given in section A of the supplementary file. According to Lemma 1 and Theorem 1, the Rademacher complexity of DLDL is controlled by the number of training samples $n$. Because the numerator is a finite number, when DLDL has infinite training samples ($n$ tends to infinity), its Rademacher complexity tends to zero.

Theorem 2. Denote $\mathbf{D}\in\mathbb{R}^{n\times c}$ and $\mathbf{W}\in\mathbb{R}^{m\times c}$ as the recovered LD matrix and the prediction weight matrix, and the complexity of $\mathbf{W}$ and the rank of $\mathbf{D}$ are upper bounded by $\epsilon_{1}$ and $\epsilon_{2}$ respectively. Then we have the upper bound of $\Theta$:

$\displaystyle\Theta\leq\Sigma_{i=1}^{n}\Sigma_{j=1}^{c}\ln\frac{{(m\exp{(m|X_{max}\epsilon_{1}}|))}}{{\exp{(-m|X_{min}\epsilon_{1}|)}}}.$

(20)

The proof is given in section A of the supplementary file. The right side of Eq.(20) is also a finite number, so when $n$ tends to infinity, the term $3\Theta\sqrt{\frac{\log 2/\delta}{2n}}$ in Lemma 1 tends to zero.

According to Lemma 1, Theorem 1 and Theorem 2, we finally have

$\displaystyle\mathcal{L}(h)\leq\mathcal{L}_{S}(h)+\dfrac{\epsilon}{\sqrt{n}},$

(21)

in which $\epsilon$ is a finite number. From Eq.(21), we can clearly see that when the number of training samples tends to infinity, the generalization risk of $h$ will be upper-bounded by the empirical risk of it.

The above generalized error bound is based on that the recovered label distribution matrix $\mathbf{D}$ is just the ground-truth one, so the last thing to prove is that under some certain conditions, DLDL can recover ground-truth label distribution from logical label.

Theorem 3. If the number of zeros in the ground-truth label distribution matrix $\mathbf{D}_{g}$ is large enough, then the average difference between $\mathbf{D}$ and $\mathbf{D}_{g}$ has an upper bound:

$\displaystyle\frac{\sum_{i,l}|d_{il}-d_{g(il)}|}{nc}\leq\frac{2p_{2}\epsilon}{(1+\epsilon)+\frac{\lambda}{\Sigma k}}+p_{3},$

(22)

in which $p_{2}\in[0,1]$ and $p_{3}$, $\epsilon$, $\frac{\lambda}{\Sigma k}$ are small positive numbers.

The detailed proof of Theorem 3 is given in section B of the supplementary file. The average difference between $\mathbf{D}$ and $\mathbf{D}_{g}$ tends to zero when $p_{3}$, $\epsilon$, $\frac{\lambda}{\Sigma k}$ are small enough, which indicates that DLDL can precisely recover the ground-truth label distribution from logical label under this circumstance. Combining all the lemmas and theorems together, we conclude that directly learning label distribution learning from logical label is theoretically feasible.

In this paper, we split each dataset into three subsets: training set (60%), validation set (20%) and testing set (20%). The training set is used for recovery experiments, that is, we perform LE methods to recover the LDs of training instances; the validation set is used to select the optimal hyper-parameters for each method; the testing set is used for predictive experiments, that is, we use an LDL model learned from the training set with the recovered LDs to predict the LDs of testing instances.

In the recovery experiment, for DLDL, $\alpha$ and $\gamma$ are chosen among {$10^{-3},10^{-2},\cdots,10,10^{2}$}, $\beta$ is selected from {$10^{-3},10^{-2},\cdots,1,10$}, the maximum of iterations $t$ is fixed to 5, the number of neighbors $k$ is set to 20. We compare DLDL with five state-of-the-art LE methods and a unified method, each configured with suggested configurations in respective literature: 1) FLE Wang et al. (2023): $\alpha$, $\beta$, $\lambda$, $\gamma$ are chosen among {$10^{-3},10^{-2},\cdots,10,10^{2}$}; 2) GLLE Xu et al. (2021): $\lambda$ is chosen among {$10^{-3},10^{-2},\cdots,1$}; 3): LEMLL Shao et al. (2018): the number of neighbors $K$ is set to 10 and $\epsilon$ is set to 0.2; 4) LESC Zheng et al. (2023): $\beta$ is set to 0.001 and $\gamma$ is set to 1; 5) FCM Gayar et al. (2006): the number of clustering centers is set to 10 times of the number of labels. 6) $\textit{L}^{2}$ Liu et al. (2021a): $\alpha$, $\gamma$, $\lambda$ are chosen among {$10^{-5},10^{-3},\cdots,10^{3},10^{5}$}, $k$ is set to 20 and $\beta$, $\mu$ keep the default value.

In the predictive experiment, we apply SA-BFGS Geng (2016) algorithm to predict the LDs of testing instances based on the recovered LDs by performing the five baseline LE methods. Note that DLDL and $\textit{L}^{2}$ can directly predict the LDs without an external LDL model.

As suggested in Geng (2016), we adopt three distance metrics (i.e., Chebyshev, Clark and One-error) and one similarity metric (i.e., Intersection) to evaluate the recovery and the predictive performances. The formulas of these evaluation metrics are summarized in section C of the supplementary file.

In this subsection, we present the visualization of two typical recovery results of all the models on two different datasets in Fig. 2. From it we can observe that DLDL has a better performance on the recovery of non-positive labels, and the recovery results of it are also more close to the ground-truth label distributions than the other comparison algorithms. For example, on the Twitter dataset, the logical values corresponding to the label 1, 4, 5, 6, 8 are all 0, indicating that these labels cannot describe this sample. However, the six comparison methods still assign positive description degrees for these invalid labels. Differently, DLDL avoids this problem, and produces differentiated description degrees fairly close to the ground-truth values.