# Laser Cooling of Radium-225 Ions

Roy A. Ready<EMAIL_ADDRESS>Department of Physics, University of
California, Santa Barbara, California 93106, USA  Haoran Li  Department of
Physics, University of California, Santa Barbara, California 93106, USA
Spencer Kofford  Department of Physics, University of California, Santa
Barbara, California 93106, USA  Robert Kwapisz  Department of Physics,
University of California, Santa Barbara, California 93106, USA  Huaxu Dan
Department of Physics, University of California, Santa Barbara, California
93106, USA  Akshay Sawhney  Department of Physics, University of California,
Santa Barbara, California 93106, USA  Mingyu Fan  Department of Physics,
University of California, Santa Barbara, California 93106, USA  Craig Holliman
Department of Physics, University of California, Santa Barbara, California
93106, USA  Xiaoyang Shi  Department of Physics, University of California,
Santa Barbara, California 93106, USA  Luka Sever-Walter  Department of
Physics, University of California, Santa Barbara, California 93106, USA  A. N.
Gaiser  Department of Chemistry, Michigan State University, East Lansing,
Michigan 48824, USA  Facility for Rare Isotope Beams, Michigan State
University, East Lansing, Michigan 48824, USA  J. R. Griswold  Radioisotope
Science and Technology Division, Oak Ridge National Laboratory, Oak Ridge,
Tennessee 37830, USA  A. M. Jayich  Department of Physics, University of
California, Santa Barbara, California 93106, USA

###### Abstract

Radium-225 (nuclear spin $I=1/2$) ions possess electronic hyperfine
transitions that are first-order insensitive to magnetic field noise, which is
advantageous for optical clocks and quantum information science. We report on
laser cooling and trapping of radium-225 ions and hyperfine splitting
measurements of the ion’s $7s$ ${}^{2}S_{1/2}$, $7p$ ${}^{2}P_{1/2}$, and $6d$
${}^{2}D_{3/2}$ states. We measured the ground state hyperfine constant,
$A(^{2}S_{1/2})=$ $-27.684\,511\,056(9)\text{\,}\mathrm{GHz}$ and the
quadratic Zeeman coefficient, $C_{2}=$
$142.3(10)\text{\,}\mathrm{Hz}\text{\,}{\mathrm{\text{G}}}^{-2}$, of the
${}^{2}S_{1/2}(F=0,m_{F}=0)\leftrightarrow~{}^{2}S_{1/2}(F=1,m_{F}=0)$
transition. We also measured the hyperfine constants of the ${}^{2}P_{1/2}$
state, $A(^{2}P_{1/2})=$ $-5.447(4)\text{\,}\mathrm{GHz}$, and the
${}^{2}D_{3/2}$ state, $A(^{2}D_{3/2})=$ $-619.7(11)\text{\,}\mathrm{MHz}$.

††preprint: APS/123-QED

Atoms with magnetic field-insensitive transitions are appealing for their use
in quantum information science [1] (QIS) and precision measurement [2, 3]. For
ions with a single valence electron and half-integer nuclear spin, there is a
ground state qubit composed of two total spin projection $m_{F}=0$ states
separated by the hyperfine splitting. These states are first order-insensitive
to magnetic field noise and are well-suited to laser driven gates [4, 5]. For
laser-coolable ions with nuclear spin $I=1/2$, the qubit is straightforward to
initialize and control optically or with microwaves. This hyperfine qubit is a
feature of 171Yb+ [6, 7] and led to the development of the radioactive 133Ba+
qubit [8]. The hyperfine qubit’s features also benefit optical clocks based on
${}^{171}\mathrm{Yb}^{+}$ [9, 10]. The radium-225 ion has nuclear spin $1/2$,
a low charge to mass ratio, and optical transitions at convenient wavelengths
[11, 12], making it a good optical clock candidate [13]. The ion’s large
hyperfine splittings make it possible to run an optical clock with only two
infrared wavelengths [14], which is amenable to integrated photonic devices.

Searches for time reversal symmetry violation are motivated by the observed
baryon asymmetry of the universe and the strong $CP$ problem [15]. Radium-225
has an octupole-deformed nucleus that enhances its sensitivity to hadronic
sources of $T$-violation [16, 17, 18]. The sensitivity can be further enhanced
by incorporating radium-225 into a molecule [19], which can be produced with
laser-cooled ${}^{225}\mathrm{Ra}^{+}$ [20].

Radium is famous for its radioactivity and radium-225 is no exception with
only a $15\text{\,}\mathrm{d}$ half-life. Despite this apparent obstacle we
have worked with laser-cooled ${}^{225}\mathrm{Ra}^{+}$ ions in a sealed
vacuum system since June 6${}^{\text{th}}$, 2023. The key to seamless
operation is the oven design based on Fan et al. [21], which continuously
produces radium via the nuclear decay of thorium-229
($7800\text{\,}\mathrm{\text{~{}yr}}$ half-life [22]).

Figure 1:  (a) Experimental apparatus. An oven emits radium atoms (pink arrow)
which are photoionized by (PI) light at 483 nm and 450 nm. Trapped ions, such
as the three shown, are detected and laser-cooled with light at 468 nm and
1079 nm. Permanent magnets define the quantization axis ($\vec{B}$) and
hyperfine transitions are driven by a microwave (MW) horn. (b) Energy level
diagram of the low-lying ${}^{225}\mathrm{Ra}^{+}$ hyperfine structure and
${}^{2}S_{1/2}$ Zeeman sublevels, showing laser and microwave-driven
transitions. State detection lasers drive transitions between the bright
states (blue) and are off-resonant from the dark states (black).

To laser cool ${}^{225}\mathrm{Ra}^{+}$ we drive optical transitions from
hyperfine levels of the ${}^{2}S_{1/2}$ and ${}^{2}D_{3/2}$ states to those of
the ${}^{2}P_{1/2}$ state. The ${}^{2}S_{1/2}$ and ${}^{2}P_{1/2}$ hyperfine
splittings were first measured by laser spectroscopy of a hot atomic beam
[23]. The ground state hyperfine splitting was re-measured [24], resulting in
a $47\text{\,}\mathrm{MHz}$ ($3.6\sigma$) discrepancy with the previous
result. With laser-cooled ${}^{225}\mathrm{Ra}^{+}$ we measured the hyperfine
structure of all three states used for laser cooling and state detection,
improving the precision of the ${}^{2}S_{1/2}$ and ${}^{2}P_{1/2}$
measurements and making the first measurement of the ${}^{2}D_{3/2}$ hyperfine
structure. We also measured the quadratic Zeeman shift coefficient of the
hyperfine qubit with microwave spectroscopy.

The ${}^{225}\mathrm{Ra}$ source is a molecular beam epitaxy oven with
$8\text{\,}\mathrm{\SIUnitSymbolMicro\text{Ci}}$ of ${}^{229}\mathrm{Th}$
deposited in a titanium crucible. The oven is heated to between
$350\text{\,}\mathrm{\SIUnitSymbolCelsius}$ and
$400\text{\,}\mathrm{\SIUnitSymbolCelsius}$ to emit an effusive beam of radium
atoms, see Fig. 1a. Radium ions are loaded into the trap with a two-stage
process: neutral radium is driven to the ${}^{1}P_{1}$ state with near-
resonant 483 nm light and then ionized with 450 nm light. Radium ions are
consistently trapped within $15\text{\,}\min$ of the oven reaching its target
temperature.

The ions are held in a linear Paul trap with characteristic radial and axial
dimensions $r_{0}=$ $0.6\text{\,}\mathrm{mm}$ and $z_{0}=$
$2.5\text{\,}\mathrm{mm}$, described previously in Ref. [20]. The radial
electrodes are driven at $8.205\text{\,}\mathrm{MHz}$ and dc offsets of
$+200\text{\,}\mathrm{mV}$ and $-100\text{\,}\mathrm{mV}$ are applied to
opposite electrode pairs to break the degeneracy between radial motional
modes. We can trap chains of ions, see Fig. 1a, though our spectroscopy was
performed with single ions.

Ions are laser-cooled with four lasers to address all hyperfine levels in the
${}^{2}S_{1/2}$ ground and ${}^{2}D_{3/2}$ metastable states, see Fig. 1b. The
frequency and power of each laser is independently controlled with an acousto-
optic modulator set up in a double-pass configuration. Decays from the
${}^{2}P_{1/2}$ state populate both the ground state and the metastable state
($638(10)\text{\,}\mathrm{ms}$ lifetime [25]). The metastable state hyperfine
levels are repumped with 1079 nm light. Both 468 nm lasers and one repump
laser are stabilized to an optical cavity, while the second repump laser is
offset-locked [26] to its counterpart. We use the first-order sidebands of
fiber electro-optic modulators (EOMs) to scan the 468 nm and 1079 nm light
across the hyperfine states and also use the 468 nm EOM for state preparation,
following Olmschenk et al. [27].

(a)

(b)

(c)

Figure 2:  (a) State preparation and measurement result for the ground state
hyperfine transition. We measure an average of $0.04\text{\,}$ photons in the
dark state and $11.6\text{\,}$ photons in the bright state. (b) The quadratic
Zeeman shift for a range of magnetic field strengths, with studentized
residuals (SR) from the quadratic fit used to extract $C_{2}$, in the bottom
panel. We determine the magnetic field magnitude at the ion by driving
$\sigma^{-}$ (orange) and $\sigma^{+}$ (red) transitions from the $m_{F}=\pm
1$ Zeeman levels, shown for the $1.5\text{\,}\mathrm{\text{G}}$ data point.
(c) Spectroscopy of the
$S_{1/2}(F=1,m_{F}=0)\leftrightarrow~{}S_{1/2}(F=0,m_{F}=0)\ $transition. A
fixed scan time is determined from a Rabi flop, pink and inset, at the
resonant frequency of the transition.

We drive magnetic dipole transitions between the ground state hyperfine levels
with microwaves emitted from a horn positioned $10\text{\,}\mathrm{cm}$ from
the trap center. The microwaves are generated by mixing a fixed tone at
$27.3\text{\,}\mathrm{GHz}$ with a tunable rf source from a direct digital
synthesizer, which is frequency doubled to near $385\text{\,}\mathrm{MHz}$.

Each hyperfine splitting measurement consists of Doppler cooling the ion,
preparing the target state, scanning the transition, and state detection.
During state detection we drive the
$S_{1/2}(F=1)\leftrightarrow~{}P_{1/2}(F=0)$ and
$D_{3/2}(F=1)\leftrightarrow~{}P_{1/2}(F=0)$ transitions. The
${}^{2}S_{1/2}(F=1)$ and ${}^{2}D_{3/2}(F=1)$ states are referred to as the
bright states, highlighted in blue in Fig. 1b. When the ion is in one of the
dark states, ${}^{2}S_{1/2}(F=0)$ or ${}^{2}D_{3/2}(F=2)$, light is not
scattered as the dark states do not decay and are far off resonance from the
state detection lasers. Scattered 468 nm photons are focused onto a
photomultiplier tube (PMT) and camera by an objective.

We characterize the hyperfine qubit by measuring the state preparation and
measurement (SPAM) fidelity. After preparing the dark ground state, we
transfer the population to the bright ground state with a
$235\text{\,}\mathrm{\SIUnitSymbolMicro s}$ resonant microwave pulse and
perform a state detection. This is compared to a state detection after only
dark state preparation (no microwave pulse). From the SPAM measurement we find
a $2.5\text{\,}$ photon threshold to discriminate between bright events
($11.6\text{\,}$ photons on average) and dark events ($0.04\text{\,}$ photons
on average) in a $1.7\text{\,}\mathrm{ms}$ detection time, see Fig. 2(a). The
threshold minimizes the average false detection fraction, given by
$1/2\left(\epsilon_{0}+\epsilon_{1}\right)$ [28], where $\epsilon_{0}$
($\epsilon_{1}$) is the fraction of dark (bright) events falsely identified as
bright (dark) events, and is related to the fidelity by
$\mathcal{F}=1-1/2\left(\epsilon_{0}+\epsilon_{1}\right)$. We determine the
fidelity of ${}^{225}\mathrm{Ra}^{+}$ in our system from an average of 13
separate measurements. Our measured average SPAM fidelity is $\mathcal{F}=$
$0.9951(9)\text{\,}$, with false identification fractions of
$\epsilon_{0}=$$0.0035(8)\text{\,}$ and $\epsilon_{1}=$ $0.007(2)\text{\,}$.
Our result is limited by off-resonant scattering, PMT dark counts, and the
$0.2241(11)\text{\,}\%$ light collection efficiency.

The $S_{1/2}(F=1,m_{F}=0)\leftrightarrow~{}S_{1/2}(F=0,m_{F}=0)\ $ hyperfine
transition is sensitive to the second-order Zeeman shift
$\Delta\nu_{\mathrm{QZ}}=C_{2}B^{2}\ ,$ where $C_{2}$ is the quadratic Zeeman
shift coefficient and $B$ is the magnetic field magnitude. We measured
$\Delta\nu_{\mathrm{QZ}}$ for a range of magnetic field strengths, as shown in
Fig. 2(b), and from the fit we extract the quadratic Zeeman shift coefficient,
$C_{2}=$ $142.3(10)\text{\,}\mathrm{Hz}\text{\,}{\mathrm{\text{G}}}^{-2}$.,
which is consistent with the calculated value of
$141\text{\,}\mathrm{Hz}\text{\,}{\mathrm{\text{G}}}^{-2}$ [29].

