# Parametric Matrix Models

Patrick Cook111Contributed equally<EMAIL_ADDRESS>Corresponding author
Facility for Rare Isotope Beams, Michigan State University, East Lansing,
Michigan 48824  Department of Physics and Astronomy, Michigan State
University, East Lansing, Michigan 48824  Danny Jammooa00footnotemark: 0
<EMAIL_ADDRESS>Corresponding author Facility for Rare Isotope Beams,
Michigan State University, East Lansing, Michigan 48824  Department of Physics
and Astronomy, Michigan State University, East Lansing, Michigan 48824  Morten
Hjorth-Jensen  Facility for Rare Isotope Beams, Michigan State University,
East Lansing, Michigan 48824  Department of Physics and Astronomy, Michigan
State University, East Lansing, Michigan 48824  Department of Physics and
Center for Computing in Science Education, University of Oslo, N-0316 Oslo,
Norway  Daniel D. Lee  Department of Electrical and Computer Engineering,
Cornell Tech, New York, NY 10044  Dean Lee  Facility for Rare Isotope Beams,
Michigan State University, East Lansing, Michigan 48824  Department of Physics
and Astronomy, Michigan State University, East Lansing, Michigan 48824

###### Abstract

We present a general class of machine learning algorithms called parametric
matrix models. Parametric matrix models are based on matrix equations, and the
design is motivated by the efficiency of reduced basis methods for
approximating solutions of parametric equations. The dependent variables can
be defined implicitly or explicitly, and the equations may use algebraic,
differential, or integral relations. Parametric matrix models can be trained
with empirical data only, and no high-fidelity model calculations are needed.
While originally designed for scientific computing, parametric matrix models
are universal function approximators that can be applied to general machine
learning problems. After introducing the underlying theory, we apply
parametric matrix models to a series of different challenges that show their
performance for a wide range of problems. For all the challenges tested here,
parametric matrix models produce accurate results within a computational
framework that allows for parameter extrapolation and interpretability.

##  1 Introduction

Any machine learning algorithm can be expressed as a set of constraint
equations, $\vec{F}(\vec{c},\vec{m},\vec{y})=0$, connecting input parameters
$\vec{c}$, model parameters $\vec{m}$ to be learned, and dependent variables
$\vec{y}$ comprising intermediate and final outputs. For example, the
constraint equations may enforce the minimization of some specific loss
function. For essentially all machine learning approaches, the constraint
equations involve explicit relations defining each dependent variable.
However, one can also consider constraint equations where the dependent
variables are defined implicitly [1, 2, 3, 4, 5, 6]. Here we introduce a
general class of machine learning algorithms called parametric matrix models
(PMMs), where the constraint equations to be solved are matrix equations. The
dependent variables can be defined implicitly or explicitly, and the equations
may use algebraic, differential, or integral relations. One very simple
example is $M(\vec{c})=M_{0}+\sum_{i}c_{i}M_{i}$, where $M_{0}$ and each
$M_{i}$ are Hermitian matrices, and the final outputs are eigenvalues of
$M(\vec{c})$. The PMM can be designed to incorporate as much mathematical and
scientific insight as possible or used more broadly as a universal function
approximator that can be efficiently optimized. In practice, PMMs typically
need fewer hyperparameters to tune as compared with other machine learning
approaches, therefore requiring less fine-tuning and model crafting. This
efficiency of description does not imply a loss of generality or flexibility.
It is instead the result of a natural design that prioritizes functions with
the simplest possible analytic properties when continued into the complex
plane.

While PMMs use data-driven methods, they also borrow the mathematical
structure of theory-based model-driven approaches such as reduced basis
methods [7, 8] without the need for model data. Such an approach is already
used in dynamic mode decomposition [9, 10, 11, 12] for dynamical systems with
coupled spatial and temporal modes. Matrix-based approaches have also been
widely used in machine learning for dimensionality reduction [13, 14, 15].
This work introduces the general strategy of PMMs and shows the utility of
PMMs for a broader class of problems.

To illustrate this, we consider the recently introduced eigenvector
continuation (EC) method [16, 17, 18, 19, 20, 21, 22, 23]. Eigenvector
continuation is a reduced basis method that finds the eigenvectors and
eigenvalues for a parameterized family of Hermitian matrices $H(\vec{c})$
whose elements are analytic functions of $\vec{c}$. The EC calculation starts
by picking some set of eigenvectors $\left|v_{j}(\vec{c}_{i})\right\rangle$ at
selected values $\vec{c}\in\left\\{\vec{c}_{i}\right\\}$. It then projects all
vectors to the subspace spanned by these eigenvector snapshots. The task then
reduces to finding the eigenvalues and eigenvectors of a much smaller
Hermitian matrix $M(\vec{c})$, whose elements are also analytic functions of
$\vec{c}$. The eigenvalues are roots of the characteristic polynomial,
$\det[M(\vec{c})-\lambda\mathbb{I}]$. If we approximate the dependence on
$\vec{c}$ over some $d$-dimensional compact domain using polynomials, then
each $\lambda$ corresponds to the roots of a polynomial in $\lambda$ with
coefficients that are polynomials with respect to $\vec{c}$.

The resulting algebraic variety defining $\lambda$ is endowed with some very
useful properties. For all real values of $\vec{c}$, $\lambda$ will be
analytic and bounded by the norm of $M(\vec{c})$, which is a polynomial in
$\vec{c}$. Using only general arguments of analyticity, in Ref. [22] it is
shown that with $N_{b}$ basis vectors, the error of the EC approximation
diminishes as a decaying exponential function of $N_{b}^{1/d}$ in the limit of
large $N_{b}$. For the case of eigenvalue problems, PMMs capture the essential
features of the EC calculations by proposing some unknown Hermitian matrix
$M(\vec{c})$ and learning the polynomials in $\vec{c}$ that comprise its
matrix elements.

The PMMs can achieve the same rapid convergence with matrix dimension as EC
for eigenvalue problems. A constructive proof is to tune the matrix parameters
to the same matrix $M(\vec{c})$ corresponding to an EC calculation. However,
this is not how PMMs will typically be used. A key computational advantage of
PMMs is that they can be trained with empirical data only. No high-fidelity
model calculations are needed. Despite starting with less information, there
are many examples where PMMs still achieve superior performance when compared
with EC.

For example, we consider first a simple system composed of $N$ non-interacting
spin-$1/2$ particles with the one-parameter Hamiltonian

$H(c)=\frac{1}{2N}\sum_{i}^{N}\left(\sigma^{z}_{i}+c\sigma^{x}_{i}\right).$
(1)

Here, $\sigma^{z}_{i}$ and $\sigma^{x}_{i}$ are the $z$ and $x$ Pauli matrices
for spin $i$, respectively. We see in Fig. 1, that the EC method has
difficulties in reproducing the ground state energy $E_{0}$ for large $N$
using five training points, or snapshots, which here are the eigenpairs
obtained from the solution of the full $N$-spin problem. The PMM
representation does not have this problem and is able to exactly reproduce
$E_{0}$ for all $N$ using a learned $2\times 2$ matrix model only of the form
$M(c)=\left(\sigma^{z}+c\sigma^{x}\right)/2$. While this particular example is
a rather trivial non-interacting system, it illustrates the general principle
that PMMs have more freedom than reduced basis methods. They do not need to
correspond to a projection onto a fixed subspace, and this allows for
efficient solutions to describe a wider class of problems.

The eigenvalue problem is only one example among many from a very broad class
of problems that PMMs can address. For scientific computing applications, the
general strategy is to incorporate as much of the underlying science and
applied mathematics into the structure of the PMM. However, PMMs can also be
used for general problems outside the domain of scientific computing. The PMMs
we have just discussed can output any polynomial function of the input
parameters, and therefore the universal function approximation condition is
guaranteed by the Weierstrass approximation theorem [24].

Figure 1: Results for the ground state energy of the Hamiltonian given by Eq.
(1) as a function of the interaction strength parameter $c$. Extrapolated
results from the $5$ training points (diamond symbols) located where $c<0$ are
shown for EC (dotted red) and a $2\times 2$ PMM (dashed blue). The exact
ground state energy is shown in solid black.

We outline here the rest of this work. In the next section, in order to
benchmark the performance and the versatility of PMMs, we consider three very
different examples of interest to a broader audience. For each case, we
compare the PMMs against other state-of-the-art methods. Our conclusions and
perspectives for future studies are presented in the subsequent section. We
also include several additional examples in the supplementary material.

##  2 Performance and Versatility of Parametric Matrix Models

In this section we showcase the performance and versatility of PMMs by
applying the method to three distinct problems. The examples we consider are
the energy levels of the quantum anharmonic oscillator (Sec. 2.1), the
extrapolation of the so-called Trotter approximation errors in quantum
computing (Sec. 2.2), and finally the unsupervised image clustering of
handwritten digits (Sec. 2.3).

###  2.1 Quantum Anharmonic Oscillator

The quantum anharmonic oscillator describes the quantum mechanics of a
particle confined by an external potential of the form
$V(x)=\frac{1}{2}kx^{2}+\lambda x^{4}$. The corresponding scaled Hamiltonian
can be written as

$H(g)=a^{\dagger}a+g\left(a^{\dagger}+a\right)^{4},$ (2)

where $a^{\dagger}$ and $a$ are creation and annihilation operators satisfying
the relation $aa^{\dagger}-a^{\dagger}a=1$. We have absorbed multiplicative
and additive constants into the definition of $H$, and the relative
anharmonicity is represented by the dimensionless parameter $g$. This model
has attracted much interest and has been the subject of many theoretical and
computational studies throughout the years [25, 26, 27, 28, 29, 30].

The quantum anharmonic oscillator has a complicated analytical structure with
an infinite number of branch points in the complex plane that accumulate at
$g=0$ [31]. While the Hamiltonian is unbounded below for $g<0$, applying a
finite truncation of the basis states allows the Hamiltonian to be defined for
all $g$. We perform this truncation using harmonic oscillator eigenstates
corresponding to $H(g=0)=H(0)$ and make the restriction of maximum energy
excitation $N_{\rm max}$. For the example considered here, we take $N_{\rm
max}=100$. For $g<0$, there are large negative potential energies of equal
depth for large positive $x$ and large negative $x$. As a result, there is an
approximate degeneracy of positive and negative parity states for $g<0$. The
energy gap between the lowest two energy states, $E_{1}-E_{0}$, provides a
useful probe of this degeneracy for $g<0$ and the change in character as we
cross $g=0$.

We compare here the performance of a multilayer perceptron (MLP) neural
network [32] and cubic spline interpolation [33] with our PMM approach in
learning the lowest two energy levels $E_{0}$ and $E_{1}$ as a function of $g$
[33]. For each case, we provide training data for $E_{0}$ and $E_{1}$ at ten
evenly-spaced values of $g$, spanning the range $g\in[-0.01,0.01]$ and for
validation data approximately $100$ evenly-spaced points throughout the same
domain. The validation set was withheld during training and only used to stop
training before overfitting. The MLP we compared to used the rectified linear
unit [32] as the activation function and had two hidden layers of $25$ neurons
each. We trained $100$ of these MLPs and show the average results. For the
cubic spline analysis, we applied the standard approach with zero curvature at
the end points. For the PMM, we use a $5\times 5$ matrix model and use the
matrix structure we would get from applying EC to the quantum anharmonic
oscillator, $M(g)=M_{0}+gM_{1}$, where $M_{0}$ and $M_{1}$ are Hermitian
matrices. Using the unitary transformation to diagonalize $M_{0}$, we can
simplify further to the form $M(g)=D+gM^{\prime}_{1}$, where $D$ is a real
diagonal matrix. All of the nonzero entries of $D$ and $M^{\prime}_{1}$ are
learned by fitting the two lowest eigenvalues of $M(g)$ to the training data.

