Quantum Annealing for Semi-Supervised Learning
Yu-Lin Zheng Wen Zhang Cheng Zhou Wei Geng
quant-ph

APS/123-QED





 wei.geng@huawei.com


 Hisilicon research, Huawei Technologies Co., Ltd., Shenzhen, China





Recent advances in quantum technology have led to the development and the manufacturing of programmable quantum annealers that promise to solve certain combinatorial optimization problems faster than their classical counterparts.
Semi-supervised learning is a machine learning technique that makes use of both labeled and unlabeled data for training, which enables a good classifier with only a small amount of labeled data. 
In this paper, we propose and theoretically analyze a graph-based semi-supervised learning method with the aid of the quantum annealing technique, which efficiently utilize the quantum resources while maintaining a good accuracy.
We illustrate two classification examples, suggesting the feasibility of this method even with a small portion (20%) of labeled data is involved.

03.67.−a, 03.67.Lx



Quantum Annealing for Semi-Supervised Learning
    Wei Geng
    December 30, 2023
==============================================





§ INTRODUCTION

The recent developments of machine learning, enable computers to infer patterns that were previously untenable from a large data set  <cit.>. Quantum computing, on the other hand, has been proved to outperform classical computers in some specific applications  <cit.>. To extend both advantages, increasing interests have been made to explore the merging of these two disciplines <cit.>. For instance, the quantum version of linear models of machine learning, such as support vector machines (SVM)  <cit.>, principal component analysis (PCA)  <cit.>, can be potentially more efficient than their classical versions. Quantum generative models were also proposed with exponential speedups than the traditional models  <cit.>. However, most of those algorithms require a large-scale fault-tolerant quantum computer that is beyond the ability of current hardware techniques.
Meanwhile, quantum annealer, as one of the noisy-intermediate scale quantum (NISQ) devices  <cit.>, has been proved useful in many applications such as optimization  <cit.>, simulation  <cit.> and machine learning  <cit.>. 
In this work, we propose a method to tackle semi-supervised classification tasks on a quantum annealer.
An encoding scheme and a similarity-calculation method that map the graph representation of the problem to the Hamiltonian of a quantum annealing (QA) system are suggested, which avoid the implementation of multi-qubit interaction. We show in two examples that good classification accuracies can be achieved using only a small amount of labeled data.




 §.§ Semi-Supervised Learning


Semi-supervised learning (SSL) method usually refers to classification tasks where trainings are usually carried out with both labeled and unlabeled data when only a small amount of labeled data is available <cit.>. A well-known model of this kind is the graph-based method, by which all the data are represented by vertices of a graph, and similarities between data are represented by the edges of the graph  <cit.>.
Specifically, we are given a labeled data set 𝒟_l ={(𝐝_1, lab_1), (𝐝_2, lab_2), …, (𝐝_l, lab_l)} and an unlabeled data set 𝒟_u = {𝐝_l+1, 𝐝_l+2, …, 𝐝_l+u}, where lab_i is the label of data 𝐝_i, l and u are the numbers of labeled and unlabeled data, respectively.
In most cases, the data set has fewer degrees of freedom than its original dimension, which allows us to map the data 𝐝_i from its original space to 𝐱_i in a certain manifold after some dimension-reduction processes, such as locally linear embedding  <cit.> and principal component analysis  <cit.>. 
Therefore, a graph G=(V, S) can be built based on 𝒟 = 𝒟_l∪𝒟_u, in which the set of vertices V = {𝐱_1, …, 𝐱_l+1, …, 𝐱_l+u} represents all the data vectors in the manifold. The adjacency matrix S = [S_ij] of this graph represents the similarities between the i-th data and the j-th data for 1≤ i,j ≤ l+u. Here we assume a symmetric similarity, i.e., S_ij=S_ji for i ≠ j and S_ii=0.
During the training process, label information tends to propagate along edges with greater similarities. When the training process ends, labels of the unlabelled vertices are decided according to their probability distributions.

In practice, we need to deal with integer programming and combinatorial optimization when solving most SSL problems, which are usually non-convex or non-smooth  <cit.>. In order to obtain a global optimal solution, the solving process usually involves high time and space complexities. With the potential speed-up in solving the optimization problems, the quantum annealing method is a natural consideration to be applied in SSL. 




 §.§ Quantum Annealing

In a QA process <cit.>, the system is firstly prepared in a ground state of an initial Hamiltonian. A target Hamiltonian is gradually applied to the system as it evolves following the time-dependent Schrödinger equation. 
If the application of the target Hamiltonian is slow enough, the system will adiabatically stay at the ground state of the instantaneous Hamiltonian and finally reach to the ground state of the target Hamiltonian, which encodes the solution of the problem.
Demonstration of QA have been vastly reported using systems based on superconducting circuits  <cit.>. 