To measure the ground state hyperfine splitting, we prepare the
${}^{2}S_{1/2}(F=0,m_{F}=0)$ dark state and then scan a
$10\text{\,}\mathrm{ms}$ microwave pulse across the $\pi$ transition,
$S_{1/2}(F=0,m_{F}=0)\leftrightarrow~{}S_{1/2}(F=1,m_{F}=0)$, and perform
state detection, see Fig. 2(c). To obtain the unperturbed $\pi$ transition
frequency, $\Delta\nu_{\mathrm{QZ}}(B=$ $3.0\text{\,}\mathrm{\text{G}}$$)$ is
subtracted from the scanned frequency. We average 18 measurements, resulting
in a ground state hyperfine constant of
$A\left(S_{1/2}\right)=$$-27.684\,511\,056(9)\text{\,}\mathrm{GHz}$. The
$0.9\text{\,}\mathrm{Hz}$ statistical uncertainty is negligible compared to
the $9\text{\,}\mathrm{Hz}$ systematic uncertainty.

The dominant source of uncertainty of the ${}^{2}S_{1/2}$ hyperfine splitting
comes from the second-order Zeeman shift, which shifts the frequency of the
measured transition by $\Delta\nu_{\mathrm{QZ}}(B)$. To determine the magnetic
field $B$ at the ion, we perform Rabi spectroscopy on the $\sigma$
transitions, $(F=0,m_{F}=0)\leftrightarrow(F=1,m_{F}=\pm 1)$, and compute $B$
from the Zeeman splitting. The average frequency of the $\sigma$ transitions
is subtracted from the $\pi$ transition frequency to find
$\Delta\nu_{\mathrm{QZ}}(B)$. The uncertainties for the quadratic Zeeman shift
data points are derived from fits to the transitions, and contribute
$9\text{\,}\mathrm{Hz}$ to the measured ground state hyperfine splitting.

The second largest contribution to the systematic uncertainty is inaccuracy of
the rf source, which is locked to a GPS-disciplined reference (SRS FS740). The
short-term stability of this reference is $1\text{\times}{10}^{-11}\text{\,}$,
and we assign an uncertainty of $0.3\text{\,}\mathrm{Hz}$ to this systematic.

We investigated frequency shifts due to the ac magnetic field of the rf trap
drive by measuring the $\pi$ transition frequency for a range of trap drive
powers. We also tested for ac Stark shifts from probe laser light leakage. We
did not observe any frequency shifts due to either of these effects.

We compare our result with previous measurements and a theoretical calculation
of $A\left(S_{1/2}\right)$, see Fig. 3. Of the two previous
$A\left(S_{1/2}\right)$ hyperfine constant measurements, our result agrees
with the first measurement [23]. The contribution to hyperfine splittings due
to the nuclear magnetization distribution is known as the Bohr-Weisskopf (BW)
effect. For ${}^{225}\mathrm{Ra}^{+}$ the BW effect is relatively large but
challenging to compute, and dominates the $380\text{\,}\mathrm{MHz}$
uncertainty for the calculated value of $A\left(S_{1/2}\right)$ [30]. The BW
effect can alternatively be extracted by combining atomic structure
calculations with measured hyperfine splittings [31], and may be used to
benchmark nuclear models.

The ${}^{2}D_{3/2}$ and ${}^{2}P_{1/2}$ hyperfine splittings are scanned with
first-order sidebands from EOMs. The 468 nm EOM sideband drives the
$S_{1/2}(F=1)\leftrightarrow~{}P_{1/2}(F=1)$ transition and the 1079 nm EOM
sideband drives the $D_{3/2}(F=1)\leftrightarrow~{}P_{1/2}(F=1)$ transition.
We reference the laser carrier frequency by performing spectroscopy on the
$D_{3/2}(F=2)\leftrightarrow P_{1/2}(F=1)$ and the
$S_{1/2}(F=1)\leftrightarrow P_{1/2}(F=0)$ transitions for the ${}^{2}D_{3/2}$
and ${}^{2}P_{1/2}$ hyperfine splitting measurements, respectively.

To measure the hyperfine splitting of the ${}^{2}D_{3/2}$ state, we prepare
the ${}^{2}D_{3/2}(F=1)$ hyperfine level and scan the 1079 nm EOM sideband
over the $D_{3/2}(F=1)\leftrightarrow~{}P_{1/2}(F=1)$ transition. We then
measure the final dark state population, which is maximized when the EOM
sideband frequency is resonant with the ${}^{2}D_{3/2}$ hyperfine splitting,
see Fig. 4. The hyperfine splitting is determined from the difference of the
$D_{3/2}(F=2)\leftrightarrow~{}P_{1/2}(F=1)$ and
$D_{3/2}(F=1)\leftrightarrow~{}P_{1/2}(F=1)$ transition frequencies. The
measured hyperfine splitting is $1239(2)\text{\,}\mathrm{MHz}$, which
corresponds to a hyperfine constant of $A(^{2}D_{3/2})=$
$-619.7(11)\text{\,}\mathrm{MHz}$. The statistical and systematic
uncertainties are $100\text{\,}\mathrm{kHz}$ and $1.0\text{\,}\mathrm{MHz}$.

To measure the ${}^{2}P_{1/2}$ hyperfine splitting, we prepare the
${}^{2}S_{1/2}(F=1)$ bright state and scan the 468 nm EOM sideband over the
$S_{1/2}(F=1)\leftrightarrow~{}P_{1/2}(F=1)$ transition. We measure the dark
state population, ${}^{2}S_{1/2}(F=0)$ and ${}^{2}D_{3/2}(F=2)$, which is
maximized when the sideband frequency is resonant with the ${}^{2}P_{1/2}$
hyperfine splitting. The hyperfine splitting constant is $A(^{2}P_{1/2})=$
$-5.447(4)\text{\,}\mathrm{GHz}$. The uncertainty is dominated by the
$4.0\text{\,}\mathrm{MHz}$ systematic uncertainty, with a
$120\text{\,}\mathrm{kHz}$ statistical uncertainty. Our result is consistent
with the previous measurement [32] and improves the precision by a factor of
1.9.

The ${}^{2}P_{1/2}$ and ${}^{2}D_{3/2}$ hyperfine splitting measurements share
the same sources of systematic uncertainty. The leading source of uncertainty
for both the ${}^{2}P_{1/2}$ and ${}^{2}D_{3/2}$ hyperfine measurements is
drift of our laser stabilization cavities, which results in laser frequency
drifts during measurements. We characterize the drift and assign uncertainties
of $3.2\text{\,}\mathrm{MHz}$ to the ${}^{2}P_{1/2}$ and
$0.7\text{\,}\mathrm{MHz}$ to the ${}^{2}D_{3/2}$ measurements.

Figure 3:  A comparison of our result with previous measurements [23, 24]
(blue circles) and a calculation [30] (orange triangle) of the
$A(^{2}S_{1/2})$ hyperfine constant. The plotted values are offset by
$A_{\mathrm{off.}}=$$-27.704\text{\,}\mathrm{GHz}$.

The combination of Zeeman splitting with imperfect linear laser polarization
or with an unequal population distribution in the Zeeman sublevels used for
state preparation results in a systematic shift of the ${}^{2}P_{1/2}$ and
${}^{2}D_{3/2}$ hyperfine frequencies. For the corresponding systematic we
assign an uncertainty that corresponds to the largest Zeeman splitting of each
transition, measured at a magnetic field of $1.1\text{\,}\mathrm{\text{G}}$.
The resulting uncertainty is $1.6\text{\,}\mathrm{MHz}$ for the
${}^{2}P_{1/2}$ measurement, and $0.8\text{\,}\mathrm{MHz}$ for the
${}^{2}D_{3/2}$ measurement.

The hyperfine levels are frequency-shifted in the presence of laser light due
to the ac Stark effect. We investigated frequency shifts of the
${}^{2}P_{1/2}$ and ${}^{2}D_{3/2}$ states due to the probe lasers by varying
the 468 nm laser power from $1.7\text{\,}\mathrm{\SIUnitSymbolMicro
W}11.0\text{\,}\mathrm{\SIUnitSymbolMicro W}$ and varying the 1079 nm laser
power from $5.0\text{\,}\mathrm{\SIUnitSymbolMicro
W}15.0\text{\,}\mathrm{\SIUnitSymbolMicro W}$. We did not observe ac Stark
shifts for either the ${}^{2}P_{1/2}$ or ${}^{2}D_{3/2}$ measurements, which
is consistent with our calculated upper bound of $10\text{\,}\mathrm{kHz}$,
well below the statistical uncertainty.

In summary, we have operated a radium-225 ion trap for over a year in a sealed
vacuum system and measured the hyperfine splitting of the electronic states
used for laser cooling and state detection. The demonstrated long-term source
of short-lived ${}^{225}\mathrm{Ra}$ isotopes enables the development of a
${}^{225}\mathrm{Ra}^{+}$ ion optical clock, which has field-insensitive
states that suppress magnetic field noise compared to a nuclear spin-zero ion
optical clock [13], as well as experiments to test fundamental symmetries with
radium-bearing molecules. Radium-225 ions are also a potential route to
trapped actinium ions, as ${}^{225}\mathrm{Ra}$ $\beta$-decays to
${}^{225}\mathrm{Ac}$, and therefore ${}^{225}\mathrm{Ra}^{+}$ decays could
result in trapped 225Ac2+, which supports laser cooling and state detection in
two independent manifolds.

Figure 4:  The ${}^{2}S_{1/2}(F=0)$ and ${}^{2}D_{3/2}(F=2)$ dark state
population as the EOM first-order sideband is scanned over the
$D_{3/2}~{}(F=1)\leftrightarrow P_{1/2}~{}(F=1)$ transition. A Lorentzian fit
determines the ${}^{2}D_{3/2}$ hyperfine splitting.

We thank Wes Campbell, Christian Sanner, and Anthony Ransford for helpful
discussions. H.L. was supported by ONR Grant No. N00014-21-1-2597 and M.F. was
supported by DOE Award No. DE-SC0022034. R.A.R., R.K., A.S., H.D., C.A.H.,
X.S., L.S.W., and A.M.J. were supported by the Heising-Simons Foundation Award
No. 2022-4066, the W.M. Keck Foundation, NIST Award No. 60NANB21D185, NSF NRT
Award No. 2152201, the Eddleman Center, the Noyce Initiative, and NSF Award
Nos. 2326810, 2146555, and 1912665. A.N.G. acknowledges the support of startup
funds and Michigan State University. The isotope used in this research was
supplied by the U.S. Department of Energy Isotope Program, managed by the
Office of Isotope R&D and Production.

## References

  * Crain  _et al._ [2014] S. Crain, E. Mount, S. Baek, and J. Kim, Appl. Phys. Lett. 105, 181115 (2014).
  * Lewty  _et al._ [2012] N. C. Lewty, B. L. Chuah, R. Cazan, B. K. Sahoo, and M. D. Barrett, Opt. Express 20, 21379 (2012).
  * Pizzocaro  _et al._ [2017] M. Pizzocaro, P. Thoumany, B. Rauf, F. Bregolin, G. Milani, C. Clivati, G. A. Costanzo, F. Levi, and D. Calonico, Metrologia 54, 102 (2017).
  * Ballance  _et al._ [2016] C. J. Ballance, T. P. Harty, N. M. Linke, M. A. Sepiol, and D. M. Lucas, Phys. Rev. Lett. 117, 060504 (2016).
  * Boguslawski  _et al._ [2023] M. J. Boguslawski, Z. J. Wall, S. R. Vizvary, I. D. Moore, M. Bareian, D. T. C. Allcock, D. J. Wineland, E. R. Hudson, and W. C. Campbell, Phys. Rev. Lett. 131, 063001 (2023).
  * Balzer  _et al._ [2006] C. Balzer, A. Braun, T. Hannemann, C. Paape, M. Ettler, W. Neuhauser, and C. Wunderlich, Phys. Rev. A 73, 041407 (2006).
  * Ma  _et al._ [2022] S. Ma, A. P. Burgers, G. Liu, J. Wilson, B. Zhang, and J. D. Thompson, Phys. Rev. X 12, 021028 (2022).
  * Hucul  _et al._ [2017] D. Hucul, J. E. Christensen, E. R. Hudson, and W. C. Campbell, Phys. Rev. Lett. 119, 100501 (2017).
  * Tamm  _et al._ [2014] C. Tamm, N. Huntemann, B. Lipphardt, V. Gerginov, N. Nemitz, M. Kazda, S. Weyers, and E. Peik, Phys. Rev. A 89, 023820 (2014).
  * Huntemann  _et al._ [2016] N. Huntemann, C. Sanner, B. Lipphardt, C. Tamm, and E. Peik, Phys. Rev. Lett. 116, 063001 (2016).
  * Fan  _et al._ [2019] M. Fan, C. A. Holliman, A. L. Wang, and A. M. Jayich, Phys. Rev. Lett. 122, 223001 (2019).
  * West  _et al._ [2019] G. N. West, W. Loh, D. Kharas, C. Sorace-Agaskar, K. K. Mehta, J. Sage, J. Chiaverini, and R. J. Ram, APL Photonics 4, 026101 (2019).
  * Holliman  _et al._ [2022] C. A. Holliman, M. Fan, A. Contractor, S. M. Brewer, and A. M. Jayich, Phys. Rev. Lett. 128, 033202 (2022).
  * Holliman  _et al._ [2023] C. A. Holliman, M. Fan, and A. M. Jayich, in  _Quantum Sensing, Imaging, and Precision Metrology_, Vol. PC12447 (SPIE, 2023) p. PC124470C.
  * Pospelov and Ritz [2005] M. Pospelov and A. Ritz, Ann. Phys. 318, 119 (2005).
  * Auerbach  _et al._ [1996] N. Auerbach, V. V. Flambaum, and V. Spevak, Phys. Rev. Lett. 76, 4316 (1996).
  * Dobaczewski and Engel [2005] J. Dobaczewski and J. Engel, Phys. Rev. Lett. 94, 232502 (2005).
  * Bishof  _et al._ [2016] M. Bishof, R. H. Parker, K. G. Bailey, J. P. Greene, R. J. Holt, M. R. Kalita, W. Korsch, N. D. Lemke, Z.-T. Lu, P. Mueller, T. P. O’Connor, J. T. Singh, and M. R. Dietrich, Phys. Rev. C 94, 025501 (2016).
  * Yu and Hutzler [2021] P. Yu and N. R. Hutzler, Phys. Rev. Lett. 126, 023003 (2021).
  * Fan  _et al._ [2021] M. Fan, C. A. Holliman, X. Shi, H. Zhang, M. W. Straus, X. Li, S. W. Buechele, and A. M. Jayich, Phys. Rev. Lett. 126, 023002 (2021).
  * Fan  _et al._ [2023] M. Fan, R. A. Ready, H. Li, S. Kofford, R. Kwapisz, C. A. Holliman, M. S. Ladabaum, A. N. Gaiser, J. R. Griswold, and A. M. Jayich, Phys. Rev. Research 5, 043201 (2023).
  * Essex  _et al._ [2018] R. M. Essex, J. L. Mann, R. Collé, L. Laureano-Perez, M. E. Bennett, H. Dion, R. Fitzgerald, A. M. Gaffney, A. Gourgiotis, A. Hubert, K. G. W. Inn, W. S. Kinman, S. P. Lamont, R. Steiner, and R. W. Williams, Journal of Radioanalytical and Nuclear Chemistry 318, 515 (2018).
  * Ahmad  _et al._ [1983] S. A. Ahmad, W. Klempt, R. Neugart, E. W. Otten, K. Wendt, and C. Ekström, Phys. Lett. B 133, 47 (1983).
  * Neu  _et al._ [1989] W. Neu, R. Neugart, E. W. Otten, G. Passler, K. Wendt, B. Fricke, E. Arnold, H. J. Kluge, and G. Ulm, Zeitschrift für Physik D Atoms, Molecules and Clusters 11, 105 (1989).
  * Pal  _et al._ [2009] R. Pal, D. Jiang, M. S. Safronova, and U. I. Safronova, Phys. Rev. A 79, 062505 (2009).
  * Schünemann  _et al._ [1999] U. Schünemann, H. Engler, R. Grimm, M. Weidemüller, and M. Zielonkowski, Rev. Sci. Instrum. 70, 242 (1999).
  * Olmschenk  _et al._ [2007] S. Olmschenk, K. C. Younge, D. L. Moehring, D. N. Matsukevich, P. Maunz, and C. Monroe, Phys. Rev. A 76, 052314 (2007).
  * Christensen  _et al._ [2020] J. E. Christensen, D. Hucul, W. C. Campbell, and E. R. Hudson, npj Quantum Inf. 6, 35 (2020).
  * Versolato  _et al._ [2011] O. O. Versolato, L. W. Wansbeek, K. Jungmann, R. G. E. Timmermans, L. Willmann, and H. W. Wilschut, Phys. Rev. A 83, 043829 (2011).
  * Ginges  _et al._ [2017] J. S. M. Ginges, A. V. Volotka, and S. Fritzsche, Phys. Rev. A 96, 062502 (2017).
  * Skripnikov [2020] L. V. Skripnikov, J. Chem. Phys. 153, 114114 (2020).
  * Wendt  _et al._ [1987] K. Wendt, S. A. Ahmad, W. Klempt, R. Neugart, E. W. Otten, and H. H. Stroke, Zeitschrift für Physik D Atoms, Molecules and Clusters 4, 227 (1987).