Figure 2 shows the results for the three different approaches in comparison
with the exact results. We see that the PMM performs significantly better than
both the MLP and cubic spline. The superior performance is not specific to the
example considered here. The PMM has the advantage that it learns the
underlying physics of branch point singularities in the complex plane of $g$
near the real axis [34]. We further explore this property of PMMs—as well as
their ability to learn observables associated with the system—in the
Supplemental Material.

Figure 2: The two lowest two energies of the quantum anharmonic oscillator as
a function of $g$ (top) and the absolute error in the three methods used to
interpolate the training data (bottom). The main figure focuses on the region
of interest where the degeneracy between the first two levels is first broken.
The inset shows the full domain of $0.01\leq g\leq 0.01$ with the focused
region highlighted. These results show that not only does the PMM outperform
MLP and cubic splines, but guarantees the preservation of important basic
properties like level ordering where the other methods do not.

###  2.2 Zero Trotter Step Extrapolation

One of the primary challenges in quantum computing is determining observables
of interest while using circuits with as few qubits and quantum gates as
possible. This minimal resource strategy is necessary due to the limitations
of noise and decoherence [35].

There are several efficient algorithms that determine energy levels on a
quantum computer using the complex phases produced during the time evolution
of quantum states [36, 37, 38, 39, 40, 41, 42, 43, 44]. The time evolution
operator for time duration $t$ corresponds to the exponential of the
Hamiltonian, $\mathrm{exp}\left\\{-iHt\right\\}$. This is implemented as a
product of evolution operators for small time steps $dt$,
$\mathrm{exp}\left\\{-iHdt\right\\}\cdots\mathrm{exp}\left\\{-iHdt\right\\}$.
Each term $U(dt)=\mathrm{exp}\left\\{-iHdt\right\\}$ can be approximated as a
product of exponentials of the individual terms comprising $H$. This
approximation becomes exact in the limit $dt\rightarrow 0$ and is known as a
Trotter product [45], and the generalization to products with higher-order
errors in $dt$ are called Trotter-Suzuki formulae [46, 47, 48].

The desired energies $E_{k}$ are determined by setting
$\mathrm{exp}\left\\{-iE_{k}dt\right\\}$ equal to the eigenvalues of $U(dt)$
and extrapolating to the limit $dt\rightarrow 0$. Data from small $dt$ are
often not possible due to the large number of quantum gates required. Several
polynomial interpolation and extrapolation methods have therefore been
developed [49, 50, 51]. In the following, we use PMMs to determine $E_{k}$ and
compare with polynomial interpolation methods.

We consider a one-dimensional quantum spin chain with nearest and next-to-
nearest neighbor interactions. The Hamiltonian of this Heisenberg system is
${H=H_{B}+H_{J_{1}}^{0}+H_{J_{1}}^{1}+H_{J_{2}}^{0}+H_{J_{2}}^{1}}$, where

$\displaystyle H_{B}$ $\displaystyle=B\sum_{i}^{N}r_{i}\sigma_{i}^{z}$ (3)
$\displaystyle H_{J_{1}}^{0|1}$ $\displaystyle=J_{1}\sum_{i\,\rm
even|odd}^{N}(\sigma_{i}^{x}\sigma_{i+1}^{x}+\sigma_{i}^{y}\sigma_{i+1}^{y}+\sigma_{i}^{z}\sigma_{i+1}^{z})$
$\displaystyle H_{J_{2}}^{0|1}$ $\displaystyle=J_{2}\sum_{i\,\rm
even|odd}^{N}(\sigma_{i}^{x}\sigma_{i+2}^{x}+\sigma_{i}^{y}\sigma_{i+2}^{y}+\sigma_{i}^{z}\sigma_{i+2}^{z}),$

where $r_{i}$ are random real numbers ranging from $[0,1)$. For $U(dt)$, we
use the Trotter product

$\displaystyle U(dt)$
$\displaystyle=\mathrm{exp}\left\\{-iH_{B}dt\right\\}\mathrm{exp}\left\\{-iH_{J_{1}}^{0}dt\right\\}$
(4)
$\displaystyle\times\mathrm{exp}\left\\{-iH_{J_{1}}^{1}dt\right\\}\mathrm{exp}\left\\{-iH_{J_{2}}^{0}dt\right\\}$
$\displaystyle\times\mathrm{exp}\left\\{-iH_{J_{2}}^{1}dt\right\\}.$

We use a PMM with the same underlying structure,

$\displaystyle U_{M}(dt)$
$\displaystyle=\mathrm{exp}\left\\{-iM_{1}dt\right\\}\mathrm{exp}\left\\{-iM_{2}dt\right\\}$
(5)
$\displaystyle\times\mathrm{exp}\left\\{-iM_{3}dt\right\\}\mathrm{exp}\left\\{-iM_{4}dt\right\\}$
$\displaystyle\times\mathrm{exp}\left\\{-iM_{5}dt\right\\},$

where each of the matrices, $M_{i}$, are $10\times 10$ Hermitian matrices. We
use the values $B=J_{1}=1$, and $J_{2}=0.5$, and choose 10 values of $dt$
spanning the range $[-0.18,-0.15]\cup[0.15,0.18]$. We train the PMM using the
ground state, first excited state, and second excited state for $N=8$ qubits
with periodic boundary conditions.

Figure 3: Results for selected energy levels in the one-dimensional Heisenberg
spin chain with nearest-neighbor and next-nearest-neighbor interactions (top)
as well as the relative error for the extrapolated values at $dt=0$ (bottom).
We show the $10\times 10$ PMM results (dashed lines, square diamonds),
polynomial interpolation results (dotted lines, squares), exact
diagonalization calculation of Trotter ground-truth (solid lines), and Trotter
training data (thin diamonds). The vertical grey line highlights $dt=0$.

Using the same training data, we compare the PMM results with polynomial
interpolation. Since we do not have data at smaller values of $dt$, the
polynomial fitting is less reliable than the Chebyshev polynomial
interpolation used in Ref. [52]. The results are shown in Fig. 3. Polynomial
interpolation was not able to handle the sharp avoided level crossings
involving the first and second excited states. In contrast, the PMM reproduces
the avoided level crossings properly—which are not present in the training
data—and also predicts the first and second excited states at $dt=0$ with much
higher accuracy.

###  2.3 Unsupervised Image Clustering

To demonstrate the usefulness of PMMs beyond scientific computing—in areas
that are dominated by neural networks—we apply a PMM to the problem of
unsupervised image clustering on the MNIST dataset. This dataset consists of
$60\,000$ ($10\,000$) labeled training (test) $28\times 28$ monochrome images
of handwritten digits from $0$ to $9$. The goal of an unsupervised learning
algorithm on this dataset is to—without the use of any data labels—project
this data from the original $28\times 28=784$ dimensional space to a
significantly lower dimensional space, often to just $2$ dimensions. This
projection should cluster similar images together in the low dimensional
space, effectively identifying the $10$ different digits without knowing what
image is what digit, or even that there are $10$ digits.

We apply an $8\times 8$ PMM of the form
${M(\vec{c})=D+\sum_{i=1}^{784}c_{i}M_{i}}$, where $D$ is a real diagonal
matrix and $M_{i}$ are complex hermitian matrices whose individual matrix
elements are drawn from a tensor network in order to drastically reduce the
number of training parameters. The details of this tensor network PMM are
described in the Supplementary Material Sec. A.3. Results both with and
without this tensor network formulation were qualitatively and quantitatively
indistinguishable. We trained the PMM using only $10\,000$ images from the
training set. For each image $\vec{c}$, the projected output was taken to be
the two most-interior eigenvalues of the PMM $M(\vec{c})$. Training the PMM is
done in a manner similar to t-distributed Stochastic Neighbor Embedding
(t-SNE) by minimizing the Kullback-Leibler divergence between the original
data and the projected data [53]. Figure 4 shows the results of the learned
embedding by a PMM applied to the training data as well as $10\,000$ images
from the MNIST test set which were unseen during training. Table 1 shows the
1-nearest-neighbor generalization error of our embedding compared to Principal
Component Analysis (PCA), a supervised technique known as Neighborhood
Components Analysis (NCA), an autoencoder, and parametric t-SNE [54, 55]. The
1-nearest-neighbor generalization error measures the percentage of nearest
neighbor pairs in the low-dimensional embedding which were not part of the
same class. An important note is that we did not preprocess the original
dataset in any way as is usually done when using t-SNE-like methods to reduce
the dimensionality of the training data [53, 56]. Our results demonstrate that
a PMM is able to produce a high-quality parametric embedding, which basic
t-SNE methods alone cannot do without preprocessing, pretraining, and
finetuning [54]. Moreover, these results demonstrate the utility of PMMs
beyond scientific computing.

Method |  Training
Examples | Train Error | Test Error | Source
---|---|---|---|---
PCA |  $60\,000$ | — |  $78.16$% | [54]
NCA |  $60\,000$ | — |  $56.84$% | [54]
Autoencoder |  $60\,000$ | — |  $66.84$% | [54]
Par. t-SNE |  $60\,000$ | — |  $9.90$% | [54]
Par. t-SNE |  $10\,000$ |  $9.92$% |  $13.09$% | This work
PMM |  $10\,000$ |  $17.66$% |  $34.43$% | This work
Table 1: Comparison of 1-nearest-neighbor generalization errors of PCA, NCA,
an autoencoder, parametric t-SNE, and a PMM applied to the MNIST handwritten
digits dataset. Lower error values are better. These results show that a PMM
outperforms all but the most fine-tuned clustering method while only having
access to one sixth the training data. Figure 4: PMM embedding applied to the
$10\,000$ images from the MNIST training dataset which were used for training
(top) as well as $10\,000$ images from the MNIST test set which were entirely
unseen during training.

##  3 Summary and Outlook

We have introduced PMMs as a general class of machine learning algorithms and
presented three examples showing the performance and utility of the approach.
The first example addressed the quantum anharmonic oscillator near the point
$g=0$, where the character of the energy states changes abruptly. The PMM is
able to reproduce the lowest two energy levels as a function of $g$ much more
accurately than the other emulators. This suggests that PMMs can be useful for
mapping out the properties of systems with complicated phase structures. Since
detailed model data is not required for the PMM, such features could be
learned directly from empirical data.

In the second example, we showed that a PMM is able to perform Trotter
extrapolation to the limit of zero step size. This will be of substantial
utility for a wide range of quantum computing applications, where the
limitations of quantum coherence and gate error rates prevent evaluations at
very small step size.

While originally designed for scientific computing, PMMs can be used for
general machine learning problems. Our third example showed the application of
a PMM to unsupervised image clustering using a dataset of handwritten images.
Our first application of a PMM to this problem is already competitive with
state-of-art machine learning algorithms—with far fewer hyperparameters.
Further developments in PMMs should make the performance substantially better.
Work in this direction is currently in progress as well as efforts to apply
PMMs to other categories of machine learning problems.

## Acknowledgements

