\section{Introduction}

Let $\Sigma = \Sigma_{g,n}$ be the compact oriented surface of genus $g$
with boundary $\partial\Sigma$ which has $n\geq 1$ components
denoted $\partial_1\Sigma,...,\partial_n\Sigma$.
Fix a basepoint $x_0$ on $\Sigma$ and let $\pi = \pi_1(\Sigma,x_0)$ denote its fundamental group.
Let $\HomeoS$ be the group of
orientation-preserving homeomorphisms of $\Sigma$
which fixes $\partial\Sigma$ pointwise.
Define the {\em mapping class group\/} of $\Sigma$:
\[ \Gamma : = \pi_0\big(\HomeoS\big).\]
Alternatively,
choose basepoints $x_i\in\partial_i\Sigma$ and paths  from $x_0$ to $x_i$.
Define $\pi_1(\partial_i\Sigma)$ as the cyclic subgroup of $\pi$
corresponding to $\pi_1\big(\partial_i\Sigma,x_i\big)$
and determined by the paths between $x_0$ and $x_i$.
Let $\AutS$ denote the subgroup of $\Aut(\pi)$
which preserves both the conjugacy classes of the
subgroups $\pi_1\big(\partial_i(\Sigma)\big)$
and the orientation of $\Sigma$.
Then $\Gamma$ is  isomorphic to the image of $\AutS$ under the quotient
homomorphism
\begin{equation*}
\Aut(\pi) \longrightarrow \Out(\pi) := \Aut(\pi)/\Inn(\pi).
\end{equation*}

Let $G$ be an algebraic group over $\R$.
Then the set of homomorphisms $\pi \to G$
enjoys the the structure of an $\R$-algebraic set
denoted $\Hom(\pi,G)$.
Choose conjugacy classes $\CC_i \subset G$
for each $i=1,\dots,n$ and let $\CC := \{\CC_1,\dots,\CC_n\}$.
Denote by $\HomC$ the subset of $\Hom(\pi,G)$ comprising homomorphisms which send
$\pi_1(\partial_i\Sigma)$ to $\CC_i$

The group $\Inn(G)$ of inner  automorphisms of $G$
acts on $\HomC$ by composition.
Denote the resulting {\em relative character variety\/} by:
\[
\M_\CC(G) := \HomC/\Inn(G).
\]

The group $\AutS$ acts on $\pi$,
and hence  on $\Hom_\CC(\pi,G)$ by composition.
Furthermore, the action descends to a $\Gamma$-action on $\MCC(G)$.
The moduli space $\MCC(G)$ has an invariant dense open subset
$\MCCo$ which is a smooth manifold.
If, for example, $G$ is $\R$-reductive (see \cite{Go84, Go97}),
this subset has an $\Gamma$-invariant symplectic structure $\Omega$.
In particular,
$\MCCo$  admits a natural smooth $\Gamma$-invariant measure $\mu$.

This paper is part of the general program to understand the dynamics of the
action of $\Gamma$ and automorphism groups of free groups
on character varieties when the Lie group is compact.
Suppose that $K$ is a compact Lie group.
In \cite{Go97}, Goldman conjectures that $\Gamma$ acts ergodically on
$\MCC(K)$ and shows this to be the case when $K$ is locally a product of
$\SU(2)$'s and $\U(1)$'s.
In \cite{PX02a} and \cite{PX03a}, the conjecture is proved for $g \geq 2$, and also established for almost all boundary classes when $g=1=n$.  In \cite{GX11}, Goldman and Xia offer an alternate and simpler proof for the case of $K = \SU(2)$.

In this paper, we consider the case $g = 1 = n$ with $K = \SUthree$.
Then $\Gamma \cong \SL(2,\Z)$  (see \cite{FM12}).
In this special case, $\MCC(K)$ is explicitly described by the
{\em commutator map\/}
\begin{align*}
K \times K &\xrightarrow{~\kappa~}  K \\
(a,b) &\longmapsto [a,b] := aba\inv b\inv.
\end{align*}
Indeed, $\MCC(K) \cong \kappa\inv(\CC)/\Inn(K)$,
for each conjugacy class $\CC \subset K$.

\begin{thm}\label{thm:main}
Let $K = \SU(3)$ and $\surf=\surf_{1,1}$.
The $\Gamma$-action is ergodic on $\MCC(K)$ with
respect to the measure $\mu$.
\end{thm}

We prove this theorem along the lines of the main results in \cite{GX11}.  If $\rho \in \HomC$, we denote its $\Inn(G)$-equivalence class as $[\rho]$.  Similarly if $S \subseteq \HomC$, then the corresponding set of $\Inn(G)$-equivalence classes is denoted by $[S]$.
A simple closed curve $\alpha$ on $\Sigma$
defines a function
\begin{align*}
\MCC(K) &\xrightarrow{~\f_\alpha~} \C \\
[\rho] &\longmapsto \Tr\big(\rho(\alpha)\big).
\end{align*}
The symplectic structure $\Omega$ together with the real and imaginary parts of $\f_\alpha$ give rise to Hamiltonian flows.
The ring-theoretical results in \cite{La07} imply the algebra of Hamiltonian
vector fields is {\em infinitesimally\/} transitive.
It follows that the group generated by these flows is {\em locally\/} transitive, and hence, ergodic.