utf8

# Sentiment-Aware Measure (SAM) for Evaluating Sentiment Transfer by Machine
Translation Systems

Hadeel Saadany
RGCL
University of Wolverhampton
Wolverhampton, UK
<EMAIL_ADDRESS>
&Constantin Orăsan
Centre for Translation Studies
University of Surrey
Guildford, UK
<EMAIL_ADDRESS>
Emad Mohamed
RGCL
University of Wolverhampton
Wolverhampton, UK
<EMAIL_ADDRESS>
&Ashraf Tantawy
School of Computer Science and Informatics
De Montfort University
Leicester, UK
<EMAIL_ADDRESS>
###### Abstract

In translating text where sentiment is the main message, human translators
give particular attention to sentiment-carrying words. The reason is that an
incorrect translation of such words would miss the fundamental aspect of the
source text, i.e. the author’s sentiment. In the online world, MT systems are
extensively used to translate User-Generated Content (UGC) such as reviews,
tweets, and social media posts, where the main message is often the author’s
positive or negative attitude towards the topic of the text. It is important
in such scenarios to accurately measure how far an MT system can be a reliable
real-life utility in transferring the correct affect message. This paper
tackles an under-recognised problem in the field of machine translation
evaluation which is judging to what extent automatic metrics concur with the
gold standard of human evaluation for a correct translation of sentiment. We
evaluate the efficacy of conventional quality metrics in spotting a
mistranslation of sentiment, especially when it is the sole error in the MT
output. We propose a numerical ‘sentiment-closeness’ measure appropriate for
assessing the accuracy of a translated affect message in UGC text by an MT
system. We will show that incorporating this sentiment-aware measure can
significantly enhance the correlation of some available quality metrics with
the human judgement of an accurate translation of sentiment.

##  1 Introduction

Standard quality measures for assessing the performance of machine translation
systems, such as BLEU (Papineni et al., 2002), are domain agnostic; they
evaluate the translation accuracy regardless of the semantic domain or
linguistic peculiarities of the source text. Consequently, they give equal
penalty weight to inaccurate translation of n-grams, which may lead to
performance overestimation (or underestimation). For example, the Arabic high-
rated Goodreads book review showing the reviewers overall satisfaction of a
novel: ‘الرواية رهيبة عيبها الوحيد الجزء الاخير¿ (‘The novel is great, its
only flaw is the last part’) is mistranslated by the available online
translation tool which wrongly outputs a negative sentiment (‘The novel is
terrible, its only flaw is the last part’). Despite the distortion of the
affect message, this translation receives an equally high score as a correct
translation (The story is great, its only flaw is the last part), but which
uses story instead of novel. This is because BLEU mildly penalises the wrong
translation as it swaps only one uni-gram (‘great’) with its opposite
(‘terrible’). Yet, the mistranslation of this particular uni-gram is a
critical error as it is most pivotal in transferring the sentiment, and hence
the MT performance is over-estimated.

There have been numerous efforts to address the common pitfalls of n-gram-
based evaluation metrics by incorporating semantic and contextual features.
However, despite research evidence of its analytical limitations, BLEU is
still the de facto standard for MT performance evaluation (Mathur et al.,
2020a; Reiter, 2018). Moreover, although the introduction of more
semantically-oriented metrics showed a better correlation with human
judgement, still the estimation of sentiment preservation in UGC has not yet
been investigated. This is partially due to the fact that the domain and
linguistic style of the WMTs datasets typically used for metric evaluation
(e.g. newstest2020, Canadian Parliament, Wikipedia, UN corpus) is quite
different than the non-standard noisy UGC where sentiment is the main content
of a telegraphic message (Ma et al., 2018; Barrault et al., 2019; Mathur et
al., 2020b). Assessed over these WMT datasets, some metrics manifest an almost
perfect correlation with human evaluation on the segment-level (e.g. WMT20
participating metrics record results of up to 0.97 Pearson correlation on the
newstest2020) Mathur et al. (2020b). However, research has also shown that
metrics usually report weaker correlation with low human assessment score
ranges Takahashi et al. (2020a, b).

In this paper, we argue that the high correlation of some metrics may not be
replicated with a different domain such as sentiment-oriented UGC,
specifically when there is a mistranslation of sentiment-critical word(s). For
this reason, we propose a ‘sentiment-closeness’ measure that can accommodate
for a better evaluation of the MT system’s ability to capture the correct
sentiment of the source text.

To present our sentiment quality measure, we first briefly explain in Section
2 why metrics commonly used for MT quality estimation may not always be
efficient in assessing sentiment-critical translation errors. In Section 3, we
present an experiment to quantitatively assess the divergence of the analysed
metrics from a human judgement of a correct/incorrect translation of an affect
message. Section 4 presents our proposed solution for fine-tuning quality
metrics for a better correlation with human judgement. Section 5 presents the
results of incorporating our sentiment-measure in different quality metrics.
In Section 6 we conduct an error analysis of our empirical approach and
discuss its limitations. Finally, Section 7 presents a conclusion on our
conducted experiments.

##  2 Available Metrics

Automatic evaluation metrics usually take the output of an MT system
(hypothesis) and compare it to one or several translations produced by human
translator(s) (reference). Based on their matching methods, the most commonly
used automatic metrics can be broadly categorised into: surface n-gram
matching and embedding matching. Surface n-gram methods work by calculating
exact matching, heuristic matching or an edit distance between the aligned
n-grams of the reference and hypothesis translation(s). The embedding methods,
on the other hand, calculate a similarity score between learned token
representations, such as contextual embedding vectors, with or without the aid
of external linguistic tools. In the following sections, we briefly explain
the methods behind three canonical metrics as representative of each category.
We illustrate why the theoretical foundation of each metric may not be optimum
for evaluating the translation of sentiment-oriented UGC.

###  2.1 Surface N-gram Matching Metrics

#### BLEU

The standard metric for assessing empirical improvement of MT systems is BLEU
(Papineni et al., 2002). Simply stated, the objective of BLEU is to compare
n-grams of the candidate translation with n-grams of the reference translation
and count the number of matches; the more the matches, the better the
candidate translation. The final score is calculated using a modified n-gram
precision multiplied by a brevity penalty so that a good candidate translation
would match the reference translation in length, in word choice, and in word
order. The disadvantage of the BLEU metric which is relevant to our present
study is that it treats all n-grams equally. Due to its restrictive surface
n-gram matching, it does not account for the semantic importance of an n-gram
in the context of a text. Accordingly, BLEU would incorrectly give a high
score to an MT output if it scores exact match with the reference except for
one uni-gram, even if this uni-gram completely changes the sentiment of a text
(e.g. ‘terrible’ and ‘great’ as in the Goodreads example above). Online built-
in MT tools have been shown to frequently transfer the exact opposite
sentiment word for some dialectical expressions in UGC translated into English
(Saadany and Orasan, 2020). Therefore, the BLEU evaluation of an MT
performance would be misleadingly over-permissive in such cases where only one
or two sentiment-critical words are mistranslated.

#### METEOR

METEOR (Banerjee and Lavie, 2005) incorporates semantic information as it
evaluates translation by calculating either exact match, stem match, or
synonymy match. For synonym matching, it utilises WordNet synsets (Pedersen et
al., 2004). More recent versions (METEOR 1.5 and METEOR++2.0) apply also
importance weighting by giving smaller weight to function words (Denkowski and
Lavie, 2014; Guo and Hu, 2019). The METEOR score ranges from 0 (worst
translation) to 1 (best translation). There are two shortcomings to the METEOR
metric which do not make it a robust solution for evaluating sentiment
transfer. First, the synonym matching is limited to checking whether the two
words belong to the same synset in WordNet. However, WordNet synonymy
classification is different than regular thesauruses. For example, ‘glad’ is a
synset of ‘happy’ and hence considered a synonym, whereas ‘cheerful’ is not a
direct synset to ‘happy’ and hence would be considered a mismatch by METEOR.
The following two examples illustrate further the limitations of using WordNet
synonymy by METEOR:

###### Example 1

Scores: [METEOR: 0.46]

  * •

Hypothesis: “The weather is sunny, what a happy day”

  * •

Reference: “The sun is shining, what a cheerful day”

###### Example 2

Scores: [METEOR: 0.48]

  * •

Hypothesis: “I’m not sure why, but I feel so happy today”

  * •

Reference: “I don’t get it, but I feel so sad today”

The METEOR scores for Examples 1 and 2 clearly diverge from a human evaluation
of a good translation. In the first example, although the translation conveys
the correct emotion (‘happiness’), it receives a similar METEOR score to the
hypothesis in the second example which gives the exact opposite emotion of the
source (‘happiness’ instead of ‘sadness’). The inadequate scoring is a result
of the WordNet taxonomy which causes the metric to equally treat both pairs
(‘sad’, ‘happy’) and (‘cheerful’, ‘happy’) as non-synonym synsets and hence
unmatched chunks.

The second problem with METEOR which may affect its efficacy in evaluating
sentiment transfer relates to its weighting schema for function and non-
function words. The following example clarifies the gravity of this problem:

###### Example 3

Scores: [METEOR: 0.92]

  * •

Hypothesis: “If he had blown himself up in your country, God would forgive
him”

  * •

Reference: “If he had blown himself up in your country, God would not
forgive”.

The hypothesis in Example 3 is the translation output of Twitter’s built-in MT
system for an Arabic tweet commenting on a terrorist
attack111https://twitter.com/gaston810/status/673950532340465664. The MT
failure to translate the negation marker flips the sentiment of the author
from ‘anger’ against the terrorist to ‘sympathy’. Despite this, the METEOR
score is 0.92 which is within the highest upper bound, ranking it as a good
translation. On the other hand, the METEOR score for a correct translation of
sentiment with a negation marker is 0.93. The main culprit for this inaccurate
scoring is the lexical weighting which causes the metric not to penalise the
missing of a negation marker which produces a sentiment-critical error. Due to
the grave consequences of such mistranslations, it becomes critical to have a
sentiment-sensitive metric that is capable of spotting similar errors.

###  2.2 Embedding-based Metrics

BERTScore Recently embedding-based metrics have proven to achieve the highest
performance in recent WMT shared tasks for quality metrics (e.g. Sellam et al.
(2020); Lo (2020); Mukherjee et al. (2020)). We take BERTScore as a
representative metric for this approach Zhang et al. (2019). BERTScore
computes a score based on a pair wise cosine similarity between the BERT
contextual embeddings of the individual tokens for the hypothesis and the
reference (Devlin et al., 2018). Accordingly, a BERTScore close to 1 indicates
proximity in vector space and hence a good translation. The main problem with
embedding-based metrics, such as BERTScore, is that antonyms contain similar
distributional information since they usually occur in similar contexts.
Example 4 illustrates this point:

