docs/background/svm_weighted_kernel_alignment.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "4a601281",
   "metadata": {},
   "source": [
    "## Quantum Kernel Alignment\n",
    "\n",
    "Quantum Kernel Alignment (QKA) is a technique to optimize quantum kernels on a given dataset. Here, we will briefly introduce the main ideas behind QKA. For a more detailed look, see Ref. [1].\n",
    "\n",
    "### Evaluating Quantum Kernels\n",
    "\n",
    "Let's consider the quantum kernel entry for two input samples $x,\\tilde{x}$, which can be viewed as the transition amplitude [2]:\n",
    "\n",
    "$$\n",
    "K(x,\\tilde{x})=|\\langle0^n|U^\\dagger(x)U(\\tilde{x})|0^n\\rangle|^2.\n",
    "$$\n",
    "\n",
    "The input samples are encoded through a quantum circuit $U(x)$. The kernel entry is calculated by preparing the state $U^\\dagger(x)U(\\tilde{x})|0^n\\rangle$ on a quantum computer, and then estimating the probability of measuring the all-zero string. Once evaluated, this kernel matrix can be plugged into a standard SVM to optimize the hyperplane and predict labels of new samples.\n",
    "\n",
    "Thus far, the quantum kernel is fixed. However, suppose we wish to find a quantum kernel that is optimized for a dataset. We can do this by parametrizing the circuit used to encode the data $U_\\lambda(x)$ with some parameters $\\lambda$, and then optimizing those parameters. To do this, we need to specify a loss function; in this case, the weighted kernel alignment, which we'll explore below.\n",
    "\n",
    "### Kernel Alignment\n",
    "\n",
    "In classical machine learning, the original definition of the alignment was as a similarity measure of two kernels with respect to the training data, $T=\\{x_i\\}_{i=1\\ldots m}$. That is, given two kernel matrices $K_1,K_2$ the empirical alignment is the Hilbert-Schmidt inner product\n",
    "\n",
    "$$\n",
    "\\tilde{A}=\\sum_{i,j=1}^{m}K_1(x_i,x_j)K_2(x_i,x_j).\n",
    "$$\n",
    "\n",
    "Christianini et al. showed [3] that if one selects $K_1(x_i,x_j)=y_iy_j$ and $K_2(x_i,x_j)=K_\\lambda(x_i,x_j)$, for some parameters $\\lambda$, the alignment becomes\n",
    "\n",
    "$$\n",
    "\\tilde{A}=\\sum_{i,j=1}^{m}y_iy_jK_\\lambda(x_i,x_j)=\\sum_{i,j,y_i=y_j}K_\\lambda(x_i,x_j)-\\sum_{i,j,y_i{\\ne}y_j}K_\\lambda(x_i,x_j)\n",
    "$$\n",
    "\n",
    "It turns out that optimizing this alignment gives an upper bound to the generalization error (the probability a trained model will misclassify unseen test samples) of a simple classifier based on center of mass of the data classes [3].\n",
    "\n",
    "### Weighted Kernel Alignment\n",
    "\n",
    "Here, we consider Support Vector Machine classifiers and so we optimize a \"weighted\" kernel alignment. To see this, recall that the Wolfe-dual of the SVM cost function is\n",
    "\n",
    "$$\n",
    "F(\\alpha,\\lambda)=\\sum_i\\alpha_i-\\frac{1}{2} \\sum_{i,j}\\alpha_i\\alpha_j{y_i}{y_j}K_{\\lambda}(x_i,x_j).\\qquad(1)\n",
    "$$\n",
    "\n",
    "Fitting an SVM involves maximizing this function over the Lagrange multipliers $\\alpha_i\\ge0$. The support vectors of the training set correspond to $\\alpha_i>0$. In addition, we have accounted for a kernel matrix parametrized by $\\lambda$, over which we wish to optimize this cost function. Note that the second summation in Eq. (1) is the kernel alignment weighted by the Lagrange multipliers. This implies that only the support vectors determine the kernel parameters.\n",
    "\n",
    "Maximizing the weighted kernel alignment then corresponds to the following optimization problem:\n",
    "\n",
    "$$\n",
    "\\min_{\\lambda}\\max_{\\alpha}F(\\alpha,\\lambda),\n",
    "$$\n",
    "\n",
    "subject to the usual constraints $0\\le\\alpha_i\\le{C}$ and $\\sum_i{y_i}{\\alpha_i}=0$ for a soft-margin SVM with penalty $C>0$. Note that maximizing the weighted alignment corresponds to minimizing over the kernel parameters due to the negative sign in Eq. (1). Interestingly, this min-max problem can be viewed as finding a kernel that minimizes the upper bound of the SVM generalization error. For a deeper look into this connection, see [1,4].\n",
    "\n",
    "### References\n",
    "\n",
    "[1] J. R. Glick, T. P. Gujarati, A. D. Córcoles, Y. Kim, A. Kandala, J. M. Gambetta, K. Temme, arXiv:2105.03406 (2021) [link](https://arxiv.org/abs/2105.03406)<br>\n",
    "[2] V. Havlíček, A. D. Córcoles, K. Temme, A. W. Harrow, A. Kandala, J. M. Chow, and J. M. Gambetta, Nature 567, 209-212 (2019) [link](https://doi.org/10.1038/s41586-019-0980-2) <br>\n",
    "[3] N. Cristianini, J. Shawe-Taylor, A. Elisseeff, and J. Kandola, Advances in Neural Information Processing Systems 14 (2001) [link](https://proceedings.neurips.cc/paper/2001/file/1f71e393b3809197ed66df836fe833e5-Paper.pdf)<br>\n",
    "[4] J. Shawe-Taylor and N. Cristianini, IEEE Transactions on Information Theory 48, 2721 (2002) [link](https://doi.org/10.1109/TIT.2002.802647)\n",
    "\n",
    "Qiskit Global Summer School on Quantum Machine Learning, lecture [6.3](https://learn.qiskit.org/summer-school/2021/lec7-1-quantum-kernels-practice), Quantum Kernels in Practice\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}