When an Ising model is used in QA system, the Hamiltonian of the annealing process is usually defined as below:

    H=s(t)H_ini+(1-s(t))H_tar


    H_tar=-∑_i=1^Nh_i σ_i-∑_i,j=1, i≠ j ^NJ_ijσ_i σ_j,

in which H_ini and H_tar are the initial and target Hamiltonian of the system, respectively, h_i is the bias applied on the i-th qubit, σ_i is a Pauli Z operator on the i-th qubit and J_ij is the coupling parameter between the i-th qubit and the j-th qubit. 
s(t), as a function of time t, controls the annealing speed by monotonically decreasing from 1 to 0.



§ METHOD

 



 §.§ Label Encoding


The graph G can be mapped onto a QA system by associating each vertex i with a group of α qubits {q_i^(1),q_i^(2),…,q_i^(α)} that encodes the label, and by associating the edge S_ij between vertices i and j with the coupling strengths J_ij between qubit groups. The binary nature of qubits leads to an intuitive choice of a binary encoding for labels, which allows the group to encode up to K=2^α labels. Such an encoding scheme usually calls for global constraints on the group of qubit in order to guarantee that a proper code is simultaneously attributed to the whole group at the end of the annealing process. However, this can only be achieved via multi-qubit interactions, a mechanism that current QA hardware can hardly address. One-hot encoding can overcome this requirement by reducing the interaction to a quadratic order at a cost of exponentially increased qubit resources with regard to the label number compared with the binary encoding <cit.>.

Here we propose another encoding method that essentially uses binary codes while avoiding the the hardware complexity introduced by multi-qubit interactions. We suggest that the a-th bit in the binary label code of all unlabeled data is determined independently by a QA process, which consists of the qubits {q_1^(a),q_2^(a),…,q_l+u^(a)}. In this case, the global information shared within one group of qubit should be maintained by the consistency of similarity between arbitrary two data and the Hamming distance of their labels. Specifically, we first calculate the barycenters of each label on the manifold by 𝐗^(k)=1/n_k∑_i𝐱_i^(k) according to the labeled data set 𝒟_l, where n_k denotes the number of data with the k-th label. A shortest path that visits all the barycenters is then searched in the manifold, leading to a sequence of all the barycenters: {𝐗^(k)|k∈𝒦}, where 𝒦 is the set of all labels. According to this sequence, labels are assigned with an ordered Gray code, which ensures that only one bit changes in the codes of two adjacent labels. Thus, the correlation of distances between arbitrary data and their label codes' Hamming distance is optimized.
Though the complexity of finding the shortest path in the manifold is equivalent to the well-known travelling salesman problem, in most cases, the number of label is far fewer than that of data in a given data set. It has also been shown that this kind of task could also be potentially accelerated by a QA device  <cit.>. 

There are certainly cases that 2^α-1<K<2^α. To avoid that the redundant codes are wrongly attributed to an unlabeled data, we can use up to two codes to encode one label while assuring the two codes are next to each other in the ordered Gray code. 
For example, if a group of α = 3 qubit is used to encode only K = 5 labels, the label codes can be attributed as follows: {000, 001}_label 1, {011, 010}_label 2, {110, 111}_label 3, {101}_label 4, {100}_label 5.



 §.§ Structure of the system

Based on the aforementioned encoding method, the whole training of the SSL classification task can be divided into α independent layers, of which the a-th corresponds to an annealing process of qubits {q_1^(a),q_2^(a),…,q_l+u^(a)}. Because of the limited connectivity that a QA hardware can currently achieve, we only require that each qubit is logically coupled with at least ξ qubit in each layer. ξ may depends on the certain distribution of a data set and should be a small number compared with the total amount of data.

This system can naturally lead to a time-division multiplexing manner, such that each part of the training process can be operated separately in time using just one smaller system. This is especially advantageous when the number of qubit in a QA hardware is limited compared with the problem size. In fact, such a time-division multiplexing manner is equivalent to a dichotomy method, which is, by determining each bit of the binary label code, the total unlabeled data are sorted into two groups after each annealing process. An example of such a system is delineated in Fig. <ref>. 

Moreover, we specify two configurations for labeled and unlabeled data separately:
Labeled data: To assure that the qubits of labeled data reveal correct labels after being measured, we should apply a bias h_i that is large enough to make the probability of their transition to wrong states close to 0 at the end of the QA process.
Unlabeled data: No bias is applied to the corresponding qubits.

Hence, Eq. <ref> can be re-written as:

    H_tar=-∑_a=1^α(∑_i=1^lh_i^(a)σ_i^(a) + ∑_i,j=1^l+uJ_ijσ_i^(a)σ_j^(a)).