###### Example 4

Scores: [BERTScore: 0.85]

  * •

Hypothesis: “What is this amount of anger, I don’t understand!”

  * •

Reference: “What is this amount of happiness, I don’t understand!”

Example 4 shows the mistranslation produced by Twitter’s Translate Tweet tab
of an Arabic tweet. Although the sentiment polarity is flipped in the
candidate translation above, the hypothesis receives a BERTScore of 0.85 which
indicates a high cosine similarity to the reference in vector space and hence
a good translation. Clearly, the metric score is not comparable to a human
perception of the emotion reflected by the source.

Figure 1 illustrates the reason behind this misleadingly high score. Figure 1
is a 2-D visualisation of BERT’s contextual embedding vectors for the
hypothesis translation (in blue) and the reference (in red). Both sentences
are very close in the embedding space due to the exact match of their
individual tokens. The only mismatch is between the antonyms ‘happiness’ and
‘anger’. As shown in the figure, the pre-trained embedding vectors of the
opposite polarity nouns are also quite close because of their common
contextual information. An embedding metric such as BERTScore, therefore, may
not penalise antonyms which typically occur in similar contexts.

Figure 1: Visualisation of Contextual Embeddings of Sentences in Example 4

Recently, there have been different approaches to overcome some distributional
problems of contextual embeddings. Reimers and Gurevych (2019), for example,
introduce SBert, a modification of the pretrained BERT network, which should
mitigate the antonymy problem. They use Siamese network structures where the
embeddings of similar sentence pairs are independently learned via two
parallel transformer architectures. We measured how far this technique could
solve the opposite sentiment problem by measuring the SBert sentence
similarity of the hypothesis and reference in Example 4. The cosine similarity
of the SBert sentence embedding vectors for the hypothesis and reference in
Example 4 reached 0.61. A correct translation of the reference, however, such
as ‘What is all this cheerfulness, I don’t understand’ has a cosine similarity
score of 0.79. This small similarity difference (0.18) would be misleading if
taken as an evaluation of how far the sentiment poles in the two hypotheses
are different. A more sentiment-targeted measure is needed for assessing
mistranslations due to this antonymy problem.

In the following section, we conduct an experiment to quantify the divergence
of the above mentioned metrics from the human perception of a proper sentiment
transfer in a translated text.

##  3 Evaluation of Mistranslated Sentiment

We have shown in the previous section that three canonical MT evaluation
metrics do not give a penalty proportional to sentiment-critical errors on
segment-level by an MT online tool. In order to quantify how far the
aforementioned quality metrics diverge or correlate with human judgement of
sentiment transfer, we measure the performance of each metric on a dataset of
tweets that had sentiment-critical translation errors. To compile this data,
first we used the Twitter built-in translation system (Google API) to
translate a dataset of tweets annotated for sentiment222The dataset is
collected from SemEval 2018 shared sentiment detection Task (Mohammad et al.,
2018). . The source dataset amounted to $\approx$7,000 tweets in three
languages: English, Arabic and Spanish. We translated the Arabic and Spanish
into English and the English was translated into Spanish and Arabic.

To extract instances where the MT system failed to translate the sentiment
correctly, we built an English sentiment-detection classifier by fine-tuning a
Roberta XML model (Liu et al., 2019) on an English dataset of 23,000 tweets
annotated for sentiment333The English dataset is collected from different
sentiment detection tasks Lo (2019); Mohammad and Bravo-Marquez (2017).. The
English classifier was used to predict the sentiment of the Google API output
for the translation of the Arabic and Spanish tweets into English and the
English back-translation of the English tweets translated into Spanish and
Arabic. The classifier’s predicted sentiment was compared to the gold standard
emotion of the source text, and instances of discrepancy were extracted as
potential mistranslations of sentiment. Finally, from the extracted instances,
we manually built a translation quality evaluation dataset.

The quality evaluation dataset, henceforth QE, consisted of target tweets
where the error is exclusively a mistranslation of the sentiment-carrying
lexicon. In these tweets, the mistranslations either completely flip the
sentiment polarity of the source tweet, similar to Examples 3 and 4 above, or
transfer the same polarity but with a mitigated sentiment tone. The tweets
with exclusive sentiment translation errors amounted to 300 tweets. We also
added 100 tweet/translation pairs where the MT system transfers the correct
sentiment. Reference translations of the QE dataset were created by native
speakers of the respective source languages. Essentially, the reference
translations aimed at correcting chunks that caused a distortion of the affect
message and retained as many of the hypothesis n-grams as possible to detect
how far each metric is sensitive to sentiment mismatching and not to the
mismatch in other non-sentiment carrying words. The translators were also
asked to assign a score to each pair of source-hypothesis tweet, where 1 is
the poorest sentiment transfer and 10 is best sentiment transfer. The average
scores of annotators were taken as the final human score444Annotators were
computational linguists working on MT research..

To quantify the ability of the three metrics explained in Section 2 to assess
the transfer of sentiment in the QE dataset, we compared their scores of the
translation hypotheses with the human judgement scores for sentiment transfer
on the segment-level. We followed the WMT standard methods for evaluating
quality metrics and used absolute Pearson correlation coefficient $r$ and the
Kendall correlation coefficient $|$$\tau$$|$ to evaluate each metric’s
performance against the human judgement. Figures 2 and 3 show heatmaps
visualising the Pearson and Kendall correlation coefficients for the studied
metrics and the human scores, respectively.

Figure 2: Absolute Pearson correlations with segment-level human judgements
for the QE dataset Figure 3: Kendall correlations with segment-level human
judgements for the QE dataset

As seen from Figures 2 and 3, both BERTScore and METEOR achieve a better
correlation with the human judgement than BLEU555We use the Sacrebleu
implementation of the BLEU score for all the experiments Post (2018). which
achieves only 0.16 and 0.12 Pearson and Kendall correlations, respectively.
However, the relatively overall low correlations (max $r$ = 0.39 and max
$|$$\tau$$|$ = 0.27) raise important doubts as to the reliability of these
accepted metrics for ranking MT systems which translate sentiments. Bearing in
mind that 75% of the segments in the QE dataset have critical translation
errors that seriously distort the sentiment, the low correlation results
highlight the need for a sentiment-targeted measure that can improve a
metric’s efficacy in capturing mistranslated sentiment by an MT system in
real-life scenarios.

##  4 Sentiment-Aware Measure (SAM) for Machine Translated UGC

In this section, we propose a new measure for assessing MT performance that
takes into account the sentiment similarity between the MT system translation
and the reference. This sentiment measure should be used as a fine-tuning tool
to adjust a quality score in cases where it is used to assess the translation
quality of sentiment-oriented text. The SAM score is calculated by using the
SentiWord dictionary of prior polarities (Gatti et al., 2015). SentiWord is a
sentiment lexicon that combines the high precision of manual lexica and the
high coverage of automatic ones (covering 155,000 words). It is based on
assigning a ‘prior polarity’ score for each lemma-POS in both SentiWordNet and
a number of human-annotated sentiment lexica (Baccianella et al., 2010;
Warriner et al., 2013). The prior polarity is the out-of-context positive or
negative score which a lemma-POS evokes. It is reached via an ensemble
learning framework that combines several formulae where each lemma-POS is
given the score that receives the highest number of votes from the different
formulae. SentiWord prior polarity scores have been proven to achieve the
highest correlation with human scores in sentiment analysis regression and
classification SemEval tasks (Gatti et al., 2015).

We assume that our sentiment adjustment factor, SAM, is proportional to the
distance between the sentiment scores of the unmatched words in the system
translation and the reference, the higher the distance the greater the SAM
adjustment. To calculate the SAM score, we designate the number of remaining
mismatched words in the system translation and reference translation by $m$
and $n$, respectively. We calculate the total SentiWord sentiment score for
the lemma-POS of the mismatched words in the translation and reference
sentences using a weighted average of the sentiment score of each mismatched
lemma-POS. The weight of a hypothesis mismatched word $w_{h}$ and a reference
mismatched word $w_{r}$ is calculated based on the sentiment score of its
lemma-POS, $s$, as follows:

$\displaystyle w^{i}_{h}$ $\displaystyle=|s_{i}|\qquad i=1,2,\ldots,m.$ (1)
$\displaystyle w^{i}_{r}$ $\displaystyle=|s_{i}|\qquad i=1,2,\ldots,n.$ (2)

Then the total sentiment score for hypothesis $S_{h}$ and reference $S_{r}$ is
given by:

$\displaystyle S_{h}$
$\displaystyle=\sum_{i=1}^{m}\alpha_{i}s_{i},\quad\alpha_{i}=\frac{w_{h}^{i}}{\sum_{i=1}^{m}w^{i}_{h}}$
(3) $\displaystyle S_{r}$
$\displaystyle=\sum_{i=1}^{n}\beta_{i}s_{i},\quad\beta_{i}=\frac{w_{r}^{i}}{\sum_{i=1}^{n}w^{i}_{r}}$
(4)

The normalised SAM adjustment is given by:

$\displaystyle p=\frac{|S_{r}-S_{h}|}{2}$ (5)

and the translation final score will be given by:

$\displaystyle\text{Score}=C_{hr}\left(1-p\right)$ (6)

where $C_{hr}$ can be any metric’s matching score between a translation
hypothesis and a reference segment. For this experiment, we will measure
$C_{hr}$ as the BLEU, METEOR and BERTScore scores. To illustrate how SAM score
adjusts a metric score with respect to the transfer of sentiment, table 1
shows the SAM score adjustment for Examples 3 and 4 above.

Table 1: Calculating the SAM adjustment for Examples 3 and 4 Example | $w_{h}$ | $w_{r}$ | $S_{h}$ | $S_{r}$ | $p$ | $C_{hr}$ | Score+SAM
---|---|---|---|---|---|---|---
3 | him#a | not#r | 0 | -1.0 | 0.5 | 0.92 | 0.46
[2pt/1pt] 4 | anger#n | happiness#n | -0.669 | 0.856 | 0.762 | 0.85 | 0.20

As can be seen from Table 1, the metric score $C_{hr}$ (here METEOR and
BERTScore, respectively) is significantly reduced due to the sentiment
distance between the mismatched words ($w_{h}$, $w_{r}$) as well as their
sentiment weights ($S_{h}$, $S_{r}$). The reduced scores are more
representative of the distortion of sentiment produced by the MT system in
Examples 3 and 4. The SAM adjustment, therefore, is a targeted-measure that
can fine-tune a metric according to the ‘sentiment-closeness’ of the
translation and the reference666More examples of SAM adjustments are in
Appendix A.

##  5 Assessing SAM performance

To check how far the SAM measure can improve the evaluation of sentiment, we
assessed the performance of the three chosen metrics on the QE dataset
utilised in the experiment in Section 3 with the SAM adjustment. Figures 4 and
5 show heatmaps of the Pearson and Kendall correlations of the SAM adjusted
metrics with the human judgement in the QE dataset.

Figure 4: Absolute Pearson correlations with SAM Adjustment for the QE dataset
Figure 5: Kendall correlations with SAM adjustment for the QE dataset

Compared to metric scores without the SAM adjustment, Figures 4 and 5 show
that the combination of SAM with the three metrics consistently leads to an
improvement in each metric’s correlation with the human judgement of a correct
sentiment transfer in our dataset. Overall, BERTScore records the highest
Pearson correlation coefficients and Kendall rank dependence (0.59 and 0.44,
respectively). This means that it is better able to penalise critical
translation errors in our QE dataset. Moreover, compared to their scores
without SAM, both BERTScore and METEOR record 20% and 18% higher correlation,
respectively. It is also worthy of notice, that although the Pearson
correlation of BLEU improves from 0.16 to 0.33 with the SAM adjustment, the
correlation is still relatively small. Knowing that BLEU score is usually the
gate-keeping tool for accepting improvement in MT research, the results cast
doubt on the efficacy of this non-semantic method to penalise sentiment-
critical translation errors.

##  6 Error Analysis and Limitations

Human sentiment can be expressed in intricately subtle ways so that the
mistranslation of the affect message is not necessarily reflected in
divergence of polarity scores. We conducted an error analysis on instances
where the SAM adjustment scores were not able to capture the MT’s failure to
transfer the correct sentiment due to different linguistic phenomena. The
first phenomenon we identified is related to structure shifting. For example,
the sentiment distance between the source tweet ‘I was saddened by him’ and
its mistranslation ‘I made him sad’ is very small despite the flipping of
sentiment direction in the translation. The three metrics with and without the
SAM adjustment failed to penalise this type of distortion in the QE dataset.
Second, some words in the lexicon did not have a score representative of their
sentiment weight. For example, most prepositions in the SentiWord lexicon are
neutral, yet by checking the data, it was found out that a mistranslation of a
preposition can distort the affect message. For example, the source tweet
‘What is the benefit of me in this world’ was mistranslated by the MT system
as ‘What is the benefit for me in this world’; the wrong preposition causes
the translation to lose the sad tone in the source tweet. Again, similar
instances were not adequately measured with the three metrics with and without
the SAM adjustment. Third, some nuanced sentiment-carrying words specific for
the informal style of tweets caused a mistranslation of sentiment which was
not captured by our approach. For instance, a one-word tweet referring to a
political figure as ‘Prick’ was mistranslated as ‘Sting’. The source is a
slang word used to refer to a mean, contemptible man. The translation wrongly
received a high score since both ‘prick’ and ‘sting’ had very similar negative
sentiment weights. The translation, however, fails to reflect the aggressive
sentiment in the source tweet. The BLEU metric, on the other hand, succeeded
in giving a penalty to similar short mistranslated tweets without the SAM
adjustment.