We are grateful for discussions with Pablo Giuliani and Kyle Godbey, who are
developing similar ideas with collaborators that combine reduced basis methods
with machine learning. We also thank Scott Bogner, Heiko Hergert, Caleb Hicks,
Yuan-Zhuo Ma, Jacob Watkins, and Xilin Zhang for useful discussions and
suggestions. This research is supported in part by U.S. Department of Energy
(DOE) Office of Science grants DE-SC0024586, DE-SC0023658 and DE-SC0021152.
P.C. was partially supported by the U.S. Department of Defense (DoD) through
the National Defense Science and Engineering Graduate (NDSEG) Fellowship
Program. M.H.-J. is partially supported by U.S. National Science Foundation
(NSF) Grants PHY-1404159 and PHY-2013047. Da.L. is partially supported by the
National Institutes of Health grant NINDS (1U19NS104653) and NSF grant
IIS-2132846. De.L. is partially supported by DOE grant DE-SC0013365, NSF grant
PHY-2310620, and SciDAC-5 NUCLEI Collaboration.

## Author Contributions

P.C. and D.J. carried out the theoretical analyses and the numerical
implementations. M.H.-J., Da.L., and De.L. supervised the work. All authors
contributed to the discussion of the results and manuscript.

## References

  * [1] Ricky TQ Chen, Yulia Rubanova, Jesse Bettencourt, and David K Duvenaud.  Neural ordinary differential equations.  Advances in neural information processing systems, 31, 2018.
  * [2] Shaojie Bai, J Zico Kolter, and Vladlen Koltun.  Deep equilibrium models.  Advances in Neural Information Processing Systems, 32, 2019.
  * [3] Ziming Zhang, Anil Kag, Alan Sullivan, and Venkatesh Saligrama.  Equilibrated recurrent neural network: Neuronal time-delayed self-feedback improves accuracy and stability.  arXiv preprint arXiv:1903.00755, 2019.
  * [4] Anil Kag, Ziming Zhang, and Venkatesh Saligrama.  RNNs evolving on an equilibrium manifold: A panacea for vanishing and exploding gradients?  arXiv preprint arXiv:1908.08574, 2019.
  * [5] Fangda Gu, Armin Askari, and Laurent El Ghaoui.  Fenchel lifted networks: A lagrange relaxation of neural network training.  In International Conference on Artificial Intelligence and Statistics, pages 3362–3371. PMLR, 2020.
  * [6] Laurent El Ghaoui, Fangda Gu, Bertrand Travacca, Armin Askari, and Alicia Tsai.  Implicit deep learning.  SIAM Journal on Mathematics of Data Science, 3(3):930–958, 2021\.
  * [7] Alfio Quarteroni, Andrea Manzoni, and Federico Negri.  Reduced basis methods for partial differential equations: an introduction, volume 92.  Springer, 2015.
  * [8] J.S. Hesthaven, G. Rozza, and B. Stamm.  Certified Reduced Basis Methods for Parametrized Partial Differential Equations.  SpringerBriefs in Mathematics. Springer International Publishing, 2016\.
  * [9] Peter J. Schmid.  Dynamic mode decomposition of numerical and experimental data.  Journal of Fluid Mechanics, 656:5–28, 2010.
  * [10] Jonathan H Tu.  Dynamic mode decomposition: Theory and applications.  PhD thesis, Princeton University, 2013.
  * [11] Joshua L Proctor, Steven L Brunton, and J Nathan Kutz.  Dynamic mode decomposition with control.  SIAM Journal on Applied Dynamical Systems, 15(1):142–161, 2016\.
  * [12] J Nathan Kutz, Steven L Brunton, Bingni W Brunton, and Joshua L Proctor.  Dynamic mode decomposition: data-driven modeling of complex systems.  SIAM, 2016.
  * [13] Daniel Lee and H Sebastian Seung.  Algorithms for non-negative matrix factorization.  Advances in neural information processing systems, 13, 2000.
  * [14] Yu-Xiong Wang and Yu-Jin Zhang.  Nonnegative matrix factorization: A comprehensive review.  IEEE Transactions on knowledge and data engineering, 25(6):1336–1353, 2012.
  * [15] Lawrence K Saul.  A geometrical connection between sparse and low-rank matrices and its application to manifold learning.  Transactions on Machine Learning Research, 2022.
  * [16] Dillon Frame, Rongzheng He, Ilse Ipsen, Daniel Lee, Dean Lee, and Ermal Rrapaj.  Eigenvector continuation with subspace learning.  Phys. Rev. Lett., 121:032501, Jul 2018.
  * [17] P. Demol, T. Duguet, A. Ekström, M. Frosini, K. Hebeler, S. König, D. Lee, A. Schwenk, V. Somà, and A. Tichai.  Improved many-body expansions from eigenvector continuation.  Phys. Rev. C, 101(4):041302, 2020.
  * [18] S. König, A. Ekström, K. Hebeler, D. Lee, and A. Schwenk.  Eigenvector Continuation as an Efficient and Accurate Emulator for Uncertainty Quantification.  Phys. Lett. B, 810:135814, 2020.
  * [19] Andreas Ekström and Gaute Hagen.  Global sensitivity analysis of bulk properties of an atomic nucleus.  Phys. Rev. Lett., 123(25):252501, 2019.
  * [20] R. J. Furnstahl, A. J. Garcia, P. J. Millican, and Xilin Zhang.  Efficient emulators for scattering using eigenvector continuation.  Phys. Lett. B, 809:135719, 2020.
  * [21] Avik Sarkar and Dean Lee.  Convergence of Eigenvector Continuation.  Phys. Rev. Lett., 126(3):032501, 2021.
  * [22] Thomas Duguet, Andreas Ekström, Richard J. Furnstahl, Sebastian König, and Dean Lee.  Eigenvector Continuation and Projection-Based Emulators.  10 2023.
  * [23] Caleb Hicks and Dean Lee.  Trimmed sampling algorithm for the noisy generalized eigenvalue problem.  Phys. Rev. Res., 5(2):L022001, 2023.
  * [24] Jan Brinkhuis and Vladimir Tikhomirov.  Optimization.  Princeton University Press, Princeton, 2006.
  * [25] R McWeeny and Charles Alfred Coulson.  Quantum mechanics of the anharmonic oscillator.  In Mathematical Proceedings of the Cambridge Philosophical Society, volume 44, pages 413–422. Cambridge University Press, 1948.
  * [26] K Banerjee, SP Bhatnagar, V Choudhry, and SS Kanwal.  The anharmonic oscillator.  Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences, 360(1703):575–586, 1978.
  * [27] ID Feranchuk, LI Komarov, IV Nichipor, and AP Ulyanenkov.  Operator method in the problem of quantum anharmonic oscillator.  Annals of physics, 238(2):370–440, 1995.
  * [28] Carl M Bender and Luis MA Bettencourt.  Multiple-scale analysis of the quantum anharmonic oscillator.  Physical review letters, 77(20):4114, 1996.
  * [29] Mojtaba Jafarpour and Davood Afshar.  Calculation of energy eigenvalues for the quantum anharmonic oscillator with a polynomial potential.  Journal of Physics A: Mathematical and General, 35(1):87, 2001.
  * [30] M Companys Franzke, Alexander Tichai, Kai Hebeler, and Achim Schwenk.  Excited states from eigenvector continuation: The anharmonic oscillator.  Physics Letters B, 830:137101, 2022.
  * [31] Carl M. Bender and Tai Tsun Wu.  Anharmonic oscillator.  Phys. Rev., 184:1231–1260, Aug 1969.
  * [32] Ian Goodfellow, Yoshua Bengio, and Aaron Courville.  Deep Learning.  The MIT Press, Cambridge, Massachusetts, 2016.
  * [33] J. Stoer and R. Bulirsch.  Introduction to Numerical Analysis.  Springer-Verlag, Berlin, 1993.
  * [34] Tosio Kato.  Perturbation Theory for Linear Operators.  1966\.
  * [35] Frank Leymann and Johanna Barzen.  The bitter truth about gate-based quantum algorithms in the nisq era.  Quantum Science and Technology, 5(4):044007, 2020.
  * [36] A. Yu. Kitaev.  Quantum measurements and the Abelian stabilizer problem.  Electronic Colloquium on Computational Complexity, 3, 1995.
  * [37] Daniel S. Abrams and Seth Lloyd.  Simulation of many body Fermi systems on a universal quantum computer.  Phys. Rev. Lett., 79:2586–2589, 1997.
  * [38] Uwe Dorner, Rafal Demkowicz-Dobrzanski, Brian J Smith, Jeff S Lundeen, Wojciech Wasilewski, Konrad Banaszek, and Ian A Walmsley.  Optimal quantum phase estimation.  Phys. Rev. Lett., 102(4):040403, 2009.
  * [39] Krysta M. Svore, Matthew B. Hastings, and Michael Freedman.  Faster Phase Estimation.  4 2013.
  * [40] Kenneth Choi, Dean Lee, Joey Bonitati, Zhengrong Qian, and Jacob Watkins.  Rodeo Algorithm for Quantum Computing.  Phys. Rev. Lett., 127(4):040505, 2021.
  * [41] Edgar Andres Ruiz Guzman and Denis Lacroix.  Accessing ground-state and excited-state energies in a many-body system after symmetry restoration using quantum computers.  Phys. Rev. C, 105(2):024324, 2022.
  * [42] Zhengrong Qian, Jacob Watkins, Gabriel Given, Joey Bonitati, Kenneth Choi, and Dean Lee.  Demonstration of the Rodeo Algorithm on a Quantum Computer.  10 2021.
  * [43] Max Bee-Lindgren, Zhengrong Qian, Matthew DeCross, Natalie C. Brown, Christopher N. Gilbreth, Jacob Watkins, Xilin Zhang, and Dean Lee.  Rodeo Algorithm with Controlled Reversal Gates.  8 2022.
  * [44] Thomas D. Cohen and Hyunwoo Oh.  Optimizing the rodeo projection algorithm.  Phys. Rev. A, 108(3):032422, 2023.
  * [45] Hale F Trotter.  On the product of semi-groups of operators.  Proceedings of the American Mathematical Society, 10(4):545–551, 1959.
  * [46] Masuo Suzuki.  Generalized Trotter’s formula and systematic approximants of exponential operators and inner derivations with applications to many-body problems.  Comm. Math. Phys., 51(2):183–190, June 1976.
  * [47] Masuo Suzuki.  General decomposition theory of ordered exponentials.  Proceedings of the Japan Academy, Series B, 69(7):161–166, 1993\.
  * [48] Andrew M Childs, Yuan Su, Minh C Tran, Nathan Wiebe, and Shuchen Zhu.  Theory of Trotter error with commutator scaling.  Physical Review X, 11(1):011020, 2021.
  * [49] Suguru Endo, Qi Zhao, Ying Li, Simon Benjamin, and Xiao Yuan.  Mitigating algorithmic errors in a hamiltonian simulation.  Phys. Rev. A, 99:012334, Jan 2019.
  * [50] Almudena Carrera Vazquez, Ralf Hiptmair, and Stefan Woerner.  Enhancing the quantum linear systems algorithm using richardson extrapolation.  ACM Transactions on Quantum Computing, 3(1):1–37, 2022.
  * [51] Gumaro Rendon, Jacob Watkins, and Nathan Wiebe.  Improved Accuracy for Trotter Simulations Using Chebyshev Interpolation.  12 2022.
  * [52] Gumaro Rendon, Jacob Watkins, and Nathan Wiebe.  Improved error scaling for Trotter simulations through extrapolation, 2023.
  * [53] Laurens van der Maaten and Geoffrey Hinton.  Viualizing data using t-SNE.  Journal of Machine Learning Research, 9:2579–2605, 11 2008.
  * [54] Laurens van der Maaten.  Learning a parametric embedding by preserving local structure.  Journal of Machine Learning Research - Proceedings Track, 5:384–391, 01 2009.
  * [55] Jacob Goldberger, Geoffrey E Hinton, Sam Roweis, and Russ R Salakhutdinov.  Neighbourhood components analysis.  In L. Saul, Y. Weiss, and L. Bottou, editors, Advances in Neural Information Processing Systems, volume 17. MIT Press, 2004.
  * [56] Laurens van der Maaten.  Accelerating t-SNE using tree-based algorithms.  Journal of Machine Learning Research, 15(93):3221–3245, 2014.
  * [57] W D Heiss, F G Scholtz, and H B Geyer.  The large n behaviour of the lipkin model and exceptional points.  Journal of Physics A: Mathematical and General, 38(9):1843, feb 2005\.
  * [58] W D Heiss.  The physics of exceptional points.  Journal of Physics A: Mathematical and Theoretical, 45(44):444016, oct 2012.
  * [59] I. Dzyaloshinsky.  A thermodynamic theory of “weak” ferromagnetism of antiferromagnetics.  Journal of Physics and Chemistry of Solids, 4(4):241–255, 1958\.
  * [60] Tôru Moriya.  Anisotropic superexchange interaction and weak ferromagnetism.  Physical review, 120(1):91, 1960.
  * [61] Mostafa Motamedifar, Fatemeh Sadeghi, and Mojtaba Golshani.  Entanglement transmission due to the Dzyaloshinskii-Moriya interaction.  Scientific Reports, 13(1):2932, 2023.
  * [62] Chandrashekar Radhakrishnan, Manikandan Parthasarathy, Segar Jambulingam, and Tim Byrnes.  Quantum coherence of the Heisenberg spin models with Dzyaloshinsky-Moriya interactions.  Scientific Reports, 7(1):13865, 2017.
  * [63] Qinghui Li, Chuanzheng Miao, Yuliang Xu, and Xiangmu Kong.  Quantum entanglement in Heisenberg model with Dzyaloshinskii-Moriya interactions.  Journal of Superconductivity and Novel Magnetism, 36(3):957–964, 2023.
  * [64] D. Perez-Garcia, F. Verstraete, M. M. Wolf, and J. I. Cirac.  Matrix product state representations.  Quantum Info. Comput., 7(5):401–430, jul 2007.

