# Complex matter field universal models with optimal scaling for solving
combinatorial optimization problems

Natalia G. Berloff1,2<EMAIL_ADDRESS>1Department of Applied
Mathematics and Theoretical Physics, University of Cambridge, Cambridge CB3
0WA, United Kingdom  2Skolkovo Institute of Science and Technology, Bolshoy
Boulevard 30, bld.1, Moscow, 121205, Russian Federation  Department of Applied
Mathematics and Theoretical Physics, University of Cambridge, Cambridge CB3
0WA, United Kingdom

###### Abstract

We develop a universal model based on the classical complex matter fields that
allow the optimal mapping of many real-life NP-hard combinatorial optimisation
problems into the problem of minimising a spin Hamiltonian. We explicitly
formulate one-to-one mapping for three famous problems: graph colouring, the
travelling salesman, and the modular N-queens problem. We show that such a
formulation allows for several orders of magnitude improvement in the search
for the global minimum compared to the standard Ising formulation. At the same
time, the amplitude dynamics escape from the local minima.

Introduction. A vast majority of real-life optimisation problems are
computationally impractical for conventional classical computers as the number
of operations grows exponentially fast with the number of variables for such
problems. Technological capabilities are hindered by the available computing
resources required to solve such problems within relevant timescales subject
to other constraints such a power consumption. Quantum computing is widely
recognised as a potential solution; however, many technological challenges
need to be overcome for this approach to become relevant for real-life
problems such as mission control, dynamical analysis of financial markets,
prediction of new chemical materials, machine learning, etc.

Technological demands, classical computing limitations and development of
quantum computing hardware and algorithms have inspired the development of
promising new algorithmic and novel unconventional analogue hardware
techniques that, on the one hand, avoid the technical challenges facing
quantum computing while, at the same time, offering significant advantages
over classical computing. The analog hardware based on lasers lasers ;
nirprl2017 ; Babaeian2019 , optical parametric oscillators (OPOs) McMahon2016
; Takata2016 ; Inagaki2016 , microring resonators Tezak2019 , polaritons
BerloffNatMat2017 ; kalinin2020polaritonic ; kalinin2018networks , photonic
systems Pierangeli2019 ; cen2020microwave , photonic integrated circuits
prabhu2019recurrent , photon condensates leonetti2021optical , confocal cavity
QEDs marsh2020enhancing , opto-electronic systems Chou2019 ; Boehm2019 , etc.
emulates interacting dynamical systems that, at their steady-state, give
solution to an optimization task.

The key to such opportunity lies in the universality of a particular
formulation. For instance, mathematically, it is possible to reformulate
optimisation problems from vastly different areas into the problem of finding
the ground state of a particular – universal – spin Hamiltonian with discrete
or continuous degrees of freedom. The minimum of such a spin Hamiltonian can
be found by a given simulator or by a special-purpose built analogue device,
capable of incorporating the principle that drives the dynamical system to a
high-quality solution of that optimisation task.

A particular and well-elucidated spin system is the Ising model on a graph
that attracts most attention since a big range of hard discrete combinatorial
optimization problems, e.g. travelling salesman, graph colouring, graph
partitioning, etc. can be mapped into it with a polynomial overhead Lucas2014
. It is known that the Ising model is universal DelasCuevas2016  and many
special-built computing devices (FPGAs, ASICs, etc.) are based on emulating
classical Ising Hamiltonians toshiba ; Tsukamoto2017 ; bohm2021not . For
instance, the Ising model can be minimised by the original Hopfield dynamical
networks Hopfield1985  and many enhancements and modifications were proposed
HopfieldModification1990 ; krotov2018dense ; krotov2020large . Many of the
physical emulators of the Ising Hamiltonians have, at their core, the
operation described by the Hopfield networks cai2020power ;
kalinin2022computational .

The main obstacle in using the available purpose-built devices to solve real-
life problems lies in driving to larger scales. Existing analogue hardware
demonstrates that performance gains diminish exponentially as the number of
interacting elements in the dynamical systems increases. When a combinatorial
optimisation problem is embedded into the Ising Hamiltonian minimisation, the
number of dynamical system elements typically grows at least as $O(N^{2})$
where $N$ is the number of the original variables. The consequences of this
increase, although polynomial, are vast. First, the quadratic increase in the
number of variables increases the physical demands on the number of spins in
the systems. Second, it requires increased analogue control precision for the
increased number of elements in the dynamical systems. Third, it further
drives the complexity of the optimisation landscape by increasing its
dimensionality and roughness. Such inefficiency currently forces the
corresponding circuit resources to grow according to a high-order power law in
the problem size.

It necessitates that we develop the techniques where the dynamical system
requirements grow (ideally) linearly with the number of problem variables.
This is the question and challenge that this Letter addresses.

To start, let’s look at where the overhead occurs. It occurs when the states
of the original variable cannot be represented as one binary number. For
example, in the travelling salesman optimisation task, each city is associated
with the order it is visited on the route. If one has $N$ cities, there are
$N$ possible orders to visit each of the cities, giving an $N^{2}$ number of
spins to represent the solution and $N^{2}$ number of dynamical equations to
deal with. A vertex takes one of the possible $n$ colours for the graph
colouring task. The N-queen problem requires $N^{2}$ spins to represent the
chessboard squares.

The (at least) quadratic increase in the number of variables (and, therefore,
in the dynamical equations or the dynamic elements in the system) is not the
only problem. The analogue hardware has a lot of other limitations, such as
those related to the topology of the dynamical systems. The type of
interactions, the graph connectivity, how finely the interactions need to be
controlled, and the range of the couplings play a significant role in the
machine performance or for the class of problems that can be efficiently
mapped to the analogue hardware. In the Ising mapping of combinatorial
problems, the constraints on the number of cities (for the travelling salesman
problems), on the number of available colours (for the graph colouring
problem), on the number of queens (in the $N$-queens problem) should come as a
strict constraint. It means that the corresponding value of the coupling
matrix has to be much larger than other coupling terms. Unfortunately, none of
the current optimisers can deal with vastly varying coupling strengths.

In this Letter, we propose a paradigmatic shift in mapping and problem
representation for the analogue implementation of optimisation problems. It
allows a linear (actually, one-to-one) mapping for the hard optimisation
problems. It employs complex matter field representation leading to what we
refer to as Complex matter Field Hamiltonian formulation (CFH).

A key function. First of all, we would like to switch to the complex domain
for the elements of our system. We shall think of each element of the
computing system (”bit”) as an oscillator described by the complex field
$\psi_{i}$ with two degrees of freedom: the amplitude, $a_{i}$, and the phase,
$\theta_{i}$. This description lies at the core of the physical optical
optimisers (OO) such as lasers, OPOs, polaritons, photons, etc. At the end of
the search for the solution, the oscillator’s state is represented by the
phase $\theta_{i}$, while the amplitudes are used to modify (anneal) the
target function. The Ising problem on a graph $G=(V,E)$ with vertices $V$ and
edges $E$ with weights $W$ consists of finding the global minimum (GM) of the
classical Ising Hamiltonian $H_{I}=-\sum_{i,j\neq i}W_{ij}s_{i}s_{j},$ where
$s_{i}=\\{\pm 1\\}.$ Quantum annealers such as D-Wave deal directly with
$H_{I}$ as the target Hamiltonian. The specialised chip devices based on FPGAs
or ASIC implement the matrix-vector multiplication and nonlinearity necessary
to project continuous variables onto $\pm 1$ to represent $H_{I}$ bohm2021not
. OOs aim at finding GM of

$H_{G}=-\frac{1}{2}\sum_{i,j\neq i}W_{ij}(\psi_{i}\psi_{j}^{*}+c.c).$ (1)

If a degenerate excitation, second-order harmonic generation, or a resonant
pumping limits the values of the phases to $\theta_{i}=0$ or $\pi$ and the
amplitudes are brought to $a_{i}=1,$ then $H_{G}=H_{I}.$ If each phase is free
to take any value in $[0,2\pi)$ (and $a_{i}=1$), then $H_{G}$ coincides with
the classical XY Hamiltonian. In OO, the search for GM is based on a gain-
dissipative dynamics kalinin2018global  driven by the principle of minimum
power dissipation where the amplitude constraints can be included as the
Lagrange multipliers vadlamani2020physics , while the special purpose
programmable chips may use threshold function for that. For instance, in the
Coherent Ising machine, each Ising spin corresponds to a degenerate OPO that
is described by a dynamics equation for the complex amplitude of the signal
field $\psi_{i}$:

$\frac{d\psi_{i}}{dt}=\gamma(t)\psi_{i}^{*}-\psi_{i}-|\psi_{i}|^{2}\psi_{i}-\frac{\delta
H_{G}}{\delta\psi_{i}^{*}},$ (2)

where the dynamics are defined by an increasing gain $\gamma$ and nonlinear
losses are normalised. For polariton condensates or degenerate lasers, the
dynamical equations are

$\frac{d\psi_{i}}{dt}=(\gamma(t)-|\psi_{i}|^{2})\psi_{i}-iU_{0}|\psi_{i}|^{2}\psi_{i}-\frac{\delta
H_{G}}{\delta\psi_{i}^{*}}+h(t)\psi_{i}^{*},$ (3)

where $U_{0}$ is the strength of the self-interactions and $h(t)$ is the
strength of the resonant excitation (if present). Eqs. (2) and (3) should be
complemented by the processes that bring the amplitudes to one. The Hopfield
networks realised by many physical platforms ramsauer2020hopfield  explicitly
use phases $0$ and $\pi$, so the signal becomes real while amplitudes are
projected into $\pm 1$ with dynamics that can be written as

$\displaystyle\frac{dRe[\psi_{i}]}{dt}$ $\displaystyle=$
$\displaystyle-\frac{\partial H_{H}}{\partial Re[\psi_{i}]},$
$\displaystyle\quad H_{H}$ $\displaystyle=$ $\displaystyle-\sum_{i,j\neq
i}W_{ij}g_{j}-\gamma(t)\sum_{i=1}^{N}\int_{0}^{g_{i}}g^{-1}(x)\,dx,$ (4)

where e.g. $g(x)={\rm sgn}(x)$ or $g(x)=\tanh(lx),$ with some $l=l(t)$
increasing with time and $g_{i}=g(Re[\psi_{i}])$. The gradient descent used in
these dynamical systems can be accelerated, for instance, by momentum as in
the Toshiba bifurcation FPGA toshiba  or by many other acceleration
techniques.

So far, we have seen that the physical optimizer performs a variant of the
gradient descent. However, the heterogeneity of the amplitudes allows the
system to do more than just find the nearest local minima. During the time
evolution, heterogeneity of the amplitudes allows ”anneal” so to effectively
tunnel between local minima in search of a lower-lying state or even for the
actual GM. The details of the anneal schedules $\gamma(t),h(t),l(t),$ the
structure of the projector $g(x)$ or the Lagrange multipliers for the
amplitude’s constraint, as well as the scheme of the gradient descent all play
an essential role in the performance of the solver. In this Letter, we propose
a new set of basic operations and a universality structure associated with
them, that dramatically reduces the number of the oscillators required to
represent the original combinatorial problems while keeping the advantage
offered by varying amplitudes in the search for the high-quality solution.

We show the construction by illustration. We start with the graph coloring
problem: given $k$ different colors and a graph $G=(V,E)$, how to color each
vertex in the graph with a specific color, such that no edge connects two
vertices of the same color? The Ising representation for this problem requires
$kN$ spins and takes form $H_{GC}=\sum_{v\in
V}(1-\sum_{c=1}^{k}x_{vc})^{2}+\sum_{(uv)\in E}\sum_{c=1}^{k}x_{uc}x_{vc},$
where $x_{vc}=(1+s_{vc})/2$ Lucas2014 . The spin $s_{vc}=1$ if vertex $v$ is
colored with color $c$ and is $-1$ otherwise. The first term in $H_{GC}$ is
the constraint (in the form of a penalty) on having a single color for each
vertex, the second penalises if two vertices connected by an edge have the
same color. Instead, we associate a single oscillator $\psi_{v}$ with each
vertex and encode the color associated with that vertex into $k$ discrete
values of the phase $\theta_{v}=\\{0,2\pi/k,4\pi/k,...,2\pi(k-1)/k\\}.$ The
constraint on having a single color per each vertex is naturally satisfied
with this representation. To express the second penalty we need to introduce a
function that returns a positive value when $\psi_{v}$ and $\psi_{u}$
connected by an edge have the same phases (are colored the same) and is zero
otherwise. Finally, there has to be a constraint leading to the discrete
values of phases. We can take care of both conditions by observing that
$\phi_{k}(\theta)\equiv|1+\exp[i2\theta]+\exp[i3\theta]+...\exp[i(k-1)\theta]|^{2}=|(1-\exp[ik\theta])/(1-\exp[i\theta])|^{2}=\sin^{2}(k\theta/2)/\sin^{2}(\theta/2)$,
so that $\phi_{k}(0)=k^{2}$, has the property that $\phi_{k}(i2j\pi/k)=0,$ if
integer $j\neq 0,$ and takes positive values otherwise. The objective
Hamiltonian replacing Eq. (1) for graph coloring problem becomes