One other limitation to the current approach for assessing the translation of
sentiment is that it relies on an English sentiment lexicon. The applicability
of this approach to other languages depends on the availability of a similar
high-precision and high-coverage sentiment lexicon. We have overcome this
problem by using the English backtranslations of the Arabic and Spanish tweets
in the QE dataset. There are, however, multilingual translations of English
sentiment lexica that are commonly used in the sentiment-analysis of non-
English text. It remains to be tested how far a translated sentiment lexicon
is capable of measuring sentiment transfer among different language pairs by
the SAM scoring approach.

##  7 Conclusion

The most frequent scenario in which an MT system is used to translate
sentiment-oriented text is for the translation of online UGC such as tweets,
reviews or social media posts. The users of the MT online tool take these
translations at face-value as there is no human intervention for accuracy
checking. It is important, therefore, to ensure the reliability of the MT
system to accurately transfer the author’s affect message before it is used as
an online tool. The reliability of an MT system with such big data is commonly
measured by automatic metrics. We have shown that conventionally accepted
metrics may not always be an optimum solution for assessing the translation of
sentiment-oriented UGC. We presented an empirical approach to quantify the
notion of sentiment transfer by an MT system and, more concretely, to modify
automatic metrics such that its MT ranking comes closer to a human judgement
of a poor or good translation of sentiment. Despite limitations to our
approach, the SAM adjustment serves as a proxy to the complicated task of
manually evaluating the translation of sentiment across different languages.

## Acknowledgements

This research work has been supported in part by the TranSent project at the
Centre for Translation Studies (CTS) of the University of Surrey.

## References

  * Baccianella et al. (2010) Stefano Baccianella, Andrea Esuli, and Fabrizio Sebastiani. 2010.  Sentiwordnet 3.0: An Enhanced Lexical Resource for Sentiment Analysis and Opinion Mining.  In _Lrec_ , volume 10, pages 2200–2204.
  * Banerjee and Lavie (2005) Satanjeev Banerjee and Alon Lavie. 2005.  METEOR: An automatic metric for MT evaluation with improved correlation with human judgments.  In _Proceedings of the ACL Workshop on Intrinsic and Extrinsic Evaluation Measures for Machine Translation and/or Summarization_ , pages 65–72.
  * Barrault et al. (2019) Loïc Barrault, Ondřej Bojar, Marta R. Costa-jussà, Christian Federmann, Mark Fishel, Yvette Graham, Barry Haddow, Matthias Huck, Philipp Koehn, Shervin Malmasi, Christof Monz, Mathias Müller, Santanu Pal, Matt Post, and Marcos Zampieri. 2019.  Findings of the 2019 conference on machine translation (WMT19).  In _Proceedings of the Fourth Conference on Machine Translation (Volume 2: Shared Task Papers, Day 1)_ , pages 1–61, Florence, Italy. Association for Computational Linguistics.
  * Denkowski and Lavie (2014) Michael Denkowski and Alon Lavie. 2014.  Meteor universal: Language specific translation evaluation for any target language.  In _Proceedings of the Ninth Workshop on Statistical Machine Translation_ , pages 376–380.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  BERT: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_.
  * Gatti et al. (2015) Lorenzo Gatti, Marco Guerini, and Marco Turchi. 2015.  Sentiwords: Deriving a high precision and high coverage lexicon for sentiment analysis.  _IEEE Transactions on Affective Computing_ , 7(4):409–421.
  * Guo and Hu (2019) Yinuo Guo and Junfeng Hu. 2019.  METEOR++ 2.0: Adopt Syntactic Level Paraphrase Knowledge into Machine Translation Evaluation.  In _Proceedings of the Fourth Conference on Machine Translation (Volume 2: Shared Task Papers, Day 1)_ , pages 501–506.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized BERT pretraining approach.  _arXiv preprint arXiv:1907.11692_.
  * Lo (2019) Chi-kiu Lo. 2019.  YiSi-A unified semantic MT quality evaluation and estimation metric for languages with different levels of available resources.  In _Proceedings of the Fourth Conference on Machine Translation (Volume 2: Shared Task Papers, Day 1)_ , pages 507–513.
  * Lo (2020) Chi-kiu Lo. 2020.  Extended study on using pretrained language models and YiSi-1 for machine translation evaluation.  In _Proceedings of the Fifth Conference on Machine Translation_ , pages 895–902.
  * Ma et al. (2018) Qingsong Ma, Ondřej Bojar, and Yvette Graham. 2018.  Results of the WMT18 metrics shared task: Both characters and embeddings achieve good performance.  In _Proceedings of the Third Conference on Machine Translation: Shared Task Papers_ , pages 671–688.
  * Mathur et al. (2020a) Nitika Mathur, Tim Baldwin, and Trevor Cohn. 2020a.  Tangled up in BLEU: Reevaluating the Evaluation of Automatic Machine Translation Evaluation Metrics.  _arXiv preprint arXiv:2006.06264_.
  * Mathur et al. (2020b) Nitika Mathur, Johnny Wei, Markus Freitag, Qingsong Ma, and Ondřej Bojar. 2020b.  Results of the WMT20 Metrics Shared Task.  In _Proceedings of the Fifth Conference on Machine Translation_ , pages 688–725.
  * Mohammad and Bravo-Marquez (2017) Saif M. Mohammad and Felipe Bravo-Marquez. 2017.  WASSA-2017 shared task on emotion intensity.  In _Proceedings of the Workshop on Computational Approaches to Subjectivity, Sentiment and Social Media Analysis (WASSA)_ , Copenhagen, Denmark.
  * Mohammad et al. (2018) Saif M. Mohammad, Felipe Bravo-Marquez, Mohammad Salameh, and Svetlana Kiritchenko. 2018.  Semeval-2018 Task 1: Affect in tweets.  In _Proceedings of International Workshop on Semantic Evaluation (SemEval-2018)_ , New Orleans, LA, USA.
  * Mukherjee et al. (2020) Ananva Mukherjee, Hema Ala, Manish Shrivastava, and Dipti Misra Sharma. 2020.  Mee: An automatic metric for evaluation using embeddings for machine translation.  In _2020 IEEE 7th International Conference on Data Science and Advanced Analytics (DSAA)_ , pages 292–299. IEEE.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  Bleu: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics_ , pages 311–318.
  * Pedersen et al. (2004) Ted Pedersen, Siddharth Patwardhan, Jason Michelizzi, et al. 2004.  Wordnet: Similarity-measuring the relatedness of concepts.  In _AAAI_ , volume 4, pages 25–29.
  * Post (2018) Matt Post. 2018.  A call for clarity in reporting BLEU scores.  _arXiv preprint arXiv:1804.08771_.
  * Reimers and Gurevych (2019) Nils Reimers and Iryna Gurevych. 2019.  Sentence-bert: Sentence embeddings using siamese bert-networks.  _arXiv preprint arXiv:1908.10084_.
  * Reiter (2018) Ehud Reiter. 2018.  A Structured Review of the Validity of BLEU.  _Computational Linguistics_ , 44(3):393–401.
  * Saadany and Orasan (2020) Hadeel Saadany and Constantin Orasan. 2020.  Is it great or terrible? preserving sentiment in neural machine translation of Arabic reviews.  In _Proceedings of the Fifth Arabic Natural Language Processing Workshop_ , pages 24–37, Barcelona, Spain (Online). Association for Computational Linguistics.
  * Sellam et al. (2020) Thibault Sellam, Amy Pu, Hyung Won Chung, Sebastian Gehrmann, Qijun Tan, Markus Freitag, Dipanjan Das, and Ankur P. Parikh. 2020.  Learning to evaluate translation beyond english: Bleurt submissions to the wmt metrics 2020 shared task.
  * Takahashi et al. (2020a) Kosuke Takahashi, Katsuhito Sudoh, and Satoshi Nakamura. 2020a.  Automatic machine translation evaluation using source language inputs and cross-lingual language model.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 3553–3558, Online. Association for Computational Linguistics.
  * Takahashi et al. (2020b) Yujin Takahashi, Satoru Katsumata, and Mamoru Komachi. 2020b.  Grammatical error correction using pseudo learner corpus considering learner’s error tendency.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics: Student Research Workshop_ , pages 27–32, Online. Association for Computational Linguistics.
  * Warriner et al. (2013) Amy Beth Warriner, Victor Kuperman, and Marc Brysbaert. 2013.  Norms of valence, arousal, and dominance for 13,915 English lemmas.  _Behavior research methods_ , 45(4):1191–1207.
  * Zhang et al. (2019) Tianyi Zhang, Varsha Kishore, Felix Wu, Kilian Q Weinberger, and Yoav Artzi. 2019\.  BERTScore: Evaluating text generation with Bert.  _arXiv preprint arXiv:1904.09675_.

##  Appendix A Examples for Mistranslated Tweets Measured with and without SAM
adjustment


# Two types of the second Hankel determinant for the class
$\boldsymbol{{\mathcal{U}}}$ and the general class
$\boldsymbol{{\mathcal{S}}}$

Milutin Obradović  Department of Mathematics, Faculty of Civil Engineering,
University of Belgrade, Bulevar Kralja Aleksandra 73, 11000, Belgrade, Serbia.
<EMAIL_ADDRESS>and  Nikola Tuneski  Department of Mathematics and
Informatics, Faculty of Mechanical Engineering, Ss. Cyril and Methodius
University in Skopje, Karpoš II b.b., 1000 Skopje, Republic of North
Macedonia<EMAIL_ADDRESS>
###### Abstract.

In this paper we determine the upper bounds of the Hankel determinants of
special type $H_{2}(3)(f)$ and $H_{2}(4)(f)$ for the class of univalent
functions and for the class ${\mathcal{U}}$ defined by

${\mathcal{U}}=\left\\{f\in{\mathcal{A}}:\left|\left[\frac{z}{f(z)}\right]^{2}f^{\prime}(z)-1\right|<1,\,z\in{\mathbb{D}}\right\\},$

where ${\mathcal{A}}$ is the class of functions analytic in the unit disk
${\mathbb{D}}$ and normalized such that $f(z)=z+a_{2}z^{2}+\cdots$.

###### Key words and phrases:

second order Hankel determinant, class ${\mathcal{U}}$, classes of univalent
functions

###### 1991 Mathematics Subject Classification:

30C45, 30C55

##  1\. Introduction and preliminaries

Let class ${\mathcal{A}}$ consists of functions analytic in the unit disk
${\mathbb{D}}:=\\{|z|<1\\}$ and are normalized such that

(1) $f(z)=z+a_{2}z^{2}+a_{3}z^{3}+\cdots,$

i.e., $f(0)=0=f^{\prime}(0)-1$; and ${\mathcal{S}}$ be the class of functions
from ${\mathcal{A}}$ that are univalent in ${\mathbb{D}}$.

In his paper [7] Zaprawa considered the following Hankel determinant of second
order defined for the coefficients of the function given by (1)

$H_{2}(n)(f)=\left|\begin{array}[]{cc}a_{n}&a_{n+1}\\\
a_{n+1}&a_{n+2}\end{array}\right|=a_{n}a_{n+2}-a_{n+1}^{2},$

for the case when $n=3$. The author studied the upper bound of
$|H_{2}(3)(f)|=|a_{3}a_{5}-a_{4}^{2}|$ in the cases when $f$ from
${\mathcal{A}}$ is starlike (${\operatorname{Re}\,}[zf^{\prime}(z)/f(z)]>0$,
$z\in{\mathcal{U}}$), convex
(${\operatorname{Re}\,}[1+zf^{\prime\prime}(z)/f^{\prime}(z)]>0$,
$z\in{\mathcal{U}}$), and with bounded turning
(${\operatorname{Re}\,}f^{\prime}(z)>0$, $z\in{\mathcal{U}}$). These types of
functions were studied separately, under the condition that the functions are
missing their second coefficient, i.e, $a_{2}=0$. For the general class
${\mathcal{S}}$, he proved that $|H_{2}(3)(f)|>1$. In [6] the authors gave
sharp bounds of the modulus of the second Hankel determinant of type
$H_{2}(2)$ of inverse coefficients for various classes of univalent functions.

Another interesting subclass of ${\mathcal{S}}$ attracting significant
interest in the past two decades is

${\mathcal{U}}=\left\\{f\in{\mathcal{A}}:\left|\left[\frac{z}{f(z)}\right]^{2}f^{\prime}(z)-1\right|<1,\,z\in{\mathbb{D}}\right\\}.$

More details can be found in [3] and Chapter 12 from [5].

The object of this paper is to find upper bounds (preferably sharp) of the
modulus of the Hankel determinants $H_{2}(3)(f)=a_{3}a_{5}-a_{4}^{2}$ and
$H_{2}(4)(f)=a_{4}a_{6}-a_{5}^{2}$ for the class ${\mathcal{U}}$, as well as
for the general class ${\mathcal{S}}$.

##  2\. Class ${\mathcal{U}}$

For the functions $f$ from the class ${\mathcal{U}}$ in [4], as a pert of the
proof of Theorem 1, the following was proven

(2) $\frac{z}{f(z)}=1-a_{2}z-z\omega(z),$

where $|\omega(z)|\leq|z|<1$ and $|\omega^{\prime}(z)|\leq 1$ for all
$z\in{\mathbb{D}}$, and additionally, for
$\omega(z)=c_{1}z+c_{2}z^{2}+\cdots,$

(3) $|c_{1}|\leq
1,\quad|c_{2}|\leq\frac{1}{2}(1-|c_{1}|^{2})\quad\text{and}\quad|c_{3}|\leq\frac{1}{3}\left[1-|c_{1}|^{2}-\frac{4|c_{2}|^{2}}{1+|c_{1}|}\right].$

In a similar way, since $|\omega^{\prime}(z)|\leq 1$ one can verify that