##  Appendix A Supplementary Material

###  A.1 Effective Hamiltonian for the Lipkin-Meshkov-Glick Model

In this section, we apply the same PMM formulation as discussed in Section 2.1
to the Lipkin-Meshkov-Glick (LMG) model. The Hamiltonian for the LMG model is
given by:

$\displaystyle H(c)=-S_{z}-\frac{2c}{N}(S_{x}^{2}-\frac{1}{2}S_{y}^{2})$ (6)

When $c<0.5$, the ground state of the LMG model maintains normal phase
symmetry. For $c>0.5$, a deformed phase emerges, breaking symmetry and causing
degeneracy between even and odd $n$. This quantum phase transition arises from
the involvement of exceptional points (EPs) in the complex plane [57, 58]. We
trained a $15\times 15$ PMM on the 5 lowest energies of a 100 site LMG model
given 10 real values of $c\in[0,1]$ for each energy as seen in Figure 5. The
learned PMM was then used to learn other observables and to extrapolate the
ground state energy for complex values of $c$.

Given data for observables $\langle S_{x}^{2}(c)\rangle/N^{2}$ and $\langle
S_{z}(c)\rangle/N$ in the ground state, one can apply the learned PMM to learn
an observable $O$, which is a simple $15\times 15$ Hermitian matrix. $O$ is
learned by fitting $\langle\psi_{0}(c)|O|\psi_{0}(c)\rangle$ to the data,
where $|\psi_{0}(c)\rangle$ is the ground state eigenvector of the learned PMM
for the energies. The training data for $\langle S_{x}^{2}(c)\rangle/N^{2}$,
($\langle S_{z}(c)\rangle/N$) consisted of 20 values of $c$ in the range
$[0,0.4]\cup[0.6,1],([0,0.4]\cup[0.55,1])$ respectively. A separate $O$ was
learned for each observable. Figures 6 and 7 show our results and compares
them to those from the average of $100$ MLPs with two hidden layers with $100$
and $50$ neurons respectively as well as cubic spline interpolation. These
results demonstrate the superior performance of a PMM in interpolating sparse
data. Moreover, these results show that the PMM for the energy of the system
can be used in a Hamiltonian-like way; the eigenvectors of this PMM can be
used exactly like state vectors to learn some related observables of the
system.

Using this example, we demonstrate the unique and powerful ability of PMMs to
extrapolate to complex values of the input features based purely on real-
valued training data. Figure 8 shows the ground state energy eigenvalue of
both the exact Hamiltonian and the learned PMM for the energy for complex
values of $c$. Remarkably, the PMM accurately captures the structure of the
true underlying data, despite only having access to real values of $c$ during
training. An important note is that the discontinuities near the phase
transition arise from the permutation of eigenvalues. A more sophisticated
sorting algorithm that is able to accurately track the trajectories of the
eigenvalues for complex $c$ would be needed to address this.

Figure 5: Results of training a $15\times 15$ PMM on the five lowest eneriges
of a $100$ site LMG model in the region of the phase transition. Figure 6:
Results of using the ground state eigenvector of the PMM used to learn the
energies of the LMG model to learn $\left\langle S_{x}^{2}\right\rangle/N^{2}$
in the ground state. Comparisons with the average of $100$ MLPs (dash-dotted)
and cubic spline interpolation (dotted) show the superior performance of the
PMM. The top plots show the learned (dashed) and exact (solid) values; the
bottom plots show the relative error. The main figure focuses in on the region
of the phase transition, where there was no training data. The inset shows the
full domain $0\leq c\leq 1$ with the focused region highlighted.  Figure 7:
Results of using the ground state eigenvector of the PMM used to learn the
energies of the LMG model to learn $\left\langle S_{z}^{2}\right\rangle/N$ in
the ground state. Comparisons with the average of $100$ MLPs (dash-dotted) and
cubic spline interpolation (dotted) show the superior performance of the PMM.
The top plots show the learned (dashed) and exact (solid) values; the bottom
plots show the relative error. The main figure focuses in on the region of the
phase transition, where there was no training data. The inset shows the full
domain $0\leq c\leq 1$ with the focused region highlighted.

Figure 8: Results of using the PMM trained on energies of the LMG model with
real-valued $c$ to extrapolate the ground state energy for complex valued $c$.
The left plots show the learned (bottom) and exact (top) values. The height of
the surface corresponds to the magnitude of $E_{0}$ while the color
corresponds to the argument. The right plot shows the relative error between
the exact values and the learned extrapolated values. The red contour shows
where the error is $10^{-3}$.

###  A.2 Second Trotter Extrapolation Example

We consider a quantum spin system corresponding to a one-dimensional
Heisenberg model with an antisymmetric spin-exchange term known as the
Dzyaloshinskii-Moriya (DM) interaction term [59, 60]. Such spin models have
recently attracted interest in studies of quantum coherence and entanglement
[61, 62, 63]. The Hamiltonian for this system is
$H=H_{B}+H_{J}^{0}+H_{J}^{1}+H_{D}^{0}+H_{D}^{1}$, where

$\displaystyle H_{B}$ $\displaystyle=B\sum_{i}r_{i}\sigma_{i}^{z},$ (7)
$\displaystyle H_{J}^{0|1}$ $\displaystyle=J\sum_{i\,\rm
even|odd}(\sigma_{i}^{x}\sigma_{i+1}^{x}+\sigma_{i}^{y}\sigma_{i+1}^{y}+\sigma_{i}^{z}\sigma_{i+1}^{z}),$
$\displaystyle H_{D}^{0|1}$ $\displaystyle=D\sum_{i\,\rm
even|odd}(\sigma_{i}^{x}\sigma_{i+1}^{y}-\sigma_{i}^{y}\sigma_{i+1}^{x}),$

where $r_{i}$ are random real numbers ranging from $[0,1)$. For $U(dt)$, we
use the Trotter product

$U(dt)=\mathrm{exp}\left\\{-iH_{B}dt\right\\}\mathrm{exp}\left\\{-iH_{J}^{0}dt\right\\}\mathrm{exp}\left\\{-iH_{J}^{1}dt\right\\}\mathrm{exp}\left\\{-iH_{D}^{0}dt\right\\}\mathrm{exp}\left\\{-iH_{D}^{1}dt\right\\}.$
(8)

We use a PMM with the same underlying structure,

$\displaystyle
U_{M}(dt)=\mathrm{exp}\left\\{-iM_{1}dt\right\\}\mathrm{exp}\left\\{-iM_{2}dt\right\\}\mathrm{exp}\left\\{-iM_{3}dt\right\\}\mathrm{exp}\left\\{-iM_{4}dt\right\\}\mathrm{exp}\left\\{-iM_{5}dt\right\\},$
(9)

where each of the matrices, $M_{i}$, are $5\times 5$ Hermitian matrices. We
use the values $B=J=1$, and $D=0.5$, and choose 10 values of $dt$ spanning the
range $[-0.18,-0.1]\cup[0.1,0.18]$. We have trained on the ground state, first
excited state, and second excited state for a one-dimensional chain with $N=8$
qubits and periodic boundary conditions. Using the same training data, we also
use a polynomial interpolation for positive and negative $dt$, similar to the
approach used in Ref. [52]. The results are shown in Fig. 9. We see that the
PMM is about one order of magnitude more accurate than polynomial
interpolation in predicting the lowest three energy levels at $dt=0$.
Polynomial interpolation was not able to handle the sharp avoided level
crossings involving the first and second excited states. We have therefore
allowed the polynomials to treat the level crossings as true level crossings
and not penalize the wrong ordering of energy levels. In contrast, the PMM
reproduces the avoided level crossings properly and also predicts the first
and second excited states at $dt=0$ more accurately.

Figure 9:  Results for selected energy levels in the one-dimensional
Heisenberg spin chain with nearest-neighbor and DM interaction. The first row
shows the results when polynomial interpolation was allowed to treat the level
crossings as true level crossings. By contrast, in the second row the
polynomial received the data in its original form. We show the $5\times 5$ PMM
(dashed lines, square diamonds), polynomial interpolation results (dotted
lines, squares), exact diagonalization calculation of Trotter ground-truth
(solid lines), and Trotter training data (thin diamonds). The vertical gray
line highlights $dt=0$.

###  A.3 Tensor Network PMM

While the naive complex Hermitian PMM given by

$M(\vec{c})=D+\sum_{i}c_{i}M_{i}$ (10)

yields strong results in unsupervised image clustering, it does not natively
account for the information that is shared between neighboring pixels,
resulting in an excess of training parameters.

To account for the shared information between neighboring pixels, we utilize a
variation of Eq. (10) inspired by Matrix Product States in which the elements
of the $M_{i}$ matrices are drawn from a tensor network [64]. Denoting each
$p\times q$ image by the rank-$2$ tensor $c_{ij}$ where $i=1,2,\ldots,p$ and
$j=1,2,\ldots,q$, the elements of all $M_{ij}$ matrices can be respresented as
a single rank-$3$ tensor $\mathcal{S}_{ijk}$. The index
$k=1,2,\ldots,n(n+1)/2$—where $n$ is the dimensionality of the PMM—denotes the
linear index into the upper-triangular portion of matrix $M_{ij}$ which is
sufficient to completely describe all of the parameters in the summation of
Eq. (10). This tensor yields $pqn(n+1)/2$ independent values and thus must
store $\mathcal{O}\left(pqn^{2}\right)$ elements. We decompose
$\mathcal{S}_{ijk}$ into a tensor network of three much smaller rank-$3$
tensors $\mathcal{P}$, $\mathcal{N}$, and $\mathcal{Q}$ with dimensions
$p\times d\times D$, $D\times n(n+1)/2\times D$, and $D\times d\times q$
respectively, such that

