A feature-free and parameter-light multi-task clustering framework

Abstract

The two last decades have witnessed extensive research on multi-task learning algorithms in diverse domains such as bioinformatics, text mining, natural language processing as well as image and video content analysis. However, all existing multi-task learning methods require either domain-specific knowledge to extract features or a careful setting of many input parameters. There are many disadvantages associated with prior knowledge requirements for feature extraction or parameter-laden approaches. One of the most obvious problems is that we may find a wrong or non-existent pattern because of poorly extracted features or incorrectly set parameters. In this work, we propose a feature-free and parameter-light multi-task clustering framework to overcome these disadvantages. Our proposal is motivated by the recent successes of Kolmogorov-based methods on various applications. However, such methods are only defined for single-task problems because they lack a mechanism to share knowledge between different tasks. To address this problem, we create a novel dictionary-based compression dissimilarity measure that allows us to share knowledge across different tasks effectively. Experimental results with extensive comparisons demonstrate the generality and the effectiveness of our proposal.

Appendix

1.1 An example of parsing a string by LZW algorithm

Given a string x = ‘abcabcabc,’ LZW parsing is given in Table 6. In the initial step, the dictionary $\Omega$ is assigned to the empty set, string $w$ is also assigned to the empty string, and $Comp(x) = 0$. In the first iteration, the first character ‘a’ is read and stored in the variable C = ‘a’. In this iteration, ‘$wC$’ = ‘$a$’ is not in the dictionary; therefore, ‘’ is added to the dictionary $\Omega$ =  {‘a’} , $Comp(x) = 1 ,\, w$’ is still the empty string. In the second iteration, C = ‘$b$’ ,  ‘$wC$’ = ‘$b$’ is also not in the dictionary, so ‘$b$’ is added to the dictionary $\Omega$ = {‘$a$’, ‘$b$’}. This process continues until the last character of ‘$x$’, and we obtain $\Omega (\mathbf{x}) = \{\mathbf{a, b, c, ab, ca, bc}\}$ and $Comp({\mathbf{x}}) = 6$ as shown in Table 6.

Table 6 Parsing string x = ‘abcabcabc’ by LZW algorithm

1.2 Summary of related theorems

In this Section, we summarize theorems of other works that are used in this paper.

• 1. Definition 3.2 of [16]: Given a compressor $Comp$ and two strings $\mathbf{x}$ and $\mathbf{y}$, the conditional compressed information, $Comp(\mathbf{y}|\mathbf{x})$, is defined as follows:

  $$\begin{aligned} {Comp(\mathbf{y}|\mathbf{x})} = {Comp(\mathbf{xy})} - {Comp(\mathbf{x})} \end{aligned}$$

  (9)

  $Comp(\mathbf{y}|\mathbf{x})$ is considered as the number of bits of information in $\mathbf{y}$, relative to $\mathbf{x}$.

• 2. Theorem 3.3 of [55]:

  $$\begin{aligned} {K(\mathbf{xy}} \le {K(\mathbf{x})} + {K(\mathbf{y})} + \mathcal O (1) \end{aligned}$$

  (10)

  where $K$ is the Kolmogorov complexity, and $K(\mathbf{x}) ,\, K(\mathbf{y})$, and $K(\mathbf{xy})$ are the lengths of the shortest programs that output $\mathbf{x} ,\, \mathbf{y}$, and $\mathbf{x}$ concatenated by $\mathbf{y}$. Proof. Refer to Theorem 3.3, page 43 of [55].

• 3. Remark II.1 of [34]: Given a string $\mathbf{x} ,\, K(\mathbf{x})$ is the length of the shortest binary program $x^*$ to compute $\mathbf{x}$ on an appropriate universal computer, such as the universal Turing machine. We require that $\mathbf{x}$ can be decompressed from its compressed version $x^*$ by a general decompressor program, but we do not require that $\mathbf{x}$ can be compressed to $x$ by a general compressor program. In fact, it is easy to prove that there does not exist such a compressor program, since $K(\mathbf{x})$ is a non-computable function. Thus, $K(\mathbf{x})$ serves as the ultimate lower bound of what a real-world compressor can possibly achieve.

• 4. Theorem VI.2 of [34]: The normalized information distance ${d_k(\mathbf{x}, \mathbf{y})}$ is a lower bound of every normalized compression distance $NCD(\mathbf{x}, \mathbf{y})$ by ${d_k(\mathbf{x}, \mathbf{y})} \le {NCD(\mathbf{x}, \mathbf{y})} + O(1/K)$ where $K = min\{{K(\mathbf{x})}, K(\mathbf{y})\}$. Proof. Refer to Theorem VI.2 in page 6 of [34]. Note that in [34], the authors used $d(x, y)$ and $f(x, y)$ to refer to $d_k(x, y)$ and $NCD(x, y)$, respectively.

 

1.3 Pseudocode of the k-medoids Algorithm

The pseudocode of the k-medoids algorithm is given in Algorithm 3. It includes three steps. Firstly, each data instance is assigned to the closest medoid based on the dissimilarity value given in the distance matrix $D$ (Lines 4–5). Then, the algorithm replaces the current medoid in each cluster by the instance which minimizes the total distance to other instances in the considering cluster (Lines 9–11). This process is repeated until there is no change in the medoids.