## 2 The Learning Algorithm
### The VC Dimension  
We further show that the Ising classifier has a finite VC dimension upper bound in two simplified toy models in Figure 5. These simplifications can be regarded as regularization methods. The intuition is that, for \(J_{ij}>0\), anti-parallel spin configurations have higher energy and it is difficult that they are a ground state. This difficulty sets a limitation on how many points can be shattered and leads to an upper bound for the VC dimension. The detail derivation is in Appendix A. We use the following definitions: \(n_{sv}\) is the number of support vectors; \(n_{t}\) is the number of prediction data points; \(N=n_{sv}+n_{t}\) is the total number of spins in the Ising model; \(d\) is the feature space dimension. We assume that \(n_{sv}\leq n_{t}\). For the first toy model, we consider a simplification by introducing equal distance constraints to the support vectors and test data. This means \(J_{ij}=\frac{1}{||J_{i}-\vec{x}_{j}||}=J\) for all \((i,j)\). The Ising prediction model, in this case, is the fully connected infinite-dimensional mean field Ising model:  
\[H=-J\sum_{i<j}s_{i}s_{j}. \tag{16}\]  
Notice that this is a strong constraint which requires \(N\leq d+1\), but there is still one continuous parameter \(J\), so the hypothesis set is still infinite. This model is exactly solvable. The eigenenergy is \(E_{m}=J(-\frac{1}{2}N(N-1)+2m(N-m))\) for eigenstates with \(m\) spin up and \(N-m\) spin down. If there are two test data, the anti-parallel state \(\uparrow\downarrow\) is always an excited state; hence, it is impossible it is part of a ground state. We obtain the result \(d_{VC}=1\) in this case.  
This upper bound can be relaxed by considering a model with less constraints. Consider a second toy model where all the support vectors form a fully connected equal-distance lattice defined by parameter \(I_{sv}\). All the test data form another fully connected equal-distance lattice defined by another parameter, \(J_{t}\). The distance between support vectors and prediction data is parametrized by a different variable \(J_{int}\). Hence, there are three continuous variables in the model. The interaction between support vectors and prediction data points is restricted to one-to-one coupling. Let  
\[\begin{cases}\{\text{support vectors}\}&=\{\vec{x}_{1},\vec{x}_{2},\ldots,\vec {x}_{n_{sv}}\}\\ \{\text{test data}\}&=\{\vec{x}_{n_{sv}+1},\vec{x}_{n_{sv}+2},\ldots,\vec{x}_{n _{sv}+n_{t}}\}\end{cases}. \tag{17}\]  
Then, the coupling for this model is  
\[J_{ij}=\begin{cases}J_{sv},&\text{if }1\leq i<j\leq n_{sv}\\ J_{t},&\text{if }(n_{sv}+1)\leq i<j\leq(n_{sv}+n_{p})\\ J_{int},&\text{if }1\leq i\leq n_{sv}\text{ and }j=i+n_{sv}\\ 0,&\text{otherwise}\end{cases}. \tag{18}\]  
For this model, we obtain the result \(d_{xc}\leq\sqrt{\frac{2I_{int}}{J_{t}}n_{sv}}\). The intuition is that, if there are more support vectors (large \(n_{sv}\)), the model has more degrees of freedom. If the support vectors are closer to the test data (large \(J_{int}\)), the model has stronger influences on the test data. Hence, the Ising model can shatter more test data for larger \(J_{int}\) and \(n_{sv}\). On the other hand, if the distance among test data is small (large \(J_{t}\)), then the strong interactions among test data make it difficult to be shattered by the model.