$\mathcal{S}_{ijk}=\sum_{t=1}^{d}\sum_{u,v=1}^{D}\mathcal{P}_{itu}\mathcal{N}_{ukv}\mathcal{Q}_{vtj}.$
(11)

Here $D$ and $d$ are bond dimensions. The bond dimension $d$ can be increased
(decreased) to further decouple (couple) the values of parameters in matrices
$M_{ij}$ corresponding to neighboring pixels. The bond dimension $D$ controls
the coupling of different elements within the same $M_{ij}$. The diagram
corresponding to Eq. (11) is shown in Fig. 10. This tensor network yields the
same $pqn(n+1)/2$ now-dependent values, but now only must store
$\mathcal{O}\left(dD(p+q)+D^{2}n^{2}\right)$ elements. We find that this
representation provides nearly indistinguishable results from the full
representation of the PMM, while requiring significantly fewer training
parameters.

In the example presented in Sec. 2.3 we used a tensor-network PMM with
$n=8,\,d=6,$ and $D=12$ which required only $9224$ training parameters
compared to the $28\,232$ of the full representation PMM.

$d$$\mathcal{S}$$\mathcal{P}$$\mathcal{Q}$$\mathcal{N}$$D$$D$$p$$q$$n(n+1)/2$$p$$q$$n(n+1)/2$
Figure 10: Diagrammatic representation of Eq. (11) showing the decomposition
of the full tensor $\mathcal{S}$ (left) into the three tensors $\mathcal{P}$,
$\mathcal{N}$, and $\mathcal{Q}$ (right). Legs are labeled with their
dimension.


# Inferring Restaurant Styles by Mining Crowd Sourced Photos
from User-Review Websites

Haofu Liao, Yucheng Li, Tianran Hu, Jiebo Luo  Department of Computer Science
University of Rochester
Rochester, New York 14627, USA
{hliao6, yli, thu<EMAIL_ADDRESS>
###### Abstract

When looking for a restaurant online, user uploaded photos often give people
an immediate and tangible impression about a restaurant. Due to their
informativeness, such user contributed photos are leveraged by restaurant
review websites to provide their users an intuitive and effective search
experience. In this paper, we present a novel approach to inferring restaurant
types or styles (ambiance, dish styles, suitability for different occasions)
from user uploaded photos on user-review websites. To that end, we first
collect a novel restaurant photo dataset associating the user contributed
photos with the restaurant styles from TripAdvior. We then propose a deep
multi-instance multi-label learning (MIML) framework to deal with the unique
problem setting of the restaurant style classification task. We employ a two-
step bootstrap strategy to train a multi-label convolutional neural network
(CNN). The multi-label CNN is then used to compute the confidence scores of
restaurant styles for all the images associated with a restaurant. The
computed confidence scores are further used to train a final binary classifier
for each restaurant style tag. Upon training, the styles of a restaurant can
be profiled by analyzing restaurant photos with the trained multi-label CNN
and SVM models. Experimental evaluation has demonstrated that our crowd
sourcing-based approach can effectively infer the restaurant style when there
are a sufficient number of user uploaded photos for a given restaurant.

###### Index Terms:

Restaurant styles, multi-label CNN, multi-instance multi-label learning,
social media, crowd sourcing, data mining

##  I Introduction

Nowadays, more and more people rely on user-review websites, such as
Foursquare, Yelp, and TripAdvisor, to find a restaurant, hotel or other
venues. Searching restaurants online is fast and convenient. By a single tap
on the screen, people can easily find thousands of restaurants in their
cities. For most of the recommended restaurants, the user-review websites will
usually provide much basic information, such as the price range, location,
operation hours, to their users. Apart from the basic information provided by
the websites, there are usually many user contributed photos. People can
therefore get a more intuitive impression of the restaurant by looking at the
pictures taken by other users.

Figure 1: Statistics of restaurants on TripAdvisor.

However, the basic information and user contributed photos of restaurants
cannot satisfy all the needs from users. Consider the situation that someone
wants to celebrate a wedding anniversary with his wife and has no idea which
restaurant is the best. Or he needs to schedule a dinner meeting with his
clients and wonders which restaurant is conducive for a business conversation.
Such demands from users require higher level information of the restaurant and
they are not directly available from the restaurant’s basic information. In
this paper, we refer to such higher level information as the style of
restaurant. Currently, user-review websites either contain no restaurant
styles, such as Foursquare, or rely on users feedbacks, such as TripAdvisor.
Therefore, for most of the restaurants online, such information is not
available. As shown in Figure 1, among the $34,787$ restaurants we extracted
from TripAdvisor, only $14.7\%$ of them have style tags. In this paper, we
will refer to styles and tags interchangeably. A even smaller percentage of
restaurants has user contributed photos to support the style tags. Only
$13.2\%$ of the collected restaurants data contain both photos and style tags.

Although the style tags are not commonly available from the user-review
websites, fortunately, it is possible that they can be derived from the user
contributed photos 111Note that there might be some other information exists
to help inferring restaurant style, such as the text reviews. However, in this
work, we will only focus on classifying restaurant styles using user-uploaded
photos, which have a much higher availability. For example, if we see photos
from a restaurant containing delicate dishes and romantic decorations, we can
infer that this restaurant is suitable for a wedding anniversary or
Valentine’s Day dinner. Hence, we propose a restaurant style inference method
based on the analysis of the user contributed photos in user-review websites.
There are multiple applications for the proposed system:  1) For a given
restaurant, it can estimate a collection of highly related restaurant styles
from user contributed photos;  2) It can then be used to guide user-review
sites to present more useful information of restaurants. The additional
availability of the restaurant style tags can help users to search particular
types of restaurants;  3) For a restaurant without photos, our method can be
used to present a collection of strongly related images that match the style
tags of the restaurant. Thus, the users can have a good idea about the style
of such a restaurant even without seeing the true images of the exact
restaurant;  4) The model can help the restaurants to select the best photos
to advertise their restaurant styles; and  5) The trained models can be used
by other websites and services related to restaurants.

Inferring restaurant styles from user-uploaded photos can be best described as
a multi-instance multi-label learning (MIML) problem [1] where each object
(i.e., restaurant) is described by a set of instances (i.e., user-uploaded
photos) and associated with several class labels (i.e., restaurant style
tags). Traditional MIML problems usually assume that  1) each instance
contributes equally and independently to the object’s class label;  2) or
there exists a “key” instance that contributes the object’s class label.
However, for the restaurant style classification problem such assumptions do
not hold. Instead, it is the collection of “key” instances that decide the
object’s class label. Based on such assumption, we propose a deep MIML
approach to address this problem. We train a multi-label CNN for two rounds in
a bootstrap fashion. We then use the trained multi-label CNN in combining with
a restaurant profiling algorithm to extract restaurant style features from the
collection of images of a restaurant. Next, we feed the extracted features to
a set of SVMs to obtain the restaurant style tags. Our experimental results
show that the proposed method is indeed effective in predicting the style tags
of a restaurant and a F-1 score of 0.58 is achieved.

The remainder of this paper is organized as follows. In Section II, we present
on the related work. In Section III, we introduce the procedure of data
collection and statistics of the collected dataset. The proposed framework and
detailed algorithms used in our method are described in Section IV. We
evaluate the performance of our method in Section V and conclusions are given
in Section VI.

##  II Related Work

###  II-A Related Work in Social Media

Mining data from user-review websites is popular in recent years [2, 3, 4,
Wang:2010:LAR:1835804.1835903, 5, 6]. However, only a few of them focus on
data mining on restaurants [7, 8, 9, 10, 11]. Aside from our work, which uses
visual information, most these restaurant related works only use restaurant
meta data, user reviews, or geographic information to provide restaurant
recommendations to users [9, 8, 11] and none of them is able to provide higher
level recommendations, such as restaurant styles. Other venue related works
make use of visual information to decide which venues should be recommended
[6, 12, 13, 14]. In particular, [6] uses deep neural networks to extract
useful features in images. What sets our work apart from this work is that we
focus more on the restaurant styles, which is highly abstract, while they
mainly concentrate on general and more concrete aspects of a venue.

###  II-B Related Work on Multiple Instance Multiple Label Learning

The formal definition of a MIML framework is given by Zhou et al [1]. They
proposed two ways of targeting the MIML problem:  1) Degenerating the MIML
problem to a multi-instance learning problem and solving the problem with a
multi-instance learner;  2) Degenerating the MIML problem to a multi-label
learning problem and solving the problem with a multi-label learner.  However,
existing MIML algorithms [15, 16, 17] are not applicable to our restaurant
style classification problem. [16] assumes that all the instances contribute
equally to the object’s labels. However, in our case, there are a number of
uninformative images, such as pictures of common dishes and images of the
dinning tables. They contribute very little to the restaurant’s style. [15,
16] are only feasible when the numbers of possible instances and objects are
not large. While, in our case, we need to train and test our model on a large-
scale dataset (See Table I). [17] is provably efficient to work on large
datasets. However, it assumes that the object is positive if and only if there
exists at least one positive instance. In our case, such assumption is not
guaranteed. For example, just one picture of a delicate dish does not mean the
restaurant itself is romantic.

###  II-C Related Work on Convolutional Neural Network

In recent years, deep convolutional neural networks (CNNs) have shown to be
very successful in lots of machine learning tasks. In relating to our problem,
some literatures target the multi-instance learning problems using CNNs.
Pathak et al. [18] proposed a novel multi-instance learning algorithm for
semantic segmentation using CNNs. The proposed algorithm try to learn pixel-
level semantic segmentation only based on the weak image-level labels, while
in our case we need to learn image-level labels from bag-level restaurant
labels. Wu et al. [19] showed that deep learning based multi-instance learning
can be very useful in image classification and auto-image notation. The
authors try to classify images based on a set of generated image proposals and
therefore the proposed algorithm relies heavily on the assumption that if
there exists at least one positive proposal then the image itself is positive.
However, such assumption does not hold for our restaurant classification
problem. There are some other works focus on solving multi-label learning
problems using CNNs. Wei et al. [20] proposed a deep CNN infrastructure,
called Hypotheses-CNN-Pooling, for multi-label image classification. Gong et
al. [21] investigated the choices of different loss functions on the
performance of multi-label image annotation using CNNs. However, none of these
works consider the MIML problem using CNNs, which sets our work apart from
existing CNNs algorithms.

##  III Data collection

Cities | # of Restaurants | # of Photos
---|---|---
Chicago | 7150 | 32676
Houston | 6732 | 14084
Los Angeles | 7903 | 22379
New York City | 9871 | 128657
Miami | 3131 | 19672
Total | 34787 | 217468
TABLE I: Restaurant statistics of five major US cities. Restaurant Styles From
TripAdvisor
---
Bar scene | Local cuisine
Business meeting | Romantic
Dining on a budget | Scenic view
Families with children | Special occasions
Large groups |
TABLE II: Restaurant styles in TripAdvisor.