$|c_{4}|\leq\frac{1}{4}(1-|c_{1}|^{2}-4|c_{2}|^{2}).$

Further, from (2), we have

$z=f(z)\left[1-\left(a_{2}z+c_{1}z^{2}+c_{2}z^{3}+\cdots\right)\right],$

and after equating the coefficients,

(4) $\begin{split}a_{3}&=c_{1}+a^{2}_{2},\\\
a_{4}&=c_{2}+2a_{2}c_{1}+a_{2}^{3},\\\
a_{5}&=c_{3}+2a_{2}c_{2}+c_{1}^{2}+3a_{2}^{2}c_{1}+a_{2}^{4}\\\
a_{6}&=c_{4}+2a_{2}c_{3}+2c_{1}c_{2}+3a_{2}^{2}c_{2}+3a_{2}c_{1}^{2}+4a_{2}^{3}c_{1}+a_{2}^{5}.\end{split}$

Now we can prove the estimates for the class ${\mathcal{U}}$.

######  Theorem 1.

Let $f\in{\mathcal{U}}$. Then

  * (a)

$|H_{2}(3)(f)|\leq 1$ if $a_{2}=0$, and the result is sharp due to the
function $f(z)=\frac{z}{1-z^{2}}=z+z^{3}+z^{5}+\cdots$.

  * (b)

$|H_{2}(3)(f)|\leq 1.4846575\ldots$ for every $f\in{\mathcal{U}}$.

###### Proof.

Using (4), after some calculations we receive

$H_{2}(3)(f)=a_{3}a_{5}-a_{4}^{2}=(c_{1}+a_{2}^{2})c_{3}-2a_{2}c_{1}c_{2}+c_{1}^{3}-c_{2}^{2},$

and from here

(5)
$|H_{2}(3)(f)|\leq|c_{1}+a_{2}^{2}||c_{3}|+2|a_{2}||c_{1}||c_{2}|+|c_{1}|^{3}+|c_{2}|^{2}.$

  * (a)

If $a_{2}=0$, from (5) we receive

$|H_{2}(3)(f)|\leq|c_{1}||c_{3}|+|c_{1}|^{3}+|c_{2}|^{2},$

and using (3),

$\begin{split}|H_{2}(3)(f)|&\leq|c_{1}|\cdot\frac{1}{3}\cdot\left[1-|c_{1}|^{2}-\frac{4|c_{2}|^{2}}{1+|c_{1}|}\right]+|c_{1}|^{3}+|c_{2}|^{2}\\\
&=\frac{1}{3}\left(|c_{1}|-|c_{1}|^{3}\right)+\frac{3-|c_{1}|}{3(1+|c_{1}|)}|c_{2}|^{2}+|c_{1}|^{3}\\\
&\leq\frac{1}{3}|c_{1}|+\frac{2}{3}|c_{1}|^{3}+\frac{3-|c_{1}|}{3(1+|c_{1}|)}\frac{1}{4}(1-|c_{1}|^{2})^{2}\\\
&=\frac{1}{12}\left(3-2|c_{1}|^{2}+12|c_{1}|^{3}-|c_{1}|^{4}\right)\equiv
h_{1}(|c_{1}|),\end{split}$

where $h_{1}(t)=\frac{1}{12}\left(3-2t^{2}+12t^{3}-t^{4}\right)$ and
$t=|c_{1}|\leq 1$ (see (3)). Now,
$h_{1}^{\prime}(t)=-\frac{1}{3}c(1-9c+c^{2})$ vanishes in only one point on
the interval $(0,1)$ and that is a minimum of $h_{1}$ on the interval since
$h_{1}(t)<0$ for small enough positive numbers (let say for $t=0.1$).
Therefore

$\max\\{h_{1}(t):t\in[0,1]\\}=\max\\{h_{1}(0),h_{1}(1)\\}=h_{1}(1)=1,$

i.e., $|H_{2}(3)(f)|\leq 1$. The sharpness of the estimate follows from the
function $f(z)=\frac{z}{1-z^{2}}$ with $a_{2}=a_{4}=0$ and $a_{3}=a_{5}=1$.

  * (b)

Since ${\mathcal{U}}\subset{\mathcal{S}}$, we have $|a_{2}|\leq 2$ and
$|a_{3}|=|c_{1}+a_{2}^{2}|\leq 3$, from (5) we have

$|H_{2}(3)(f)|\leq
3|c_{3}|+4|c_{1}||c_{2}|+|c_{1}|^{3}+|c_{2}|^{2}\equiv\varphi_{1}(|c_{1}|,|c_{2}|,|c_{3}|),$

where $\varphi_{1}(x,y,z)=3z+4xy+x^{3}+y^{2}$ with due to (3),

$0\leq x\leq 1,\quad 0\leq y\leq\frac{1}{2}(1-x^{2}),\quad 0\leq
z\leq\frac{1}{3}\left(1-x^{2}-\frac{4y^{2}}{1+x}\right).$

It evident that

$\begin{split}\varphi_{1}(x,y,z)&\leq
3\cdot\frac{1}{3}\left(1-x^{2}-\frac{4y^{2}}{1+x}\right)+4xy+x^{3}+y^{2}\\\
&=1-x^{2}+\left(4-\frac{4}{1+x}\right)y^{2}-3y^{2}+4xy+x^{3}\\\ &\leq
1-x^{2}+\frac{4x}{1+x}\cdot\frac{1}{4}\left(1-x^{2}\right)^{2}-3y^{2}+4xy+x^{3}\\\
&=1+x-2x^{2}+x^{4}+4xy-3y^{2}\equiv\psi(x,y).\end{split}$

It remains to find the maximal value of $\psi$ on the domain
$\Omega_{1}=\Big{\\{}(x,y):0\leq x\leq 1,\,0\leq
y\leq\frac{1}{2}(1-x^{2})\Big{\\}}$.

Since $\psi^{\prime}_{y}(x,y)=4x-6y$ vanishes for $x=\frac{3}{2}y$, and
$\psi^{\prime}_{x}(3y/2,y)=1-2y+\frac{27}{2}y^{3}$ vanishes only for
$y=-0.535\ldots$ we realize that $\psi$ attains its maximal value on the
boundary of $\Omega_{1}$. Finally, when $x=0$ or $x=1$, the maximum is 1,
while for $y=0$, maximum is $1.1295\ldots$ for $x=0.26959\ldots$, and for
$y=\frac{1}{2}(1-x^{2})$, maximum is $1.4846575\ldots$, for $x=0.6618\ldots$.
This completes the proof.

∎

######  Theorem 2.

Let $f\in{\mathcal{U}}$ and $a_{2}=0$. Then $|H_{2}(4)(f)|\leq 1$ and the
estimate is sharp due to the function
$f(z)=\frac{z}{1-z^{2}}=z+z^{3}+z^{5}+z^{7}+\cdots$.

###### Proof.

If $f\in{\mathcal{U}}$ and $a_{2}=0$, then from (4) we receive

$a_{4}=c_{2},\quad a_{5}=c_{3}+c_{1}^{2},\quad c_{6}=c_{4}+2c_{1}c_{2},$

and further,

$H_{2}(4)(f)=a_{4}a_{6}-a_{5}^{2}=c_{2}c_{4}+2c_{1}c_{2}^{2}-c_{3}^{2}-2c_{1}^{2}c_{3}+c_{1}^{4},$

and using (3),

$\begin{split}&\quad|H_{2}(4)(f)|\\\
&\leq|c_{2}||c_{4}|+2|c_{1}||c_{2}|^{2}+|c_{3}|^{2}+2|c_{1}|^{2}|c_{3}|+|c_{1}|^{4}\\\
&\leq\frac{1}{2}(1-|c_{1}|^{2})\cdot\frac{1}{4}(1-|c_{1}|^{2}-4|c_{2}|^{2})+2|c_{1}||c_{2}|^{2}+\frac{1}{9}\left(1-|c_{1}|^{2}-\frac{4|c_{2}|^{2}}{1+|c_{1}|}\right)^{2}\\\
&\quad+2|c_{1}|^{2}\cdot\frac{1}{3}\left(1-|c_{1}|^{2}-\frac{4|c_{2}|^{2}}{1+|c_{1}|}\right)+|c_{1}|^{4}\\\
&=A|c_{2}|^{4}+B|c_{2}|^{2}+C\equiv h_{2}(|c_{2}|),\end{split}$

where $h_{2}(t)=At^{4}+Bt^{2}+C$,

$\begin{split}A&=\frac{16}{9(1+|c_{1}|)^{2}},\\\
B&=2|c_{1}|-\frac{1}{2}(1-|c_{1}|^{2})-\frac{8}{9}(1-|c_{1}|)-\frac{8}{3}\frac{|c_{1}|^{2}}{1+|c_{1}|},\\\
C&=\frac{17}{72}(1-|c_{1}|^{2})^{2}+\frac{2}{3}|c_{1}|^{2}(1-|c_{1}|^{2})+|c_{1}|^{4},\end{split}$

with $A>0$, $0\leq|c_{2}|\leq\frac{1}{2}(1-|c_{1}|^{2})$ and $|c_{1}|\leq 1$.
Therefore, $h_{2}$ attains its maximal value on the boundary, i.e.,

$\max
h_{2}(|c_{2}|)=\max\left\\{h_{2}(0),h_{2}\left(\frac{1}{2}(1-|c_{1}|^{2})\right)\right\\}.$

Now, let note that $h_{2}(0)=C\equiv g_{1}(|c_{1}|)$, where
$g_{1}(t)=\frac{1}{72}(41t^{4}+14t^{2}+17)$, has a maximal value 1 when $0\leq
t=|c_{1}|\leq 1$, attained for $t=1$.

Further, let $g_{2}(|c_{1}|)\equiv
h_{2}\left(\frac{1}{2}(1-|c_{1}|^{2})\right)$, where

$g_{2}(t)=\frac{1}{72}(17t^{6}-12t^{5}+38t^{4}-24t^{3}+17t^{2}+36t),$

$0\leq t=|c_{1}|\leq 1$. In order to complete the proof of the theorem it is
enough to show that this function is increasing on the interval $[0,1]$, which
will lead to the conclusion that
$h_{2}\left(\frac{1}{2}(1-|c_{1}|^{2})\right)=g_{2}(|c_{1}|)\leq g_{2}(1)=1$.

Indeed,
$g_{2}^{\prime\prime\prime}(t)=\frac{1}{72}\left(1020t^{2}-288t+228\right)>0$
for all $t\in[0,1]$, meaning that
$g_{2}^{\prime\prime}(t)=\frac{1}{72}\left(340t^{3}-144t^{2}+228t-48\right)$
is increasing on the same interval. Since $g_{2}^{\prime\prime}(0)<0$ and
$g_{2}^{\prime\prime}(1)>0$, there is only one real solution of
$g_{2}^{\prime\prime}(t)=0$ on $[0,1]$, i.e., only one local extreme (minimum)
on $[0,1]$ for $t_{*}=0.22554\ldots$ with value
$g_{2}^{\prime}(t_{*})=39.028\ldots>0$. Thus, $g_{2}^{\prime}(t)>0$ for all
$t\in[0,1]$. ∎

Theorem 1(a) and Theorem 2 are motivation for the following conjecture for the
functions from ${\mathcal{U}}$ with missing second coefficient.

######  Conjecture 1.

Let $f\in{\mathcal{U}}$ and $a_{2}=0$. Then
$|H_{2}(n)(f)|=|a_{n}a_{n+2}-a_{n+1}^{2}|\leq 1$ for any integer $n\geq 3$.
The estimate is a sharp due to the function
$f(z)=\frac{z}{1-z^{2}}=\sum_{n=1}^{\infty}z^{2n-1}$.

##  3\. General class ${\mathcal{S}}$

For obtaining the estimates of the modulus of $H_{2}(3)(f)$ for the general
class $\mathcal{S}$ we will use method based on Grunsky coefficients based on
the results and notations given in the book of N.A. Lebedev ([2]) as follows.

Let $f\in\mathcal{S}$ and let

$\log\frac{f(t)-f(z)}{t-z}=\sum_{p,q=0}^{\infty}\omega_{p,q}t^{p}z^{q},$

where $\omega_{p,q}$ are the Grunsky’s coefficients with property
$\omega_{p,q}=\omega_{q,p}$. For those coefficients the next Grunsky’s
inequality ([1, 2]) holds:

(6)
$\sum_{q=1}^{\infty}q\left|\sum_{p=1}^{\infty}\omega_{p,q}x_{p}\right|^{2}\leq\sum_{p=1}^{\infty}\frac{|x_{p}|^{2}}{p},$

where $x_{p}$ are arbitrary complex numbers such that last series converges.

Further, it is well-known that if the function $f$ given by (1) belongs to
$\mathcal{S}$, then also

(7) $\tilde{f_{2}}(z)=\sqrt{f(z^{2})}=z+c_{3}z^{3}+c_{5}z^{5}+\cdots$

belongs to the class $\mathcal{S}$. Then, for the function $\tilde{f_{2}}$ we
have the appropriate Grunsky’s coefficients of the form
$\omega_{2p-1,2q-1}^{(2)}$ and the inequality (6) has the form:

(8)
$\sum_{q=1}^{\infty}(2q-1)\left|\sum_{p=1}^{\infty}\omega_{2p-1,2q-1}x_{2p-1}\right|^{2}\leq\sum_{p=1}^{\infty}\frac{|x_{2p-1}|^{2}}{2p-1}.$

Here, and further in the paper we omit the upper index (2) in
$\omega_{2p-1,2q-1}^{(2)}$ if compared with Lebedev’s notation.

If in the inequality (8) we put $x_{1}=1$ and $x_{2p-1}=0$ for $p=2,3,\ldots$,
then we receive

(9)
$|\omega_{11}|^{2}+3|\omega_{13}|^{2}+5|\omega_{15}|^{2}+7|\omega_{17}|^{2}\leq
1.$