Here σ_i^(a) is the Pauli Z operator on the i-th qubit at the a-th layer in the system. 
After the annealing process, we can obtain the labels by measuring the corresponding qubits with its Pauli Z operator. 
The label we obtained is written as y_i=string y_i^(1)… y_i^(α). In order to describe labels in quantum language, we use y_i^(a)∈{-1, +1} rather than {0, 1} which depends on the state after being measured denoted as |y_i^(a)⟩, in which |y_i^(a)⟩⟨ y_i^(a)| = 1/2(1+y_i^(a)σ_i^(a)).





 §.§ Similarity and coupling parameters

In the QA model of Eq. <ref>, when J_ij>0, the stronger the two qubits are coupled, the more likely they are to have the same orientations. Therefore, it is intuitive to map the similarity between two data to the coupling coefficient between two qubits in a QA system.
According to the vectors of two data in the manifold, the similarity between the two data can be calculated as below:

 
S_ij={
f(𝐱_i-𝐱_j _p)    ,    if   i≠j

0    ,    otherwise
.,

where Θ_p is the p-norm of vector Θ and f(Θ) is a monotonically decreasing function of Θ. To better describe the similarities of a particular data set, f(Θ) may contain parameters that can be learned as will be discussed in the next section.
For example, we can use Euclidean distance-based similarity:

S_ij = {
β_1/β_2+𝐱_i-𝐱_j_2    ,    if   i≠j

0    ,    otherwise
.,

where β_1 and β_2 are parameters to be learned. 

For some data that have normal distributions in the manifold, we can also use the Gaussian-like function to describe the similarity between 𝐱_i and 𝐱_j as: 


 
S_ij={
∑_k=1^K p(k)/√((2π)^d|B_k|)e^-1/2(𝐱_i-𝐱_j)^T B_k^-1(𝐱_i-𝐱_j)    ,     if   i≠j

0    ,     otherwise
.,

in which B_k is assumed to be a symmetric matrix whose elements are to be learned from the labeled data set 𝒟_l, d is the dimension of the manifold, p(k) is the proportion of the k-th label in a given labeled data set, i.e., p(k) = n_k/l in which n_k is the amount of data with the k-th labels.

We then map the similarity to the coupling parameter in a QA system. As mentioned above, a limited connectivity of a qubit with others in the system is usually favoured to reduce the hardware complexity as well as to increase the accuracy. The latter is due to the consideration that an unlabeled data should be affected mainly by the surrounding ones in the manifold which are more likely to have smaller Hamming distance.
The configuration of connection can be determined using a symmetric mask matrix M applied on the similarity matrix S. First, we search the ξ largest elements in row S_i* to find the ξ closest ones to data x_i. A matrix M' is defined as:


M'_ij={
1    ,     if   S_ij   is among the   ξ  largest of   S_i*


0    ,     otherwise
..

The mask matrix is then calculated by M = (M')^T OR (M'), in which (A) OR (B) means take bitwise OR operation between matrix A and B.
The coupling parameters J_ij between two arbitrary qubits in Eq. <ref> can be calculated as:


    J_ij = M_ij*S_ij.


It should be noted that there may be cases where more than ξ qubits need to be topologically coupled to a certain one using this approach. A random elimination of the coupling parameters can be made to further reduce the connectivity. Or we can use extra qubits as intermediate couplers to realize a larger connectivity at a cost of reduced problem size that can be solved  <cit.>.



 §.§ Parameters learning


The final step concerns the attribution of appropriate values to the parameters that are related to the system's Hamiltonian. Firstly, parameters involved in the similarity calculation can be determined by a supervised learning process using the labeled data set. 
In the learning process, H_tar is replaced with H_learn by removing the bias h_i, thus we have

    H_learn= -∑_a=1^α ∑_i,j=1^lJ_ijσ_i^(a)σ_j^(a).

E_learn is the system energy corresponds to H_learn. 
The probability distribution of labels after the QA process follows the Bolzman distribution as:

    p(y_1,…,y_l|𝐱_1,…,𝐱_l;θ)
    
        =   1/Zexp(-E_learn(y_1,…,y_l)/T)
    
        =   1/Zexp(-∑_a^α∑_i,j=1^l⟨ y_i^(a)y_j^(a)|H_learn|y_i^(a)y_j^(a)⟩/T)
    
        =   1/Zexp(-∑_a^α∑_i,j=1^l -J_ijy_i^(a)y_j^(a)/T)

where Z is the partition function and Z=Tr[exp{-H_learn/T}], θ is the vector containing all parameters to learn. 

A negative log-likelihood function is therefore defined as below:

    ℒ(𝒟_l;θ) 
               = -log p(lab_1,…,lab_l|𝐱_1,…,𝐱_l;θ).
 

Then the elements of θ are determined by minimizing the conditional likelihood separately:

    θ_j = min -log p(lab_1,…,lab_l|𝐱_1,…,𝐱_l;θ).


Such a learning process is similar with the Boltzmann machine model  <cit.>, except that the sampling process can be accelerated by iterated QA processes and project measurements of qubits  <cit.>.

Again, some hyperparameters needs to be tuned properly according to a specific data set and hardware system. For instance, the value of h_i^(a) should be large enough such that the labels of labeled data is obtained correctly after annealing process. ξ should be properly set to (i) ensure that every unlabeled data can reach to a labeled one through a connected path to avoid a random result and to (ii) reduce the implication of data that are far away in the manifold.



§ EXAMPLE

Here we give two examples based on realistic database to verify the method discussed above. As a proof-of-principle demonstration, the annealing processes are simulated by a classical computer.







 §.§ Example 1: Iris

We first use a database of iris that has been widely used in pattern recognition literatures <cit.>.
There are three kinds of label in the data set, shown by points in three colors in Fig. <ref>(a). According to the labeled data (open circles), it is obvious that the shortest path that connects all the labels' barycenters is green-red-blue. Therefore, we encode the label by an ordered binary Gray Code as {00}_Setosa, {01}_Versicolour and {10, 11}_Virginica. We assume that the similarity between arbitrary two data follows a 2-dimensional mixed Gaussian-like function:


    S_ij = ∑_k=1^3 p(k)/2[1-(ρ^(k))^2][ x_i(1)-x_j(1)/(β_1^(k))^2+x_i(2)-x_j(2)/(β_2^(k))^2. 
    .-2ρ(l)(x_i(1)-x_j(1))(x_i(2)-x_j(2))/β^(k)_1β^(k)_2],

where x_i(1) (x_i(2)) is the first (second) element of data 𝐱_i, ρ^(l) is the correlation coefficient between 𝐱_i(1) and 𝐱_i(2). In this exmaple, the data have been processed with PCA  <cit.>, so we can assume that ρ = 0. J_ij are calculated using Eq. <ref> with ξ=6.

In Eq. <ref>, β_*^(k) are the parameters to be learned using the data of the k-th label. For each k, we substitute J_ij into Eq. <ref> and <ref> to have:

    ℒ(𝒟_l;β_*^(k)) 
           = -log p(lab_1,…,lab_l|𝐱_1,…,𝐱_l;β_*^(k))
       = 1/lZ(θ)∑_a^α∑_i,j=1^l∑_k=1^3p(k)/2[x_i(1)-x_j(1)/(β_1^(k))^2T+.
       .x_i(2)-x_j(2)/(β_2^(k))^2T]lab_i^(a)lab_j^(a),

in which lab_i^(a) is the a-th bit of lab_i with binary encoding.
Then we can obtain the optimized β_*^(k) with Eq.  <ref>. 

The classification results are shown in Fig. <ref>(b)-(d): when the 30% of the data set is unlabeled, the accuracy of the algorithm is 100%. An accuracy of 94.26% can still be maintained when 80% unlabeled data is considered. 



 §.§ Example 2: handwriting digital pictures

The second example is the handwritten digital recognition using the database from MNIST  <cit.>. We pick 200 images of digits 1, 8, 5, and 6 from the original data set and reduce the original dimension to 2 <cit.> as shown in Fig. <ref>(a). According to their barycenters on the manifold, we encode the 4 labels by {00}_1, {01}_8, {11}_5 and {10}_6.

Here the Euclidean distance given by Eq. <ref> and ξ = 4 are applied to calculate the similarity matrix S and coupling parameters J. Parameters concerning the similarity calculation are trained using similar approaches as the first example.

Fig. <ref>(b)-(d) shows the classification results. The accuracy of QA-SSL changes from 96.15% to 92.13% , as the portion of the unlabeled data in the whole data set increases from 30% to 80%, showing the feasibility of this method.



§ CONCLUSION


So far, quantum machine learning algorithms have been studied extensively on clustering (unsupervised learning)  <cit.> or supervised learning  classification algorithms <cit.>. In this paper we introduce a new semi-supervised learning method based on quantum annealing. In this method, the classification problem is mapped to the QA Hamiltonian through a graph representation, of which the vertices are efficiently implemented by qubits with an encoding scheme based on a binary Grey code. Calculations of the similarity between data are improved with a learning process using various models. Compared with previous proposed classification method using QA, this scheme significantly saves the quantum resources while maintaining the ability to express the original problem. The results of two proof-of-principle examples indicate that this method can still yield high accuracies for classification problem when the amount of labeled data is limited.

*