All of our data are collected from TripAdvisor. We choose TripAdvisor because
some of its restaurants contain user labeled style tags. We can use them as
the pseudo ground truth to guide the training of a multi-label CNN, which will
be discussed in Section IV-A. However, as we have mentioned in Section I, for
most of the restaurants, the style tags are not available. Therefore, we still
need to use the trained framework in Section IV to assign them restaurant
styles based on the associated user contributed photos.

To make sure the restaurant photos we use are representative, we choose
restaurants from five major cities in the United States. A list of cities with
the number of restaurants and photos is given in Table I. In total, our data
set contains $34,787$ restaurants and $217,468$ photos. According to
TripAdvisor’s taxonomy, there are in general 9 restaurant styles. The taxonomy
of these styles is shown in Table II.

##  IV Methodology

The framework of our approach is illustrated in Figure 2. The flowchart at the
top demonstrates the training phase and the bottom represents the testing
phase. For a given restaurant, our goal is to detect a collection of
applicable restaurant styles from user contributed photos. To deal with this
MIML learning task, we adapt the idea from [1]: reducing the task to a multi-
label learning task and solving it with a multi-label learner. In a high level
view, our proposed framework extracts the features of a restaurant from a bag
of images using CNNs and then feeds the features to a series of binary SVMs to
obtain the restaurant styles.

Figure 2: Illustration of the framework of our method. Top: training phase.
Bottom: testing phase.

In the training phase, we build a multi-label CNN that can infer the style
features represented by the collection of user-contributed photos from a
restaurant. For each photo, the multi-label CNN outputs a vector of scores
where each score indicates the confidence of the photo relating to a
restaurant style. The score vectors will be used to obtain the style features
of a restaurant. However, due to the multi-instance learning nature of our
problem, the challenge we face is that we do not have individually labeled
photos for direct training. The only information we have is the style tags of
the restaurants, which are supplied by users (and can be noisy). To solve this
problem, we propose to train the multi-label CNN for two rounds in a bootstrap
fashion. As illustrated in Figure 2, the first round CNN plus the pseudo
tagging algorithm is used to estimate the labels of each image in the
restaurant. Then, we train the second round CNN based on the labeled images
and use this CNN to extract restaurant style features in the test phase.
Notice that there is no need to train for the third round (or even further).
As we will then train and test on the same dataset and there will not be any
performance gain using the pseudo tagging algorithm.

In the first round, we aggressively initialize the tags of each photo
according to its restaurant style tags, i.e., all the images from the same
restaurant will have the same style tags as the restaurant. Note that such
assignment of tags may result lots of false positives and negatives. Based on
our observations, most of the false positives and negatives relate to
uninformative images. They frequently appear across restaurants and contain no
information that indicate specific styles. Those uninformative images are not
considered as noise for the multi-label CNN, as their contribution to each
restaurant styles will be canceled out during the optimization process of the
training. In the cases that false positives and negatives are actually
informative images, the multi-label CNN training may be degraded by those
images. However, such cases are not frequent, otherwise the tags of the
corresponding restaurants would be changed. Therefore, in general the
assignments of photos with their restaurant’s tags are reasonable and the
trained multi-label CNN classifier should give us good estimates of labels of
individual images. The output of our multi-label CNN is a $9$-dimension score
vector, where each score represents the weight of the image on the
corresponding tag. We will discuss more details of the structure of the multi-
label CNN model in Section IV-A and a set of top scored photos is shown in
Figure 4.

Figure 3: The probability relation between photo scores and restaurant styles.
Given a photo with a score $x$ on tag $t$ greater than $s$, the probability of
its restaurant has a style $t$ is denoted by $P(A_{t}|x>s)$. Given a photo
with a score $x$ on tag $t$ less than $s$, the probability of its restaurant
has no style $t$ is denoted by $P(\overline{A_{t}}|x<s)$. Here, the scores of
photos are computed from the first round multi-label CNN. $P(A_{t}|x>s)$ and
$P(\overline{A_{t}}|x<s)$ for each tag are calculated using Equations (4) and
(5).

Before training the multi-label CNN for the second round, we use a pseudo
tagging algorithm to relabel the tags of each image in the training set.
Basically, this algorithm takes the scores of each image as an indicator of
being relevant to the tags and remove the presumably false negatives and
positives accordingly. The details of this algorithm are given in section
IV-B. There are two reasons that we need this algorithm and the second round
multi-label CNN. First, the pseudo tagging algorithm can remove some
incorrectly labeled informative images and thus can improve the performance of
the second round multi-label CNN. Second, the pseudo tagging algorithm rewards
higher scored images and punishes lower scored images by adding and removing
the corresponding tags. Thus, the outputs of the second round multi-label CNN
will be more sensitive to those images that have higher similarity with the
top scored images in the training set. Such a sensitivity would be helpful to
extract better restaurant features in the restaurant profiling phase. Based on
the scores of images, we extract the features of each restaurant using the
restaurant profiling algorithm, which we shall discuss more details in Section
IV-C. We then train $9$ binary classifiers using SVM, and the outputs of the
classifiers give the tags of the restaurants.

Finally, in the testing phase, we use the entire collection of photos from a
restaurant as the input. Next, compute their scores using the second round
multi-label CNN model. For each label, we extract the restaurant’s features
using the top-$k$ scores and use the output of the SVM classifiers to derive
the restaurant styles.

###  IV-A Multi-label CNN

####  IV-A1 Test

As we have discussed in the previous section, our approach uses the multi-
label CNN to evaluate each image of a restaurant. The multi-label CNN outputs
the score vectors that will be further used to obtain the style features of a
restaurant. Here, each score indicates the confidence of the photo being
related to a restaurant style.

Formally put, let $\mathbf{X}_{i}$ and $\mathbf{Y}_{i}$ denote the images and
the associated tags, respectively. The associated tags
$\mathbf{Y}_{i}=[y_{i}^{1},y_{i}^{2},\dots,y_{i}^{L}]^{T}$ is a binary vector,
where

$y_{i}^{t}=\begin{cases}1,\text{if tag }t\text{ belongs to }\mathbf{X}_{i},\\\
0,\text{otherwise.}\end{cases}$ (1)

and $L$ is the total number of tags (in this work $L=9$). Due to its high
capacity and flexibility, CNN has become a common framework to learn image
representation that adapts to specific domains [22]. CNN maps images
$\mathbf{X}_{i}$ to a feature space with multiple layers of convolution,
pooling, non linear activations and fully connected layers. The final layer of
the architecture is designed to output the label confidence scores with
respect to the image. Let
$\mathbf{S}_{i}=[s_{i}^{1},s_{i}^{2},\dots,s_{i}^{L}]^{T}$ denotes the score
vector with respect to $\mathbf{X}_{i}$. A proper loss function
$l(\mathbf{S}_{i},\mathbf{Y}_{i})$ is designed over the score vector
$\mathbf{S}_{i}$ to learn the weights $\theta$ in the CNN architecture using
stochastic gradient descent (SGD),

$\theta:=\theta-\alpha\sum_{i}\nabla_{\theta}l(\mathbf{S}_{i},\mathbf{Y}_{i};\theta),$
(2)

where $\theta$ denotes the network parameters to be learned from the training
dataset and $\alpha$ is the learning rate for the optimization algorithm. We
use the cross entropy sigmoid loss function [23, Chapter 3] as our form of
$l(\mathbf{S}_{i},\mathbf{Y}_{i})$,

$l(\mathbf{S}_{i},\mathbf{Y}_{i})\triangleq\sum_{t}y_{i}^{t}\sigma(s_{i}^{t})+(1-y_{i}^{t})(1-\sigma(s_{i}^{t})),$
(3)

where $\sigma$ is the sigmoid function $\sigma(x)=1/(1+\exp(-x))$ which
transforms label confidence into probabilities. The objective of (3) is to
maximize the confidence of the labels in the target $\mathbf{Y}_{i}$ and
suppress those not in the target $\mathbf{Y}_{i}$. From (3), we compute the
gradients of the loss function with respect to the label confidence
$\mathbf{S}_{i}$, which is used to compute
$\nabla_{\theta}l(\mathbf{S}_{i},\mathbf{Y}_{i};\theta)$ for the stochastic
gradient descent algorithm by applying chain rules. This process is also
called backpropagation.

###  IV-B Pseudo Tagging

As mentioned in Section IV, we do not have the ground truth of the individual
training images. Therefore, we use the first round multi-label CNN combined
with the pseudo tagging algorithm to estimate the labels of the training
images. The pseudo tagging algorithm is based on the following assumption:

  * •

Images with the highest scores are likely to be related to the tag and images
with the lowest scores are likely to be unrelated to the tag.

This assumption is based on the analysis and observation that the first round
multi-label CNN training in general provides a good indication of being
relevant to the tags. It can be further verified using the following
conditional probabilities. Let $A_{t}$ be the event that a given style tag $t$
should be assigned to the restaurant $A$ and $x$ be the confidence score of an
image. Thus, given that an image has the score $x$ greater than $s$, the
probability of event $A_{t}$ can be estimated by

$P(A_{t}|x>s)=\frac{C(A_{t},x>s)}{C(x>s)}.$ (4)

Here, $C(A_{t},x>s)$ is the number of images whose restaurant tag is $t$ and
have a score on $t$ greater than $s$. $C(x>s)$ is the total number of images
whose score on $t$ is greater than $s$. Note that we do not aggregate images
from the same restaurant yet as we only focus on the score effectiveness of
individual images. As long as we have the scores of training images from the
first round multi-label CNN. $C(A_{t},x>s)$ and $C(x>s)$ can be easily
counted. Similarly, we can estimate $P(\overline{A_{t}}|x<s)$ by

$P(\overline{A_{t}}|x<s)=\frac{C(\overline{A_{t}},x<s)}{C(x<s)}.$ (5)

where $\overline{A_{t}}$ denotes the event that tag $t$ is not assigned to
restaurant $A$. The probability distribution of $P(A_{t}|x>s)$ and
$P(\overline{A_{t}}|x<s)$ among the training photos is shown in Figure 3. In
the left figure, we can see that in general when the score of a photo is high
on a tag, then it is very possible that its restaurant will also be assigned
to this tag. Similarly, in the right figure, those lower scored images on tag
$t$ are more likely coming from restaurants without style $t$. Detailed
discussion of this experimental result is given in Section V-A.

Let $\mathbf{X}_{m,n}$ be the $m$th image of the $n$th restaurant in the
training set,
$\mathbf{S}_{m,n}=[s_{m,n}^{1},s_{m,n}^{2},\dots,s_{m,n}^{L}]^{T}$ be the
score vector with respect to $\mathbf{X}_{m,n}$, and
$\mathbf{Y}_{m,n}=[y_{m,n}^{1},y_{m,n}^{2},\dots,y_{m,n}^{L}]^{T}$ be the
binary label vector associated with $\mathbf{X}_{m,n}$, where

$y_{m,n}^{t}=\begin{cases}1,\text{ if tag }t\text{ belongs to
}\mathbf{X}_{m,n},\\\ 0,\text{ otherwise.}\end{cases}$ (6)

and $L$ is the total number of possible tags in the dataset. The score vector
$\mathbf{S}_{m,n}$ can be obtained from the multi-label CNN which we trained
in the first round. Since $s_{m,n}^{t}$ denotes the confidence of assigning
tag $t$ to $\mathbf{X}_{m,n}$ and a higher score denotes a higher confidence,
we can estimate the binary label vector $\mathbf{Y}_{m,n}$ using
$\mathbf{S}_{m,n}$. To this end, we propose the following algorithm:

1.