As it has been shown in [2, p.57], if $f$ is given by (1) then the
coefficients $a_{2}$, $a_{3}$, $a_{4}$ and $a_{5}$ are expressed by Grunsky’s
coefficients $\omega_{2p-1,2q-1}$ of the function $\tilde{f}_{2}$ given by (7)
in the following way:

(10) $\begin{split}a_{2}&=2\omega_{11},\\\
a_{3}&=2\omega_{13}+3\omega_{11}^{2},\\\
a_{4}&=2\omega_{33}+8\omega_{11}\omega_{13}+\frac{10}{3}\omega_{11}^{3},\\\
a_{5}&=2\omega_{35}+8\omega_{11}\omega_{33}+5\omega_{13}^{2}+18\omega_{11}^{2}\omega_{13}+\frac{7}{3}\omega_{11}^{4},\\\
0&=3\omega_{15}-3\omega_{11}\omega_{13}+\omega_{11}^{3}-3\omega_{33},\\\
0&=\omega_{17}-\omega_{35}-\omega_{11}\omega_{33}-\omega_{13}^{2}+\frac{1}{3}\omega_{11}^{4}.\end{split}$

We note that in the cited book of Lebedev there exists a typing mistake for
the coefficient $a_{5}$. Namely, instead of the term $5\omega_{13}^{2}$, there
is $5\omega_{15}^{2}$.

######  Theorem 3.

Let $f\in\mathcal{S}$ is given by (1). Then

  * (a)

$|H_{2}(3)(f)|\leq 2.02757\ldots$ if $a_{2}=0$;

  * (b)

$|H_{2}(3)(f)|\leq 4.8986977\ldots$ for every $f\in{\mathcal{S}}$.

###### Proof.

From the fifth relation of (10) we have

$\omega_{33}=\omega_{15}-\omega_{11}\omega_{13}+\frac{1}{3}\omega_{11}^{3}.$

This, together with the sixth relation from (10) brings

$\omega_{35}=\omega_{17}-\omega_{11}\omega_{15}+\omega_{11}^{2}\omega_{13}-\omega_{13}^{2}.$

By applying the two expressions from above in the relations for $a_{4}$ and
$a_{5}$ from (10) we obtain

$\begin{split}a_{4}&=2\omega_{15}+6\omega_{11}\omega_{13}+4\omega_{11}^{3},\\\
a_{5}&=2\omega_{17}+6\omega_{11}\omega_{15}+12\omega_{11}^{2}\omega_{13}+3\omega_{13}^{2}+5\omega_{11}^{4}.\end{split}$

Finally, these two relations, together with the relation for $a_{3}$ from (10)
bring

(11) $\begin{split}H_{2}(3)(f)&=a_{3}a_{5}-a_{4}^{2}\\\
&=2(2\omega_{13}+3\omega_{11}^{2})\omega_{17}-12\omega_{11}\omega_{13}\omega_{15}-3\omega_{11}^{2}\omega_{13}^{2}+6\omega_{13}^{3}\\\
&\quad-2\omega_{11}^{4}\omega_{13}+2\omega_{11}^{3}\omega_{15}-\omega_{11}^{6}-4\omega_{15}^{2}.\end{split}$

  * (a)

If $a_{2}=2\omega_{11}=0$, then $\omega_{11}=0$, and we receive

$H_{2}(3)(f)=4\omega_{13}\omega_{17}+6\omega_{13}^{3}-4\omega_{15}^{2},$

with the following constraints over $\omega_{13}$, $\omega_{15}$ and
$\omega_{17}$ obtained from (9):

$|\omega_{13}|\leq\frac{1}{\sqrt{3}},\quad|\omega_{15}|\leq\frac{1}{\sqrt{5}}\sqrt{1-3|\omega_{13}|^{2}},$

and

$|\omega_{17}|\leq\frac{1}{\sqrt{7}}\sqrt{1-3|\omega_{13}|^{2}-5|\omega_{15}|^{2}}.$

So,

$\begin{split}|H_{2}(3)(f)|&=4|\omega_{13}||\omega_{17}|+6|\omega_{13}|^{3}+4|\omega_{15}|^{2}\\\
&\leq\frac{4}{\sqrt{7}}|\omega_{13}|\sqrt{1-3|\omega_{13}|^{2}-5|\omega_{15}|^{2}}+6|\omega_{13}|^{3}+4|\omega_{15}|^{2}\\\
&=\psi_{1}(|\omega_{13}|,|\omega_{15}|),\end{split}$

where $\psi_{1}(y,z)=\frac{4}{\sqrt{7}}y\sqrt{1-3y^{2}-5z^{2}}+6y^{3}+4z^{2}$
with $0\leq y=|\omega_{13}|\leq\frac{1}{\sqrt{3}}$, $0\leq
z=|\omega_{15}|\leq\frac{1}{\sqrt{5}}\sqrt{1-3y^{2}}$. It remains to find
upper bound of the function $\psi_{1}(y,z)$ on its domain

$\Omega=\left\\{(y,z):0\leq y\leq\frac{1}{\sqrt{3}},\,0\leq
z\leq\frac{1}{\sqrt{5}}\sqrt{1-3y^{2}}\right\\}.$

Not being able to do better and leaving the sharp bound as an open problem, we
continue with what is easy to get:

$\begin{split}\psi_{1}(y,z)&\leq\frac{4}{\sqrt{7}}y+6y^{3}+\frac{4}{5}(1-3y^{2})=\frac{4}{5}+\frac{4}{\sqrt{7}}y-\frac{12}{5}y^{2}+6y^{3}\\\
&\leq\frac{4}{\sqrt{21}}+\frac{2}{\sqrt{3}}=2.02757\ldots,\end{split}$

obtained for $y=\frac{1}{\sqrt{3}}$.

  * (b)

In the general case, if $a_{2}\neq 0$, since $|a_{2}|\leq 2$ and
$|c_{1}+a_{2}^{2}|=|a_{3}|\leq 3$, from (11) we get

$\begin{split}|H_{2}(3)(f)|&=6|\omega_{17}|+12|\omega_{11}||\omega_{13}||\omega_{15}|+3|\omega_{11}|^{2}|\omega_{13}|^{2}\\\
&\quad+6|\omega_{13}|^{3}+2|\omega_{11}|^{4}|\omega_{13}|+2|\omega_{11}|^{3}|\omega_{15}|\\\
&\quad+|\omega_{11}|^{6}+4|\omega_{15}|^{2}\\\ &\leq
6\cdot\frac{1}{\sqrt{7}}\sqrt{1-|\omega_{11}|^{2}-3|\omega_{13}|^{2}-5|\omega_{15}|^{2}}+12|\omega_{11}||\omega_{13}||\omega_{15}|\\\
&\quad+3|\omega_{11}|^{2}|\omega_{13}|^{2}+6|\omega_{13}|^{3}+2|\omega_{11}|^{4}|\omega_{13}|\\\
&\quad+2|\omega_{11}|^{3}|\omega_{15}|+|\omega_{11}|^{6}+4|\omega_{15}|^{2}\\\
&=\psi_{2}(|\omega_{11}|,|\omega_{13}|,\omega_{15}|),\end{split}$

where

$\begin{split}\psi_{2}(x,y,z)&=\frac{6}{\sqrt{7}}\sqrt{1-x^{2}-3y^{2}-5z^{2}}+12xyz+3x^{2}y^{2}\\\
&\quad+6y^{3}+2x^{4}y+2x^{3}z+x^{6}+4z^{2}\end{split}$

with $0\leq x=|\omega_{11}|\leq 1$, $0\leq
y=|\omega_{13}|\leq\frac{1}{\sqrt{3}}\sqrt{1-x^{2}}$, $0\leq
z=|\omega_{15}|\leq\frac{1}{\sqrt{5}}\sqrt{1-x^{2}-3y^{2}}$. Similarly as in
the part (a), finding upper bound of the function $\psi_{2}(x,y,z)$ on its
domain

$\begin{split}&\left\\{(x,y,z):0\leq x\leq 1,\,0\leq
y\leq\frac{1}{\sqrt{3}}\sqrt{1-x^{2}},\right.\\\ &\quad\left.0\leq
z\leq\frac{1}{\sqrt{5}}\sqrt{1-x^{2}-3y^{2}}\right\\},\end{split}$

is still an open problem, even though analysis suggest that it is 1. Easy way
arround, leading to a non-sharp upper bound is:

$\begin{split}\psi_{2}(x,y,z)&\leq\frac{6}{\sqrt{7}}\sqrt{1-x^{2}}+12xyz+3x^{2}y^{2}\\\
&\quad+6y^{3}+2x^{4}y+2x^{3}z+x^{6}+4z^{2},\end{split}$

which after applying $y\leq\frac{1}{\sqrt{3}}\sqrt{1-x^{2}}$ and
$z\leq\frac{1}{\sqrt{5}}\sqrt{1-x^{2}}$ leads to

$\begin{split}\psi_{2}(x,y,z)&\leq\frac{6}{\sqrt{7}}\sqrt{1-x^{2}}+\frac{12}{\sqrt{15}}x(1-x^{2})+\frac{3}{15}(1-x^{2})^{2}\\\
&\quad+\frac{6}{3\sqrt{3}}(1-x^{2})\sqrt{1-x^{2}}+\frac{2}{\sqrt{3}}x^{4}\sqrt{1-x^{2}}\\\
&\quad+\frac{2}{\sqrt{5}}x^{3}\sqrt{1-x^{2}}+x^{6}+\frac{4}{5}(1-x^{2})^{2}\equiv
h_{*}(x).\end{split}$

Numerical computations show that this function has maximal value
$4.8986977\ldots$ obtained for $x=0.3945667\ldots$.

∎

## References

  * [1] P.L. Duren, Univalent function, Springer-Verlag, New York, 1983.
  * [2] N.A. Lebedev, _Area principle in the theory of univalent functions_ , Nauka, Moscow, 1975 (in Russian).
  * [3] M. Obradović, S. Ponnusamy, On the class $\mathcal{U}$, Proc. 21st Annual Conference of the Jammu Math. Soc. and a National Seminar on Analysis and its Application, 11-26, 2011.
  * [4] M. Obradović, N. Tuneski, Some properties of the class $\mathcal{U}$, Ann. Univ. Mariae Curie-Skłodowska Sect. A 73 (2019), no. 1, 49–56.
  * [5] D.K. Thomas, N. Tuneski, A. Vasudevarao, Univalent Functions: A Primer, De Gruyter Studies in Mathematics, 69, De Gruyter, Berlin, Boston, 2018.
  * [6] M. Obradovic, N. Tuneski, Hankel determinant of type $H_{2}(3)$ for inverse functions of some classes of univalent functions with missing second coefficient, submitted. arXiv:2211.12325
  * [7] P. Zaprawa, On Hankel determinant $H_{2}(3)$ for univalent functions, Results Math., (2018), 73-89.


# Practical Estimation of Ensemble Accuracy

Simi Haber
Bar-Ilan University and Q (cue) ltd.
<EMAIL_ADDRESS>
&Yonatan Wexler
Q (cue) ltd.
<EMAIL_ADDRESS>

###### Abstract

Ensemble learning combines several individual models to obtain better
generalization performance. In this work we present a practical method for
estimating the joint power of several classifiers which differs from existing
approaches by not relying on labels, hence enabling the work in unsupervised
setting of huge datasets. It differs from existing methods which define a
“diversity measure”.

The heart of the method is a combinatorial bound on the number of mistakes the
ensemble is likely to make. The bound can be efficiently approximated in time
linear in the number of samples. Thus allowing an efficient search for a
combination of classifiers that are likely to produce higher joint accuracy.
Moreover, having the bound applicable to unlabeled data makes it both accurate
and practical in modern setting of unsupervised learning. We demonstrate the
method on popular large-scale face recognition datasets which provide a useful
playground for fine-grain classification tasks using noisy data over many
classes.

The proposed framework fits neatly in trending practices of unsupervised
learning. It is a measure of the inherent independence of a set of classifiers
not relying on extra information such as another classifier or labeled data.

##  1 Introduction

Classifier ensembles allow combining several classifiers into a possibly more
accurate one. Traditionally features and “weak learners” were used in boosting
[3, 17, 15]. Nowadays it is common to combine several deep learning networks
or random forests into an ensemble classifier [13, 14, 4]. Each component in
the ensemble is chosen according to some specific principle or is randomly
selected. In Ensemble Learning there is empirical evidence that ensembles tend
to yield better results when there is significant diversity among the models,
with several definitions of the term [9, 16] that are useful when labeled data
exists.

In this paper we devise a computationally efficient bound for the number of
errors an ensemble will make — even without using labeled data or joint
optimization. It therefore extends existing approaches to unsupervised
learning regime over massive datasets. This is also true for many modern
datasets which are labeled automatically and contain mistakes such as wrong or
duplicate identities [18]. To the best of our knowledge this is the first time
that the idea of “diversity” is extended to unsupervised setting.

Intuitively, weak-learners are useful together when they split the input space
differently. Specifically, they need to disagree on their mistakes. The
suggested bound is computed over the observed mapping of the inputs by the
classifiers, essentially ignoring their labels. We show that this information
suffices to surface errors the ensemble will produce by posing it as an
optimal assignment problem which can be efficiently approximated in $O(N)$
where $N$ is the number of samples. The bound relies on reasonable assumptions
and is verified to work well experimentally.

To give a numeric example, we can check an ensemble of three classifiers over
a face recognition dataset with 10 million samples of one million identities
by picking about a hundred random samples and testing the joint classification
on them.