$\widetilde{H_{GC}}=\sum_{(vu)\in
E}\Phi_{k}(\psi_{v},\psi_{u}),\quad\Phi_{k}(\psi_{v},\psi_{u})\equiv\biggl{|}\frac{1-(\psi_{v}\psi_{u}^{*})^{k}}{1-\psi_{v}\psi_{u}^{*}}\biggr{|}^{2}.$
(5)

The functional $\Phi_{k}(\psi_{u},\psi_{v})$ defined in Eq. (5) becomes the
main building block of our CFH basis.

Figure 1: Mapping for the two combinatorial problems discussed in the main
text: graph colouring (top row) and the modular $N$-queens problem (bottom
row). The solutions to the problems are shown in (a). (b) depicts the Ising
formulation of these problems where each vertex of the graph colouring problem
is mapped into three Ising spins, and each board square of the N-queens
problem is mapped into one Ising spin. (c) depicts the CFH formulation where
each vertex colour is mapped into one discrete phase $\\{0,2\pi/3,4\pi/3\\}$
for the graph colouring problem. The position of each queen is mapped into a
single discrete phase $\\{0,2\pi/5,4\pi/5,6\pi/5,8\pi/5\\}.$ Figure 2: The
structures of the Hamiltonian in different representations of the modular
$N$-queens problem. The Monte Carlo simulations assisted by the
Broyden–Fletcher–Goldfarb–Shanno quasi-Newton method are used to elucidate the
structure of the Ising (Eq. (8) (a) and the CFH (Eq. (9) (b) Hamiltonians for
$N=5$ and $a_{i}=1$. We use $10,000$ random initial conditions to find the
minimum. The statistics of the minima found is given for the Ising (a) and CFH
(b) formulations. The success probability of finding the GM is more than $1/5$
for the CFH, whereas the Ising formulation of the same problem is two orders
of magnitude lower with $0.0023$. The CFH also has a large spectral gap
separating the GM from the first excited state. For the Ising formulation we
used its continuous representation with $x_{ij}=(\cos(\theta_{ij})+1)/2$ and
the penalty $M\sum_{ij}\cos(2\theta_{ij})$ to project phases onto $0$ and
$\pi$ added to $H_{Q}.$ The optimal parameters for minimisation were found and
used as $B=2$, $M=1$.

Travelling salesman problem is another famous NP-hard problem that searches
for the Hamiltonian cycle in the graph $G=(V,E),$ $|V|=N$, such that the sum
of the weights, $w_{uv}$ of each edge in the cycle is minimized. The Ising
formulation of this problem is Lucas2014

$\displaystyle H_{TS}$ $\displaystyle=$ $\displaystyle
A\sum_{v=1}^{N}(1-\sum_{i=1}^{N}x_{vi})^{2}+A\sum_{i=1}^{N}(1-\sum_{v=1}^{N}x_{vi})^{2}$
(6) $\displaystyle+$ $\displaystyle\sum_{u,v\neq
u}W_{uv}\sum_{i=1}^{N}x_{ui}x_{vi+1},$

where $x_{vi}=1$ if the vertex labeled $v$ is visited in the step $i$. We
assumed a cycle notation $N+1=1$ and introduced $W_{uv}=w_{uv}$ if $(uv)\in E$
and $W_{uv}={\bar{w}}>\max(w_{uv})$ if $(uv)\nin E$. Total $N^{2}$ spins are
required for the mapping into the Ising formulation. To fulfil the constraints
(each vertex and each order appear exactly once), we have to take
$A\gg{\bar{w}},$ which leads to a large spread of the coefficients that
hinders minimisation success.

Instead, we associate one oscillator $\psi_{v}$ with each vertex (requires $N$
oscillators). The objective to minimise becomes

$\widetilde{H_{TS}}=\sum_{u,v\neq u}W_{uv}\Phi_{N}(\psi_{u},\psi_{v}\times
e^{i\frac{2\pi}{N}}).$ (7)

In the last example, we consider the $N-$queens problem that tasks placing $N$
queens on an $N$x$N$ chessboard in non-attacking positions (queens attack
along rows, columns, and diagonals). The variations of this problem (with
blocked diagonals or some queens already placed on the board) is an NP-hard
problem gent2017complexity . It is a straightforward exercise to introduce
such variations into the formulation, so we will not consider them here for
brevity. We also formulate our representation for the queen’s placement on the
doubly periodic board (so-called modular $N$-queens problem). The Ising
formulation requires $N^{2}$ spins: $s_{ij}=1$ if there is a queen in the
$i-$th row and $j-$th column and $-1$ otherwise. The Hamiltonian in the Ising
formulation torggler2019quantum  reads

$H_{Q}=B(N-\sum_{i=1}^{N}\sum_{j=1}^{N}x_{ij})^{2}++\sum_{ijkl=1}^{N}W_{ijkl}x_{ij}x_{kl},$
(8)

where the weights are $W_{ijkl}=1$ if the squares $(ij)$ and $(kl)$ are on the
same diagonal, row or column and zero otherwise. The first term is the
constraint on the number of queens with $B\gg 1$. With the growth in $N$,
coupling strengths in the matrix of interactions grow as $BN$, leading to a
vast difference in coupling strengths between the terms.

In CFH representation, we associate one oscillator $\psi_{k}$ with the queen
in the $k-$th row, so the constraint on the number of queens is naturally
satisfied and the Hamiltonian becomes

$\displaystyle\widetilde{H_{Q}}$ $\displaystyle=$
$\displaystyle\sum_{j=1,k>j}^{N}\Phi_{N}(\psi_{k},\psi_{j})+\sum_{j=1,k\neq
j}^{N}\Phi_{N}(\psi_{k}e^{i\frac{2\pi(k-j)}{N}},\psi_{j})$ (9)
$\displaystyle+$
$\displaystyle\Phi_{N}(\psi_{k},\psi_{j}e^{i\frac{2\pi(k-j)}{N}}).$

Figure 1 illustrates the differences in Ising and CFH representations for the
graph coloring problem Fig. (1)(top row) and the modular N-queens problem Fig.
(1)(bottom row).

Figure 3: Time evolution of the target landscape with amplitudes assisting the
search for the GM. The inset shows the projection of the target Hamiltonian
$\widetilde{H_{Q}}$ of Eq. (9) with $a_{i}=1$ for $N=5$ to the plane with
$\theta_{1}=0,\theta_{2}=6\pi/5,\theta_{3}=2\pi/5,\theta_{4}=8\pi/5$, so only
$\theta_{5}$ remains to be found. The optimal value is at $\theta_{5}=4\pi/5$,
however, if the initial point is chosen as $\theta_{5}=7\pi/5$ (marked ”A” in
the inset), the gradient descent ($A\rightarrow B\rightarrow C\rightarrow D$)
brings it to the excited state with $\theta_{5}=7\pi/5$. However, the
amplitudes change the structure of the function to be minimised. On the main
graph we show $\widetilde{H_{Q}}$ of Eq. (9) with
$\theta_{1}=0,\theta_{2}=6\pi/5,\theta_{3}=2\pi/5,\theta_{4}=8\pi/5$ but this
time the amplitudes are not $1$, instead they are changing gradually. Starting
with the same point as in the inset $\theta_{5}=7\pi/5$, the gradient decent
brings the solution to the true GM. The graphs shown corresponds to
$a_{1}=1,a_{2}=0.5,a_{3}=0.9,a_{4}=0.4,a_{5}=0.4$ (blue),
$a_{1}=1,a_{2}=0.7,a_{3}=0.9,a_{4}=0.4,a_{5}=0.55$ (orange),
$a_{1}=1,a_{2}=0.75,a_{3}=0.95,a_{4}=0.45,a_{5}=0.6$ (green). The gradient
decent follows $A\rightarrow B\rightarrow C\rightarrow D\rightarrow
E\rightarrow F$ route to the GM.

When the original problem is mapped into a universal Hamiltonian, the
dynamical system can be tuned to find the solution, so Eqs. (2, 3, 4) etc. can
be employed with the CFH formulations reflected by
$\widetilde{H_{GC}},\widetilde{H_{TS}},\widetilde{H_{Q}}$ replacing the Ising
Hamiltonians $H_{G}$ or $H_{H}$. The effectiveness of the search for the
solution depends on the structure and parameters of the dynamical system
employed, however, it is correlated with the structure of the target
Hamiltonian. We compare the target Ising Hamiltonians given by Eq. (8) with
the CFH defined by Eq. (9) with $|\psi_{k}|^{2}=1$ for all $k$ using the Monte
Carlo simulations. Figure (2) summarizes our findings showing that CFH
formulation brings two orders of magnitude improvement over the Ising
formulation even for small to moderate tasks, while this advantage is bound to
grow exponentially for larger tasks. Figure (3) illustrates the importance of
the amplitude dynamics in finding the GM.

The mapping of $N$ states into the discrete values of the phase becomes
problematic as $N$ grows. There is a limit on the precision with which the
phases can be measured for the physical implementation. Also, the discrepancy
between the values of $\Phi$ at zero and on non-discrete phase values
increases with $N$, hindering the algorithmic performance. This problem can be
overcome by associating two or more oscillators with each vertex and mapping
$N$ states of the vertex into the discrete phases of oscillators representing
each state. For instance, let’s assume that only $p$ discrete values of the
phase can be experimentally resolved. In this case, we can encode $N$ states
into $\lfloor\log_{p}N\rfloor$ oscillators. When the Ising formulation
requires $N^{2}$ spins (and $N^{2}$ dynamical equation in OO), the CFH
requires only $\lfloor\log_{p}N\rfloor N$ oscillators and dynamical equations.
The effect of this modification on the Hamiltonian structure and performance
will be considered elsewhere.

Discussion.We proposed a complex field Hamiltonian mapping that allows
overcoming the power-law scaling of the Ising Hamiltonian mapping that is
typical for real-life problems. Such CFHs are universal (any NP problem can be
mapped into them) and consist of a well defined set of the operations
described by the function $\Phi_{k}(\psi_{i},\psi_{j})$ of Eq. (5) and may
require the implementation of the phase shifts
$\psi\rightarrow\psi\exp[i\theta]$ for some $\theta$. The dramatic reduction
in the number of variables is accompanied by an improved structure of the
Hamiltonian suitable to various OO dynamical implementations. The annealing of
the amplitudes allows the transition away from the local minima in the search
for a high quality (low energy) solution.

## References

  * (1) L. Bao, N.-H. Kim, L. J. Mawst, N. N. Elkin, V. N. Troshchieva, D. V. Vysotsky, and A. P. Napartovich, “Near-diffraction-limited coherent emission from large aperture antiguided vertical-cavity surface-emitting laser arrays,” Applied physics letters, vol. 84, no. 3, pp. 320–322, 2004.
  * (2) V. Pal, C. Tradonsky, R. Chriki, A. A. Friesem, and N. Davidson, “Observing dissipative topological defects with coupled lasers,” Physical review letters, vol. 119, no. 1, p. 013902, 2017.
  * (3) M. Babaeian, D. T. Nguyen, V. Demir, M. Akbulut, P.-A. Blanche, Y. Kaneda, S. Guha, M. A. Neifeld, and N. Peyghambarian, “A single shot coherent ising machine based on a network of injection-locked multicore fiber lasers,” Nature communications, vol. 10, no. 1, pp. 1–11, 2019.
  * (4) P. L. McMahon, A. Marandi, Y. Haribara, R. Hamerly, C. Langrock, S. Tamate, T. Inagaki, H. Takesue, S. Utsunomiya, K. Aihara, et al., “A fully programmable 100-spin coherent ising machine with all-to-all connections,” Science, vol. 354, no. 6312, pp. 614–617, 2016.
  * (5) K. Takata, A. Marandi, R. Hamerly, Y. Haribara, D. Maruo, S. Tamate, H. Sakaguchi, S. Utsunomiya, and Y. Yamamoto, “A 16-bit coherent ising machine for one-dimensional ring and cubic graph problems,” Scientific reports, vol. 6, p. 34089, 2016.
  * (6) T. Inagaki, Y. Haribara, K. Igarashi, T. Sonobe, S. Tamate, T. Honjo, A. Marandi, P. L. McMahon, T. Umeki, K. Enbutsu, et al., “A coherent ising machine for 2000-node optimization problems,” Science, vol. 354, no. 6312, pp. 603–606, 2016.
  * (7) N. Tezak, T. Van Vaerenbergh, J. S. Pelc, G. J. Mendoza, D. Kielpinski, H. Mabuchi, and R. G. Beausoleil, “Integrated coherent ising machines based on self-phase modulation in microring resonators,” IEEE Journal of Selected Topics in Quantum Electronics, vol. 26, no. 1, pp. 1–15, 2019.
  * (8) N. G. Berloff, M. Silva, K. Kalinin, A. Askitopoulos, J. D. Töpfer, P. Cilibrizzi, W. Langbein, and P. G. Lagoudakis, “Realizing the classical xy hamiltonian in polariton simulators,” Nature materials, vol. 16, no. 11, p. 1120, 2017.
  * (9) K. P. Kalinin, A. Amo, J. Bloch, and N. G. Berloff, “Polaritonic xy-ising machine,” Nanophotonics, vol. 9, no. 13, pp. 4127–4138, 2020.
  * (10) K. P. Kalinin and N. G. Berloff, “Networks of non-equilibrium condensates for global optimization,” New Journal of Physics, vol. 20, no. 11, p. 113023, 2018.
  * (11) D. Pierangeli, G. Marcucci, and C. Conti, “Large-scale photonic ising machine by spatial light modulation,” Physical Review Letters, vol. 122, no. 21, p. 213902, 2019.
  * (12) Q. Cen, T. Hao, H. Ding, S. Guan, Z. Qin, K. Xu, Y. Dai, and M. Li, “Microwave photonic ising machine,” arXiv preprint arXiv:2011.00064, 2020.
  * (13) M. Prabhu, C. Roques-Carmes, Y. Shen, N. Harris, L. Jing, J. Carolan, R. Hamerly, T. Baehr-Jones, M. Hochberg, V. Čeperić, et al., “A recurrent ising machine in a photonic integrated circuit,” arXiv preprint arXiv:1909.13877, 2019.
  * (14) M. Leonetti, E. Hörmann, L. Leuzzi, G. Parisi, and G. Ruocco, “Optical computation of a spin glass dynamics with tunable complexity,” Proceedings of the National Academy of Sciences, vol. 118, no. 21, 2021.
  * (15) B. P. Marsh, Y. Guo, R. M. Kroeze, S. Gopalakrishnan, S. Ganguli, J. Keeling, and B. L. Lev, “Enhancing associative memory recall and storage capacity using confocal cavity qed,” arXiv preprint arXiv:2009.01227, 2020.
  * (16) J. Chou, S. Bramhavar, S. Ghosh, and W. Herzog, “Analog coupled oscillator based weighted ising machine,” Scientific reports, vol. 9, no. 1, pp. 1–10, 2019.
  * (17) F. Böhm, G. Verschaffelt, and G. Van der Sande, “A poor man’s coherent ising machine based on opto-electronic feedback systems for solving optimization problems,” Nature communications, vol. 10, no. 1, pp. 1–9, 2019.
  * (18) A. Lucas, “Ising formulations of many np problems,” Frontiers in Physics, vol. 2, p. 5, 2014.
  * (19) G. De las Cuevas and T. S. Cubitt, “Simple universal models capture all classical spin physics,” Science, vol. 351, no. 6278, pp. 1180–1183, 2016\.
  * (20) H. Goto, K. Tatsumura, and A. R. Dixon, “Combinatorial optimization by simulating adiabatic bifurcations in nonlinear hamiltonian systems,” Science advances, vol. 5, no. 4, p. eaav2372, 2019.
  * (21) S. Tsukamoto, M. Takatsu, S. Matsubara, and H. Tamura, “An accelerator architecture for combinatorial optimization problems,” Fujitsu Sci. Tech. J, vol. 53, no. 5, pp. 8–13, 2017.
  * (22) F. Böhm, T. Van Vaerenbergh, G. Verschaffelt, and G. Van der Sande, “Not all ising machines are created equal: choice of nonlinearity induces order-of-magnitude differences in computational performance,” in Photonics in Switching and Computing, pp. M2B–4, Optical Society of America, 2021.
  * (23) J. J. Hopfield and D. W. Tank, ““neural” computation of decisions in optimization problems,” Biological cybernetics, vol. 52, no. 3, pp. 141–152, 1985.
  * (24) S. V. Aiyer, M. Niranjan, and F. Fallside, “A theoretical investigation into the performance of the hopfield model,” IEEE transactions on neural networks, vol. 1, no. 2, pp. 204–215, 1990.
  * (25) D. Krotov and J. Hopfield, “Dense associative memory is robust to adversarial inputs,” Neural computation, vol. 30, no. 12, pp. 3151–3167, 2018.
  * (26) D. Krotov and J. Hopfield, “Large associative memory problem in neurobiology and machine learning,” arXiv preprint arXiv:2008.06996, 2020.
  * (27) F. Cai, S. Kumar, T. Van Vaerenbergh, X. Sheng, R. Liu, C. Li, Z. Liu, M. Foltin, S. Yu, Q. Xia, et al., “Power-efficient combinatorial optimization using intrinsic noise in memristor hopfield neural networks,” Nature Electronics, vol. 3, no. 7, pp. 409–418, 2020.
  * (28) K. P. Kalinin and N. G. Berloff, “Computational complexity continuum within ising formulation of np problems,” Communications Physics, vol. 5, no. 1, pp. 1–10, 2022.
  * (29) K. P. Kalinin and N. G. Berloff, “Global optimization of spin hamiltonians with gain-dissipative systems,” Scientific reports, vol. 8, no. 1, pp. 1–9, 2018.
  * (30) S. K. Vadlamani, T. P. Xiao, and E. Yablonovitch, “Physics successfully implements lagrange multiplier optimization,” Proceedings of the National Academy of Sciences, vol. 117, no. 43, pp. 26639–26650, 2020.
  * (31) H. Ramsauer, B. Schäfl, J. Lehner, P. Seidl, M. Widrich, T. Adler, L. Gruber, M. Holzleitner, M. Pavlović, G. K. Sandve, et al., “Hopfield networks is all you need,” arXiv preprint arXiv:2008.02217, 2020\.
  * (32) I. P. Gent, C. Jefferson, and P. Nightingale, “Complexity of n-queens completion,” Journal of Artificial Intelligence Research, vol. 59, pp. 815–848, 2017.
  * (33) V. Torggler, P. Aumann, H. Ritsch, and W. Lechner, “A quantum n-queens solver,” Quantum, vol. 3, p. 149, 2019.


# Studying quantum algorithms for particle track reconstruction in the LUXE
experiment

Lena Funcke1 Tobias Hartung2,3 Beate Heinemann4,5 Karl Jansen6 Annabel Kropf4
Stefan Kühn2 Federico Meloni4 David Spataro4 Cenk Tüysüz6,7 and Yee Chinn Yap4
1 Center for Theoretical Physics, Co-Design Center for Quantum Advantage, and
NSF AI Institute for Artificial Intelligence and Fundamental Interactions,
Massachusetts Institute of Technology, 77 Massachusetts Avenue, Cambridge, MA
02139, USA  2 Computation-Based Science and Technology Research Center, The
Cyprus Institute, 20 Kavafi Street, 2121 Nicosia, Cyprus  3 University of
Bath, Claverton Down, Bath BA2 7AY, UK  4 Deutsches Elektronen-Synchrotron
DESY, Notkestr. 85, 22607 Hamburg, Germany  5 Physikalisches Institut, Albert-
Ludwigs-Universität Freiburg, Hermann-Herder-Str. 3a, 79104 Freiburg, Germany
6 Deutsches Elektronen-Synchrotron DESY, Platanenallee 6, 15738 Zeuthen,
Germany  7 Institüt für Physik, Humboldt-Universität zu Berlin, Newtonstr. 15,
12489 Berlin, Germany<EMAIL_ADDRESS>
Preprint number: MIT-CTP/5399, DESY-22-027

###### Abstract

The LUXE experiment (LASER Und XFEL Experiment) is a new experiment in
planning at DESY Hamburg, which will study Quantum Electrodynamics (QED) at
the strong-field frontier. In this regime, QED is non-perturbative. This
manifests itself in the creation of physical electron-positron pairs from the
QED vacuum. LUXE intends to measure the positron production rate in this
unprecedented regime by using, among others, a silicon tracking detector. The
large number of expected positrons traversing the sensitive detector layers
results in an extremely challenging combinatorial problem, which can become
computationally very hard for classical computers. This paper presents a
preliminary study to explore the potential of quantum computers to solve this
problem and to reconstruct the positron trajectories from the detector energy
deposits. The reconstruction problem is formulated in terms of a quadratic
unconstrained binary optimisation. Finally, the results from the quantum
simulations are discussed and compared with traditional classical track
reconstruction algorithms.

##  1 Introduction

LUXE [1] is a proposed experiment at DESY with the aim to study QED in the
strong-field regime where QED becomes non-perturbative. The experiment uses
the high-energy electron beam from the European XFEL and a high-power laser.
Both the interactions of the electron beam with the laser and the interactions
of a beam of bremsstrahlung photons with the laser are studied. The two
processes of interest are the Compton scattering process of a photon radiated
from the electron in the laser field,

$e^{-}+n\gamma_{L}\rightarrow e^{-}+\gamma,$ (1)

where $n$ is the number of laser photons $\gamma_{L}$ participating in the
process, and the Breit-Wheeler pair creation

$\gamma+n\gamma_{L}\rightarrow e^{+}+e^{-}$ (2)

from the interaction of a photon (which can be the photon from the Compton
process) in the laser field.

An important parameter that characterises these interactions is $\xi$, the
laser field intensity parameter, defined as

$\xi=\sqrt{4\pi\alpha}\,\,\frac{\epsilon_{L}}{\omega_{L}m_{e}}=\frac{m_{e}\epsilon_{L}}{\omega_{L}\epsilon_{cr}},$
(3)

where $\alpha$ is the fine structure constant, $\epsilon_{L}$ is the laser
field strength, $\omega_{L}$ is the frequency of the laser, $m_{e}$ is the
electron mass, and $\epsilon_{cr}$ is the critical field strength, also known
as the Schwinger limit.

##  2 Experimental setup

The experimental setup of LUXE in the e-laser mode is shown in Figure 2. In
this setup, the electron beam is guided to the interaction point (IP), where
it collides with the laser beam. The initial phase-0 of the experiment will
use a 40 TW laser, whereas phase-1 will utilise an upgraded laser power of 350
TW. The electrons and positrons produced in these interactions are deflected
by a magnet and then detected in a variety of detectors. The tracking study
presented here concerns mainly positrons, which are detected using a silicon
pixel tracking detector. The tracker consists of 4 layers, each comprising two
$\approx 27$ cm long staves placed next to each other, which overlap
partially, as illustrated in the figure. Each stave contains nine sensors,
which each is made up of $512\times 1024$ pixels of size $27\times
29~{}{\mu\textrm{m}}^{2}$.

One of the main measurements at LUXE is the positron flux as a function of the
laser field intensity parameter $\xi$ over a large range of $\xi$ values. The
positron flux is especially relevant for the e-laser case to measure the
Breit-Wheeler pair creation rate without the huge electron beam background.
The number of positrons per bunch crossing as a function of $\xi$ spans over
ten orders of magnitude, as shown in Figure 2. The two main tracking
challenges maintain good linearity up to very high multiplicity and keep a
very low background rate below $10^{-3}$ per bunch crossing at low $\xi$. To
cope with these challenges, we investigate the potential use of quantum
computing in track reconstruction. A review of various quantum computing
algorithms studied for charged particle tracking can be found in Ref. [2].

Figure 1:  Schematic layout of LUXE for the e-laser setup. Reproduced from
Ref. [1].

Figure 2: Number of positrons per bunch crossing produced in the e-laser and
$\gamma$-laser set-ups for phase-0 and phase-1, as a function of the laser
field intensity parameter $\xi$ defined in Eq. (3). Reproduced from Ref. [1].

##  3 Data sets and selection

Simulated data sets are used in this study. The positrons resulting from the
signal interactions at the IP, generated using a custom Monte Carlo code named
PTARMIGAN [3], are propagated through the dipole magnet and tracking detector
using a simplified simulation. In this simulation, four detection layers
without gap or overlap are considered and the complexity (position resolution,
multiple scattering, etc.) of the simulation can be tuned.

The data set used here corresponds to the e-laser phase-1 setup with $\xi$
values ranging from 3 to 7, and with positron multiplicities between 800 and
500,000. In this study, the tracking problem is limited to the 500 tracks
closest to the beamline, such that the size of the problem remains constant
but the complexity, due to increasing track density, increases with $\xi$.

The starting point for the tracking is either doublets or triplets, defined as
a set of two or three hits in consecutive detector layers. A pre-selection is
applied on the initial doublet or triplet candidates to reduce the
combinatorial candidates while keeping the efficiency at around 100%. Doublets
are formed first, after applying a pre-selection based on the expected angles
from the knowledge of the geometry. Triplets are subsequently constructed by
combining doublet candidates with the requirement on the maximum angle
difference of the doublet pairs allowed by multiple scattering in the
detector. Since triplets consist of three hits, they are formed from either
the first to the third layer or from the second to the fourth layer.

##  4 Methodology

###  4.1 Classical benchmark

A tracking based on A Common Tracking Software (ACTS) toolkit [4] with the
combinatorial Kalman Filter (CKF) technique for track finding and fitting is
used as a benchmark. In this classical tracking method, track finding starts
from seeds, which are the triplets formed from the first three detector
layers. An initial estimate of track parameters is obtained from the seed and
is used to predict the next hit and is updated progressively, with the
measurement search performed at the same time as the fit. Finally, after the
track finding and fitting procedures, an ambiguity-solving step is applied to
remove tracks with shared hits from the initial track collection.

###  4.2 Graph neural network

Another tracking method explored in this study is based on a graph neural
network (GNN) [5, 6]. The graph is constructed from doublets, where the hits
are nodes and the connections between hits are edges. All nodes of consecutive
layers are connected and only the ones that satisfy the pre-selection criteria
are kept. Alternating EdgeNetwork and NodeNetwork are applied in the model,
such that the model adaptively learns with each iteration which hit
connections are important. A hybrid quantum-classical version of the GNN-based
tracking also exists [7], but is not explored in this work.

###  4.3 Quantum approach

In the quantum approach to tracking, the correct pairs of triplet candidates
(where one triplet has hits from the first three layers and the other triplet
has hits from the last three layers), which can be combined to form tracks,
are identified using a quadratic unconstrained binary optimisation (QUBO),
similar to Ref. [8]. The QUBO is expressed as the objective function

$O=\sum_{i}^{N}\sum_{j<i}b_{ij}T_{i}T_{j}+\sum_{i=1}^{N}a_{i}T_{i},$ (4)

where $T_{i}$ and $T_{j}$ are triplets, $T_{i},T_{j}\in\\{0,1\\}$, and $a_{i}$
and $b_{ij}$ are coefficients.

Minimising the QUBO is equivalent to finding the ground state of a
Hamiltonian, as explained below. The linear term of the QUBO weighs the
individual triplets by their quality quantified by the coefficient $a_{i}$.
The quadratic term expresses the interactions between triplet pairs, where the
coefficient $b_{ij}$ characterises the compatibility. The coefficient $b_{ij}$
is positive if the triplets are in conflict, negative if they are compatible
to form a track, and zero otherwise.

The QUBO in Eq. (4) can be mapped to an Ising Hamiltonian and solved using the
Variational Quantum Eigensolver (VQE) in Qiskit [9]. VQE is a hybrid quantum-
classical algorithm to find the minimum eigenvalue of a Hamiltonian. The Ising
Hamiltonian

$\mathcal{H}=-\sum_{n=1}^{N}\sum_{m<n}\bar{b}_{nm}\sigma_{n}^{x}\sigma_{m}^{x}-\sum_{n=1}^{N}\bar{a}_{n}\sigma_{n}^{x}$
(5)

has a similar form to the QUBO. An exact solution using the Numpy Eigensolver
is available and used as a benchmark. For the VQE, noise is disabled in this
study and a simple entangled TwoLocal ansatz with $R_{Y}$ gates and a circular
CNOT entangler is chosen, as shown in Figure 3. The selected optimiser is
Constrained Optimization by Linear Approximation (COBYLA).

Figure 3: Layout of the variational quantum circuit using the TwoLocal ansatz
with $R_{Y}$ gates and a circular CNOT entangling pattern. For simplicity,
only four qubits are shown.

To solve the QUBO, the number of required qubits is determined by the number
of triplet candidates. Due to the limited number of qubits available, the QUBO
in this work is split into sub-QUBOs of size 7 to be solved iteratively.

Figure 4 shows a sketch of the QUBO solving process. An initial binary vector
is defined by randomly assigning the values {0,1} to the triplet candidates.
The vector is sorted in order of impact, which is assessed by the change in
the value of the QUBO when a bit flip is performed. The splitting into sub-
QUBOs is done by partitioning the sorted vector into sub-QUBO size. After the
sub-QUBOs are solved, the solution is combined and a tabu search is performed.
These steps are repeated for a number of iterations.

Figure 4: Sketch of the full QUBO solving procedure.

##  5 Results

The performance of various tracking methods is assessed using the efficiency
and the fake rate as metrics, which are computed on the final set of tracks. A
track is required to have four hits, which is either found directly with a
classical CKF tracking method or by combining selected triplet pairs into
quadruplets. A track is only considered matched if the track has all four hits
matched to the same particle.

The efficiency and fake rate are defined as

$\textrm{Efficiency}=\frac{N_{\rm tracks}^{\rm matched}}{N_{\rm tracks}^{\rm
generated}}\qquad\text{and}\qquad\textrm{Fake rate}=\frac{N_{\rm tracks}^{\rm
fake}}{N_{\rm tracks}^{\rm reconstructed}}\,.$ (6)

Figure 6 and 6 show the track reconstruction efficiency and fake rate as a
function of the laser field intensity parameter $\xi$ for the four methods
tested: conventional CKF-based tracking, GNN-based tracking, VQE, and the VQE
exact solution using the Eigensolver.

Figure 5: Track reconstruction efficiency as a function of the field intensity
parameter $\xi$.

Figure 6: Track fake rate as a function of $\xi$.

The conventional CKF-based tracking, while performant, deteriorates with
$\xi$. The performance of CKF-based tracking is used as a benchmark to
demonstrate the performance that can be realistically achieved. The intial
results using the Eigensolver are slightly poorer than the CKF tracking, which
thus need to be further optimised. The results for VQE demonstrate that our
initial implementation is less effective; however, it can also be further
optimised, e.g., by using a more appropriate choice of circuit ansatz and
optimiser. The limited size of the quantum device, which prompts the sub-QUBO
algorithm, is also a potential contributing factor to the initial degradation
of the quantum approach. We will study these different factors in detail in
future work. Finally, the preliminary result for the GNN-based tracking is
shown for a specific $\xi$ value of 4. Here, the current underperformance is
likely caused by a lack of statistics in the training sample, which will also
be extended and further optimised in future work.

##  6 Conclusion

The use of a hybrid quantum-classical algorithm in track reconstruction is
studied along with a conventional tracking method as well as a GNN-based
tracking. A first implementation of track reconstruction in the LUXE
experiment using quantum devices is in place. In its current version, the
performance is less effective than the conventional tracking method, which
implies that the quantum algorithm needs to be further optimised, in
particular by improving the circuit ansatz. Moreover, the performance of the
sub-QUBO algorithm is currently limited by the size of the quantum device. We
plan to mitigate these effects in extended future studies.

The work by B.H., A.K., F.M., D.S. and Y.Y. was in part funded by the
Helmholtz Association - “Innopool Project LUXE-QED”. K.J. and C.T. are
supported in part by the Helmholtz Association - “Innopool Project Variational
Quantum Computer Simulations (VQCS)”. L.F. is supported by the U.S. Department
of Energy, Office of Science, National Quantum Information Science Research
Centers, Co-design Center for Quantum Advantage (C2QA) under contract number
DE-SC0012704, by the DOE QuantiSED Consortium under subcontract number 675352,
by the National Science Foundation under Cooperative Agreement PHY-2019786
(The NSF AI Institute for Artificial Intelligence and Fundamental
Interactions, http://iaifi.org/), and by the U.S. Department of Energy, Office
of Science, Office of Nuclear Physics under grant contract numbers DE-
SC0011090 and DE-SC0021006. S.K. acknowledges financial support from the
Cyprus Research and Innovation Foundation under project “Future-proofing
Scientific Applications for the Supercomputers of Tomorrow (FAST)”, contract
no. COMPLEMENTARY/0916/0048. This work has benefited from computing services
provided by the German National Analysis Facility (NAF).

## References

## References

  * [1] H. Abramowicz et al., Conceptual design report for the LUXE experiment, Eur. Phys. J. ST 230, 2445 (2021), Preprint 2102.02032
  * [2] H. Gray, Quantum pattern recognition algorithms for charged particle tracking, Phil. Trans. R. Soc. A. 380, 20210103 (2021)
  * [3] T. G. Blackburn, A. J. MacLeod, and B. King, From local to nonlocal: higher fidelity simulations of photon emission in intense laser pulses, New J. Phys. 23, 085008 (2021), Preprint 2103.06673
  * [4] X. Ai et al., A Common Tracking Software Project, Preprint 2106.13593 (2021)
  * [5] S. Farrell et al., Novel deep learning methods for track reconstruction, Preprint 1810.06111 (2018)
  * [6] X. Ju et al., Performance of a geometric deep learning pipeline for HL-LHC particle tracking Eur. Phys. J. C 81, 876 (2021), Preprint 2103.06995
  * [7] C. Tüysüz, C. Rieger, K. Novotny, B. Demirköz, D. Dobos, K. Potamianos, S. Vallecorsa, J. Vlimant, and R. Forster, Hybrid Quantum Classical Graph Neural Networks for Particle Track Reconstruction, Quantum Mach. Intell. 3, 29 (2021), Preprint 2109.12636
  * [8] F. Bapst, W. Bhimji, P. Calafiura, H. Gray, W. Lavrijsen, L. Lindner, and A. Smith, A Pattern Recognition Algorithm for Quantum Annealers, Comput. Softw. Big Sci. 4 1 (2020)
  * [9] M. Treinish et al., Qiskit: An Open-source Framework for Quantum Computing, Zenodo (2022)


# Domain Adaptation for Semantic Segmentation with Maximum Squares Loss

Minghao Chen, Hongyang Xue, Deng Cai

State Key Lab of CAD&CG, College of Computer Science, Zhejiang University,
Hangzhou, China
Fabu Inc., Hangzhou, China
Alibaba-Zhejiang University Joint Institute of Frontier Technologies,
Hangzhou, China
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Corresponding author

###### Abstract

Deep neural networks for semantic segmentation always require a large number
of samples with pixel-level labels, which becomes the major difficulty in
their real-world applications. To reduce the labeling cost, unsupervised
domain adaptation (UDA) approaches are proposed to transfer knowledge from
labeled synthesized datasets to unlabeled real-world datasets. Recently, some
semi-supervised learning methods have been applied to UDA and achieved state-
of-the-art performance. One of the most popular approaches in semi-supervised
learning is the entropy minimization method. However, when applying the
entropy minimization to UDA for semantic segmentation, the gradient of the
entropy is biased towards samples that are easy to transfer. To balance the
gradient of well-classified target samples, we propose the maximum squares
loss. Our maximum squares loss prevents the training process being dominated
by easy-to-transfer samples in the target domain. Besides, we introduce the
image-wise weighting ratio to alleviate the class imbalance in the unlabeled
target domain. Both synthetic-to-real and cross-city adaptation experiments
demonstrate the effectiveness of our proposed approach. The code is released
at https://github.com/ZJULearning/MaxSquareLoss.

##  1 Introduction

In the last few decades, deep learning has achieved great success in the
semantic segmentation task [2, 3, 4, 19, 35]. Researchers have made remarkable
progress in promoting the performance of deep models on current datasets, such
as PASCAL VOC-2012 [8] and Cityscapes [6]. However, these real-world datasets
with pixel-wise semantic labels demand an enormous amount of manual annotation
work. For annotating Cityscapes, it takes $90$ minutes to label one image
accurately [25]. Because of this “curse of dataset annotation”, real-world
datasets for semantic segmentation often contain only a small number of
samples, which inhibits the model’s generalization to various real-world
situations. One possible way to overcome this limitation is to utilize
synthetic datasets, such as the Grand Theft Auto V (GTA5) [25] and SYNTHIA
[26], which take much less time to label and own more samples containing
various situations. However, the model trained on the synthetic dataset cannot
generalize well to real-world examples via direct transfer, due to the large
appearance gap between the two datasets.

Figure 1: In UDA, the gradient of the entropy minimization method ($H$) is
focused on well-classified samples in the target domain. Consequently, we
propose the maximum squares loss ($MS$), which is the negative sum of squared
probabilities. The gradient of the maximum squares loss is linearly
increasing, which reduces the gradient magnitude of samples that are easy to
transfer and makes difficult samples be trained more efficiently.

Unsupervised domain adaptation (UDA) for semantic segmentation [13, 28, 36] is
a task aiming at solving the above transfer problem. In UDA, the labeled
synthetic dataset is known as the source domain, and the unlabeled real-world
dataset is known as the target domain. The general idea of UDA is utilizing
the unlabeled data from the target domain to help minimize the performance gap
between these two domains.

Recently, inspired by semi-supervised learning [11, 17], which also utilizes
the unlabeled data, semi-supervised learning based UDA [9, 31, 36] approaches
are introduced to align feature distributions between domains implicitly.
These semi-supervised learning based approaches achieve state-of-the-art
results in both classification [9] and semantic segmentation [36]. Entropy
minimization [11], which encourages unambiguous cluster assignments, is one of
the most popular methods in semi-supervised learning. ADVENT [31] directly
adopts the entropy minimization method to UDA for semantic segmentation, but
their result is inferior to state-of-the-art approaches.

By analyzing the gradient of the entropy minimization method, we find that
higher prediction probability induces a larger gradient111In this paper, the
gradient refers to the magnitude of the gradient. for the target sample (Fig.
1). If we adopt the assumption in self-training [36] that target samples with
higher prediction probability are more accurate, areas with high accuracy will
be trained more sufficiently than areas with low accuracy. Therefore, the
entropy minimization method will allow for adequate training of samples that
are easy to transfer, which hinders the training process of samples that are
difficult to transfer. This problem in the entropy minimization can be termed
probability imbalance: classes that are easy to transfer have a higher
probability, which results in a much larger gradient than classes that are
difficult to transfer. One simple solution is to replace the prediction
probability $P$ in the entropy formula with $P_{scaled}=(1-2\gamma)P+\gamma$,
in which $\gamma$ is the scale ratio (“Scaled $H$” in Fig. 1). Then the
maximum gradient can be bounded by the factor $\gamma$, instead of going to
infinity. However, this method introduces an extra hyper-parameter $\gamma$,
which is tricky to select.

In this paper, we introduce a new loss, the maximum squares loss, to tackle
the probability imbalance problem. Since the maximum squares loss has a
linearly increasing gradient (Fig. 1), it can prevent high confident areas
from producing excessive gradients. Meanwhile, we show optimizing our loss is
equivalent to maximizing the Pearson $\chi^{2}$ divergence with the uniform
distribution. Maximizing this divergence can achieve class-wise distribution
alignment between source and target domains.

Moreover, we notice the class imbalance in the unlabeled target domain. Due to
unavailable labels in the target domain, we propose the image-wise weighting
factor based on percentages of different classes in an image. Last but not
least, we utilize multi-level outputs to boost performance. We apply the idea
in weakly-supervised learning [34] to UDA and generate self-produced guidance
to train the low-level feature.

The main contributions of this paper are as follows:

  * •

We discover the probability imbalance problem in the entropy minimization
method of UDA, by analyzing the gradient of entropy. We propose the maximum
squares loss with a linear growth gradient to balance the gradient of highly
confident classes.

  * •

To tackle the class imbalance in the unlabeled target domain, we introduce the
image-wise weighting factor, which is more suitable to UDA than conventional
class weighting factors.

  * •

Our approach can achieve competitive results with state-of-the-art methods
under multiple UDA settings. It should be emphasized that our approach does
not need additional structure or discriminator. Moreover, unlike self-training
[36], our approach does not demand redundant computation to get pseudo-labels.

##  2 Related Work

Semantic Segmentation. After years of research, semantic segmentation models
based on deep neural networks (_e.g_., Deeplab [2, 3, 4], PSPNet [35]) can
achieve astonishing performance on the real-world datasets, _e.g_., PASCAL
VOC-2012 [8], and Cityscapes [6]. Nevertheless, the performance heavily relies
on high-quality labeled datasets, which need lots of manual effort. One
possible way to reduce manual labeling cost is to adopt synthetic datasets
constructed from the virtual world, _e.g_., SYNTHIA [26] and GTA5 [25].
However, due to the appearance difference between rendering and real images,
there is a performance gap during the transfer from synthetic to real
datasets.

Unsupervised Domain Adaptation. Traditionally, unsupervised domain adaptation
(UDA) [10, 20, 21, 29, 30, 33] is studied to tackle the domain-shift problem
between the labeled source domain and unlabeled target domain for the
classification task. The core idea behind UDA is to minimize the divergence
between the feature distributions of the source and target domains, which
means to learn domain invariant features. The distribution divergence can be
measured by Maximum Mean Discrepancy (MMD) based methods [20, 21, 30] or
adversarial learning based methods [10, 29]. Apart from global distribution
alignment, class-wise and conditional distribution alignments [21, 33] are
also widely studied.

UDA for Semantic Segmentation. For the semantic segmentation task, it is not
suitable for direct adoption of approaches proposed for the classification
task, due to the higher dimensional feature space. FCN in the wild [14]
firstly introduced the task of UDA for semantic segmentation, and tackled it
with global feature alignment and label statistic matching. Output adaptation
method [28] adapted the structured output space to transfer the structured
spatial knowledge. The conditional generator can be utilized to align the
conditioned distribution [15]. Besides the adversarial methods, another idea
is to transfer the style of real images to synthetic samples while keeping
semantic labels. CyCADA [13] adopted CycleGAN [16] to construct a labeled
real-like dataset, which is more similar to the target dataset.

Semi-supervised Learning Based Methods. Recently, inspired by semi-supervised
learning [11, 17] which also utilizes the unlabeled data, there are several
semi-supervised learning based methods [9, 24, 36, 31] proposed for UDA task.
Assuming that areas with higher prediction probability are more accurate, the
class-balanced self-training [36] generated pseudo labels based on class-wise
thresholds.

In semi-supervised learning study, it is concluded that the information
content of unlabeled examples decreases as classes overlap [1, 22]. Thus
making unlabeled samples less ambiguous can help classes to be more separable,
_e.g_., minimizing the conditional entropy [11]. ADVENT [31] adopted this idea
in the UDA field and minimized the prediction entropy of the target sample.

##  3 Methods

In this section, we present our major contributions, _i.e_., the maximum
squares loss, and the image-wise class-balanced weighting factor. In Section
3.1, we review UDA for semantic segmentation. In Section 3.2, we illustrate
the probability imbalance problem in the entropy minimization method for UDA
and introduce our maximum squares loss. Then we reveal the benefit of maximum
squares loss by the gradient analysis and explain the meaning of this loss
from the perspective of $f$-divergence. Furthermore, in Section 3.3, we notice
the class imbalance and solve it with our image-wise weighting factor. Last
but not least, we apply the self-produced guidance to UDA, in Section 3.4.

###  3.1 Overview of UDA

In unsupervised domain adaptation (UDA), the labeled source domain is denoted
as $\mathcal{D}_{S}=\\{(x_{s},y_{s})|x_{s}\in\mathbb{R}^{H\times W\times
3},y_{s}\in\mathbb{R}^{H\times W}\\}$, and the unlabeled target domain is
denoted as $\mathcal{D}_{T}=\\{x_{t}|x_{t}\in\mathbb{R}^{H\times W\times
3}\\}$. The general objective function of UDA for semantic segmentation can be
formulated as follows:

$\displaystyle\mathcal{L}(x_{s},x_{t})=\mathcal{L}_{CE}(p_{s},y_{s})+\lambda_{T}\mathcal{L}_{T}(x_{t}),$
(1)
$\displaystyle\mathcal{L}_{CE}(p_{s},y_{s})=-\frac{1}{N}\sum_{n=1}^{N}\sum_{c=1}^{C}y^{n,c}_{s}\log(p^{n,c}_{s}),$
(2)

where $\mathcal{L}_{CE}$ is the cross entropy loss of source samples, $n$
represents a pixel point in the $H\times W$ space and $N=HW$ is the total
number of pixels in a picture . $p^{n,c}_{s}$ is the model prediction
probability of the class $c$ at point $n$ for sample $x_{s}$.
$\mathcal{L}_{T}(x_{t})$ is the loss part for target samples.

Entropy Minimization. In the [31], they try to minimize the Shannon entropy of
the target sample prediction. Thus, their objective function for target
samples is:

$\displaystyle\mathcal{L}_{T}(x_{t})=-\frac{1}{N}\sum_{n=1}^{N}\sum_{c=1}^{C}p^{n,c}_{t}\log(p^{n,c}_{t}).$
(3)

For the sake of simplicity, we consider the binary classification case. Then
the entropy formula and the gradient function of the entropy can be written as
follows:

$\displaystyle H(p|x_{t})$ $\displaystyle=-p\log p-(1-p)\log(1-p),$ (4)
$\displaystyle|\frac{dH}{dp}|$ $\displaystyle=|\log p-\log(1-p)|.$ (5)

After plotting the gradient function image on Fig. 1, we can see that the
gradient of the high probability point is much larger than the mediate point.
As a result, the key principle behind the entropy minimization method is that
the training of target samples is guided by the high probability area, which
is assumed to be more accurate.

###  3.2 Maximum Squares Loss

Figure 2: From GTA5 to Cityscapes, the mean of prediction probability v.s.
Intersection over Union(IoU) for each target class. They are almost linearly
related. Thus well-classified classes (high IoU) have larger prediction
probability.

Probability Imbalance Problem. The probability of different classes varies
widely. Classes with high accuracy always have higher prediction probabilities
(Fig. 2). However, the gradient growth (Eq. 5) of the high probability point
is approximated as $|\log p|(p\to 0)$, which will grow to infinity. Then the
simple class will produce a much larger gradient on each pixel than the
difficult class, resulting in the probability imbalance problem mentioned in
Section 1. To remedy this problem, we define the maximum squares loss as:

$\displaystyle\mathcal{L}_{T}(x_{t})=-\frac{1}{2N}\sum_{n=1}^{N}\sum_{c=1}^{C}({p^{n,c}_{t}})^{2}.$
(6)

####  3.2.1 Benefit of Maximum Squares Loss

For the binary classification case, we have the maximum squares loss and its
gradient function as follows:

$\displaystyle MS(p|x_{t})$ $\displaystyle=-p^{2}-(1-p)^{2},$ (7)
$\displaystyle|\frac{dMS}{dp}|$ $\displaystyle=|4p-2|.$ (8)

As the above equation shows, the gradient of the maximum square loss increases
linearly (Fig. 1). It has a more balanced gradient for different classes than
the entropy minimization method in the target domain. Areas with higher
confidence still have larger gradients, but their dominant effects have been
reduced, allowing other difficult classes to obtain training gradients.
Therefore, equipped with the maximum square loss, we alleviate the probability
imbalance in the entropy minimization.

In the experiments (Section 4.4), we show the maximum square loss does balance
the training process of different samples and exceeds the entropy minimization
method by a large margin.

####  3.2.2 Interpretation from $f$-divergence View

The target part loss $\mathcal{L}_{T}(x_{t})$ can be treated as the distance
between the model prediction distribution $p^{n,c}$ and uniform distribution:
$\mathcal{U}=\frac{1}{C}$. Minimizing this distance will reduce the ambiguity
of the target samples and help classes to be more separable [11].

In probability theory, it is common to use $f$-divergence functions to measure
the difference between distributions:

$\displaystyle D_{f}(p\|q)=\sum_{c}q(c)f\left(\frac{p(c)}{q(c)}\right).$ (9)

Figure 3: The illustration of the effect of the maximum squares loss.
Optimizing the maximum squares loss implicitly pushes the target sample
features away from the decision boundary to the corresponding source feature
distribution, which achieves class-wise distribution alignment.

We consider the Pearson $\chi^{2}$ divergence: $f(t)=t^{2}-1$ (or
$f(t)=(t-1)^{2}$ equally). Then Eq. 9 becomes:

$\displaystyle D_{\chi^{2}}({p^{n,c}}\|\mathcal{U})$
$\displaystyle=C\sum_{c}({p^{n,c}})^{2}-1.$ (10)

Similar to entropy, the above equation is another metric for the ambiguity of
the target sample. Maximize the Pearson $\chi^{2}$ divergence is equivalent to
minimizing the objective function (Eq. 6). Maximizing the Pearson $\chi^{2}$
divergence with $\mathcal{U}$ will push the target features away from the
decision boundary to the corresponding source feature distribution (Fig. 3).
In this way, optimizing the maximum squares loss can achieve class-wise
distribution alignment between two domains.

###  3.3 Image-wise Class-balanced Weighting Factor

As Fig. 4 demonstrates, classes with higher accuracy always have more pixels
on the label map, which leads to an imbalance in quantity. The regular method
to balance the number of classes is to introduce weighting factor
$\alpha_{c}$, which is usually set as the inverse class frequency [18].
However, in the UDA task, there is no class label to calculate the class
frequency. It is also not appropriate to replace the target class statistics
with the class statistics on the source dataset, because there is no guarantee
that the target domain will have the same class frequency as the source
domain.

Instead of using the class frequency of the entire target dataset, we
calculate them on each target image:

$\displaystyle{m}^{n,c^{*}}$ $\displaystyle=\begin{cases}1&\text{ if
}c^{*}=\underset{c}{\arg\max}p^{n,c}\\\ 0&\text{ otherwise },\end{cases}$ (11)
$\displaystyle N^{c}$ $\displaystyle=\sum_{n}{m}^{n,c}.$ (12)

In Eq. 6, we divide the sum by N to average the loss on the target image.
Instead, we average the loss based on the number of classes $N^{c}$. Due to
inaccurate predictions, interpolation between these two numbers is more
stable:

$\displaystyle\mathcal{L}_{T}(x_{t})=-\sum_{n=1}^{N}\sum_{c=1}^{C}\frac{1}{2{(N^{c})}^{\alpha}\times
N^{(1-\alpha)}}{(p^{n,c}_{t})}^{2},$ (13)

where $\alpha$ is treated as a hyper-parameter to be selected by cross-
validation.

Figure 4: From GTA5 to Cityscapes, the log frequency v.s. Intersection over
Union (IoU) for each target class. They are almost linearly related. Thus
well-classified classes (high IoU) have more pixels (high frequency).

###  3.4 Multi-level Self-produced Guidance for UDA

As mentioned in [28], adapting low-level feature can enhance the final
performance. We extract the feature maps from the conv4 layer of ResNet [12]
and add an ASPP module to it as the low-level output. Then we extend the
objective function of target samples as:

$\displaystyle\mathcal{L}_{T}(x_{t})=\mathcal{L}_{T}^{final}(x_{t})+\lambda_{low}\mathcal{L}_{T}^{low}(x_{t}),$
(14)

where $\mathcal{L}_{T}^{final}(x_{t})$ denotes the loss function of model
final prediction for the target sample, _e.g_., the maximum squares loss (Eq.
6). Because the high-level output is more accurate than the low-level output,
it is more reasonable to use the high-level output to guide the training of
low-level features. As a result, we adopt the idea of the self-produced
guidance learning [34] in weakly-supervised learning. We first get the
ensemble output $P_{ens}$ by averaging the output map of different levels,
_i.e_., $P_{final}$ and $P_{low}$. Then we generate the self-produced guidance
$\overline{y}^{n,c^{*}}_{t}$ by:

$\displaystyle\overline{y}^{n,c^{*}}_{t}=\begin{cases}1&\text{ if
}c^{*}=\underset{c}{\arg\max}\,p^{n,c}_{ens},\\\
&p^{n,c^{*}}_{final}>\delta\;or\;p^{n,c^{*}}_{low}>\delta\\\ 0&\text{
otherwise },\end{cases}$ (15)

where the choice of $\delta$ dose not effect the experimental result and we
set $\delta=0.95$. We use this high-qualify guidance to guide the low-level
training:

$\displaystyle\lambda_{low}\mathcal{L}_{T}^{low}(x_{t})=\lambda_{low}\mathcal{L}_{CE}(p_{low},\overline{y}^{n,c^{*}}_{t}).$
(16)

In the experiment, we fix $\lambda_{low}=0.1$, the same as [28].

##  4 Experiment

In this section, we first present the comparison between entropy minimization
and maximum square loss on the classification task. Then, we conduct several
experiments in the synthetic-to-real and cross-city settings to demonstrate
the effectiveness of our approach in unsupervised domain adaptation for
semantic segmentation. The code will be available at
https://github.com/ZJULearning/MaxSquareLoss.

Method | A $\to$ W | D $\to$ W | W $\to$ D | A $\to$ D | D $\to$ A | W $\to$ A | Avg
---|---|---|---|---|---|---|---
ResNet-50 [12] | 68.4$\pm$0.2 | 96.7$\pm$0.1 | 99.3$\pm$0.1 | 68.9$\pm$0.2 | 62.5$\pm$0.3 | 60.7$\pm$0.3 | 76.1
DANN [10] | 82.0$\pm$0.4 | 96.9$\pm$0.2 | 99.1$\pm$0.1 | 79.7$\pm$0.4 | 68.2$\pm$0.4 | 67.4$\pm$0.5 | 82.2
EntMin | 89.0$\pm$0.1 | 99.0$\pm$0.1 | 100.0$\pm$.0 | 86.3$\pm$0.3 | 67.5$\pm$0.2 | 63.0$\pm$0.1 | 84.1
MaxSquare | 92.4$\pm$0.5 | 99.1$\pm$0.1 | 100.0$\pm$.0 | 90.0$\pm$0.2 | 68.1$\pm$0.4 | 64.2$\pm$0.2 | 85.6

Table 1: Comparison between the entropy minimization and maximum square loss
on Office-31.

GTA5$\to$Cityscapes
---
Method | Backbone |  road |  sidewalk |  building |  wall |  fence |  pole |  light |  sign |  veg. |  terrain |  sky |  person |  rider |  car |  truck |  bus |  train |  motor |  bike | mIoU (%)
Source only [36] | Wider | 70.0 | 23.7 | 67.8 | 15.4 | 18.1 | 40.2 | 41.9 | 25.3 | 78.8 | 11.7 | 31.4 | 62.9 | 29.8 | 60.1 | 21.5 | 26.8 | 7.7 | 28.1 | 12.0 | 35.4
CBST [36] | ResNet-38 | 86.8 | 46.7 | 76.9 | 26.3 | 24.8 | 42.0 | 46.0 | 38.6 | 80.7 | 15.7 | 48.0 | 57.3 | 27.9 | 78.2 | 24.5 | 49.6 | 17.7 | 25.5 | 45.1 | 45.2
CBST-SP [36] | [32] | 88.0 | 56.2 | 77.0 | 27.4 | 22.4 | 40.7 | 47.3 | 40.9 | 82.4 | 21.6 | 60.3 | 50.2 | 20.4 | 83.8 | 35.0 | 51.0 | 15.2 | 20.6 | 37.0 | 46.2
AdaptSegNet [28] | ResNet101 | 86.5 | 36.0 | 79.9 | 23.4 | 23.3 | 23.9 | 35.2 | 14.8 | 83.4 | 33.3 | 75.6 | 58.5 | 27.6 | 73.7 | 32.5 | 35.4 | 3.9 | 30.1 | 28.1 | 42.4
MinEnt [31] | 86.2 | 18.6 | 80.3 | 27.2 | 24.0 | 23.4 | 33.5 | 24.7 | 83.3 | 31.0 | 75.6 | 54.6 | 25.6 | 85.2 | 30.0 | 10.9 | 0.1 | 21.9 | 37.1 | 42.3
AdvEnt+MinEnt [31] | 87.6 | 21.4 | 82.0 | 34.8 | 26.2 | 28.5 | 35.6 | 23.0 | 84.5 | 35.1 | 76.2 | 58.6 | 30.7 | 84.8 | 34.2 | 43.4 | 0.4 | 28.4 | 35.3 | 44.8
Source only | ResNet101 | 71.4 | 15.3 | 74.0 | 21.1 | 14.4 | 22.8 | 33.9 | 18.6 | 80.7 | 20.9 | 68.5 | 56.6 | 27.1 | 67.4 | 32.8 | 5.6 | 7.7 | 28.4 | 33.8 | 36.9
MinEnt† | 84.2 | 34.4 | 80.7 | 27.0 | 15.7 | 25.8 | 32.6 | 18.0 | 83.4 | 29.4 | 76.9 | 58.7 | 24.0 | 78.7 | 35.9 | 29.9 | 6.5 | 28.3 | 31.4 | 42.2
MaxSquare | 88.1 | 27.7 | 80.8 | 28.7 | 19.8 | 24.9 | 34.0 | 17.8 | 83.6 | 34.7 | 76.0 | 58.6 | 28.6 | 84.1 | 37.8 | 43.1 | 7.2 | 32.2 | 34.2 | 44.3
MaxSquare+IW | 89.3 | 40.5 | 81.2 | 29.0 | 20.4 | 25.6 | 34.4 | 19.0 | 83.6 | 34.4 | 76.5 | 59.2 | 27.4 | 83.8 | 38.4 | 43.6 | 7.1 | 32.2 | 32.5 | 45.2
MaxSquare+IW+Multi | 89.4 | 43.0 | 82.1 | 30.5 | 21.3 | 30.3 | 34.7 | 24.0 | 85.3 | 39.4 | 78.2 | 63.0 | 22.9 | 84.6 | 36.4 | 43.0 | 5.5 | 34.7 | 33.5 | 46.4

Table 2: Results for GTA5-to-Cityscapes experiments. “MaxSquare” denotes our
maximum squares loss method and “MaxSquare+IW” is the maximum squares loss
combined with our image-wise weighting factor (Eq. 13). “ Multi” denotes
combining the multi-level self-guided method in Section 3.4. For comparison,
we reproduce the result of entropy minimization method [31], which is denoted
as “MinEnt†”. CBST [36] adopts a wider ResNet model [32], which is more
powerful than the original ResNet [12] that we adopt.

###  4.1 Datasets

Classification. Office-31 [27] is the most commonly used dataset for
unsupervised domain adaptation, which contains 4,652 images and 13 categories
collected from three domains: Amazon (A), Webcam (W) and DSLR (D). We evaluate
all methods across six domain adaptation tasks A $\to$ W, D $\to$ W, W $\to$
D, A $\to$ D, D $\to$ A and W $\to$ A.

Semantic Segmentation. As for the transfer from synthetic datasets to real-
world datasets, we consider Cityscapes [6] as the target domain, and set GTA5
[25] or SYNTHIA [26] dataset as the source domain, which is same as the
setting in previous works [28, 36]. Cityscapes dataset contains 5,000
annotated images with $2048\times 1024$ resolution taken from real urban
street scenes. GTA5 dataset [25] contains 24,966 annotated images with
$1914\times 1052$ resolution taken from the the GTA5 game. For SYNTHIA
dataset, we use the SYNTHIA-RAND-CITYSCAPES subset consisting of 9,400
$1280\times 760$ synthetic images. During training, we use the labeled
training sets of GTA5 or SYNTHIA as the source domain and the 2,975 images
from Cityscapes training set without annotation as the target domain. We
evaluate all methods on the 500 images from Cityscapes validation set.

In the evaluation, we adopt the Intersection-over-Union (IoU) of each class
and the mean-Intersection-over-Union (mIoU) as performance metrics. We
consider the IoU and mIoU of all 19 classes in the GTA5-to-Cityscapes case.
While SYNTHIA only shares 16 classes with Cityscapes, we consider the IoU and
mIoU of 16-class and 13-class in the SYNTHIA-to-Cityscapes case.

As for cross-city adaptation, we choose the training set of Cityscapes as the
source domain and NTHU dataset [5] as the target domain. The NTHU dataset
consists of images with $2048\times 1024$ resolution from four different
cities: Rio, Rome, Tokyo, and Taipei. For each city, we use 3200 images
without annotations as the target domain for training and 100 images labeled
with 13 classes for evaluation. We consider the shared 13-class IoU and mIoU
for evaluation.

###  4.2 Implementation Details

Classification. We applied entropy minimization and maximum square loss to
ResNet-50 [12]. We adopt the model pre-trained on ImageNet [7], except the
final classifier layer. We train the model using stochastic gradient descent
(SGD) with momentum of 0.9. Following learning rate annealing strategy in
[10], the learning rate is adjusted by $\eta_{p}=\frac{\eta_{0}}{(1+\alpha
p)^{\beta}}$, where p is the training progress linearly changing from 0 to 1,
$\eta_{0}=0.01$, $\alpha=10$, $\beta=0.75$. We set the batch size to 128, half
of which is source samples and half is target samples. We set
$\lambda_{T}=0.3$ for maximum square loss and $\lambda_{T}=0.03$ for entropy
minimization.

Semantic Segmentation. As argued in [28], it is important to adopt a stronger
baseline model to understand the effect of different adaption approaches and
enhance the performance for the practical application. Therefore, in all
experiment, we use Deeplabv2 [2] with ResNet-101 [12] backbones pre-trained on
ImageNet [7] as our base model, which is the same as other works [28, 31].

Before the adaptation, we pre-train the network on the source domain for $70k$
steps to get a high-quality source trained network. We implement the
algorithms using PyTorch [23] on a single NVIDIA $1080$Ti GPU. Due to memory
limitations, we train the model with batch size $2$ (one from the source
domain and one from the target domain).

Following [28], we train the model with Stochastic Gradient Descent (SGD)
optimizer with learning rate $2.5\times 10^{-4}$ , momentum $0.9$ and weight
decay $5\times 10^{-4}$. We schedule the learning rate using “poly” policy:
the learning rate is multiplied by $(1-\frac{iter}{max\\_iter})^{0.9}$ [2]. We
employ the random mirror and gaussian blur to augment data, the same as [35].

As for the selection of hyper-parameters, we set $\lambda_{T}=0.1$ in all
experiments. In the experiments related to the image-wise weighting factor
(Eq. 13), we fix $\alpha=0.2$.

Figure 5: Accuracy of different difficulty samples on A$\to$W. For instance,
“EntMin_bottom” is the accuracy of the entropy minimization on the “bottom
set” (most difficult samples).

###  4.3 Experiments on Classification

Results Tab. 4 shows comparison results on office-31. Although the results are
uncompetitive with state-of-the-art methods, the maximum square loss
(MaxSquare) exceeds the entropy minimization (EntMin) and DANN [10] by a large
margin. Because the semantic segmentation task is much harder than the
classification, this difference will be more apparent in the following
semantic segmentation experiments.

SYNTHIA$\to$Cityscapes
---
Method | Backbone |  road |  sidewalk |  building |  wall* |  fence* |  pole* |  light |  sign |  veg. |  sky |  person |  rider |  car |  bus |  motor |  bike | mIoU (%) | mIoU* (%)
Source only [36] | Wider | 32.6 | 21.5 | 46.5 | 4.8 | 0.1 | 26.5 | 14.8 | 13.1 | 70.8 | 60.3 | 56.6 | 3.5 | 74.1 | 20.4 | 8.9 | 13.1 | 29.2 | 33.6
CBST [36] | ResNet-38 | 53.6 | 23.7 | 75.0 | 12.5 | 0.3 | 36.4 | 23.5 | 26.3 | 84.8 | 74.7 | 67.2 | 17.5 | 84.5 | 28.4 | 15.2 | 55.8 | 42.5 | 48.4
AdaptSegNet [28] | ResNet101 | 84.3 | 42.7 | 77.5 | - | - | - | 4.7 | 7.0 | 77.9 | 82.5 | 54.3 | 21.0 | 72.3 | 32.2 | 18.9 | 32.3 | - | 46.7
MinEnt [31] | 73.5 | 29.2 | 77.1 | 7.7 | 0.2 | 27.0 | 7.1 | 11.4 | 76.7 | 82.1 | 57.2 | 21.3 | 69.4 | 29.2 | 12.9 | 27.9 | 38.1 | 44.2
AdvEnt+MinEnt [31] | 85.6 | 42.2 | 79.7 | 8.7 | 0.4 | 25.9 | 5.4 | 8.1 | 80.4 | 84.1 | 57.9 | 23.8 | 73.3 | 36.4 | 14.2 | 33.0 | 41.2 | 48.0
Source only | ResNet101 | 17.7 | 15.0 | 74.3 | 10.1 | 0.1 | 25.5 | 6.3 | 10.2 | 75.5 | 77.9 | 57.1 | 19.2 | 31.2 | 31.2 | 10.0 | 20.1 | 30.1 | 34.3
MinEnt† | 67.8 | 28.3 | 79.0 | 4.8 | 0.1 | 24.7 | 4.0 | 7.3 | 81.7 | 84.1 | 58.9 | 19.4 | 75.9 | 36.2 | 10.4 | 26.1 | 38.0 | 44.5
MaxSquare | 77.4 | 34.0 | 78.7 | 5.6 | 0.2 | 27.7 | 5.8 | 9.8 | 80.7 | 83.2 | 58.5 | 20.5 | 74.1 | 32.1 | 11.0 | 29.9 | 39.3 | 45.8
MaxSquare+IW | 78.5 | 34.7 | 76.3 | 6.5 | 0.1 | 30.4 | 12.4 | 12.2 | 82.2 | 84.3 | 59.9 | 17.9 | 80.6 | 24.1 | 15.2 | 31.2 | 40.4 | 46.9
MaxSquare+IW+Multi | 82.9 | 40.7 | 80.3 | 10.2 | 0.8 | 25.8 | 12.8 | 18.2 | 82.5 | 82.2 | 53.1 | 18.0 | 79.0 | 31.4 | 10.4 | 35.6 | 41.4 | 48.2

Table 3: Results for SYNTHIA-to-Cityscapes experiments.

Verification of Maximum Square Loss. As shown in Section 3.2, the maximum
squares loss can make difficult samples be trained more efficiently than the
entropy minimization. We use A$\to$W task to verify this conclusion
experimentally. We first train the model on the source domain and mark the 30%
most confident samples in the test set as “top set” and the 30% least
confident samples as “bottom set”. Then we fine-tune the model with EntMin or
MaxSquare and record the accuracy on the test set, “top set” and “bottom set”.
As Fig. 5 shows, there is no difference between the accuracy of two methods on
the “top set”. However, the accuracy of MaxSquare on the “bottom set” is much
higher than EntMin. These results imply that the main improvement of MaxSquare
to EntMin comes from the improvement of difficult samples.

###  4.4 GTA5 to Cityscapes

####  4.4.1 Overall Results

Table 2 summarizes the experimental results for GTA5-to-Cityscapes adaption
comparing with state of the art methods [28, 31, 36]. As Table 2 shows,
equipped with ResNet-101 backbone, our “MaxSquare+IW+Multi” method achieves
state-of-the-art performance. Compared with “MaxSquare”, “MaxSquare+IW” shows
better transfer results on small object classes, _e.g_., fence, person, truck,
train, and motorbike. Besides, for those hard-to-transfer classes, _e.g_.,
terrain, bus and bike, “MaxSquare” performs better than the original entropy
minimization method “MinEnt†” [31]. However, we also find the “MaxSquare’
result for the well-classified road class is also improved than “MinEnt†”. We
explain this phenomenon that the maximum squares loss not only reduces
gradients of easy-to-transfer classes but also reduces gradients of simple
samples, which allows difficult samples from the road class to be trained more
efficiently. This mechanism is similar to focal loss [18].

We notice that “CBST-SP” [36] achieves similar results to our approach. Their
method assumes the spatial priors are shared between source and target
domains. However, different datasets may have different spatial distributions,
and their assumption does not always hold, which will be revealed in the
experiment of cross-city adaptations.

####  4.4.2 Analysis of Maximum Square Loss

We perform the following investigative experiments on GTA5 to Cityscapes.

GTA5$\to$Cityscapes
---
Entropy | MaxSquare | IW | Multi | mIoU
✓ |  |  |  | 42.2
| ✓ |  |  | 44.3
✓ |  | ✓ |  | 43.5
| ✓ | ✓ |  | 45.2
| ✓ |  | ✓ | 45.2
| ✓ | ✓ | ✓ | 46.4

Table 4: Ablation study.

GTA5$\to$Cityscapes
---
param $\lambda_{T}=$ | 0.5 | 0.2 | 0.1 | 0.05 | 0.02 |
MaxSquare | 43.2 | 44.1 | 44.3 | 43.7 | 43.0 |
param $\alpha=$ | 0 | 0.1 | 0.15 | 0.2 | 0.25 | 0.3
MaxSquare+IW | 44.3 | 44.8 | 45.2 | 45.2 | 44.8 | 44.4
param $\delta=$ | 0.98 | 0.95 | 0.9 | 0.8 |  |
MaxSquare+IW+Multi | 46.4 | 46.4 | 46.2 | 46.1 |  |

Table 5: Parameter sensitivity analysis.

Cross-City Adaptation
---
City | Method |  road |  sidewalk |  building |  light |  sign |  veg. |  sky |  person |  rider |  car |  bus |  motor |  bike | mIoU (%)
Rome | Cross city [5] | 79.5 | 29.3 | 84.5 | 0.0 | 22.2 | 80.6 | 82.8 | 29.5 | 13.0 | 71.7 | 37.5 | 25.9 | 1.0 | 42.9
CBST [36] | 87.1 | 43.9 | 89.7 | 14.8 | 47.7 | 85.4 | 90.3 | 45.4 | 26.6 | 85.4 | 20.5 | 49.8 | 10.3 | 53.6
AdaptSegNet [28] | 83.9 | 34.2 | 88.3 | 18.8 | 40.2 | 86.2 | 93.1 | 47.8 | 21.7 | 80.9 | 47.8 | 48.3 | 8.6 | 53.8
Source only | 85.0 | 34.7 | 86.4 | 17.5 | 39.0 | 84.9 | 85.4 | 43.8 | 15.5 | 81.8 | 46.3 | 38.4 | 4.8 | 51.0
MaxSquare | 80.0 | 27.6 | 87.0 | 20.8 | 42.5 | 85.1 | 92.4 | 46.7 | 22.9 | 82.1 | 53.5 | 50.8 | 8.8 | 53.9
MaxSquare+IW | 82.9 | 32.6 | 86.7 | 20.7 | 41.6 | 85.0 | 93.0 | 47.2 | 22.5 | 82.2 | 53.8 | 50.5 | 9.9 | 54.5
Rio | Cross city [5] | 74.2 | 43.9 | 79.0 | 2.4 | 7.5 | 77.8 | 69.5 | 39.3 | 10.3 | 67.9 | 41.2 | 27.9 | 10.9 | 42.5
CBST [36] | 84.3 | 55.2 | 85.4 | 19.6 | 30.1 | 80.5 | 77.9 | 55.2 | 28.6 | 79.7 | 33.2 | 37.6 | 11.5 | 52.2
AdaptSegNet [28] | 76.2 | 44.7 | 84.6 | 9.3 | 25.5 | 81.8 | 87.3 | 55.3 | 32.7 | 74.3 | 28.9 | 43.0 | 27.6 | 51.6
Source only | 74.2 | 42.2 | 84.0 | 12.1 | 20.4 | 78.3 | 87.9 | 50.1 | 25.6 | 76.6 | 40.0 | 27.6 | 17.0 | 48.9
MaxSquare | 70.9 | 39.2 | 85.6 | 14.5 | 19.7 | 81.8 | 88.1 | 55.2 | 31.5 | 77.2 | 39.3 | 43.1 | 30.1 | 52.0
MaxSquare+IW | 76.9 | 48.8 | 85.2 | 13.8 | 18.9 | 81.7 | 88.1 | 54.9 | 34.0 | 76.8 | 39.8 | 44.1 | 29.7 | 53.3
Tokyo | Cross city [5] | 83.4 | 35.4 | 72.8 | 12.3 | 12.7 | 77.4 | 64.3 | 42.7 | 21.5 | 64.1 | 20.8 | 8.9 | 40.3 | 42.8
CBST [36] | 85.2 | 33.6 | 80.4 | 8.3 | 31.1 | 83.9 | 78.2 | 53.2 | 28.9 | 72.7 | 4.4 | 27.0 | 47.0 | 48.8
AdaptSegNet [28] | 81.5 | 26.0 | 77.8 | 17.8 | 26.8 | 82.7 | 90.9 | 55.8 | 38.0 | 72.1 | 4.2 | 24.5 | 50.8 | 49.9
Source only | 81.4 | 28.4 | 78.1 | 14.5 | 19.6 | 81.4 | 86.5 | 51.9 | 22.0 | 70.4 | 18.2 | 22.3 | 46.4 | 47.8
MaxSquare | 79.3 | 28.5 | 78.3 | 14.5 | 27.9 | 82.8 | 89.6 | 57.3 | 31.9 | 71.9 | 6.0 | 29.1 | 49.2 | 49.7
MaxSquare+IW | 81.2 | 30.1 | 77.0 | 12.3 | 27.3 | 82.8 | 89.5 | 58.2 | 32.7 | 71.5 | 5.5 | 37.4 | 48.9 | 50.5
Taipei | Cross city [5] | 78.6 | 28.6 | 80.0 | 13.1 | 7.6 | 68.2 | 82.1 | 16.8 | 9.4 | 60.4 | 34.0 | 26.5 | 9.9 | 39.6
CBST [36] | 86.1 | 35.2 | 84.2 | 15.0 | 22.2 | 75.6 | 74.9 | 22.7 | 33.1 | 78.0 | 37.6 | 58.0 | 30.9 | 50.3
AdaptSegNet [28] | 81.7 | 29.5 | 85.2 | 26.4 | 15.6 | 76.7 | 91.7 | 31.0 | 12.5 | 71.5 | 41.1 | 47.3 | 27.7 | 49.1
Source only | 82.6 | 33.0 | 86.3 | 16.0 | 16.5 | 78.3 | 83.3 | 26.5 | 8.4 | 70.7 | 36.1 | 47.9 | 15.7 | 46.3
MaxSquare | 81.2 | 32.8 | 85.4 | 31.9 | 14.7 | 78.3 | 92.7 | 28.3 | 8.6 | 68.2 | 42.2 | 51.3 | 32.4 | 49.8
MaxSquare+IW | 80.7 | 32.5 | 85.5 | 32.7 | 15.1 | 78.1 | 91.3 | 32.9 | 7.6 | 69.5 | 44.8 | 52.4 | 34.9 | 50.6

Table 6: Results for Cross-City experiments.

Ablation Study. We investigate the effect of the image-wise weighting factor
introduced in Section 3.3. When combined with the image-wise weighting factor
(IW), performances of the entropy minimization and the maximum squares are
improved by nearly 1 point (Tab. 4). As a result, the image-wise weighting
factor is a robust solution to the class imbalance in the unlabeled target
domain.

We also study the effect of the multi-level self-produced guidance in Section
3.4. As Table 4 demonstrates, utilizing multi-level output can significantly
improve the final performance.

Parameter Sensitivity Analysis. We show the sensitivity analysis of parameters
$\lambda_{T}$, $\alpha$ and $\delta$ in Tab 5. Too large or too small
$\lambda_{T}$ cannot take advantage of the maximum square loss. We empirically
choose $\lambda_{T}=0.1$. As the table shows, “MaxSquare+IW” with different
$\alpha$ always yields better performance than “MaxSquare”, which shows that
the image-wise weighting factor is robust to the hyper-parameter $\alpha$.
Meanwhile, the choice of $\delta$ does not affect the result significantly, as
mentioned in 3.4.

###  4.5 SYNTHIA to Cityscapes

Following the evaluation protocol of other works [31, 36], we evaluate the IoU
and mIoU of the shared 16 classes between two datasets and the 13 classes
excluding the classes with ∗. As Table 3 shows, our methods achieve
competitive results to other methods. “MaxSquare+IW” surpasses “MaxSquare”
method on the several small object classes, _e.g_., traffic light, traffic
sign, and motorbike.

###  4.6 Cross City Adaptation

To show the efficiency of our methods for smaller domain shift, we conduct our
experiment on the NTHU dataset with ResNet-101 backbone. We consider the IoU
and mIoU of shared 13 classes for evaluation. Table 6 shows the results of
transferring from Cityscapes to the four cities in the NTHU dataset. In all
four adaptation experiments, our “MaxSquare+IW” outperforms the other most
advanced methods by about 1 point. These excellent results demonstrate the
effectiveness of our maximum squares loss and our image-wise weighting factor.
Moreover, unlike self-training [36], our approach does not assume that source
and target domains share the same spatial priors. Therefore, our method is
robust to various transfer settings.

##  5 Conclusion

In this paper, we demonstrate the probability imbalance problem when applying
the entropy minimization method to UDA for semantic segmentation. We propose
the maximum squares loss to prevent easy-to-transfer classes from dominating
the training on the target domain. We show that optimizing the maximum squares
loss is equivalent to maximizing the Pearson $\chi^{2}$ divergence with the
normal distribution. As for the class imbalance in the target domain, we
propose to compute class weighting factor for each image, based on the
prediction quantity of each class. The synthetic-to-real and cross-city
adaption experiments show that our method can achieve state-of-the-art
performance, without the discriminator in adversarial learning methods.

### Acknowledgments

This work was supported in part by the National Nature Science Foundation of
China (Grant Nos: 61751307) and the National Youth Top-notch Talent Support
Program.

## References

  * [1] Vittorio Castelli and Thomas M. Cover.  The relative value of labeled and unlabeled samples in pattern recognition with an unknown mixing parameter.  IEEE Trans. Information Theory, 42(6), 1996.
  * [2] Liang-Chieh Chen, George Papandreou, Iasonas Kokkinos, Kevin Murphy, and Alan L. Yuille.  Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs.  CoRR, abs/1606.00915, 2016.
  * [3] Liang-Chieh Chen, George Papandreou, Florian Schroff, and Hartwig Adam.  Rethinking atrous convolution for semantic image segmentation.  CoRR, abs/1706.05587, 2017.
  * [4] Liang-Chieh Chen, Yukun Zhu, George Papandreou, Florian Schroff, and Hartwig Adam.  Encoder-decoder with atrous separable convolution for semantic image segmentation.  In ECCV, 2018.
  * [5] Yi-Hsin Chen, Wei-Yu Chen, Yu-Ting Chen, Bo-Cheng Tsai, Yu-Chiang Frank Wang, and Min Sun.  No more discrimination: Cross city adaptation of road scene segmenters.  In ICCV, 2017.
  * [6] Marius Cordts, Mohamed Omran, Sebastian Ramos, Timo Rehfeld, Markus Enzweiler, Rodrigo Benenson, Uwe Franke, Stefan Roth, and Bernt Schiele.  The cityscapes dataset for semantic urban scene understanding.  In CVPR, 2016.
  * [7] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Fei-Fei Li.  Imagenet: A large-scale hierarchical image database.  In CVPR, 2009.
  * [8] Mark Everingham, S. M. Ali Eslami, Luc J. Van Gool, Christopher K. I. Williams, John M. Winn, and Andrew Zisserman.  The pascal visual object classes challenge: A retrospective.  International Journal of Computer Vision, 111(1), 2015.
  * [9] Geoffrey French, Michal Mackiewicz, and Mark Fisher.  Self-ensembling for visual domain adaptation.  In ICLR, 2018.
  * [10] Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor S. Lempitsky.  Domain-adversarial training of neural networks.  Journal of Machine Learning Research, 17, 2016.
  * [11] Yves Grandvalet and Yoshua Bengio.  Semi-supervised learning by entropy minimization.  In NIPS, 2004.
  * [12] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In CVPR, 2016.
  * [13] Judy Hoffman, Eric Tzeng, Taesung Park, Jun-Yan Zhu, Phillip Isola, Kate Saenko, Alexei A. Efros, and Trevor Darrell.  Cycada: Cycle-consistent adversarial domain adaptation.  In ICML, 2018.
  * [14] Judy Hoffman, Dequan Wang, Fisher Yu, and Trevor Darrell.  Fcns in the wild: Pixel-level adversarial and constraint-based adaptation.  CoRR, abs/1612.02649, 2016.
  * [15] Weixiang Hong, Zhenzhen Wang, Ming Yang, and Junsong Yuan.  Conditional generative adversarial network for structured domain adaptation.  In CVPR, 2018.
  * [16] Phillip Isola, Jun-Yan Zhu, Tinghui Zhou, and Alexei A. Efros.  Image-to-image translation with conditional adversarial networks.  In CVPR, 2017.
  * [17] Dong-Hyun Lee.  Pseudo-label : The simple and efficient semi-supervised learning method for deep neural networks.  ICML 2013 Workshop : Challenges in Representation Learning (WREPL).
  * [18] Tsung-Yi Lin, Priya Goyal, Ross B. Girshick, Kaiming He, and Piotr Dollár.  Focal loss for dense object detection.  In ICCV, 2017.
  * [19] Jonathan Long, Evan Shelhamer, and Trevor Darrell.  Fully convolutional networks for semantic segmentation.  In CVPR, 2015.
  * [20] Mingsheng Long, Yue Cao, Jianmin Wang, and Michael I. Jordan.  Learning transferable features with deep adaptation networks.  In ICML, 2015.
  * [21] Mingsheng Long, Han Zhu, Jianmin Wang, and Michael I. Jordan.  Deep transfer learning with joint adaptation networks.  In ICML, 2017.
  * [22] Terence J. O’neill.  Normal discrimination with unclassified observations.  Journal of the American Statistical Association, 73(364), 1978.
  * [23] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer.  Automatic differentiation in pytorch.  In NIPS-W, 2017.
  * [24] Christian S. Perone, Pedro Ballester, Rodrigo C. Barros, and Julien Cohen-Adad.  Unsupervised domain adaptation for medical imaging segmentation with self-ensembling.  CoRR, abs/1811.06042, 2018.
  * [25] Stephan R. Richter, Vibhav Vineet, Stefan Roth, and Vladlen Koltun.  Playing for data: Ground truth from computer games.  In ECCV, 2016.
  * [26] Germán Ros, Laura Sellart, Joanna Materzynska, David Vázquez, and Antonio M. López.  The SYNTHIA dataset: A large collection of synthetic images for semantic segmentation of urban scenes.  In CVPR, 2016.
  * [27] Kate Saenko and Brian Kulis.  Adapting visual category models to new domains.  In ECCV, 2010.
  * [28] Yi-Hsuan Tsai, Wei-Chih Hung, Samuel Schulter, Kihyuk Sohn, Ming-Hsuan Yang, and Manmohan Chandraker.  Learning to adapt structured output space for semantic segmentation.  In CVPR, 2018.
  * [29] Eric Tzeng, Judy Hoffman, Kate Saenko, and Trevor Darrell.  Adversarial discriminative domain adaptation.  In CVPR, 2017.
  * [30] Eric Tzeng, Judy Hoffman, Ning Zhang, Kate Saenko, and Trevor Darrell.  Deep domain confusion: Maximizing for domain invariance.  CoRR, abs/1412.3474, 2014.
  * [31] Tuan-Hung Vu, Himalaya Jain, Maxime Bucher, Matthieu Cord, and Patrick Pérez.  ADVENT: adversarial entropy minimization for domain adaptation in semantic segmentation.  CoRR, abs/1811.12833, 2018.
  * [32] Zifeng Wu, Chunhua Shen, and Anton van den Hengel.  Wider or deeper: Revisiting the resnet model for visual recognition.  CoRR, abs/1611.10080, 2016.
  * [33] Shaoan Xie, Zibin Zheng, Liang Chen, and Chuan Chen.  Learning semantic representations for unsupervised domain adaptation.  In ICML, 2018.
  * [34] Xiaolin Zhang, Yunchao Wei, Guoliang Kang, Yi Yang, and Thomas Huang.  Self-produced guidance for weakly-supervised object localization.  In ECCV, 2018.
  * [35] Hengshuang Zhao, Jianping Shi, Xiaojuan Qi, Xiaogang Wang, and Jiaya Jia.  Pyramid scene parsing network.  In CVPR, 2017.
  * [36] Yang Zou, Zhiding Yu, B. V. K. Vijaya Kumar, and Jinsong Wang.  Unsupervised domain adaptation for semantic segmentation via class-balanced self-training.  In ECCV, 2018.