Initialize all the images in the training set with their restaurant tags,
i.e., $\forall m,n$, $\mathbf{Y}_{m,n}=\mathbf{Y}_{n}$, where $\mathbf{Y}_{n}$
denotes the binary label vector of the $n$th restaurant.

2.

For each image $\mathbf{X}_{m,n}$ in the training set, compute their score
vector $\mathbf{S}_{m,n}$ using the multi-label CNN.

For

each tag $t$ do

3.

Pick the image $\mathbf{X}_{a,b}$ that has the highest score $s_{a,b}^{t}$
among all the images that do not have tag $t$ and assign $t$ to
$\mathbf{X}_{a,b}$, i.e., pick

$a,b=\operatorname*{arg\,max}_{m,n}\\{s_{m,n}^{t}\mid y_{m,n}^{t}=0\\}$ (7)

and set $y_{a,b}^{t}=1$.

4.

Pick the image $\mathbf{X}_{c,d}$ that has the lowest score $s_{c,d}^{t}$
among all the images that have tag $t$ and remove $t$ from $\mathbf{X}_{c,d}$,
i.e., pick

$c,d=\operatorname*{arg\,min}_{m,n}\\{s_{m,n}^{t}\mid y_{m,n}^{t}=1\\}$ (8)

and set $y_{c,d}^{t}=0$.

5

If $s_{a,b}^{t}-s_{c,d}^{t}>const$, go to step $3$.

End for

Here, in step $3$ and $4$, each time we only alter the tag of the image that
has the highest possibility that it was incorrectly labeled. For example, in
step $3$, the algorithm searches the image that does not have tag $t$ but has
a relatively high confidence score on $t$ (the highest among all the images
that are not labeled with $t$). As such an image is very likely to be
incorrectly labeled, we flip its label (from $0$ to $1$). Therefore, in
general, this algorithm will yield a better estimation of the tags in each
iteration.

In each iteration of the inner-loop, the confidence scores on tag $t$ of image
$\mathbf{X}_{a,b}$ and $\mathbf{X}_{c,d}$ will keep on decreasing and
increasing, respectively. This is because we always flip the tags of images
with highest (in step $3$) or lowest (in step $4$) confidence scores. When the
difference of $s_{a,b}^{t}$ and $s_{c,d}^{t}$ becomes very small, the multi-
label CNN has a low confidence in classifying $\mathbf{X}_{a,b}$ and
$\mathbf{X}_{c,d}$ correctly. In this case, image $\mathbf{X}_{a,b}$ and
$\mathbf{X}_{c,d}$ are actually uninformative images. Since the flipping of
tags of $\mathbf{X}_{a,b}$ and $\mathbf{X}_{c,d}$ will not help us distinguish
the informative images, we should then stop the label estimation with respect
to tag $t$ and move on to the next tag. Note that as we only want to find the
informative images of each restaurant, those incorrectly labeled uninformative
images will not degrade the performance of the multi-label CNN and that is why
we call this algorithm pseudo tagging. The parameter $const$ in the stop
condition of step $5$ is chosen empirically based on the score distribution of
the uninformative images. The pseudo tagged photos are used to train the
multi-label CNN for the second round. The image scores computed by the second
round CNN will then be used for restaurant profiling.

Figure 4: Top scored photos. From top to bottom rows: Family with children,
romantic, bar scene, business meetings, dining on a budget, large groups,
local cuisine, scenic view, special occasions.

###  IV-C Restaurant Profiling

To infer the styles of a restaurant, we need to extract the restaurant
features from a collection of photos. However, for a restaurant with a given
style, not all the photos are necessarily related to this style. In fact, in
most of the cases, only a small portion of the images will be useful. For
example, for a “bar scene” style, we are usually looking for glasses or
bottles of wine, bar counters, and dark scenes with a group of people drinking
alcohol. Therefore, images of regular dishes or foods will not contribute much
to our decision. However, usually most of the user contributed photos are
related to the dishes themselves instead of the “bar scene”. To this end, we
design a restaurant profiling algorithm, which is based on the following
assumption:

  * •

The tag of a restaurant is determined by a number of informative images. If a
restaurant is labeled with a certain tag, there must be a number of images
that are highly related to this tag.

Based on this assumption, we use the photo scores computed by the multi-label
CNN as an indicator of informativeness. As a higher score means a higher
possibility an image is relevant to a tag, top scored images always have a
better chance that they are the informative images. Thus, we pick the top-$k$
scored images as the candidates of the informative images and choose their
scores as the extracted features on a given tag. Here, $k$ denotes the number
of the photos we choose to treat as the informative images of a restaurant. We
will discuss more about the choice of $k$ in Section V-C.

Formally put, let
$\mathbf{G}_{n}^{t}=[s_{1,n}^{t},s_{2,n}^{t},\dots,s_{M_{n},n}^{t}]^{T}$ be
the score vector of the $n$th restaurant with respect to tag $t$, where
$s_{m,n}^{t}$, $m\in\\{1,\dots,M_{n}\\}$, denotes the confidence score of
image $\mathbf{X}_{m,n}$ with respect to tag $t$. $M_{n}$ is the total the
number of images in the $n$th restaurant. Thus, following the discussion
above, we can use the $k$-largest elements of $\mathbf{G}_{n}^{t}$ as the
feature vector of the $n$th restaurant on tag $t$. We denote such feature
vector as $\mathbf{F}_{n}^{t}$. Then, for each tag $t$, we can train a binary
classifier $C^{t}$ using any linear discriminative model, such as SVM. The
procedure of the algorithm is given in Algorithm 1. Here, $L$ is the total
number of the tags and $N$ is the total number of restaurants in the training
set.

Algorithm 1 Restaurant profiling algorithm

1:procedure Restaurant Profiling($k$)

2: for $n\in\\{1,2,\dots,N\\}$ do

3: for $m\in\\{1,2,\dots,M_{n}\\}$ do

4: $\mathbf{S}_{m,n}\leftarrow$ compute the score vector of image
$\mathbf{X}_{m,n}$

5: end for

6: end for

7: for $t\in\\{1,2,\dots,L\\}$ do

8: for $n\in\\{1,2,\dots,N\\}$ do

9:
$\mathbf{G}_{n}^{t}\leftarrow[s_{1,n}^{t},s_{2,n}^{t},\dots,s_{M_{n},n}^{t}]^{T}$

10: $\mathbf{F}_{n}^{t}\leftarrow$ $k$-largest elements of
$\mathbf{G}_{n}^{t}$

11: end for

12:
$\mathbf{F}^{t}\leftarrow\\{\mathbf{F}_{1}^{t},\mathbf{F}_{2}^{t},\dots,\mathbf{F}_{N}^{t}\\}$

13: $C^{t}\leftarrow$ train a binary classifier using $\mathbf{F}^{t}$

14: end for

15: $\mathbf{C}\leftarrow\\{C^{1},C^{2},\dots,C^{L}\\}$

16: return $\mathbf{C}$

17:end procedure

##  V Experimental Results

In our experiments, we choose the restaurants that contains both user
contributed photos and user labeled tags for training and testing. Among the
$34,787$ restaurants we tracked, $4,573$ satisfy this requirement. We use
5-fold cross-validation for training and testing. In the training phase,
$113,550$ photos are used to train the multi-label CNN models. We use the BVLC
Caffe deep learning framework [24] to perform all the CNN training and
testing. For hyper parameters, we follow the standard practice on ImageNet
challenges[25], i.e., batch size $=256$, learning rate $=0.001$, momentum
$=0.9$ and weight decay $=5e-06$. The network is fine tuned from the Alexnet
[22], which was the early winning entry of the ImageNet challenges and
considered adequate for this study (although other network structures may
provide marginal improvements). The optimization converges after $5$ epochs.
GPUs are used to accelerate our experiments.

(a) Bar scene

(b) Local cuisine

Figure 5: Distributions of image scores on the “bar scene” and “local cuisine”
tags. First column: image scores computed from the first round multi-label
CNN. Second column: image scores computed from the second round multi-label
CNN. Negative photos are those photos without the “bar scene”/“local cuisine”
tag. Positive photos are those photos tagged with “bar scene”/“local cuisine”
tags.

###  V-A Performance of Multi-label CNN

For an input image, the multi-label CNN model will output a vector of scores
where each element as the score of the corresponding tag. Ideally, for an
image that is strongly related to the style tag $t$, our multi-label CNN
should output a relatively high score on $t$. On the other hand, if an image
is irrelevant to the tag $t$, then its corresponding score from CNN should be
relatively low. Figure 4 shows some top scored images of different restaurant
styles. Not surprisingly, photos with a higher score on the “family with
children” style mostly contain fast foods or snacks, which are very popular
among children. Those photos that receive the top scores on the “romantic”
style usually contain delicate dishes or desserts, which are favored by
lovers. Finally, for the “bar scene” style, top scored images are often dark
with neon lights and contain people drinking wine or beer. Top scored photos
in other rows also show strong relations to their corresponding tags. It is
also very interesting to observe that the top scored images of “romantic”,
“business meetings”, and “special occasions” styles are very similar. It is
reasonable as a restaurant, which is good for “special occasions”, is usually
also a good place for “romantic” scenes or “business meetings”.

There are also some interesting mistakes. The last image of the second row
just contains some fruits. However, our multi-label CNN gives it a relative
high score on the “romantic” tag. The reason for this situation is that in
most of the cases, a “romantic” photo contains some delicate food that placed
in a big white plate. It looks like the multi-label CNN has learned that in
general a photo with “romantic” tag should have a white background. Hence, the
fruit image gets a high score on the “romantic” tag. Another mistake can be
found in the last two images of the “bar scene” row. Apparently, these two
images only contain the logos of the restaurants and are not related to the
“bar scene”. The reason for this mistake is that these two restaurants are
“bar scene” restaurants and lots of photos contain the logos of these two
restaurants in our training set. Therefore, the logos are learned by the
multi-label CNN to the extent that images containing such logos will get a
high score on the “bar scene” tag.

To further evaluate the performance of the multi-label CNN, we use the two
conditional probability equations discussed in Section IV-B. The basic idea of
using these two equations is if we see an image with a very high score on a
certain tag $t$, then it is very possible that the image’s corresponding
restaurant has a style $t$. Similarly, if an image get a very low score on tag
$t$, then it is unlikely that the corresponding restaurant has a style $t$.
For Equation (4), we compute $P(A_{t}|x>s)$ by counting the proportion of the
images whose restaurant has a style $t$ among all the images with a score
greater than $s$. For different values of $s$, we calculate the conditional
probability $P(A_{t}|x>s)$ and the final probability distribution is given in
Figure 3. We can see from the left figure that when the score $x$ on a tag $t$
is high, the probability $P(A_{t}|x>s)$ is also very high. This observation is
consistent with our assumption. A similar analysis can also be applied to
Equation (5). Therefore, we can conclude that the trained multi-label CNN
performs well as expected on our dataset.