Figure 1 illustrates the method for an ensemble of two classifiers
$f_{1},f_{2}:\mathcal{X}\mapsto[L]$. We count duplicity of tuples
$\displaystyle{(f_{1}(x_{i}),f_{2}(x_{i}))}_{i=1}^{N}$ creating the matrix $C$
(Panel 1(b), where rows are the output of $f_{1}$ and columns of $f_{2}$). The
count enables efficient approximation of a lower bound for the number of
mistakes over all possible mappings from a class into (one or more) matrix
cell (Panel 1(c)) such that all samples are accounted for. This without
knowing the ground truth (Panel 1(a)).

The paper is organized as follows: In Section 2, we show how two or more
metric-learner based classifiers can be used to construct a joint space
partitioning scheme. In Section 3 we formally define and analyze the proposed
bound. In Section 4 we verify the method on real data and conclude.

(a) Ground truth (unknown)

(b) Cell Occupancy $\mathbf{C}$
(visible)

(c) Bipartite graph
representation

(d) Mistakes
multigraph

Figure 1:  A schematic example of the approach where we wish to estimate the
potential ensemble performance of $Q=2$ classifiers over $K=6$ classes
projected onto $L=3$ samples. (1(a)) shows the (unknown) true mapping. Note
that monkey class is split among several cells thus limiting the potential
accuracy. (1(b)) shows the count of the number of elements in the mapping
$x_{i}\mapsto\left(f_{1}(x_{i}),f_{2}(x_{i})\right)$ which is our only
observable. (1(c)) illustrates the bipartite graph of the same mapping where
multiplicity of edges is counted. (1(d)) shows the multigraph used in the
proof of Claim 5.

##  2 Problem Formulation

Let $\\{x_{i}\in\mathcal{X}\\}_{i=1}^{N}$ be samples from $K$ classes. Let
$\\{f_{q}\\}_{q=1}^{Q}$ be multi-class classifiers. We aim to estimate their
potential accuracy over the samples without using labels.

Every multi-class classifier partitions $\mathcal{X}$ into (not necessarily
connected) parts, one for each class. Two classifiers splitting the space
differently have the potential to jointly refine the partition of
$\mathcal{X}$, thus possibly enabling higher accuracy. At high dimension the
number of parts in the joint partition is likely to grow exponentially while
the likelihood of a sample to appear in a part diminishes. We therefore pick a
small random set of $L\ll K$ samples from distinct classes and observe the
joint behavior of $f_{q}$ on them. A good choice is $L>\sqrt[Q]{K}$ yielding
more cells than classes. This forces some cells to be empty in a perfect
classification which increases the probability of visible errors.

We start with the following claim:

######  Claim 1.

Every multi-class classifier can be converted to a metric-learner and vice-
versa.

###### Proof.

By construction for each direction separately:

$\Leftarrow$

Given a multi-class classifier $f(x)\mapsto[K]$ define a metric learner
$g(x):=e_{f(x)}$ which maps the class $k$ into the unit vector $e_{k}\in
R^{K}$ in the standard basis.

$\Rightarrow$

Given a metric learner $f(x)\mapsto R^{d}$ satisfying
$||f(x)-f(y)||\leq||f(x)-f(z)||$ for $x,y$ in one class and $z$ in another,
and given a one or more (sample, class) pair from each class $(x_{i},y_{i})$.
Define $g(x):=y_{j}$ where $j:=\mathrm{argmin}_{i}||f(x)-f(x_{i})||$.

It is immediate to verify that this mapping preserves mistakes and hence also
accuracy. ∎

By claim 1 we can assume w.l.o.g. that $f_{q}$ are metric-learners. Therefore
any choice of a random set of $L$ samples induces a mapping of samples
$x_{i}\mapsto\vec{i}\in[L]^{Q}$ where
$\vec{i}:=\left(\,f_{1}(x_{i}),\cdots,f_{Q}(x_{i})\,\right)$. The structure
$\textbf{C}=[c_{\vec{i}}]$ counts how many samples are mapped into each tuple
(also called Cell). When $Q=2$ the structure C is a matrix. This count is our
only observable. We next show it is indicative of ensemble accuracy.

##  3 Approach and analysis

The core idea for our error analysis is that any cell $c_{\vec{i}}$ which is
not of a class size must contain an error. We seek a mapping matching classes
to cells such that all samples are accounted for. Given such mapping we count
the number of samples that are mapped incorrectly. This approach may miss
cells that unknowingly mix several classes, a point which we address in 5.

We define the bound by considering bipartite multi-graphs (see Panel 1(c))
with two types of nodes $N=[K]\cup\\{\vec{i}\\}$. On the left the nodes
represent the $K$ classes and on the right the nodes represent the $L^{Q}$
cells. Denote by $H_{\vec{i}}^{k}$ the (unknown) number of elements from class
$k$ that are mapped into cell $\vec{i}$. Out of all possible bipartite
multigraphs on this vertex set with left degrees $S$ and right degrees
$c_{\vec{i}}$, we seek $H^{*}$ maximizing
$\sum_{\vec{i}}\sum_{k}(H_{\vec{i}}^{k})^{2}$. The objective function counts
pairs of samples of the same class that end up in the same cell and penalizes
the rest.

This leads to the following definition:

######  Definition 2.

Given a list of cell sizes $\mathbf{C}$ and class size $S$ we define

$\mathrm{CB}(\mathbf{C})=\max_{H}\sum_{\vec{i}}\sum_{k}(H_{\vec{i}}^{k})^{2},\quad\text{s.t.}\quad\sum_{\vec{i}}H_{\vec{i}}^{k}=S\,,\,\sum_{k}H_{\vec{i}}^{k}=c_{\vec{i}}.$

Computing $\mathrm{CB}(\mathbf{C})$ is NP-hard, being a generalization of the
Multiway Number Partitioning problem [5]. Yet it is sometimes called “The
easiest NP-hard problem” [12] as it can be approximated efficiently. In some
cases we can find $\mathrm{CB}(\mathbf{C})$ exactly:

######  Claim 3.

There is a pseudopolynomial algorithm for exact computation of
$\mathrm{CB}(\mathbf{C})$ requiring $O(L^{2}(K_{r}-1)C_{m}^{K_{r}-1})$ memory
where $C_{m}$ is the size of the largest cell and $K_{r}$ is the number of
classes after removal of classes and cells of equal size.

The proof follows [8] with two adaptations. First, as long as there is a cell
of size $S$, we remove it from C. The second modification is that we allow
cells to be split between classes and vice-versa. As $K$ tends to be large the
above does not provide a practical solution in most cases.

######  Claim 4.

There is a polynomial time approximation scheme (PTAS) for finding
$\mathrm{CB}(\mathbf{C})$ with runtime $O(K_{r})$ with exponential dependence
in the reciprocal of the precision.

Here we apply a PTAS of Alon et al. [1], again after removal of cells and
classes of equal size.

Finally, a greedy algorithm gives a $4/3$ approximation ratio [5]. Our
experiments demonstrate this suffices in some cases.

We next prove that the number of “hidden” mistakes is likely to grow as
$\mathrm{CB}(\mathbf{C})$ grows, something that is also shown empirically in
Section 4. Intuitively, some misclassifications may change cell counts and be
visible to us, while others are not. We do not expect classifiers to have a
tendency towards detectable vs. invisible errors, so it is not surprising the
two grow together. Hence we hypothesize that the number of visible errors
increases monotonically with the total number of mistakes.

Let $\varphi^{*}$ be an optimal mapping of classes to cells achieving
$\mathrm{CB}(\mathbf{C})$. Whenever a sample from class $c$ is mapped to a
different cell than $\varphi^{*}(c)$ we consider it a mistake. We can show the
following:

######  Claim 5.

Let $F$ be a classifier and assume that when $F$ misclassifies, the target
class is chosen uniformly at random. Then the expectation of
$\mathrm{CB}(\mathbf{C})$ is monotonically increasing with the total number of
mistakes.

For the proof we define the mistakes graph — a directed multigraph where each
sample not mapped into the correct cell is represented by an arc between the
correct cell and the mapped cell (see Fig. 1(d)). Hidden mistakes are those
appearing in a cycle or in a path besides the first and last edges. Hence
counting such errors amounts to finding an edge maximum cover of the multi-
graph by edge disjoint directed cycles and paths. We complete the proof by
analyzing edge-maximal edge-disjoint collection of cycles in the appropriate
random graph model

The approach of the last proof yields a polynomial relation:
$\mathrm{CB}(\mathbf{C})=O(f^{c})$ where $f$ is the number of errors and
$c>1/5$ is constant. We believe that a stronger result, $c\geq 1/2$, may be
obtained by finding an analog to the main result of [11] for the mistakes
graph — showing essential independence between degrees. In silico, when using
two similar classifiers, we get heavy counts on the diagonal of $\mathbf{C}$,
and then the number of visible errors grows linearly with the number of total
mistakes.

##  4 Experiments

(a) CelebsA dataset

(b) artificial faces dataset - DigiFace1M

Figure 2: Real True-same counts vs. $\mathrm{CB}$ estimation

We created a collection of ten classifiers $f_{q}$ and measured $\mathrm{CB}$
for all $45$ pairs on two datasets. We have used the Dlib [7, 6] as a base.
This metric learner maps a photo into ${\mathcal{R}}^{128}$. The authors
recommend a distance threshold of $0.6$ when deciding if two photos are of the
same origin. Representatives from $L$ random classes were randomly chosen, and
proximity to them was used in classification. We have created our metric
learners in a few different ways:

  * •

$d$ pairs of samples were randomly chosen. For each pair we took the line
connecting the two samples and projected each sample on it, with an affine
correction making the center of the segment the origin. This projection
bisects the samples along probable interesting affine hyperplanes.

  * •

Using only randomly chosen $d$ coordinated from the original 128.

  * •

Same as above, but using more representatives from each class.

Table 1 lists the datasets we used. Figure 2 presents the results, Panel 2(a)
for the CelebsA dataset [10] and Panel 2(b) for DigiFace1M [2]. In both charts
the $x$-axis is $\mathrm{CB}$ and $y$-axis is the real False-Same error
measured using labels. Pairs of samples were considered Same when both
classifiers agreed they are the same. Markers are sized according to the sum
of real performances of each classifier. Regression lines were added for
convenience.

Table 1: Datasets characteristics Name | Identities | Samples | Reference | Remarks
---|---|---|---|---
CelebaA | 10,000 | 200,000 | [10] |
DigiFace1M | 100,000 | 1,220,000 | [2] | Artificially generated

##  5 Conclusion

We presented a combinatorial bound on the number of mistakes an ensemble is
likely to make, without relying on labeled data. The bound is approximated
efficiently while still agreeing with real data. As such it is useful in
modern settings of huge datasets in the unsupervised learning regime. Due to
space limitations we left out some proofs to be added in a longer version of
this manuscript.

## References

  * [1] Noga Alon, Yossi Azar, Gerhard J. Woeginger, and Tal Yadid.  Approximation schemes for scheduling on parallel machines.  Journal of Scheduling, 1:55–66, December 1998.
  * [2] Gwangbin Bae, Martin de La Gorce, Tadas Baltrušaitis, Charlie Hewitt, Dong Chen, Julien Valentin, Roberto Cipolla, and Jingjing Shen.  Digiface-1m: 1 million digital face images for face recognition.  In 2023 IEEE Winter Conference on Applications of Computer Vision (WACV). IEEE, 2023.
  * [3] Yoav Freund and Robert E. Schapire.  A desicion-theoretic generalization of on-line learning and an application to boosting.  In Paul Vitányi, editor, Computational Learning Theory, pages 23–37, 1995.
  * [4] M.A. Ganaie, Minghui Hu, A.K. Malik, M. Tanveer, and P.N. Suganthan.  Ensemble deep learning: A review.  Engineering Applications of Artificial Intelligence, 115:105151, 2022.
  * [5] Ron L. Graham.  Bounds on multiprocessing timing anomalies.  SIAM Journal on Applied Mathematics, 2(17):416–429, March 1969\.
  * [6] Davis E. King.  Dlib c++ library.  http://dlib.net.  Version 19.24; Accessed: 2023-08-31.
  * [7] Davis E. King.  Dlib-ml: A machine learning toolkit.  Journal of Machine Learning Research, 10:1755–1758, 2009.
  * [8] Richard E. Korf.  Multi-way number partitioning.  In IJCAI-09, pages 538–543, 2009.
  * [9] Ludmila I. Kuncheva and Christopher J. Whitaker.  Measures of diversity in classifier ensembles and their relationship with the ensemble accuracy.  Machine Learning, 51:181––207, 2003.
  * [10] Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang.  Deep learning face attributes in the wild.  In Proceedings of International Conference on Computer Vision (ICCV), December 2015.
  * [11] Brendan D. McKay and Nicholas C. Wormald.  The degree sequence of a random graph. I. The models.  Random Structures & Algorithms, 11(2):97–117, September 1997.
  * [12] Stephan Mertens.  The easiest hard problem: Number partitioning.  In Allon G. Percus, Gabriel Istrate, and Cristopher Moore, editors, Computational Complexity and Statistical Physics, pages 125–139. Oxford University Press, 2006.
  * [13] Robi Polikar.  Ensemble based systems in decision making.  IEEE Circuits and Systems Magazine, 6(3):21–45, 2006.
  * [14] Lior Rokach.  Ensemble-based classifiers.  Artif. Intell. Rev., 33:1–39, 02 2010.
  * [15] Shai Shalev-Shwartz, Yonatan Wexler, and Amnon Shashua.  Shareboost: Efficient multiclass learning with feature sharing, 2011.
  * [16] Peter Sollich and Anders Krogh.  Learning with ensembles: How overfitting can be useful.  Advances in Neural Information Processing Systems, 8:190–196, 1996\.
  * [17] Antonio Torralba, Kevin P. Murphy, and William T. Freeman.  Sharing visual features for multiclass and multiview object detection.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(5):854–869, 2007.
  * [18] Viktor Varkarakis and Peter Corcoran.  Dataset cleaning – a cross validation methodology for large facial datasets using face recognition, 2020.