Depending on the choice of $\alpha$, these Hamiltonian flows preserve the sets $[\H(a, b)]$ or $[\H'(a,b)]$ defined in Section~\ref{subsec:DH}.
On the other hand, $\Gamma$ contains the Dehn twist $\tau_\alpha$ along $\alpha$.  The $\tau_\alpha$ action also preserves $[\H(a,b)]$ and is ergodic in almost all $[\H(a,b)]$.
It follows that a $\mu$-measurable function is
invariant under $\tau_\alpha$ if and only if it
is invariant under the Hamiltonian flows associated with $\f_\alpha$.
By local transitivity, such a measurable function is almost everywhere constant.

\subsection*{Acknowledgements}
Goldman and Lawton were partially supported by U.S. National Science Foundation grants: DMS 1107452, 1107263, 1107367 1309376 ``RNMS: Geometric structures And Representation varieties" (the GEAR Network).  Lawton acknowledges support from U.S. National Science Foundation grants: DMS 1309376, and also DMS 0932078000 while he was in residence at the Mathematical Sciences Research Institute in Berkeley, California during the Spring 2015 semester.  He was also partially supported by a Simons Foundation Collaboration grant. Xia was partially supported by the Ministry of Science and Technology Taiwan with grants 103-2115-M-006-007-MY2, 105-2115-M-006-006, 106-2115-M-006-008 and 107-2115-M-006-009 and the National Center for Theoretical Sciences, Taiwan.

\section*{Notation and terminology}

Let $G$ be a group.  Denote the inner automorphism induced by $A\in G$ by:
\begin{align*}
G &\xrightarrow{~\Inn(A)~} G \\
B  &\longmapsto ABA\inv
\end{align*}
The set of conjugacy classes in $G$ equals the quotient $G/\Inn(G)$,
and we denote the image of a subset $S\subseteq G$ under the quotient map
by $[S]$.

Denote the {\em centralizer\/} of $A$ in $G$ by:
\[ G_A := \Fix\big(\Inn(A)\big) \subgroup G, \]
where $\Fix(S)$ is the set of fixed points of $S \subseteq G$.

Define the commutator map of $G$:
\begin{align*}
G \times G &\xrightarrow{~\kappa~} G \\
(A,B) &\longmapsto [A,B] := ABA^{-1}B^{-1}. \end{align*}

Suppose further that $G$ is a
Lie %
group  with Lie algebra $\g$,
and denote the adjoint representation of $G$ on $\g$ by $\Ad$.
Identify $\g$ with the Lie algebra of {\em right-invariant vector fields\/} on $G$;
then for any right-invariant vector field $X \in \g$,
the element $\Ad(a)(X)$ equals the image of $X$ under left-multiplication
by $a$.
Denote the {\em centralizer\/} of $a$ in $\g$ by:
\[ \g_a := \Fix\big(\Ad(a)\big) \subseteq \g. \]

Denote the trace of a matrix $a$ by $\Tr(a)$
and the $\lambda$-eigenspace of a matrix $a$ by $\Eig_\lambda(a)$,
for a scalar $\lambda\in\C$.

The notation $K$ and $\fk$ are reserved for compact Lie groups and its Lie algebra, respectively.

If $(M,\Omega)$ is a symplectic manifold,  and
$M \xrightarrow{~f~} \R$ is a smooth function,
denote its {\em Hamiltonian vector field\/} by $\Ham(f)$.
We denote the tangent space to a smooth manifold $M$ at a point $p\in M$
by $T_p M$.

When we say a set is {\em closed}, we mean it to be closed in the
classical topology.

\section{Character varieties and the mapping class group}\label{sec:char}
We fix a basepoint on the boundary of $\surf : = \surf_{1,1}$.
The fundamental group $\pi := \pi_1(\surf)$ is isomorphic to the rank 2 free group $\Ftwo$, generated
by homotopy classes of
oriented based loops $\alpha$ and $\beta$.
We often do not distinguish elements in $\pi$ from corresponding oriented based loops on $\surf$.

We write
$$
\pi = \la \alpha, \beta, \sigma | \kappa(\alpha, \beta) = \sigma \ra,
$$
where $\sigma$ is the boundary element.
In this way, we have
$$
R := \Hom(\pi, K) \cong K \times K \ \ \ \text{ and } \ \ \ \M := R/K,
$$
where the $K$-action is by conjugation.

In our case, we have only one boundary circle and we let
$\CC \subseteq K$ be a conjugacy class and $c \in \CC$.  Then the relative representation variety and character variety are
$$
R_c : = \Hom_\CC(\pi,K) := \kappa^{-1}(c) \ \text{ and } \ \M_c := R_c(K)/K_c.
$$
Again, the $K_c$-action is by conjugation.
In this way, a representation $\rho \in R_c$ corresponds to $(a,b) \in K \times K$ such that $\kappa(a,b) = c$.
Notice that $\M_c$ is usually and equivalently defined as
$$
\M_c = \kappa^{-1}(\CC)/K.
$$
The space $\M_c$ has a natural symplectic structure $\Omega$ \cite{Go84, Go97}.

The diffeomorphism group of $\Sigma$ (fixing the boundary, hence, also the basepoint) acts on $\pi$ and this action descends to a $\Gamma$-action on $\pi$, fixing the conjugacy class of $\sigma$.
This further induces an action:
\begin{align*}
\M_c \times \Gamma &\longrightarrow \M_c \\
([\rho], \gamma) &\longmapsto [\rho \circ \gamma].
\end{align*}
The $\Gamma$-action leaves $\Omega$ and $\mu$ invariant \cite{Go97}.
For any oriented simple closed curve $\alpha$ on $\surf$, denote by $\tau_\alpha$ the Dehn twist along $\alpha$.
The mapping class group $\Gamma$ %
contains all
Dehn twists; %
indeed the Dehn twists {\em generate\/} $\Gamma$
(although we do not need this fact).
Denote by $\Scal$ the set of homotopy classes of oriented simple closed curves on $\Sigma$.

\section{Compact Lie groups}
This section reviews well known facts that are used in the proofs.
{\em Generic elements\/} are introduced; these are regular elements
which are dense in their maximal tori,
and provide nontrivial dynamics.

\subsection{Regularity}

Suppose $M$ is an irreducible algebraic set over $\R$ or $\C$ and $M^s \subset M$ its singular locus.
Then $U  = M \setminus M^s$ is a smooth manifold and Zariski dense in $M$.
The smooth structure on $U$ gives rise to the Lebesgue measure class on $U$ and on $M$,
by assigning $M^s$ to be a null set.
We shall always mean this class, which coincides with the measure class discussed in the introduction \cite{Hu95}.

Let $G$ be a linear
semisimple algebraic group over $\C$ of rank $r$
and $K < G$ a maximal compact subgroup.
The corresponding Lie algebras are denoted by $\fk$ and $\g$, respectively.

Recall that an element $a \in K$ is {\bf regular} if $K_a$ has dimension $r$.
In general, $\dim(K_a) \ge r$, and $K_a$  contains a maximal torus of $K$.
An element $a \in K$ is regular if and only if $K_a$ is a maximal torus (that is, a Cartan subgroup) in $K$.

Recall that an action on a topological space is {\em minimal\/} if every orbit is dense.
If $a\in K$, denote the Haar measure on $K_a$ by
$\mu_{K_a}$ and the pushforward  $(L_b)_*\mu_{a}$ under left-multiplication
$K_a \xrightarrow{~L_b~} bK_a$ by $\mu_{ba}$.

\subsection{Genericity}
In general regularity is too weak a notion for dynamical complexity.
We introduce a notion of {\em genericity\/} which is more useful for
constructing nontrivial dynamics.

Let $(a,b)\in K\times K$.
Then the cyclic group $\la a\ra$ acts on the left-coset $b K_a$ by:
\[
b\zeta \xmapsto{~a^n~}  b\zeta a^n \]
where $n\in\Z$ and $\zeta\in K_a$.

\begin{prop}\label{prop:irrational rotation}
Let $a\in K$ be a regular element.
For any $b\in K$,
the following conditions are equivalent:
\begin{itemize}
\item the cyclic group $\la a \ra < K_a$ is Zariski dense in $K_a$;
\item the cyclic group $\la a \ra < K_a$ is dense in $K_a$;
\item the action of $\la a\ra$ on $bK_a$ is minimal;
\item the action of $\la a\ra$ on $(bK_a,\mu_{ba})$ is ergodic.
\end{itemize}
\end{prop}
In this case, we say that $a$ is {\em generic.\/}
The proof of Proposition~\ref{prop:irrational rotation} uses standard facts about compact abelian Lie groups,
such as:
\begin{lem}\label{lem:Density}
A cyclic subgroup of $K_a$ is dense in the classical topology if and only if it is dense in the Zariski topology.
\end{lem}
\begin{proof}
Any set that is classically dense is also Zariski dense since the Zariski topology is coarser than the classical topology. We now show the converse.
Clearly the cyclic group $\la a\ra \subset K_a$, and its Zariski-closure is also an abelian subgroup.
Its closure in the classical topology
\[ H :=\overline{\la a\ra} \] is a closed abelian subgroup of $K_a$.
Now every compact linear group is Zariski-closed
(See Onishchik-Vinberg~\cite{OV90}, \S 4.4, Theorem~5, pp.133--134).  Hence $H$ is Zariski closed in $K_a$.  Since ${\la a\ra}$ is Zariski dense in $K_a$ and $H \supseteq {\la a \ra}$, $H=K_a$.

\end{proof}

\begin{proof}[Proof of Proposition~\ref{prop:irrational rotation}]
The proof now follows from Lemma~\ref{lem:Density} and
the fact that dense subgroups of the torus act minimally
(see Katok-Hasselblatt \cite [\S 1.4 (p.28) ]{KH95})
and ergodically (\cite[Proposition 4.2.2 (p.147)]{KH95},
or Walters \cite[Theorem 1.9 (p.30)]{Wa82}.
\end{proof}

\section{Infinitesimal transitivity and Hamiltonian flows}\label{sec:IT}
In this section, we let $G$ be a semi-simple complex algebraic Lie group.
Let $M$ be a symplectic manifold and $M \xrightarrow{~f~} \R$ a smooth function.
Denote by $\Ham(f)$ the associated Hamiltonian vector field.

\begin{defin}
Let $M$ be a manifold and $\Fm$ be a set of
real smooth $\R$-functions on $M$ such that at $x \in M$, the
differentials $df(x)$, for $f\in\Fm$, span the cotangent space
$T_x^*(M)$. Then $\Fm$ is said to be infinitesimally transitive at $x$.  $\Fm$ is infinitesimally transitive on $M$ if
$\Fm$ is infinitesimally transitive at all $x \in M$.
\end{defin}

\begin{prop}\label{prop:Ham}
Let $M$ be a connected symplectic manifold and $\Fm$ be infinitesimally transitive on $M$.
Then the group $\mH$ generated by the Hamiltonian flows
$\Ham(f)$ of the vector fields $\Ham(f)$, for $f\in\Fm$, acts
transitively on $M$.
\end{prop}
\begin{proof}
See Lemma 3.2 in \cite{GX11}.
\end{proof}

We now briefly review results of Goldman~\cite{Go86},
describing the flows generated by
the Hamiltonian vector fields by {\em simple\/}  closed curves on $\Sigma$.
In this case, the local flow of this vector field on $\M_c$
lifts to a flow on the representation variety $R_c$.
Furthermore this flow admits a simple description~\cite{Go86}
as follows.
\subsection{Invariant functions and flows on groups}
Let $G$ be a semi-simple complex Lie group with Lie algebra $\g$.
Then the adjoint representation $\Ad$ preserves a nondegenerate symmetric
bilinear form $\langle \_ , \_ \rangle$ on $\g$. In the case $G=\SL(n,\C)$, this is
\begin{equation*}
\langle X, Y\rangle := \Tr (X Y).
\end{equation*}

Let $G\xrightarrow{\f} \R$ be a function invariant under the inner automorphisms $\Inn(G)$.
Following \cite{Go86}, we describe how
$\f$ determines a way to associate to every element $x\in G$
a one-parameter subgroup
\begin{equation*}
\zeta^t(x) \, = \, \exp\big( t F(x) \big)
\end{equation*}
centralizing $x$.
Given  $\f$, define  its {\em variation function\/}
$ G \xrightarrow{F} \g$ by:
\begin{equation*}
\langle F(x), \upsilon \rangle = \frac{d}{dt}\bigg|_{t=0}
\f \big( x \exp(t\upsilon)\big)
\end{equation*}
for all $\upsilon\in\g$.
Invariance of $\f$ under $\Inn(G)$ implies that $F$ is $G$-equivariant:
\begin{equation*}
F( g x g^{-1}) = \Ad(g) F(x).
\end{equation*}
Taking $g = x$ implies that the one-parameter subgroup
\begin{equation}\label{eq:oneparameter}
\zeta^t(x) := \exp(t F(x))
\end{equation}
lies in the centralizer of $x\in G$.

Intrinsically, $F(x)\in\g$ is dual (by  $\langle \_, \_\rangle$) to the
element of $\g^*$ corresponding to
the left-invariant 1-form  on $G$ extending the covector
$df(x) \in T^*_x(G)$.

\subsection{Invariant functions and centralizing one-parameter subgroups}

\label{ssec:hamilton}
Recall that $\Scal$ denotes the set of homotopy classes of oriented simple closed curves on $\Sigma$.
If $\alpha \in \Scal$ is an oriented homotopy class of based loops,
then $\f_\alpha$, the {\em trace function\/} of $\alpha$, is defined as:
\begin{align*}
\Hom(\pi,G) & \xrightarrow{~\f_\alpha~} \C \\
\rho & \longmapsto  \Tr\big(\rho(\alpha)\big).
\end{align*}
Since the function $G \xrightarrow{~\Tr~} \C$ is $\Inn(G)$-invariant,
$\f_\alpha$ defines a $\C$-valued function (also denoted by $\f_\alpha$) on $\M_c$.
Let
$$\f_\alpha^R = \Re(\f_\alpha),  \ \ \ \f_\alpha^I = \Im(\f_\alpha).$$
Then $\f_\alpha^R$ and $\f_\alpha^I$ define $\R$-valued functions on $\M_c$.

Let $\alpha \in \Scal$ and $\Sigma | \alpha$ denote the compact surface
obtained by {\em splitting\/} $\Sigma$ along $\alpha$.
The two components $\alpha_\pm$ of $\partial \Sigma | \alpha$ corresponding to $\alpha$
are the preimages of $\alpha\subset\surf$ under the quotient mapping $\Sigma|\alpha \longrightarrow\surf$.
The original surface $\Sigma$ may be reconstructed as a quotient
space under the identification of $\alpha_-$ with $\alpha_+$.

The fundamental group $\pi$ can be
reconstructed from the fundamental group $\pi_1(\Sigma | \alpha)$ as
an HNN-extension:
\begin{equation}\label{eq:hnn}
\pi \;\cong\;   \bigg(\pi_1(\Sigma | \alpha) \amalg
\langle\beta\rangle \bigg)
\bigg/
\bigg(\beta \alpha_- \beta^{-1} = \alpha_+ \bigg).
\end{equation}
A representation $\rho$ of $\pi$ is determined by:
\begin{itemize}
\item the restriction $\rho'$ of $\rho$ to the subgroup
$\pi_1(\Sigma|\alpha)\subset\pi$, and
\item the value $\beta' = \rho(\beta)$
\end{itemize}
which satisfies:
\begin{equation}\label{eq:hnnrep}
\beta'  \rho'(\alpha_-) \beta'^{-1} = \rho'(\alpha_+).
\end{equation}
Furthermore any pair $(\rho',\beta')$ where $\rho'$ is a representation of
$\pi_1(\Sigma|\alpha)$ and $\beta'\in G$ satisfies \eqref{eq:hnnrep}
determines a representation $\rho$ of $\pi$.

Let $\f = \f_\alpha^R$ or $\f = \f_\alpha^I$.
Define the {\em twist flow\/} $\xi_\alpha^t$, associated with $\f$ on $\Hom(\pi,\SU(3))$:
\begin{equation}\label{eq:hamtwist1}
\xi_\alpha^t(\rho):\gamma \longmapsto \begin{cases}  \rho(\gamma)
& \text{if}~ \gamma \in \pi_1(\Sigma|\alpha) \\
\rho(\beta) \zeta^t\big(\rho(\alpha_-)\big)
& \text{if}~ \gamma = \beta. \end{cases}
\end{equation}
where $\zeta^t$ is defined in \eqref{eq:oneparameter}.
This flow covers the flow generated
by $\Ham(\f)$ on $\M_c$
(See \cite{Go86}).

\subsection{Infinitesimal transitivity}
Let $\XX$ be the Geometric Invariant Theory quotient of  $\Hom\big(\Ftwo,\SL(3,\C)\big)$ by
$\Inn\big(\SL(3,\C)\big)$.
Choose $\alpha, \beta \in \Scal$ as in Section \ref{ssec:hamilton} to correspond to curves with geometric
intersection number $1$ (or equivalently a free basis of $\Ftwo$).
Let
\[ \Gg :=
\{\alpha,\beta,\alpha \beta,\alpha\beta\inv,\alpha\beta\alpha\inv\beta\inv\}\subset \Scal \]
and
$\Gg\inv := \{\gamma\inv : \gamma\in\Gg \}$.
Let  \[\Fm_{\alpha,\beta} := \{ \f_\gamma : \gamma\in\Gg\cup \Gg\inv\}. \]

\begin{thm}[Lawton~\cite{La06,La07}]\label{thm:top of SU(3) rep}
The coordinate ring $\C[\XX]$ is generated by $\Fm_{\alpha,\beta}$.
\end{thm}
Since $\Tr(A\inv) = \overline{\Tr(A)}$ for $A\in\SUthree$,
the set $\Fm_{\alpha,\beta}$ is invariant under complex conjugation.

The relative $\SUthree$-character variety $\M_c$ of $\Ftwo$ embeds in $\XX$ as a real semialgebraic
subset.
The regular functions on this $\R$-semialgebraic set are the real and imaginary parts
of the restrictions to $\M_c$ of the regular functions on $\XX$.
\begin{cor}\label{prop:IT g=1}
The set
\[
\Fm_{\alpha,\beta}^\R := \{\f_\gamma^R, \f_\gamma^I : \gamma \in \Scal_{\alpha,\beta}\} \]
is infinitesimally transitive on $\M_c$.
\end{cor}

\begin{proof}
Given the remarks preceding this corollary, the result follows from Theorem \ref{thm:top of SU(3) rep} and  \cite[Lemma 3.1]{GX11}.
\end{proof}

\section{The Dehn twists}\label{ssec:Dehn}
Let  $\alpha \in \Scal$ and $\tau_\alpha\in \Gamma$ be the corresponding Dehn twist.
The fundamental group $\pi$ can be
reconstructed from the fundamental group $\pi_1(\Sigma | \alpha)$ as
an HNN-extension as in \eqref{eq:hnn}.
Then $\tau_\alpha$ induces the automorphism
$(\tau_\alpha)_*\in\Aut(\pi)$ defined by:

\begin{equation*}
(\tau_\alpha)_*:\gamma \longmapsto
\begin{cases}  \gamma
& \text{if}~ \gamma \in \pi_1(\Sigma|\alpha) \\
\gamma  \alpha
& \text{if}~ \gamma = \beta. \end{cases}
\end{equation*}
This further induces the map $(\tau_\alpha)^*$ on $\Hom(\pi,G)$ mapping
$\rho$ to:
\begin{equation}\label{eq:dehnnonsep}
(\rho)(\tau_\alpha)^*:\gamma \longmapsto
\begin{cases}  \rho(\gamma)
& \text{if}~ \gamma \in \pi_1(\Sigma|\alpha) \\
\rho(\gamma)  \rho(\alpha)
& \text{if}~ \gamma = \beta. \end{cases}
\end{equation}
(See \cite{Go86}).

\subsection{Dehn twists and Hamiltonian twist flows}\label{subsec:DH}

Let $a := \rho(\alpha)$ and $b = \rho(\beta).$
Then
\begin{align*}
R_c & = \{\rho \in \Hom(\pi, K) : \kappa(\rho(\alpha), \rho(\beta)) = c\} \\ & = \{(a,b) \in K \times K : \kappa(a,b) = c\}.
\end{align*}
Let
$$\H(a,b) := \{a\}\times bK_a, \ \ \ \ \H'(a,b) := aK_b \times \{b\}$$

\begin{prop}\label{prop:flow}
If $(a,b) \in R_c$, then
$\H(a,b), \H'(a,b) \subseteq R_c.$
\end{prop}
\begin{proof}
Suppose $t \in K_b$.  Then $at = ta$ and $t^{-1}a^{-1} = a^{-1}t^{-1}$.
Then
$$
k(a,bt) = a(bt)a^{-1}(bt)^{-1} = abta^{-1}t^{-1}b^{-1} = aba^{-1}b^{-1} = k(a,b) = c.
$$
Hence $(a,bt) \in R_c$.  The proof of $aK_b \times \{b\} \subseteq R_c$ is similar.
\end{proof}
\begin{prop}\label{prop: H-orbit}
If $(a,b) \in R_c$,
then the Hamiltonian flows of the vector fields $\Ham(\f_\alpha^R)$ and  $\Ham(\f_\alpha^I)$ preserve $[\H(a,b)]$.  Similarly, $\Ham(\f_\beta^R)$ and $\Ham(\f_\beta^I)$ preserve $[\H'(a,b)]$.
\end{prop}
\begin{proof}
This follows from \eqref{eq:hamtwist1} and by exchanging $\alpha$ and $\beta$.
\end{proof}

\begin{cor}\label{cor:generic1}
If $a$ is generic, then $\la \tau_\alpha\ra$ acts ergodically on $\H(a,b)$.
If $b$ is generic, then $\la \tau_\beta\ra$ acts ergodically on $\H'(a,b)$.
\end{cor}

\begin{proof}
By \eqref{eq:dehnnonsep},
$\tau_\alpha(a,b) \in \H(a,b)$ and $\tau_\beta(a,b) \in \H'(a,b)$
The corollary then follows from Proposition \ref{prop:irrational rotation}.
\end{proof}

\section{The case of $K = \SU(3)$}
For the rest of this paper, we denote $\omega := e^{2\pi i/3}$ and the identity transformation by $\Id$.
In this section we fix $K = \SU(3)$.

The classification of conjugacy classes of $K$ can be described in terms of the {\em trace\/} function
\[
K \xrightarrow{~\Tr~} \C. \]
Let $\Delta = \Tr(K)$.

If $\zeta_1,\zeta_2,\zeta_3\in\C$ are the eigenvalues of $a\in K$,
then they satisfy
\begin{equation}\label{eq:Eigenvalues}
\vert \zeta_1\vert = \vert \zeta_2\vert = \vert \zeta_3\vert = 1 \text{~and~} \zeta_1 \zeta_2 \zeta_3 = 1. \end{equation}
 The coefficients of the character polynomial $\chi_a$ are:
\begin{align*}
1 & = 1\\
\zeta_1 + \zeta_2 + \zeta_3 &  = \Tr(a) \\
\zeta_2\zeta_3 + \zeta_3\zeta_1 + \zeta_1\zeta_2 & = \overline{\Tr(a)} \\
\zeta_1 \zeta_2\zeta_3 & = 1.
\end{align*}
Therefore the  characteristic polynomial is:
\[
\chi_A(\lambda) \  = \
\lambda^3 \  - \ z\, \lambda^2 \ + \ \bar{z} \,\lambda \  - 1\]
where $z = \Tr(a)\in\C$.
Furthermore \eqref{eq:Eigenvalues} is equivalent to the condition:
\[
\vert z \vert^4 -  8\mathsf{Re} (z^3)  + 18 \vert z\vert^2  - 27 \le 0 \]
and this real polynomial condition exactly describes the image $\Delta \subseteq \C$.

\begin{figure}\label{fig:Delta}
 \includegraphics[scale=0.5]{SUthreeTraces.pdf}
 \caption{$\Delta$ the traces in $\SU(3)$.}
 \end{figure}

The traces of central elements are the vertices $3, 3\omega, 3\bar{\omega}$ of
$\Delta$.
The trace of a regular element of order three is the center $0$ of $\Delta$.
The traces of elements of order two are $-1, -\omega, -\bar{\omega}$,
the midpoints of the edges of $\partial \Delta$.

\begin{prop}\label{prop:Sard}
The map $\Tr$ is a local submersion at almost all points of $\Delta$.
\end{prop}
\begin{proof}
The map $\Tr$ is smooth.  Hence, by Sard's theorem, almost all points of $\C$ are regular values of $\Tr$ \cite[\S 1.7]{GP10}.  Hence $\Tr$ is a local submersion at almost all points of $\Delta$.
\end{proof}
\begin{rem}
It is not difficult to show that $\Tr$ has full rank in the interior of $\Delta$, but we only need Proposition \ref{prop:Sard}.  For a general discussion of $\Delta$ and Weyl chambers, see \cite{DK00}.
\end{rem}

\begin{prop} \label{cor:GenericityConullInDelta}
The image $\Tr(N)$ of the subset $N \subseteq K$ of generic elements
is conull in  $\Delta$.
\end{prop}
\begin{proof}
Let
$$
U = \{(\alpha, \beta) \in \R \times \R : \alpha, \beta, \frac{\alpha}{\beta} \in \R \setminus \Q\}
$$
Let $\Delta'\subset\Delta$ be the image of $U$ under the mapping
\begin{align*}
\R \times \R &\longrightarrow \C \\
(\alpha, \beta) &\longmapsto e^{2\pi i\alpha} + e^{2\pi i\beta} + e^{-2\pi i(\alpha +\beta)}
\end{align*}
Then $\Delta'$ is conull in $\Delta$ and $\Tr^{-1}(\Delta') \subseteq N$.
\end{proof}

\section{Central fibers of $\kappa$}
Again in this section, we fix $K = \SU(3)$.
\subsection{The abelian representations}\label{sec:ab}
The fiber $R_\I = \kappa\inv(\I)$ consists of commuting pairs $(a,b)$.
In this case, $a$ and $b$ lie in a maximal torus $\bT^2$.  Hence $\M_\I \cong (\bT^2 \times \bT^2)/W$, where $W$ is the Weyl group of $K$ acting diagonally (see \cite{FL14} for more discussion of these abelian character varieties)

\subsection{The non-abelian cases}\label{sec:nab}
\begin{prop}\label{prop:single point}
If $k = \omega\I$ where $\omega\neq 1$, then $\M_k$ consists of a single point.
Specifically, if $(a,b)\in R_k$, then there exists $g\in K$ such that
\[
a = g a_0 g\inv , \qquad b = g b_0 g\inv \]
where
\begin{equation}\label{eq:A0B0}
a_0 := \bmatrix 1 & 0 & 0 \\ 0 & \omega & 0 \\ 0 & 0 & \omega^2 \endbmatrix, \qquad
b_0 := \bmatrix 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \endbmatrix. \end{equation}
\end{prop}
\begin{proof}
Suppose $(a,b)\in R_k$, that is,
\begin{equation} \label{eq:CommOmega}
a b a\inv b\inv = \omega\I.  \end{equation}
We first prove:
\begin{lem}\label{lem:OrderThree}
$a^3 = b^3 = \Id$ \end{lem}
\begin{proof}[Proof of Lemma~\ref{lem:OrderThree}]
By \eqref{eq:CommOmega} and taking traces,
\begin{equation*}
\Tr(a)  = \Tr(\omega b a b\inv) = \omega \Tr(a)    \ \text{ and } \
\Tr(a\inv)  = \Tr(\omega b\inv a\inv b) = \omega \Tr(a^{-1}).
\end{equation*}
Hence $\omega\neq 1$ implies that $\Tr(a) = \Tr(a\inv) = 0$.
Now apply the Cayley-Hamilton theorem:
\[ a^3 -  \Id = a^3 - \Tr(a) a^2 + \Tr(a\inv) a - \Det(a) \Id = 0. \]
The same argument applied to
$b   = \omega a\inv b a$ implies $b^3=\Id$, as claimed. \end{proof}
Returning to the proof of Proposition~\ref{prop:single point},
Lemma~\ref{lem:OrderThree} implies that
$a = \Inn(g) a_0$ for some $g\in K$, since $a\neq \I$.

We claim that $b = \Inn(g) b_0$.
For convenience assume that $a = a_0$;
then we show that \eqref{eq:CommOmega} implies that
$b$ is the permutation matrix $b_0$ defined in \eqref{eq:A0B0}.

Recall that $\Eig_\lambda(a)$ is the $\lambda$-eigenspace of $a$.
We claim that \eqref{eq:CommOmega} implies that
\begin{equation}\label{eq:PermuteEig}
b \big( \Eig_\lambda (a) \big) \ = \ \Eig_{\omega\lambda} (a). \end{equation}
To see this, rewrite \eqref{eq:CommOmega} as:
\begin{equation}\label{eq:ABBA}
a b \ = \ \omega ba  \end{equation}
Suppose that $v\in  \Eig_\lambda (a)$, that is,
\[
a v = \lambda v \]
so applying \eqref{eq:ABBA},
\[
a (b v) \ = \ \omega b a v \ = \ \omega\lambda (b v) \]
whence $b v \in \Eig_{\omega\lambda} (a)$, as claimed.

Since $a$ is the diagonal matrix $a_0$ defined by \eqref{eq:A0B0},
the lines
$\Eig_1(a), \Eig_\omega(a),$ and $\Eig_{\bar\omega}(a)$ are the three coordinate lines in $\C^3$.
Thus \eqref{eq:PermuteEig} implies that $b = b_0$,
concluding the proof of Proposition~\ref{prop:single point}.
\end{proof}

In particular, both $a$ and $b$ have order $3$.
Since $\kappa(a,b)$ has order 3 and is central,
the subgroup $\langle a, b\rangle \subset K$ is a nonabelian group of order $27$,
a nontrivial central extension of $\Z/3 \oplus \Z/3$ by $\Z/3$.

\section{Ergodicity}
Let $K$ be any compact Lie group.
Each tangent space $T_a K$ identifies with the Lie algebra $\fk$ of {\em right-invariant vector fields:\/}
namely, a tangent vector $v\in T_a K$ identifies with the right-invariant vector $X \in \fk$ such that $X(a) = v$.  In this way, the differential of the commutator map $\kappa$ at
$(a,b) \in K \times K$ identifies with the linear map (see \cite{Go84, Go20, PX02a}):
\begin{align*}
 \D\kappa_{(a,b)} : \fk \oplus \fk & \longrightarrow \fk
\\
 (X,Y) &\longmapsto \Ad(ba)\big((\Ad(b^{-1}) - \I\big)X  \\
 & \qquad \qquad + \big(\I - \Ad(a^{-1})\big)Y.
\end{align*}
From this formula, the following proposition holds:
\begin{prop}\label{prop:C-singular}
$\kappa$ is
submersive %
at $(a,b)$ if and only if $\fk_a \cap \fk_b = 0$.
\end{prop}
For the rest of this section, let $K = \SU(3)$ which comes with the standard representation $\Pi$ on $\C^3$.  An element in $(a,b) \in R_c$ corresponds to a representation $\rho$ of $\pi$ (see Section \ref{sec:char}).  Hence $\rho \circ \Pi$ is a representation of $\pi$.  Denote by $\M_c^i \subseteq \M_c$ the subspace of irreducible representation classes.

\subsection{Relation to the moduli space of $K$-bundles}  If we fix a complex structure on $\Sigma$, then we can construct the coarse moduli space $\N^{ss}$ of semi-stable parabolic $K$-bundles \cite{BR89} on $\Sigma$, endowed with a complex structure.  $\N^{ss}$ contains the subspace $\N^s$ of stable parabolic $K$-bundles.

\begin{prop}\label{prop:connected}
The set of smooth points of $\M_c$ is a connected manifold.
\end{prop}
\begin{proof}
There is a homeomorphsim $\M_c \cong \N^{ss}$, restricting to a diffeomorphism $\M_c^i \cong \N^s$ (Theorem 1, \cite{BR89}).
The moduli space $\N^{ss}$ is irreducible and contains $\N^s$ as an open subvariety (Theorem II,  $\M_c$ \cite{BR89}).  Hence $\N^s$ is open and connected.  Hence $\M_c^i$ is open and connected. Proposition \ref{prop:C-singular} implies that
a point $[\rho] = [(a,b)] \in \M_c$ is a smooth point if and only if $\rho$ is irreducible, i.e. $\M_c^i$ is also the set of smooth points of $\M_c$.  The proposition follows.
\end{proof}

For almost every conjugacy class $c$,
the action $\M_c \times \Gamma \to \M_c$ is ergodic \cite{PX02a}.
This section proves that this is true for {\em all} $c$.

Let $ c \in K$.  Up to conjugation,
\[
c = \bmatrix c_1 & 0 & 0 \\ 0 & c_2 & 0 \\ 0 & 0 & c_3  \endbmatrix.
\]
For $(a,b) \in R_c$, we have the natural map
$$
\iota : K_a \lto \H(a,b), \ \ \ \iota(t) = (a,bt).
$$

Let $P_2 : K \times K \lto K$ be the projection to the second factor.
An element $\rho \in R_c$ corresponds to a pair $(a,b) \in K \times K$.  Let
$$\T = \Tr \circ P_2 : R_c \lto \Delta \ \ \text{ and } \ \  T := \iota \circ \T : K_a \lto \Delta.$$

\begin{prop}\label{prop:submersion}
Let $c \not\in Z(K)$.
Then $(a,b) \in R_c$ exists such that:
\begin{enumerate}
\item $(a,b)$ is a smooth point;
\item $T$ is a submersion at $(a,b)$.
\end{enumerate}
\end{prop}

\begin{proof}
Let $(a,b) \in R_c$ such that
\begin{equation}\label{eqn:ab}
a = \bmatrix 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0  \endbmatrix, \ \ \
b = \bmatrix b_1 & 0 & 0 \\ 0 & b_2 & 0 \\ 0 & 0 & b_3  \endbmatrix.
\end{equation}
Then
\begin{equation}
c = \kappa(a,b) = \bmatrix \frac{b_2}{b_3} & 0 & 0 \\ 0 & \frac{b_3}{b_1} & 0 \\ 0 & 0 & \frac{b_1}{b_2}  \endbmatrix.
\end{equation}
This formula for $c$ implies that $\kappa$ is onto $K$.
\begin{rem}
A result of Goto \cite{Go49} states that for any compact semi-simple Lie group K, $K \times K \xrightarrow{~\kappa~} K$ is surjective.  Hence $R_c \neq \emptyset$ for all $c \in K$.
\end{rem}

Note that $a$ is regular.  For (1), there are three cases for $b \in Z(K)$, $b_1 = b_2 \neq b_3$ (and its permutation variation) and $b$ being regular.

If $b \in Z(K)$, then $\kappa(a,b) = \I = c$ and this violates our hypothesis of $c \neq Z(K)$.

If $b$ is regular, then $t \in \fk_b$ implies
\begin{equation}\label{eq:t}
t = \bmatrix t_1 & 0 & 0 \\ 0 & t_2 & 0 \\ 0 & 0 & t_3  \endbmatrix,  \ \ \ t_1 + t_2 + t_3 = 0.
\end{equation}
Then
$$
(\Ad(a) - \I)t = \bmatrix t_2 - t_1 & 0 & 0 \\ 0 & t_3 - t_2 & 0 \\ 0 & 0 & t_1 - t_3  \endbmatrix.
$$
Hence if $t \in \fk_a$, then $(\Ad(a) - \I)t = 0$.  This implies $\fk_a \cap \fk_b = 0$.
Hence, by Proposition \ref{prop:C-singular}, we conclude that $\kappa$ is regular at $(a,b)$.

If $b_1 = b_2 \neq b_3$ and $t \in \fk_b$, then
$$
t = \bmatrix t_{11} & t_{12} & 0 \\ t_{21} & t_{22} & 0 \\ 0 & 0 & t_{33}  \endbmatrix, \ \ \ t_1 + t_2 + t_3 = 0.
$$
Then
$$
(\Ad(a) - \I)t = \bmatrix t_{22} - t_{11} & -t_{12} & t_{21} \\ -t_{21} & t_{33} - t_{22} & 0 \\ t_{12} & 0 & t_{11} - t_{33}  \endbmatrix.
$$
Hence if $t \in \fk_a$, then $(\Ad(a) - \I)t = 0$ This implies $t = 0$.  Hence $\fk_a \cap \fk_b = 0$.
By Proposition \ref{prop:C-singular}, $\kappa$ is regular at $(a,b)$.  We conclude that in all cases $(a,b) \in R_c$ is a smooth point.

Notice that $\H(a,b) \subseteq R_c$.
We consider $T$ restricted to $\H(a,b)$.
Let
$$
p = \bmatrix 1 & \omega^2 & \omega \\ 1 & \omega & \omega^2 \\ 1 & 1 & 1  \endbmatrix \ \ \text{ and } \ \
q = \bmatrix 1 & 0 & 0 \\ 0 & \omega^2 & 0 \\ 0 & 0 & \omega  \endbmatrix.
$$
Then
$a = p q p^{-1}$.  The element $t \in K_a$ has the form $t = p t_b p^{-1}$, where $t_b \in K_b$ is diagonal.
Then
$$
T(t) = \Tr(bt) = \frac{1}{3} \Tr(b) \Tr(t).
$$
By Proposition \ref{prop:Sard}, $T$ is a local submersion for all almost all $t \in \Delta$ unless $\Tr(b)=0$.  However $\Tr(b) = 0$ implies $c \in Z(K)$, a contradiction.  Hence $\Tr(b) \neq 0$ and $T$ is a local submersion for almost all $t$.

\end{proof}
\begin{cor}
$\T$ is a local submersion for almost all points in $\H(a,b)$.
\end{cor}
\begin{proof}
Since $\D T = \D \T \circ \D \iota,$  $\D T_{t}$ being surjective implies $\D \T_{(a,bt)}$ is surjective.
\end{proof}

\begin{cor}\label{cor:generic2}
There is a conull set $V \subset R_c$ such that $b$ is generic for almost all $(a,b) \in V$.
\end{cor}
\begin{proof}
The subset containing points at which a map is locally submersive is Zariski open.
Hence,
by Proposition~\ref{prop:submersion}, there exists smooth and Zariski open $V \subseteq R_c$ such that $T|_V$ is a submersion.  Let $Q \subseteq R_c$ be the smooth part.  By Proposition~\ref{prop:connected}, $Q$ is connected, hence, irreducible.  Since Zariski open subset of a smooth irreducible variety is conull in the Lebesgue class, $V$ is conull.  The map $T|_V$ is a fibration over an open domain of $\Delta$.
The corollary follows from Proposition~\ref{cor:GenericityConullInDelta}.
\end{proof}

\begin{cor}\label{cor:GH}
Suppose $c \not\in Z(K)$.  Suppose $\beta \in \Scal$ and $\phi : \M_c \lto \R$ is a $\mu$-measurable function.  If $\phi$ is $\tau_\beta$-invariant, then $\phi$
is $\Ham(\f_\beta^R)$-invariant and $\Ham(\f_\beta^I)$-invariant.
\end{cor}

\begin{proof}
By Proposition~\ref{prop:submersion}, $R_c$ contains a smooth point $(a,b)$ with $b$ generic.
By Proposition~\ref{prop:connected} and Corollary~\ref{cor:generic2},
$b \in K$ is generic for almost all $(a,b)\in R_c$.  Hence $b \in K$ is generic for almost all $[(a,b)] \in \M_c$.  By Proposition~\ref{prop:irrational rotation}, \ref{prop:flow} and Corollary~\ref{cor:generic1}, $\tau_\beta$-orbit is dense in $\H'(a,b)$ and $\phi$ is $\Ham(\f_\beta^R)$-invariant and $\Ham(\f_\beta^I)$-invariant.
\end{proof}

With the notation we have adopted, we restate Theorem \ref{thm:main} as:
\begin{thm}
The action $\M_c \times \Gamma \to \M_c$ is ergodic.
\end{thm}

\begin{proof}
Suppose that $c = \I$.
Identifying $\R^2$ with its dual $(\R^2)^*$, the group $\SL(2,\Z)$ has the standard dual linear action on $\R^2$ which induces the diagonal action on $\bT^2 \times \bT^2$.  This $\SL(2,\Z)$-action is known to be ergodic because $\SL(2,\Z)$ contains hyperbolic elements, meaning that the eigenvalues of these elements do not have absolute value $1$ \cite[\S 4]{BS15}.

There is an isomorphism \cite{FM12}
$
\iota : \Gamma \stackrel{\cong}{\lto} \SL(2,\Z).
$
By Section \ref{sec:ab}, $\M_c \cong (\bT^2 \times \bT^2)/W$.  The $\Gamma$-action on $\M_c$ lifts to an action on $\bT^2 \times \bT^2$.
Moreover, this $\Gamma$-action is equivariant with respect to $\iota$.  Hence the $\Gamma$-action on $\M_c$ is ergodic.

Suppose that $c \in Z(K)$ and $c \neq \I$, then $\M_c$ is a single point by Proposition~\ref{prop:single point} and the statement is trivially true.

Suppose $c \not\in Z(K)$.
Recall that $\mH$ is the group generated by all Hamiltonian flows $\Ham(\f_\beta^R)$ and $\Ham(\f_\beta^I)$ where $\beta \in \Scal$.  Let $\phi : \M_c \lto \R$ be a $\Gamma$-invariant $\mu$-measurable function.  By Corollary \ref{cor:GH}, $\phi$ is $\mH$-invariant. By Corollary~\ref{prop:IT g=1} and Proposition~\ref{prop:Ham}, $\phi$ is constant almost everywhere.  Our theorem follows.
\end{proof}

\bibliographystyle{alpha}


\section{Introduction}
\begin{figure*}
    \centering
    \includegraphics[width=0.4\textwidth]{Fig/YOLO.pdf}
    \caption{YOLO, a social robot that can boost creativity in children.}
    \label{fig:yolo-robot}
\end{figure*}
Creativity is one of the most sought-after skills, with recognized benefits in education, mental health, and professional success \cite{robinson2011out, collard2014nurturing}. It is associated with states of joy, play, efficiency, and pleasure \cite{baer2017content, kaufman2018creativity}. When stimulated in childhood, it promotes overall development with specific benefits in learning and adaptation. \cite{gardner2008art}. Creativity has been stimulated through the use of different intervention programs with promising effectiveness levels, demonstrating the potential to develop creativity with proper training \cite{scott2004types, ma2009effect}. However, most of these interventions developed for children lack elements of joy and fun. Therefore, they are considered similar to test-like exercises that can hinder their creative expression. The fast pace of technology development enabled the design of new tools for exploring the context of creativity stimulation \cite{shneiderman2009creativity} (e.g., the CUBUS virtual environment for storytelling with emotionally evocative characters \cite{pires2017cubus}).

In our work, we aim to expand the range of technologies used for creativity stimulation by incorporating social robots to catalyze this ability.
With this in mind, we designed and developed YOLO (Your Own Living Object), an original social robot to be used as a toy during children's play times (see Figure \ref{fig:yolo-robot}). YOLO belongs to a new generation of technological toys meant to stimulate creative abilities in children. This robot is envisioned as a character children use during storytelling. By having a small-size and a light-weight design, YOLO can be manipulated by children as if it was a traditional toy while children create stories with it (similarly to what they do with dolls or car toys). The added-value of this robot is that it can increase the creative thought process of children during story creation by providing novel ideas for storylines. Because YOLO is a non-anthropomorphic robot, it interacts with children using alternative but effective interactive modalities. These comprise variable motion and illumination profiles. In this paper, we detail the artificial intelligence software of YOLO. The software is composed of Creativity and Social Behaviors whose design was grounded on creativity research \cite{smith1998idea}, the Big Five personality model \cite{john1999big}, and co-design sessions with children \cite{alves2017yolo}.
We release the robot's software \footnote{Download YOLO Software: \url{https://github.com/patricialvesoliveira/YOLO-Software}} along with its installation guide\footnote{Link to YOLO Software installation guide: \url{https://github.com/patricialvesoliveira/YOLO-Software/wiki}} in open access. This software should be exclusively installed on YOLO hardware \cite{alves2019guide}).

\section{Software description}
\label{sec:software-description}
In our work, we developed software that gives life to the social robot YOLO, whose interaction is composed of Creativity and Social Behaviors.

\begin{table}[]
\caption{Software functionalities considering the sensors used, the input collected, the actuators in place, and the output provided.}
\label{tab:software-functionalities}
\begin{tabular}{p{1.5cm}p{4.5cm}p{1.5cm}p{4.5cm}}
\hline
\textbf{Sensor} & \textbf{Input}                                         & \textbf{Actuator} & \textbf{Output}                                                                                \\ \hline
Touch sensor    & Ability to recognize when the robot is being touched.                  & LED lights        & The robot displays white lights while being touched, refrains from performing any behavior. When not sensing touch, the robot displays colors associated with its different social behaviors.\\
Optical sensor  & Recognition of play patterns of children while manipulating the robot. & Omni wheels       & Imitating the collected movement patterns.                                                                                \\
Time & Stage of the storytelling that children are currently engaged in. & Omni wheels and LED lights & The robot performs a creativity technique according to the storytelling arc.\\  \hline
\end{tabular}
\end{table}

\subsection{Creativity behavior}
\label{sec:creativity-behavior}
In our specific application scenario, YOLO acts as a character that can trigger new directions in children's stories that otherwise would not emerge. During story creation, a combination of divergent (i.e., broad gathering of multiple ideas) and convergent thinking (i.e., narrowing down possibilities to create a coherent story plot) is required \cite{alrutz2015digital, brenner2016design, elbow1983teaching}.
We have chosen two techniques to stimulate creativity, named ``contrast''and ``mirror'' \cite{smith1998idea} (see Figure \ref{fig:arc})\footnote{Parameterization specifications for the creativity behaviors of YOLO can be found here: \url{https://github.com/patricialvesoliveira/YOLO-Software/wiki/CreativityProfile}}:

\begin{itemize}[noitemsep]
    \item \textbf{Contrast ---} This technique is used to stimulate divergent thinking \cite{rickards1975problem}. In the Contrast technique, YOLO provides stimuli unrelated to the storyline that children are exploring at the moment, producing an opportunity to explore new directions in the plot. This leads to heightened action and interesting plot twists in the stories of children.
    \item \textbf{Mirror ---} This technique is used to stimulate convergent thinking \cite{vangundy1988techniques}. When using the Mirror technique, YOLO provides stimuli that are connected with the storyline that children are exploring, leading to the elaboration and convergence of story ideas. This leads to then emergence of interesting details about a character, a scenario, or an action in the story.
\end{itemize}

\subsection{Storytelling arc}
\label{sec:storytelling-arc}
Successful and satisfying stories follow a storytelling arc \cite{freytag1872technik, freytag1896freytag}. According to the Theory of Dramatic Structure, each story has five acts: exposition, raising action, climax, falling action, and d\'{e}nouement \cite{freytag1872technik, freytag1896freytag}. These five acts can be modified and adapted to the dramatic structure of short stories, fables, or fairy-tales. In our software, we considered a short-story format similar to what is used in children's stories \cite{wright1995storytelling}. Therefore, we divide the narrative of a story in the following phases:

\begin{itemize}[noitemsep]
    \item \textbf{Rising action ---} Characters are introduced, a context is given to the story, and the story builds. During this stage, YOLO stimulates convergent thinking by using the mirror creativity technique (see Section \ref{sec:creativity-behavior});
    \item \textbf{Climax ---} The story reaches the point of greatest tension. During this stage, YOLO stimulates divergent thinking by applying the contrast creativity technique (see Section \ref{sec:creativity-behavior});
    \item \textbf{Falling action ---} The story shifts to an action that happens because of the climax, which means that the conflict is resolved and the story reaches its end. During this stage, YOLO stimulates convergent thinking by using the mirror creativity technique (see Section \ref{sec:creativity-behavior}).
\end{itemize}

\subsection{Social behavior}
\label{sec:social-behavior}
YOLO expresses different social profiles to exhibit social behaviors. The profiles are named \textit{Exuberant}, \textit{Aloof}, and  \textit{Harmonious}\footnote{Parameterization specifications for all the social behaviors of YOLO can be found here: \url{https://github.com/patricialvesoliveira/YOLO-Software/wiki/SocialProfile}}. These social behaviors appear as pre-sets when YOLO is turned on and can be used interchangeably, making the robot a flexible character in the children's stories. The three different social modes for YOLO are explained below:

\begin{itemize}[noitemsep]
    \item \textbf{Exuberant ---} YOLO reacts to every social interaction in an ``enthusiastic'' manner. Movements are fast and have a high amplitude. It displays vibrant colors such as purple and red with high brightness levels. As Exuberant, YOLO is proactive and seeks out social interaction. This is a vibrant, frenetic, and daring social profile;
    \item \textbf{Aloof ---} YOLO is less ``socially reactive'' and is a ``shy robot''. In this mode, the robot exhibits low amplitude, slow movements and displays cold colors such as green and blue with low brightness levels. As Aloof, YOLO is not proactive; does not seek interactions. This profile could also be described as loner, contemplative, or reclusive;
    \item \textbf{Harmonious ---} YOLO acts in a moderated fashion, presenting behaviors that are in-between the extreme versions of Exuberant and Aloof. As Harmonious, YOLO exhibits medium speed, movements with medium amplitude, and displays warm colors such as yellow and orange at medium brightness levels. This is a balanced and moderate profile.
\end{itemize}

\section{Related work}
\begin{figure*}
    \centering
    \includegraphics[width=0.8\textwidth]{Fig/Arc.pdf}
    \caption{Storytelling arcs associated with creativity techniques: convergent thinking is stimulated during rising and falling action phases by using the mirror technique; divergent thinking is stimulated during climax by using the contrast technique.}
    \label{fig:arc}
\end{figure*}
\subsection{Background on creativity research}
\label{sec:introduction}
As societies develop into creativity-based economies, innovative and creative problem solving and the ability to collaborate are becoming must-have skills \cite{florida2005cities, robinson2011out}. However, around the age of $7$--$9$ years old there is a decline in children's creativity abilities known as the ``creative crisis'' \cite{kim2011creativity}. Research has shown that everyone has the potential to be creative and that creativity can be nurtured if stimulated \cite{runco2004everyone, sawyer2003creativity}. In our work, we aim to contribute to the increase in children's creativity by using a social robot. It therefore becomes imperative to stimulate this ability at a young age. In particular, emphasizing the school environment where children spend most of their time. While some schools already feature activities (e.g., storytelling) to support the promotion of children's creative thinking \cite{di2010collective}, current activities can be challenging to integrate into traditional classroom formats as they need preparation time and are not formally included in the school curriculum \cite{chan2014personal}. Technologies --- such as social robots --- appear as a more effective tool to apply in these contexts.

\subsection{Robots for creativity}
\label{sec:related-work}
Robots have been programmed with a deep variety of socially intelligent behaviors and affective states; thus, permitting robots to be perceived as social actors \cite{breazeal2004designing, reeves1996people}. Additionally, due to their physical and interactive nature, they become a technology that can uniquely impact creativity stimulation. Ali, Moroso, and Breazel \cite{ali2019can} demonstrated that a robot displaying creative behaviors positively influenced the creativity of children. The authors found that children who interacted with a creative robot generated more ideas, explored more themes, and were more original, than children who interacted with a non-creative robot \cite{ali2019can}. Additionally, Gordon et al. \cite{gordon2015can} demonstrated that children become more curious, an important creativity trait, when interacting with a curious robot. The authors found that these children posed more questions and become avid explores, compared to children who interacted with a non-curious robot \cite{gordon2015can}.

\section{Conclusions and Impact}
\label{sec:conclusions}
As societies develop increasingly higher levels of sophistication, social robots can play a crucial role in the development of human creativity. Related research has indicated that social robots impact the play behaviors in children, pulling them towards traditional play formats such as physical, unstructured, and unrestrained play, benefiting multiple aspects of growth \cite{pellegrini1998physical}.

In this article, we presented the software which allows the YOLO robot to encourage creativity stimulation. This software allows potential developers to create behaviors that make the robot act according to different social behaviors. We also described several tests applying our software in real-world scenarios. These tests revealed the potential of our program, as robots using our software provoke creative narratives in stories which the children created.

The impact of this software is broad. By being an easy-to-use tool, children's stakeholders such as educators and parents, have access to a robot that is easy to prepare (e.g., for \ac{STEAM}-related activities), contrasting with other existing technological tools that can be cumbersome for non-experts to prepare \cite{chan2014personal}. Additionally, this software serves as a solid platform in academic studies, where researchers can use YOLO's \ac{API} to study child-robot interaction.
\section{Highlights}

\begin{itemize}
    \item \textbf{Creativity stimulating robot:} YOLO can stimulate children's creativity during play;
    \item \textbf{Open-access:} Access to the code and the guide to install and execute the software;
    \item \textbf{Scalability and personalization:} \ac{API} for developers to create new behaviors for YOLO;
    \item \textbf{Application:} YOLO can be used by children's stakeholders and by the research community.
\end{itemize}
\section{Illustrative Example}
\label{sec:illustrative-example}
To validate the effectiveness of our software, we have tested it with children in a storytelling activity. The instruction provided information that they should use the robot as a character for the story they created. In the box below, we transcribed part of an interaction case during a study session between a child and YOLO (see complementary Figure \ref{fig:use-case}). In this example, it is visible how the robot makes use of its interaction profiles to stimulate convergent and divergent thinking and how this relates to the different stages of the storytelling.

\begin{figure}
\centering
\includegraphics[width=0.7\textwidth]{Fig/CaseStudy.pdf}
\caption{\label{fig:use-case} Use-case example of a child using YOLO as a character for the creativity-stimulating storytelling scenario. Details about this scenario are explained in Section \ref{sec:illustrative-example}.}
\end{figure}

\begin{tcolorbox}

The child is on the floor playing with YOLO.

\textbf{Child:} \textit{``This is a football field and YOLO is from the Benfica team, so we are going to win!''}

The child manipulates YOLO in the imaginary football field, imitating the robot running after an imaginary ball and deviating from imaginary team adversaries. Because YOLO is still in the first part of the storytelling arc, i.e., in the Raising Action stage, the robot will stimulate convergent thinking abilities. Therefore, the robot imitates the last movement that the child performed. The child looks at the robot while it is moving.

\textbf{Child:} \textit{``Yes! Go for it, C\'{a}diz, score!} (C\'{a}diz is the name of a Benfica team player that the child gave to the robot).

The child imitates scoring a goal and then grabs YOLO and celebrates.

\textbf{Child:} \textit{``Ok C\'{a}diz, but we have to continue doing well. These other guys are good too.}

The child continues manipulating YOLO through the adversaries. At this point in time, YOLO entered the next storytelling arc which is the Climax. During climax, divergent thinking is stimulated so the robot will perform a movement that is different from the last movement that  the child has performed. The child manipulates the robot straight ahead towards the soccer goal but the robot goes the opposite direction.

\textbf{Child:} \textit{``What happened? Oh no, the other guys hit you in the knee. Assistance is needed here!''}

The game continues.

\end{tcolorbox}

\section*{Acknowledgements}
This work was supported by national funds through Funda\c{c}\~{a}o para a Ci\^{e}ncia e a Tecnologia (FCT-UID/CEC/500 21/2013) and through AMIGOS project ref. PTDC/EEISII/7174/2014. P. Alves-Oliveira acknowledges a FCT grant ref. SFRH/BD/110223/2015. We thank Andr\'{e} Pires for his contribution on the initial stage of software development.
\section*{Required Metadata}
\label{section:RequiredMetadata}

\subsection*{Current code version}
\begin{table}[!h]
\begin{tabular}{|p{6.5cm}|p{6.5cm}|}
\hline
\textbf{Code metadata description} & \textbf{Please fill in this column} \\
\hline
Current code version & v0.4 \\
\hline
Permanent link to code/repository used for this code version & \url{https://github.com/patricialvesoliveira/YOLO-Software} \\
\hline
Legal Code License   & CC Attribution 4.0 International \\
\hline
Code versioning system used & git \\
\hline
Software code languages, tools, and services used & Python \\
\hline
Compilation requirements, operating environments \& dependencies & Raspbian Stretch Lite OS\\
\hline
If available Link to developer documentation/manual & \url{https://github.com/patricialvesoliveira/YOLO-Software/wiki}\\
\hline
Support email for questions & Samuel Gomes: \url{samuel.gomes@tecnico.ulisboa.pt} and Patr\'{\i}cia Alves-Oliveira: \url{patricia_alves_oliveira@iscte-iul.pt}\\
\hline
\end{tabular}
\caption{Code metadata}
\label{}
\end{table}
\section{Software functionalities}
\label{sec:software-functionalities}

A primary function of this software is to serve as an \ac{API} that enables any user the opportunity to design personalized behaviors for YOLO, consequently providing the possibility to generate new behaviors and interaction modes\footnote{Guide for YOLO's \ac{API}: \url{https://github.com/patricialvesoliveira/YOLO-Software/wiki/API-Documentation}}. The robot can receive information from the environment (input) and express different interactive behaviors towards (output). Table \ref{tab:software-functionalities} lists pre-sets that were developed for YOLO to act as a social robot that can stimulate creativity in children.

Since each aspect of the robot is controllable and parameterizable, behaviors can be tweaked, created and mixed. To demonstrate the \ac{API} functionality, we conducted testing sessions in which we asked two participants unfamiliar with YOLO software to create different behaviors for the robot. One of the participants had a background in Computer Science and the other in Psychology. The participants were instructed to choose beloved characters from animation movies and to create a behavior for the robot that would resemble the behavior of those characters. The examples created by the participants were Mickey, Barbie, Bugs Bunny, and Genie from Aladdin \footnote{Examples created by the participants using the \ac{API}: \url{https://github.com/patricialvesoliveira/YOLO-Software/wiki/Examples}}.

\section{Software architecture}
\label{sec:software-architecture}
\begin{figure}
\centering
\includegraphics[width=1.0\textwidth]{Fig/YoloModulesDiagram.pdf}
\caption{\label{fig:YOLOModulesDiagram} Architecture of the the modules that compose YOLO software.}
\end{figure}
The architecture of our software includes several modules that manipulate data at different levels of abstraction from the low-level sensors and actuators to high-level behaviors. Figure \ref{fig:YOLOModulesDiagram} shows the scheme of these modules and how they interact. Each module is explained in the next sections.

\begin{figure}
\centering
\includegraphics[width=0.7\textwidth]{Fig/YOLOShapeRecognizer.pdf}
\caption{\label{fig:YOLOShapeRecognizer} Workflow of the ML algorithm for shape recognition used by YOLO.}
\end{figure}

\subsection{Control}
\label{sec:Control-module}

This module has two main functions: first, it extracts data associated with the robots' sensors and translates into a programmable format. Second, it instructs the actuators what to do based on the software calls.

The \emph{touch sensor} of YOLO indicates the robot is recognizing physical contact, and the \emph{optical sensor} observes the differences in position to detect the direction of movement. The sensors record movement at each moment. The \emph{shape recognizer} dynamically identifies and characterizes each movement using \ac{ML}. The pre-trained \ac{KNN} algorithm determines a shape using the robot motion sensors which capture coordinates in $3$ seconds intervals  \cite{altman1992introduction}. Figure \ref{fig:YOLOShapeRecognizer} depicts the \ac{ML} workflow. We trained the model by collecting raw coordinates and converting these coordinates into a feature vector using the convex hull algorithm \cite{barber1996quickhull}\footnote{More details about our shape recognizer algorithm are present at this link: \url{https://github.com/patricialvesoliveira/YOLO-Software/wiki/Algorithm}}. Every time a movement is detected, \ac{KNN} is used to determine the closest matching shape from the training data. Simulations with a computer mouse showed us that with n=$3$, \ac{KNN} provided high accuracy (94\%). Therefore, we used this parameterization. The current \ac{ML} model was trained with the physical robot and can recognize with an $80$\% success rate the following shapes: circle, rectangles, loops, curls, spikes, and a straight line (see Figure \ref{fig:movement-patterns}).

\begin{figure*}
    \centering
    \includegraphics[width=0.7\textwidth]{Fig/MovementPatterns.PNG}
    \caption{The lines illustrate the movement shapes performed by YOLO that are recognized by our algorithm. Illustrated shapes are: circle, rects, loops, curls, spikes, and straight line. For additional details see Section \ref{sec:Control-module}.}
    \label{fig:movement-patterns}
\end{figure*}

YOLO actuators include the \textit{Wheel Actuator} and \textit{LED Actuator}. While \textit{Wheel Actuator} receives direction and speed values and moves the wheels' motors accordingly, \textit{LED Actuator} receives a color and brightness level and displays it in the robot's jewel LEDs.

\begin{figure}
\centering
\includegraphics[width=1.0\textwidth]{Fig/PlanningFlowDiagram.pdf}
\caption{\label{fig:PlanningFlowDiagram}State machine diagram representing the schedule of the procedures executed in the \textit{Planning} module.}
\end{figure}

\subsection{Behaviors}
The \textit{Behaviors} module coordinates the simultaneous execution of different actuators based on given parameters. The intended behavior arises from the simultaneous execution of different actuators. To simplify the development process, we divided behaviors into more concrete \textit{Simple Behaviors}, which directly use the actuator data and \textit{Composed Behaviors}, which unite several simple behaviors. \textit{Simple behaviors} directly call the \textit{Control} module. These behaviors consist of assigning different light behaviors (different colors, animations, and brightness) to different movement configurations (different movement patterns at varying speed)\footnote{Examples of simple behaviors are detailed at this link: \url{https://github.com/patricialvesoliveira/YOLO-Software/wiki/SimpleBehavior-Hierarchy}}. \textit{Composed behaviors} can be used to define the social behaviors which YOLO exhibits, such as Exuberant, Aloof, and Harmonious\footnote{Composed behaviors are further explained at this link: \url{https://github.com/patricialvesoliveira/YOLO-Software/wiki/ComposedBehavior}}.

\subsection{Planning}
The \textit{Planning} module schedules the behaviors in each moment of the interaction, executing specific ones based on the current interaction state. In order to trigger new interaction states, \textit{Planning} module uses the data extracted from the sensors which the \textit{Control} module provides. A flowchart illustrating the \textit{Planning} module's is depicted in Figure \ref{fig:PlanningFlowDiagram}.


\section{Introduction}
Neural architecture search~(NAS) aims to automatically design neural network architectures. Recent NAS works show impressive results and have been applied in many tasks, including image classification~\cite{nas,nasnet}, object detection~\cite{nasfpn}, super resolution~\cite{chu2019fast}, language modeling~\cite{enas}, neural machine translation~\cite{evovledtransformer} and model compression~\cite{autoslim}. Without loss of generality, the search process can be viewed as iterations of two steps: (1) In each iteration, the NAS algorithm generates some candidate architectures to estimate and the architectures are trained and evaluated on the task. (2) Then the algorithm learns from the evaluation results of the candidate architectures. In principle, it needs to estimate each generated candidate architecture by training it until convergence, therefore the estimation procedure is resource consuming.

\begin{figure}[ht]
\centering
\includegraphics[width=1.0\columnwidth]{f1.png}
\caption{Balanced One-shot Neural Architecture Optimization. Each architecture is sampled in proportion to its model size during training in the search procedure, to balance architectures of different sizes.}
\label{fig:bnao}
\end{figure}

One-shot NAS was proposed~\cite{oneshot,enas} to reduce the resources, by utilizing a supernet to include all candidate architectures in the search space and perform weight inheritance between different architectures. However, the architectures discovered by such one-shot NAS works show inferior performance to conventional NAS which trains and evaluates each architecture individually. Meanwhile, the stability is weak that the architectures generated by the algorithms do not always achieve the performance reported originally~\cite{random}. We conduct experiments on ENAS~\cite{enas}, DARTS~\cite{darts} and NAO-WS~\cite{nao}, and find that the stability is weak and the performance is inferior to conventional NAS~\cite{nasnet,amoebanet,nao}.

During the search, the algorithm aims to differentiate the candidate architectures and figures out relatively good architectures among the all. Then the key to the algorithm is the ability to rank these candidate architectures. Then we should expect that the ranking of the architectures during final full training to be preserved when they are trained under such one-shot method during the search, so the algorithm can learn well. We investigate into the one-shot training with the weight-sharing mechanism and find that the ranking correlation of the architectures is not well preserved under such one-shot training, which misleads the algorithm to effectively and robustly find an optimal architecture, as shown in Fig.~\ref{fig:nas framework}. Architectures discovered could perform relatively well when trained in such one-shot method, without guarantee to perform well when fully trained stand-alone.

Under one-shot training, thousands of candidate architectures are included in a supernet and one architecture~(or one dominant architecture) is sampled at each step during the training to update its parameters. The average training time of each architecture is handful and the optimization is insufficient, where the validation accuracy of the architecture is less representative of its ground-truth performance in final training. We show that the ranking correlation of the architectures is weak under one-shot training, and the ranking correlation increases as the training time increases.

Since small architectures are easier to train than big architectures, given handful training steps and insufficient optimization, small architectures tend to perform well than big architectures, which is not consistent in the final training. Therefore the training of the candidate architectures is imbalanced, and the ranking correlation is weak, which is demonstrated by our experiments. This misleads the search algorithm to effectively find good architecture and the algorithms are observed to produce some small architectures that generalize worse during the final training.

\begin{figure}[ht]
	\centering
	\subfigure[Conventional NAS]{
		\label{fig:conventional nas}
		\includegraphics[width=1.0\columnwidth]{f2a.png}
	}
	\subfigure[One-shot NAS]{
		\label{fig:one-shot nas}
		\includegraphics[width=1.0\columnwidth]{f2b.png}
	}
\caption{Illustration of ranking correlation between architectures in neural architecture search. Rectangles with different colors and numbers represent different architectures ranked by performance. (a) In conventional NAS, the ranking correlation between architectures during search and final fully trained ones is well preserved with slight bias. (b) In one-shot NAS, the ranking correlation is hardly preserved.}
\label{fig:nas framework}
\end{figure}

Based on such insight, we propose balanced NAO where we introduce balanced training to encourage large architectures for more updates than small architectures during the one-shot training of the supernet, depicted in Fig.~\ref{fig:bnao}. We expect the training time of an architecture to be proportional to its model size. Specifically, we sample a candidate architecture in proportion to its model size, instead of uniformly random sampling. With this proportional sampling approach, the expected training time of the architecture associates with its size, and experiments show that the ranking correlation increases.

Extensive experiments on CIFAR-10 demonstrate that:~(1) Architectures discovered by our proposed method show significant improvements compared to baseline one-shot NAS methods, with a test error rate of 2.60\% on CIFAR-10 and top-1 accuracy of 74.4\% on ImageNet.~(2) Our proposed method generates architectures with more stable performance and lower variance, which brings better stability.

\section{Related Work}
Recent NAS algorithms mainly lie in three lines: reinforcement learning~(RL), evolutionary algorithm~(EA) and gradient based.~\cite{nas} firstly proposed to search neural network architectures with reinforcement learning~(RL) and achieved better performances than human-designed architectures on CIFAR-10 and PTB. ~\cite{amoebanet} proposed AmoebaNet using regularized evolutionary algorithm.~\cite{nao} maps the discrete search space to continuous space and search by gradient descent. These works achieve promising results on several tasks, however they are very costly.

To reduce the large amount of resources conventional NAS methods require, one-shot NAS was proposed.~\cite{oneshot} proposed to include all candidate operations in the search space within a supernet and share parameters among different candidate architectures. ENAS~\cite{enas} leverages the idea of weight sharing and searches by RL. DARTS~\cite{darts} searched based on the supernet through a bi-level optimization by gradient descent. NAO~\cite{nao} also incorporates the idea of weight sharing. ProxylessNAS~\cite{proxylessnas} binaries architecture associated parameters to reduce the memory consumption in DARTS and can directly search on large-scale target task. SNAS~\cite{snas} trains the parameters of the supernet and architecture distribution parameters in the same round of back-propagation. However, such supernet requires delicate design and needs to be carefully tuned.

\section{Analyzing One-shot NAS}
\subsection{Stability of Baselines}
\label{sec:analysis}
\begin{table}[ht]
\centering
\begin{tabular}{cccc}
\hline
Architectures & ENAS & DARTS & NAO-WS \\
\hline
Original & 2.89 & 2.83 & 2.93 \\
\hline
network 1  & 3.09 &3.00 & 2.90 \\
network 2  & 3.00 &2.82 & 2.96 \\
network 3  & 2.97 &3.02 & 2.98 \\
network 4  & 2.79 &2.96 & 3.02 \\
network 5  & 3.07 &3.00 & 3.05 \\
\hline
\end{tabular}
\caption{Evaluation of the stability of three recent one-shot NAS algorithms. The first block shows the test performance reported by the original authors. The second block shows the test performance of architectures we got using the algorithms. We ran the search process for $5$ times, and evaluated the $5$ network architectures generated. All the models are trained with cutout~\cite{cutout} and the results are test error rate on CIFAR-10. We follow the default settings and training procedure in the original works.}
\label{analysis:baseline}
\end{table}
Firstly, we study the stability of three previous popular one-shot NAS algorithms, ENAS~\cite{enas}, DARTS~\cite{darts} and NAO~\cite{nao}, as many one-shot NAS works are based on these three works. For NAO, we use NAO-WS~(NAO with weight sharing), which leverages the one-shot method. We use the official implementation of ENAS\footnote{https://github.com/melodyguan/enas.git}, DARTS\footnote{https://github.com/quark0/darts.git} and NAO-WS\footnote{https://github.com/renqianluo/NAO\_pytorch.git}. We searched and evaluated on CIFAR-10 dataset, and adopted default settings and hyper-parameters by the authors, if not stated explicitly in the following context. We ran the search process for $5$ times, and evaluated the discovered architectures. The results are shown in Table~\ref{analysis:baseline}.

We can see that for all the three algorithms, among the $5$ network architectures we evaluated, at least one of them could achieve the performance as reported in the original paper. However the results are unstable. ENAS achieved $2.79$\% in the fourth run which is on par with the result reported in the paper~($2.89$\%), while the other four runs got inferior results with about $0.2$ drop. DARTS achieved $2.82$\% in the second run which is on par with the result reported originally~($2.83$\%), but got around $3.0$\% in the other four runs with about $0.2$ drop. NAO-WS achieved $2.90$\% and $2.96$\% on the first and the second architectures which are on par with the result reported by the authors~($2.93$\%), but got around $3.0$\% on the other three architectures with also about $0.1$ drop. Moreover, all the results are inferior to the performance achieved by conventional NAS algorithms which do not leverage one-shot method~(e.g., AmoebaNet-B achieved $2.55$\%, NAONet achieved $2.48$\%).

In the search process, the ability of the performance of an architecture under one-shot training~(noted as \emph{one-shot performance}) to predict its performance under final full training~(noted as \emph{ground-truth performance}) is vital. Further, as the algorithm is practically supposed to learn to figure out relatively better architectures among the candidate architectures according to their one-shot performance, the \emph{ranking correlation} between candidate architectures during one-shot training and full training is the key to the algorithm. That is, if one architecture is better than another architecture in terms of ground-truth performance, we would expect that their one-shot performance also preserves the order, no matter what concrete values they are. Since the search algorithms of most one-shot NAS works still hold RL, EA or gradient based optimization that are almost the same to the conventional NAS~(e.g., NAO has both regular version and one-shot version while the latter shows inferior performance), we conjecture that the challenge is in the one-shot training mechanism.

\subsection{Insufficient Optimization}
First, we consider the issue is due to the insufficient optimization of the architectures, as is also shown by~\cite{random}. In one-shot training, the average training time of an individual architecture is surprisingly inadequate. Generally, an architecture should be trained for hundreds of epochs to converge in the full training pipeline to evaluate its performance. In conventional NAS, early-stop is performed to cut-off the high cost but each architecture is still trained for several tens of epochs, so the performance ranking of the models is relatively stable and can be predictable of their final ground-truth performance ranking. However in one-shot NAS, the supernet is usually trained in total for the time that training a single architecture needs. Since all the candidates are included, in average each architecture is trained for handful steps. Though with the help of weight-sharing and the parameters of an architecture could be updated by other architectures that share the same part, the operations could play different roles in different architectures and may be affected by other ones. Therefore, architectures are still far from convergence and the optimization is insufficient. Their evaluated one-shot performance are largely biased from their ground-truth performance.

\begin{table}[ht]
\centering
\begin{tabular}{ccc}
\hline
Training Epochs & Pairwise accuracy(\%) \\
\hline
5  & 62 \\
10 & 65 \\
20 & 71 \\
30 & 75 \\
50 & 76 \\
\hline
\end{tabular}
\caption{Pairwise accuracy of one-shot performance and ground-truth performance under different training epochs.}
\label{analysis:time}
\end{table}
To verify this, we conduct experiments to see how training time affects the ranking correlation. We randomly generate $50$ different architectures and train each architecture stand-alone and completely, exactly follow the default settings in~\cite{nao}, and collect their performance~(valid accuracy) on CIFAR-10. Then we train the architectures using one-shot training with weight-sharing. Concretely at each step, one architecture from the $50$ architectures is uniformly randomly sampled and trained at each step. We train the architectures under one-shot training for different time~(i.e., $5$, $10$, $20$, $30$, $50$ epochs respectively), and collect their performance on CIFAR-10.

In order to evaluate the ranking correlation between the architectures under one-shot training and stand-alone trained ones, we calculate the pairwise accuracy between the one-shot performance and the stand-alone performance of the given architectures. The pairwise accuracy metric is the same as in~\cite{nao} which ranges from $0$ to $1$, meaning the ranking is completely reversed or perfectly preserved. The results are listed in Table~\ref{analysis:time}.

We can see that, when the training time is short~(as in the case in practical one-shot NAS), the pairwise accuracy is $62\%$ which is slightly better than random guess, meaning that the ranking is not well-preserved. The ranking of the architectures under one-shot training is weakly correlated to that of ground-truth counterpart. As the training time increases, the average number of updates of individual architecture increases and pairwise accuracy increases evidently. One may think that when training for $50$ epochs, the pairwise accuracy seems to be satisfactory and commonly the supernet is trained for hundreds of epochs. However we should notice that this is only a demonstrative experiment where we only use $50$ architectures to train the supernet. In practice, the search algorithms always need to sample thousands of architectures~(i.e., more than $10$ times) to train~\cite{enas,nao,amoebanet} so the average training time of each individual architecture is handful as limited as the setting of $5$ epochs here. This indicates that the short average training time and inadequate update of individual architecture lead to insufficient optimization of individual architecture in one-shot training and brings weak ranking correlation.

\subsection{Imbalanced Training of Architectures}
\label{sec:imbalanced}
\begin{table}[ht]
\centering
\begin{tabular}{cccc}
\hline
Model Sizes & Pairwise Accuracy(\%) \\
\hline
diverse & 62 \\
similar & 73 \\
\hline
\end{tabular}
\caption{Pairwise accuracy of one-shot performance and ground-truth performance, of architectures with similar sizes and diverse sizes.}
\label{analysis:imbalanced}
\end{table}
During multiple runs of one-shot NAS~(e.g., DARTS and NAO-WS), we find that they sometimes tend to produce small networks, which contain many parameter-free operations~(e.g., skip connection, pooling). These architectures are roughly less than $2MB$. Theoretically, this means that these small architectures should perform well on the target task during final training. However, they do not consistently perform well when fully trained and on the contrary, they generally perform worse. This is an interesting finding, meaning that during the one-shot training, these inferior small architectures tend to perform well than big architectures, so they are picked out by the algorithms as good architectures.

In general, small architectures are easier to train and need fewer updates than big architectures to converge. Given the insights above of the inadequate training and insufficient optimization, we conjecture that small networks are easier to be optimized and tend to perform better than big networks. Big networks are then relatively less-trained on the contrary compared to small networks and perform worse. Consequently, the algorithm learns from the incorrect information that small networks would perform well. In conventional NAS, where each architecture is trained for tens of epochs though with early-stopping, both small architectures and big architectures are updated relatively more adequately and their performance ranking is more stable and close to the final ground-truth ranking.

Therefore, different architectures are imbalanced during one-shot training. To verify this and demonstrate whether this affects the ranking correlation, we conduct experiments on architectures with diverse sizes~(as in the practical case) and similar sizes. For architectures with diverse sizes, we just use the architectures and the results in the above experiment in Table~\ref{analysis:time}. Then we randomly generate other $50$ architectures with similar sizes and train them using supernet.

From the results in Table~\ref{analysis:imbalanced}, we can see that when the architectures are of diverse sizes, the pairwise accuracy is low. When the architectures have similar model sizes, the pairwise accuracy increases. This indicates that in practical case the training of the architectures with different sizes is imbalanced and the ranking correlation is not preserved well.

\begin{table*}[h]
\centering
\begin{tabular}{ccccc}
\hline
Model                            & Test error(\%)     & Params(M)  & Methods\\
\hline
Hier-EA~\cite{hanxiao}           & 3.75               & 15.7     & EA \\
NASNet-A~\cite{nasnet}           & 2.65               & 3.3      & RL \\
AmoebaNet-B~\cite{amoebanet}     & 2.13               & 34.9     & EA \\
NAONet~\cite{nao}                & 2.48               & 10.6     & gradients \\
NAONet~\cite{nao}                & 1.93               & 128      & gradients \\
\hline
ENAS~\cite{enas}                 & 2.89               & 4.6      & one-shot + RL \\
DARTS~\cite{darts}               & 2.83               & 3.4      & one-shot + gradients \\
NAO-WS~\cite{nao}                & 2.90               & 2.5      & one-shot + gradients \\
SNAS~\cite{snas}                 & 2.85               & 2.9      & one-shot + gradients \\
P-DARTS~\cite{pdarts}            & 2.50               & 3.4      & one-shot + gradients \\
PC-DARTS~\cite{pcdarts}          & 2.57               & 3.6      & one-shot + gradients \\
BayesNAS~\cite{bayesnas}         & 2.81               & 3.4      & one-shot + gradients \\
ProxylessNAS~\cite{proxylessnas} & 2.08               & 5.7      & one-shot + gradients \\
Random~\cite{darts}              & 3.29               & 3.2      & random               \\
\hline
Balanced NAO                     & 2.60              & 3.8      & one-shot + gradients \\
\hline
\end{tabular}
\caption{Test performance on CIFAR-10 dataset of our discovered architecture and architectures by other NAS methods, including methods with or without one-shot method. The first block is conventional NAS without one-shot method. The second block is one-shot NAS methods.}
\label{tbl:cifar10}
\end{table*}

\begin{table}[h]
\centering
\begin{tabular}{cccc}
\hline
Model/Method                                    & Top-1(\%) \\
\hline
MobileNetV1~\cite{mobilenet}                    & 70.6 \\
MobileNetV2~\cite{mobilenetv2}                  & 72.0 \\
\hline
NASNet-A~\cite{nasnet}                          & 74.0 \\
AmoebaNet-A~\cite{amoebanet}                    & 74.5 \\
MnasNet~\cite{mnasnet}                          & 74.0 \\
NAONet~\cite{nao}                               & 74.3 \\
DARTS~\cite{darts}                              & 73.1 \\
SNAS~\cite{snas}                                & 72.7 \\
P-DARTS(C10)~\cite{pdarts}                      & 75.6 \\
P-DARTS(C100)~\cite{pdarts}                     & 75.3 \\
\hline
Single-Path NAS~\cite{singlepathnas}            & 74.96 \\
Single Path One-shot~\cite{singlepathoneshot}   & 74.7 \\
ProxylessNAS~\cite{proxylessnas}                & 75.1 \\
PC-DARTS~\cite{pcdarts}                         & 75.8 \\
\hline
Balanced NAO                                    & 74.4 \\
\hline
\end{tabular}
\caption{Test performances on Imagenet dataset under mobile setting. The first block shows human designed networks. The second block lists NAS works that search on CIFAR-10 or CIFAR-100 and directly transfer to ImangeNet. The third block are NAS works that directly search on ImageNet}
\label{tbl:imagenet}
\end{table}

\section{Method}
We have shown that the training of the architectures in common one-shot NAS is imbalanced, then we propose an approach to balance architectures with different sizes. We mainly propose our approach based on NAO~\cite{nao} for the following two reasons: Firstly, both ENAS and NAO perform sampling from candidate architectures at each step during the search. NAO directly samples from the architecture pool while ENAS samples from the learned controller, so the sampling procedure is easier to control in NAO. Secondly, DARTS and DARTS-like works~(e.g., ProxylessNAS~\cite{proxylessnas}, SNAS~\cite{snas}) combine the parameter optimization and architecture optimization together in a forward pass which is not based on sampling architectures.

To balance the architectures, we expect to encourage more updates for large architectures over small architectures. Specifically, we expect an architecture $x_i$ to be trained for $T_i$ steps where $T_i$ is in proportional to its model size, following:
\begin{equation}
\label{eqn:timepropto}
T_i \propto model\_size\_of(x_i)
\end{equation}

One naive and simple way is to calculate the size of the smallest model noted as $x_s$ in the search space, and set a base step $T_{base}$ for it. Then for any architecture $x_i$, its number of training steps is calculated as:
\begin{equation}
\label{eqn:time}
T_i = T_{base} \times \frac{model\_size\_of(x_i)}{model\_size\_of(x_s)}
\end{equation}
However, such a naive implementation may lead to expensive cost which may run out of the search budget, and the relationship between training time and model size is not as simple as a strictly linear relationship.

Therefore, we use proportional sampling to address the problem. Specifically in NAO~\cite{nao}, during the training of the supernet, an architecture is randomly sampled from the candidate architecture population at each step. Instead of randomly sampling, we sample the architectures with a probability in proportion to their model sizes. Mathematically speaking, we sample an architecture $x_i$ from the candidate architecture pool $\mathcal{X}$ with the probability:
\begin{equation}
\label{eqn:sample}
P(x_i)=\frac{model\_size\_of(x_i)}{\sum_{x_i\in \mathcal{X}} model\_size\_of(x_i)}.
\end{equation}
If the supernet is trained for $T_t$ steps in total, then the expectation of the training steps of architecture $x_i$ is:
\begin{equation}
\label{eqn:exptime}
\mathbb{E}T_i=T_t \times \frac{model\_size\_of(x_i)}{\sum_{x_i \in \mathcal{X}} model\_size\_of(x_i)}
\end{equation}
It is proportional to the model size of $x_i$. Following this, the architectures of different sizes could be balanced during training within the supernet.

We incorporate this proportional sampling methodology into NAO~\cite{nao}, specifically the one-shot NAO version~(i.e., NAO-WS in the original paper) which utilizes weight sharing technology, and propose \emph{Balanced NAO}. The final detailed algorithm is shown in Alg.~\ref{alg:BNAO}.
\begin{algorithm}[ht]
\caption{Balanced Neural Architecture Optimization}
\label{alg:BNAO}
\begin{algorithmic}
\STATE \textbf{Input}: Initial candidate architectures set $\mathcal{X}$. Initial architectures set to be evaluated denoted as $\mathcal{X}_{eval}=\mathcal{X}$. Performances of architectures $\mathcal{S}=\emptyset$. Number of seed architectures $\mathcal{K}$. Number of training steps of the supernet $\mathcal{N}$. Step size $\eta$. Number of optimization iterations $\mathcal{L}$.
\FOR {$l= 1,\cdots, \mathcal{L}$}
\FOR {$i= 1,\cdots, \mathcal{N}$}
\STATE Sample an architecture $x\in \mathcal{X}_{eval}$ using Eqn.~(\ref{eqn:sample})
\STATE Train the supernet with the sampled architecture $x$
\ENDFOR
\STATE Evaluate all the candidate architectures $\mathcal{X}$ to obtain the dev set performances $\mathcal{S}_{eval}=\{s_x\}, \forall x \in \mathcal{X}_{eval}$. Enlarge $\mathcal{S}$: $\mathcal{S}=\mathcal{S}\bigcup \mathcal{S}_{eval}$.
\STATE Train the NAO model~(encoder, performance predictor and decoder) using $\mathcal{X}$ and $\mathcal{S}$.
\STATE Pick $\mathcal{K}$ architectures with top $\mathcal{K}$ performances among $\mathcal{X}$, forming the set of seed architectures $\mathcal{X}_{seed}$.
\STATE For $x \in \mathcal{X}_{seed}$, obtain a better representation $e_{x'}$ from $e_{x'}$ by applying gradient descent with step size $\eta$, based on trained encoder and performance predictor. Denote the set of enhanced representations as $E'=\{e_{x'}\}$.
\STATE Decode each $x'$ from $e_{x'}$ using decoder, set $\mathcal{X}_{eval}$ as the set of new architectures decoded out: $\mathcal{X}_{eval} = \{\mathcal{D}(e_{x'}), \forall e_{x'}\in E'\}$. Enlarge $\mathcal{X}$ as $\mathcal{X}= \mathcal{X}\bigcup \mathcal{X}_{eval}$.
\ENDFOR
\STATE \textbf{Output}: The architecture within $\mathcal{X}$ with the best performance
\end{algorithmic}
\end{algorithm}

\section{Experiments}
\label{sec:exp}

\subsection{Ranking Correlation Improvement}
\begin{table}[ht]
\centering
\begin{tabular}{cccc}
\hline
Training & Sampling & Pairwise \\
Epochs & Method & Accuracy(\%) \\
\hline
5 & Random sampling & 62 \\
5 & Proportional sampling & 69 \\
10 & Random sampling & 65 \\
10 & Proportional sampling & 72 \\
20 & Random sampling & 71 \\
20 & Proportional sampling & 76 \\
30 & Random sampling & 75 \\
30 & Proportional sampling & 77 \\
50 & Random sampling & 76 \\
50 & Proportional sampling & 78 \\
\hline
\end{tabular}
\caption{Pairwise accuracy of one-shot performance and ground-truth performance.}
\label{exp:ranking}
\end{table}
Firstly, to see whether our proposed proportional sampling improves the ranking correlation, we conduct experiments following the same setting as in Sec.~\ref{sec:imbalanced}. We train the $50$ architectures with and without proportional sampling, and compute the pairwise accuracy, as listed in Table~\ref{exp:ranking}. When equipped with proportional sampling, the accuracy increases by more than $10$ points.

\subsection{Stability Study}
\begin{table}[h]
\centering
\begin{tabular}{ccccccc}
\hline
Methods & ENAS & DARTS & NAO-WS & Balanced NAO \\
\hline
network 1 & 3.09 & 3.00 & 2.90 & \textbf{2.60}\\
\hline
network 2 & 3.00 & 2.82 & 2.96 & 2.63\\
\hline
network 3 & 2.97 & 3.02 & 2.98 & 2.65\\
\hline
network 4 & 2.79 & 2.96 & 3.02 & 2.71\\
\hline
network 5 & 3.07 & 3.00 & 3.05 & 2.77\\
\hline
mean      & 2.98 & 2.96 & 2.98 & \textbf{2.67}\\
\hline
\end{tabular}
\caption{Evaluation of stability. Scores are test error rate on CIFAR-10 of 5 architectures discovered. All models are trained with cutout. The first block lists the baseline one-shot NAS we compare to. The second block is our proposed Balanced NAO.}
\label{exp:stability}
\end{table}
Then, as we claim the stability to be a problem, we evaluate the stability of our proposed Balanced NAO and compare to baseline methods~(i.e., ENAS, DARTS, NAO-WS). Same to the experiments before, We evaluate $5$ architectures discovered by the algorithms and measure the mean performance. We search and test on CIFAR-10 and show the results in Table~\ref{exp:stability}.

Compared to baseline methods, all the $5$ architectures perform better with an average test error rate of $2.67$\% and a best test error rate of \textbf{$2.60$\%}. Notably, we find that they perform well enough with lower variance, leading to better stability.

\subsection{Compared to Various NAS Methods}
We then compare our proposed Balanced NAO with other NAS methods, including NAS with or without the one-shot approach, to demonstrate the improvement of our approach. Table~\ref{tbl:cifar10} reports the test error rate, model size of several methods and our method.

The first block lists several classical conventional NAS methods without the one-shot approach and trains each candidate architecture from scratch for several epochs. They achieved promising test error rate but require hundreds or thousands of GPU days to search, which is intractable for most researchers. The second block lists several main-stream one-shot NAS methods which largely reduce the cost to less than ten GPU days, but the test performance of most works are relatively inferior compared to conventional methods as we claimed before.

Note that our method in the last block achieves better performance than previous baseline one-shot NAS~(e.g., ENAS, DARTS, NAO-WS, SNAS), and is on par with conventional NAS~(e.g., NASNet and NAONet) under similar model size, while the latter is costly.

\subsection{Transfer to Large Scale Imagenet}
To further verify the transferability of our discovered architecture, we transfer it to large scale Imagenet dataset. All the training settings and details exactly follow DARTS~\cite{darts}. The results of our model and other models are listed in Table~\ref{tbl:imagenet} for comparison.

Our model achieves a top-1 accuracy of $74.4$\%, which surpasses human designed models listed in the first block. We mainly compare our model to the models in the second block for fair comparison since they have roughly similar search space and apply the same transfer strategy from CIFAR to ImageNet. Our model surpasses many NAS methods in the second block and is on par with the best-performing work with minor gap. It is worth noting that NASNet-A, AmoebaNet-A, MnasNet and NAONet are all discovered with conventional NAS approaches that are not one-shot methods and the architectures are trained from scratch. Our model achieves better or almost the same performance compared to them.

However, it is slightly worse than~\cite{singlepathnas}, ~\cite{singlepathoneshot},~\cite{proxylessnas} and~\cite{pcdarts} in the third blocks which directly search on ImageNet with more careful design and more complex search space.

\section{Conclusion}
In this paper, we find that due to the insufficient optimization problem in one-shot NAS, architectures of different sizes are imbalanced, which introduces incorrect rewards and leads to weak ranking correlation. This further misleads the search algorithm and leads to inferior performance against conventional NAS and weak stability. We therefore propose Balanced NAO by balancing the architectures via proportional sampling. Extensive experiments show that our proposed method shows significant improvements both on performance and stability. For future work, we would like to further investigate into one-shot NAS to improve its performance.

\bibliographystyle{ijcai20}