Styles | Baseline | Proposed Method
---|---|---
Rec(%) | Prec(%) | F-1 score(%) | Rec(%) | Prec(%) | F-1 score(%)
Bar scene | 100.00 | 36.69 | 53.68 | 80.39 | 48.81 | 60.74
Business meeting | 37.21 | 84.21 | 51.61 | 76.74 | 52.38 | 62.26
Dining on a budget | 11.76 | 100.00 | 21.05 | 94.12 | 35.56 | 51.61
Families with children | 100.00 | 67.15 | 80.35 | 77.17 | 86.59 | 81.61
Large groups | 71.67 | 39.45 | 50.89 | 58.33 | 50.72 | 54.26
Local cuisine | 3.85 | 33.33 | 6.90 | 69.23 | 48.65 | 57.14
Romantic | 17.24 | 100.00 | 29.41 | 89.66 | 35.14 | 50.49
Scenic view | 14.29 | 100.00 | 25.00 | 71.43 | 17.86 | 28.57
Special occasions | 37.04 | 80.00 | 50.63 | 90.74 | 68.06 | 77.78
Average | 43.67 | 71.20 | 41.06 | 78.65 | 49.31 | 58.27
TABLE III: Performance of the baseline method and the proposed method on
different style tags. Here, we choose $k^{\prime}=3$ and the minimum number of
photos is $50$. Note that the F-1 scores have improved across all the styles
due to the proposed method.

###  V-B Performance of Pseudo Tagging

As we have discussed in Section V-A, the photo scores output by the first
round multi-label CNN are good indicators of the style tags. As shown in
Figure 3, the first round multi-label CNN performs very well when the score is
very high or very low. However, when the score of an image falls in the
middle, it is difficult to tell whether it belongs to the style tag or not.

Figure 5 shows the score distributions before and after using the pseudo
tagging algorithm. Here, the first row shows the image score distributions of
the “bar scene” tag. The second row shows the image score distributions of the
“local cuisine” tag. The figures in the first column show the distributions of
image scores computed from the first round multi-label CNN. For the “bar
scene” tag, most of the images have a score between $1$ and $2$ while the
positive and negative images are mixed together. It means for images with
scores between $1$ and $2$, the first round multi-label CNN model cannot
distinguish their styles. This is also the case for the “local cuisine” tag.
After applying the pseudo tagging algorithm to our training set, we train the
multi-label CNN for the second round and the distributions of the computed
image scores are shown in the second column of Figure 5. We can find that in
this case negative and positive images do not mix as much as before, which
means the second round multi-label CNN has a better performance in
distinguishing the styles of images. Therefore, the binary classifier training
in the restaurant profiling algorithm can benefit significantly from the
better separated score distributions. We can also see that our pseudo tagging
algorithm helps in separating the score distribution of the “local cuisine”
tag. That is why there is a much improved performance gain for the “local
cuisine” tag in Table III.

###  V-C Overall Performance

To show the performance gain from the pseudo tagging and the restaurant
profiling algorithm, we also establish a baseline for comparison. For the
baseline method, we only train the multi-label CNN once and assign
top-$k^{\prime}$ scored tags to photos. If more than a half of the photos are
assigned a particular tag, the restaurant is determined to be labeled as such.

In our experiments, we test the performance of the baseline method and our
proposed method on a variety of choices of $k^{\prime}$ and $k$. We notice
that the more photos a restaurant have, the more information about the
restaurant’s styles we can extract. Therefore, we also set different minimum
numbers of photos to restaurants in the test set. The performances of the two
methods with the best parameter settings are given in Table III. Following the
evaluation methods in [26, 16], we use recall, precision, and F-1 measure as
the metrics to evaluate the performances of the two methods on different style
tags. We can see from Table III that, in general, the proposed method performs
much better than the baseline method. It means that the pseudo tagging and the
restaurant profiling algorithms play a key role in improving the performance
of the proposed method. An interesting finding here is that the “scenic view”
style has a very low precision. A closer look at the dataset finds that there
are a number of the restaurants contain outdoor images. But those restaurants
cannot be considered as typical “scenic view” style restaurant and are not
labeled with the “scenic view” tag.

We also investigate the performance differences of our proposed method when
choosing different parameter settings. From Figure 6, we can find that the
choice of $k$ does not affect the performance much. However, when we choose
the restaurants with a higher minimum number of photos the performance gets
better. It means when the number of photos of a restaurant is high, our
proposed method can achive more accurate estimates of the restaurant styles.

Figure 6: The average f-measure scores of our method when choosing different
$k$ and minimum numbers of photos.

##  VI Conclusions

We have presented a novel approach to profiling restaurant styles directly
from user uploaded photos on user-review sites. We propose to build a deep
MIML framework to deal with the special problem setting of restaurant style
classification. Due to the absence of individual photo tags, we initially
train the multi-label CNN using photos labeled with all the restaurant tags
supplied by users. We then refine the photo tags using our pseudo tagging
algorithm and train the multi-label CNN for a second round. Experiments show
that the multi-label CNN performs very well in inferring the restaurant
styles, and the pseudo tagging algorithm plays a key role in helping the
multi-label CNN to distinguish different restaurant styles. Finally, the
photo-level style estimates are used by the restaurant profiling algorithm to
train a binary classifier for each style tags using SVM. Our experimental
results show that our approach has achieved a significant performance gain due
to the pseudo tagging and restaurant profiling algorithms. We also show that
when the number of photos of a restaurant increases, the performance of our
approach increases as well.

## Acknowledgment

We gratefully acknowledge the support from the University, New York State
through the Goergen Institute for Data Science, and our corporate sponsors
Xerox and Yahoo.

## References

  * [1] Z. hua Zhou and M. ling Zhang, “Multi-instance multi-label learning with application to scene classification,” in _Advances in Neural Information Processing Systems 19_ , B. Schölkopf, J. C. Platt, and T. Hoffman, Eds. MIT Press, 2007, pp. 1609–1616.
  * [2] A. Noulas, S. Scellato, N. Lathia, and C. Mascolo, “Mining user mobility features for next place prediction in location-based services,” in _Data Mining (ICDM), 2012 IEEE 12th International Conference on_ , Dec 2012, pp. 1038–1043.
  * [3] Z. Cheng, J. Caverlee, K. Lee, and D. Z. Sui, “Exploring millions of footprints in location sharing services.” _ICWSM_ , vol. 2011, pp. 81–88, 2011.
  * [4] Q. Yuan, G. Cong, Z. Ma, A. Sun, and N. M. Thalmann, “Time-aware point-of-interest recommendation,” in _Proceedings of the 36th International ACM SIGIR Conference on Research and Development in Information Retrieval_ , ser. SIGIR ’13. New York, NY, USA: ACM, 2013, pp. 363–372.
  * [5] A. Ghose, P. G. Ipeirotis, and B. Li, “Designing ranking systems for hotels on travel search engines by mining user-generated and crowdsourced content,” _Marketing Science_ , vol. 31, no. 3, pp. 493–520, 2012.
  * [6] J. Zahálka, S. Rudinac, and M. Worring, “New yorker melange: Interactive brew of personalized venue recommendations,” in _Proceedings of the 22Nd ACM International Conference on Multimedia_ , ser. MM ’14. New York, NY, USA: ACM, 2014, pp. 205–208.
  * [7] L. Mui, P. Szolovits, and C. Ang, “Collaborative sanctioning: Applications in restaurant recommendations based on reputation,” in _Proceedings of the Fifth International Conference on Autonomous Agents_ , ser. AGENTS ’01. New York, NY, USA: ACM, 2001, pp. 118–119.
  * [8] H.-W. Tung and V.-W. Soo, “A personalized restaurant recommender agent for mobile e-service,” in _e-Technology, e-Commerce and e-Service, 2004. EEE ’04. 2004 IEEE International Conference on_ , March 2004, pp. 259–262.
  * [9] B.-H. Lee, H.-N. Kim, J.-G. Jung, and G.-S. Jo, “Location-based service with context data for a restaurant recommendation,” in _Database and Expert Systems Applications_. Springer, 2006, pp. 430–438.
  * [10] L.-M. Liu, S. Bhattacharyya, S. L. Sclove, R. Chen, and W. J. Lattyak, “Data mining on time series: an illustration using fast-food restaurant franchise data,” _Computational Statistics & Data Analysis_, vol. 37, no. 4, pp. 455 – 476, 2001.
  * [11] Y. Fu, B. Liu, Y. Ge, Z. Yao, and H. Xiong, “User preference learning with multiple information fusion for restaurant recommendation.” in _SDM_. SIAM, 2014, pp. 470–478.
  * [12] S. Rudinac, A. Hanjalic, and M. Larson, “Generating visual summaries of geographic areas using community-contributed images,” _Multimedia, IEEE Transactions on_ , vol. 15, no. 4, pp. 921–932, June 2013.
  * [13] C. Kofler, L. Caballero, M. Menendez, V. Occhialini, and M. Larson, “Near2me: An authentic and personalized social media-based recommender for travel destinations,” in _Proceedings of the 3rd ACM SIGMM International Workshop on Social Media_ , ser. WSM ’11. New York, NY, USA: ACM, 2011, pp. 47–52.
  * [14] A.-J. Cheng, Y.-Y. Chen, Y.-T. Huang, W. H. Hsu, and H.-Y. M. Liao, “Personalized travel recommendation by mining people attributes from community-contributed photos,” in _Proceedings of the 19th ACM International Conference on Multimedia_ , ser. MM ’11. New York, NY, USA: ACM, 2011, pp. 83–92.
  * [15] Z.-J. Zha, X.-S. Hua, T. Mei, J. Wang, G.-J. Qi, and Z. Wang, “Joint multi-label multi-instance learning for image classification,” in _Computer Vision and Pattern Recognition, 2008. CVPR 2008. IEEE Conference on_ , June 2008, pp. 1–8.
  * [16] Z.-H. Zhou, M.-L. Zhang, S.-J. Huang, and Y.-F. Li, “Multi-instance multi-label learning,” _Artificial Intelligence_ , vol. 176, no. 1, pp. 2291 – 2320, 2012.
  * [17] S.-J. Huang and Z.-H. Zhou, “Fast multi-instance multi-label learning,” _arXiv preprint arXiv:1310.2049_ , 2013.
  * [18] D. Pathak, E. Shelhamer, J. Long, and T. Darrell, “Fully convolutional multi-class multiple instance learning,” _CoRR_ , vol. abs/1412.7144, 2014\.
  * [19] J. Wu, Y. Yu, C. Huang, and K. Yu, “Deep multiple instance learning for image classification and auto-annotation,” in _2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2015, pp. 3460–3469.
  * [20] Y. Wei, W. Xia, J. Huang, B. Ni, J. Dong, Y. Zhao, and S. Yan, “CNN: single-label to multi-label,” _CoRR_.
  * [21] Y. Gong, Y. Jia, T. Leung, A. Toshev, and S. Ioffe, “Deep convolutional ranking for multilabel image annotation,” _CoRR_ , vol. abs/1312.4894, 2013\.
  * [22] A. Krizhevsky, I. Sutskever, and G. E. Hinton, “Imagenet classification with deep convolutional neural networks,” in _Advances in neural information processing systems_ , 2012, pp. 1097–1105.
  * [23] M. A. Nielsen, _Neural Networks and Deep Learning_. Determination Press, 2015.
  * [24] Y. Jia, E. Shelhamer, J. Donahue, S. Karayev, J. Long, R. Girshick, S. Guadarrama, and T. Darrell, “Caffe: Convolutional architecture for fast feature embedding,” _arXiv preprint arXiv:1408.5093_ , 2014.
  * [25] O. Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpathy, A. Khosla, M. Bernstein, A. C. Berg, and L. Fei-Fei, “ImageNet Large Scale Visual Recognition Challenge,” _International Journal of Computer Vision (IJCV)_ , vol. 115, no. 3, pp. 211–252, 2015.
  * [26] O. Yakhnenko and V. Honavar, “Multi-instance multi-label learning for image classification with large vocabularies,” in _Proceedings of the British Machine Vision Conference_. BMVA Press, 2011, pp. 59.1–59.12.