# Exercises in orthodox geometry

Edited by A. Petrunin
<EMAIL_ADDRESS>
###### Abstract

This collection is oriented to graduate students who want to learn fast simple
tricks in geometry. (Solution of each problem requires only one non-trivial
idea.)

For problem solvers. The meaning of signs next to number of the problem:

  * $\circ$

— easy problem;

  * $*$

— hard problem;

  * $+$

— the solution requires knowledge of a theorem;

  * $\sharp$

— there are interesting solutions based on different ideas.

To get a hint, send an e-mail to the above address with the number and the
name of the problem.

For problem makers. This collection is under permanent development. If you
have suitable problems or corrections please e-mail it to me.

Many thanks. I want to thank everyone sharing the problems. Also I want to
thank R. Matveyev, P. Petersen, S. Tabachnikov and number of students in my
classes for their interest in this list and for correcting number of mistakes.
I’m also thankfull to everyone who took part in the discussion of this list on
mathoverflow.

##  1 Curves and surfaces

1.1. Geodesic for birds. Let $f\colon\mathbb{R}^{2}\to\mathbb{R}$ be a
$\ell$-Lipschitz function. Consider closed region $W$ cut from
$\mathbb{R}^{3}$ by graph of $f$; i.e.

$W=\\{(x,y,z)\in\mathbb{R}^{3}\,\mid\,z\geqslant f(x,y)\\}.$

Show that any _geodesic_ in $W$ has _variation of turn_ at most $2\ell$.
[D. Berg],[J. Liberman]

It is much easier to give some eatimate of turn in terms of $\ell$, say
$\pi(1+\ell)$. The bound $2\ell$ is optimal; to prove it one has to do some
calculations.

1.2. Kneser’s spiral. Let $\gamma$ be a plane curve with strictly monotonic
curvature function. Prove that $\gamma$ has no self-intersections.
[Ovsienko–Tabachnikov]

1.3. Closed curve. A smooth closed _simple curve_ with curvature at most $1$
bounds a rigion $\Omega$ in a plane. Prove that $\Omega$ contains a disc or
radius $1$. ???

1.4♯. A curve in a sphere. Let $\gamma$ be a closed curve in a unit sphere
which intersects each equator, prove that its length is at least $2\pi$. N.
Nadirashvili

1.5♯. A spring in a tin. Let $\alpha$ be a closed smooth immersed curve inside
a unit disc. Prove that the average absolute curvature of $\alpha$ is at least
$1$, with equality if and only if $\alpha$ is the unit circle possibly
traversed more than once. [S. Tabachnikov]

If instead of a disc we have a region bounded by closed convex curve $\gamma$
then it is still true that the average absolute curvature of $\alpha$ is at
least as big as average absolute curvature of $\gamma$. The proof is not that
simple, see ???.

1.6. A minimal surface.111If $\Sigma$ does not pass through the center and we
only know the distance $r$ from center to $\Sigma$ then optimal bound is
expected to be $\pi(1-r^{2})$. This is known if $\Sigma$ is topological disc,
see [Alexander–Osserman]. An analog result for area-minimizing submanifolds
holds for dimensions and codimensions, see [Alexander–Hoffman–Osserman]. Let
$\Sigma$ be a _minimal surface_ in $\mathbb{R}^{3}$ which has boundary on a
unit sphere. Assume $\Sigma$ passes through the center of the sphere. Show
that area of $\Sigma$ is at least $\pi$. ???

The problem is simpler if you assume that $\Sigma$ is a topological disc.

1.7. Asymptotic line. Consider a smooth surface $\Sigma$ in $\mathbb{R}^{3}$
given as a graph $z=\nobreak f(x,y)$. Let $\gamma$ be a closed smooth
asymptotic line on $\Sigma$. Assume $\Sigma$ is _strictly saddle_ in a
neighborhood of $\gamma$. Prove that projection of $\gamma$ on $xy$-plane is
not star shaped. [D. Panov, 1]

1.8. Closed twisted geodesics. Give an example of a closed Riemannian
2-manifold which has no closed smooth curve with constant geodesic curvature
$=1$.
[V. Ginzburg]

1.9. Non contractable geodesics. Give an example of a non-flat metric on
$2$-torus such that it has no contractible geodesics.
Y. Colin de Verdière, [M. Gromov, 4; 7.8(1/2)+]

1.10. Fat curve. Construct a _simple plane curve_ with non-zero Lebesgue’s
measure. ???

1.11. Stable net. Show that there is no stable net in standard $2$-sphere. By
“net” we understand an embedding $f\colon\Gamma\to\SS^{2}$ of a graph $\Gamma$
and it is stable if small variation of $f$ can not decreasse the total length
of all its edges. Z. Brady

1.12. Oval in oval. Consider two closed smooth strictly convex planar curves,
one inside another. Show that there is a chord of the outer curve, which is
tangent to the inner curve and divided by the point of tangency into equal
parts.

There is a similar open problem: find a point on outer curve (not necessary
convex) which has two tangent segments from this point to the inner curve has
equal size.

##  2 Comparison geometry

For doing most of problems in this section it is enough to know second
variation formula. Knowledge of some basic results such as O’Neil formula,
Gauss formula, Gauss–Bonnet theorem, Toponogov’s comparison theorem, Soul
theorem, Toponogov splitting theorems and Synge’s lemma also might help. To
sove problem 2, it is better know that factor positively curved Riemannian
manifold by an isometry group is a positively curved Alexandrov space. Problem
2 requires Liouville’s theorem for geodesic flow. Problem 2 requires a Bochner
type formula.

2.1. Totally geodesic hypersurface. Prove that if a compact positively curved
$m$-manifold $M$ admits a totally geodesic embedded hypersurface then $M$ or
its double cover is homeomorphic to the $m$-sphere. P. Petersen

2.2. Immersed convex hypersurface I. Let $M$ be a complete simply connected
Riemannian manifold with nonpositive curvature and
$\operatorname{dim}M\geqslant 3$. Prove that any immersed locally convex
hypersurface in $M$ is globally convex, i.e. it is an embedded hypersurface
which bounds a convex set. [S. Alexander]

2.3∗. Immersed convex hypersurface II. Prove that any immersed locally convex
hypersurface in a complete positively curved manifold $M$ of dimension
$m\geqslant 3$, is the boundary of an immersed ball. I.e. there is an
immersion of a closed ball $\bar{B}^{m}\to M$ such that the induced immersion
of its boundary $\partial\bar{B}^{m}\to M$ gives our hypersurface. [M. Gromov,
3], [J. Eschenburg], [B. Andrews]

2.4. Almgren’s inequalities. Let $\Sigma$ be a closed $k$-dimensional _minimal
surface_ in the unit $\SS^{n}$. Prove that
$\operatorname{vol}\Sigma\geqslant\operatorname{vol}\SS^{k}$. [F. Almgren],
[M. Gromov, 1]

2.5. Hypercurve. Let $M^{m}\hookrightarrow\mathbb{R}^{m+2}$ be a closed smooth
$m$-dimensional submanifold and let $g$ be the induced Riemannian metric on
$M^{m}$. Assume that sectional curvature of $g$ is positive. Prove that
curvature operator of $g$ is positively defined. [A. Weinstein, 2]

In particular, it follows from [Micallef–Moore]/[Böhm–Wilking] that the
universal cover of $M$ is homeomorphic/diffeomorphic to a standard sphere.

2.6. Horosphere. Let $M$ be a complete simply connected manifold with
negatively pinched sectional curvature (i.e. $-a^{2}\leqslant
K\leqslant-b^{2}<0$). And let $\Sigma\subset M$ be an horosphere in $M$ (i.e.
$\Sigma$ is a level set of a _Busemann function_ in $M$). Prove that $\Sigma$
with the induced intrinsic metric has _polynomial volume growth_.
V. Kapovitch

2.7. Minimal spheres. Show that a positively curved $4$-manifold can not
contain two distinct _equidistant_ _minimal_ 2-spheres. D. Burago

2.8. Fixed point of conformal mappings. Let $(M,g)$ be an even-dimensional
positively curved closed oriented Riemannian manifold and $f\colon M\to M$ be
a conformal orientation preserving map. Prove that $f$ has a fixed point.
[A. Weinstein, 1]

2.9. Totally geodesic immersion. Let $(M,g)$ be a simply connected positively
curved $m$-manifold and $N\hookrightarrow M$ be a totally geodesic immersion.
Prove that if $\operatorname{dim}N>\tfrac{m}{2}$ then $N$ is embedded. B.
Wilking

2.10. Minimal hypersurfaces. Show that any two compact _minimal hypersurfaces_
in a Riemannian manifold with positive Ricci curvature must intersect.
[T. Frankel]

2.11. Negative curvature vs. symmetry. Let $(M,g)$ be a closed Riemannian
manifold with negative Ricci curvature.

Prove that $(M,g)$ does not admit an isometric $S^{1}$-action. ???

2.12$\displaystyle{}^{{}^{{}_{+}}}$. Positive curvature and symmetry. Let
$(M,g)$ be a positively curved $4$-dimensional closed Riemannian manifold with
an isometric $S^{1}$-action.

Prove that $S^{1}$-action has at most $3$ isolated fixed points.
B. Kleiner???

2.13$\displaystyle{}^{{}^{{}_{+}}}$. Scalar curvature vs. injectivity radius.
Let $(M,g)$ be a closed Riemannian $m$-manifold with scalar curvature
$\mathrm{Sc}_{g}\geqslant m(m-1)/2$ (i.e. bigger then scalar curvature of
$\SS^{m}$). Prove that the injectivity radius of $(M,g)$ is at most $\pi$. ???

2.14. Almost flat manifold. Show that for any $\epsilon>0$ there is
$n=n(\epsilon)$ such that there is a compact $n$-dimensional manifold $M$
which is not a finite factor of a _nil-manifold_ and which admits a Riemannian
metric with diameter $\leqslant 1$ and sectional curvature $|K|<\epsilon$. [G.
Guzhvina]

2.15. Lie group. Show that the space of non-negatively curved left invariant
metrics on a compact Lie group $G$ is contractable. B. Wilking

2.16. Simple geodesic. Let $g$ be a complete Riemannian metric with positive
curvature on $\mathbb{R}^{2}$. Show that there is a two-sided infinite
geodesic in $(\mathbb{R}^{2},g)$ with no self-intersections. [V. Bangert]

2.17♯. Polar points. Let $(M,g)$ be a Riemannian manifold with sectional
curvature $\geqslant 1$. A point $p^{*}\in M$ is called polar to $p\in M$ if
$|px|+|xp^{*}|\leqslant\pi$ for any point $x\in M$. Prove that for any point
in $(M,g)$ there is a polar. [A. Milka]

2.18. Deformation to a product. Let $(M,g)$ be a compact Riemannian manifold
with non-negative sectional curvature. Show that there is a continuous one
parameter family of non-negatively curved metrics $g_{t}$ on $M$, $t\in[0,1]$,
such that a finite Riemannian cover of $(M,g_{1})$ is isometric to a product
of a flat torus and a simply connected manifold. [B. Wilking]

2.19∗. Isometric section. Let $s\colon(M,g)\to(N,h)$ be a Riemannian
submersion. Assume that $g$ is positively curved. Show that $s$ does not admit
an isometric section; i.e. there is no isometry
$\imath\colon(N,h)\hookrightarrow(M,g)$ such that
$s\circ\imath=\operatorname{id}_{N}$.
[G. Perelman]

2.20♯. Minkowski space. Let us denote by $\mathbb{M}^{m}$ the set
$\mathbb{R}^{m}$ equipped with the metric induced by the $\ell^{p}$-norm.
Prove that if $p\not=2$ then $\mathbb{M}^{m}$ can not be a Gromov–Hausdorff
limit of Riemannian $m$-manifolds $(M_{n},g_{n})$ such that
$\operatorname{Ric}_{g_{n}}\geqslant\nobreak C$ for some contant
$C\in\mathbb{R}$.

2.21. An island of scalar curvature. Construct a Riemannian metric $g$ on
$\mathbb{R}^{3}$ which is Euclidean outside of an open bounded set $\Omega$
and scalar curvature of $g$ is negative in $\Omega$. [J. Lohkamp]

2.22$\displaystyle{}^{{}^{{}_{+}}}$. If hemisphere then sphere. Let $M$ is an
$m$-dimensional Riemannian manifold with Ricci curvatur at least $m-1$;
moreover there is a point $p\in M$ such that sectional curvature is exactly
$1$ at all points on distance $\leqslant\tfrac{\pi}{2}$ from $p$. Show that
$M$ has constant sectional curvature. [Hang–Wang]

The problem is still interesting if instead of the first condition one has
that sectional curvature $\geqslant 1$. If instead of first condition one only
has that scalar curvature $\geqslant m(m-1)$, then the question is open, it
was conjectured by Min-Oo in 1995.

##  3 Curvature free

Most of the problems in this section require no special knowledge. Solution of
3 relies on Gromov’s pseudo-holomorphic curves; problem 3 uses Liouville’s
theorem for geodesic flow.

3.1$\displaystyle{}^{{}^{{}_{+}}}$. Minimal foliation. Consider
$\SS^{2}\times\SS^{2}$ equipped with a Riemannian metric $g$ which is
$C^{\infty}$-close to the product metric. Prove that there is a conformally
equivalent metric $\lambda{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}g$ and re-
parametrization of $\SS^{2}\times\SS^{2}$ such that each sphere $\SS^{2}\times
x$ and $y\times\SS^{2}$ forms a _minimal surface_ in
$(\SS^{2}\times\SS^{2},\lambda{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}g)$.

3.2. Smooth doubling. Let $N$ be a Riemannian manifold with boundary which is
isometric to $(M,g)/\SS^{1}$, where $g$ is an $\SS^{1}$-invariant complete
smooth Riemannian metric on $M$. Prove that the _doubling_ of $N$ is a smooth
Riemannian manifold.
[A. Lytchak]

3.3. Loewner’s theorem. Given $\mathbb{R}$Pn equipped with a Riemannian metric
$g$ conformally equivalent to the canonical metric $g_{\text{can}}$ let $\ell$
denote the minimal length of curves in $(\mathbb{R}$P${}^{n},g)$ not homotopic
to zero. Prove that

$vol(\mathbb{R}\text{P}^{n},g)\geqslant
vol(\mathbb{R}\text{P}^{n},g_{\text{can}})(\ell/\pi)^{n}$

and in case of equality $g=c{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}g_{\text{can}}$ for some positive constant $c$. ???

3.4$\displaystyle{}^{{}^{{}_{+}}}$. Convex function vs. finite volume. Let $M$
be a complete Riemannian manifold which admits a non-constant convex function.
Prove that $M$ has infinite volume. [S. Yau]

3.5. Besikovitch inequality. Let $g$ be a Riemannian metric on a
$n$-dimensional cube $Q=(0,1)^{n}$ such that any curve connecting opposite
faces has length $\geqslant 1$. Prove that $\operatorname{vol}(Q,g)\geqslant
1$ and equality holds if and only if $(Q,g)$ is isometric to the interior of
the unit cube. ???

3.6. Mercedes-Benz. Construct a Riemannian metric $g$ on $\SS^{3}$ and
involution $\imath\colon\SS^{3}\to\SS^{3}$ such that
$\operatorname{vol}(\SS^{3},g)$ is arbitrary small and $|x\,\imath(x)|_{g}>1$
for any $x\in\SS^{3}$.
[C. Croke]

Note that for $\SS^{2}$ such thing is not possible.

##  4 Metric geometry.

The necessary definitions can be found in [Burago–Burago–Ivanov]. It is very
hard to do 4 without using Kuratowski embedding. To do problem 4 first do
problem 4; to do this problem you have to know a construction of compact
manifolds of constant negative curvature of given dimension $m$. To do problem
4 you should be familiar with the proof of Nash–Kuiper theorem. Problems 4 and
4 are similar, in both you have to know Rademacher’s theorem on
differentiability of Lipschitz maps.

4.1∘. Noncontracting map. Let $X$ be a compact metric space and $f\colon X\to
X$ be a noncontracting map. Prove that $f$ is an isometry.

4.2$\displaystyle{}^{{}^{{}_{+}}}$. Embedding of a compact. Prove that any
compact metric space is isometric to a subset of a compact _length spaces_.

4.3. Bounded orbit. Let $X$ be a _proper metric space_ and $\imath\colon X\to
X$ is an isometry. Assume that for some $x\in X$, the the orbit
$\imath^{n}(x)$, $n\in\mathbb{Z}$ has a partial limit in $X$. Prove that for
one (and hence for any) $y\in X$, the orbit $\imath^{n}(y)$ is bounded.
[A. Całka]

4.4. Covers of figure eight. Let $(\Phi,d)$ be a “figure eight”; i.e. a metric
space which is obtained by gluing together all four ends of two unit segments.

Prove that any compact _length spaces_ $X$ is a Gromov–Hausdorff limit of a
sequence of metric covers $(\widetilde{\Phi}_{n},\tilde{d}/n)\to(\Phi,d/n)$.
[V. Sahovic]

4.5$\displaystyle{}^{{}^{{}_{+}}}$. Constant curvature is everything. Given
integer $m\geqslant 2$, prove that any compact _length spaces_ $X$ is a
Gromov–Hausdorff limit of a sequence of $m$-dimensional manifolds $M_{n}$ with
curvature $-n^{2}$. [V. Sahovic]

4.6∗. Diameter of m-fold cover. Let $X$ be a _length space_ and $\tilde{X}$ be
a connected $m$-fold cover of $X$ equiped with induced intrinsic metric. Prove
that

$\operatorname{diam}\tilde{X}\leqslant m{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}\operatorname{diam}X.$

A. Nabutovsky, [S. Ivanov]

4.7. 2-sphere is far from a ball. Show that there is no sequence of Riemannian
metrics on $\SS^{2}$ which converge in Gromov–Hausdorff topology to the
standard ball $\bar{B}^{2}\subset\mathbb{R}^{2}$.

4.8. 3-sphere is close to a ball. Construct a sequence of Riemannian metrics
on $\SS^{3}$ which converge in Gromov–Hausdorff topology to the standard ball
$\bar{B}^{3}\subset\mathbb{R}^{3}$.
???

4.9∘. Macrodimension. Let $M$ be a simply connected Riemannian manifold with
the following property: any closed curve can be shrunk to a point in an
$\varepsilon$-neighborhood of itself. Prove that $M$ is 1-dimensional on scale
$10^{10}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}\varepsilon$; i.e. there is a
graph $\Gamma$ and a continuous map $f\colon M\to\Gamma$, such that for any
$x\in\Gamma$ we have diam$(f^{-1}(x))\leqslant 10^{10}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}\varepsilon$. N. Zinoviev

4.10. Anti-collapse. Construct a sequence of Riemannian metric $g_{i}$ on a
2-sphere such that $\mathop{\it vol}g_{i}<1$ such that induced distance
functions $d_{i}\colon\SS^{2}\times\SS^{2}\to\mathbb{R}_{+}$ converge to a
metric $d\colon\SS^{2}\times\SS^{2}\to\mathbb{R}_{+}$ with arbitrary large
Hausdorff dimension.
[Burago–Ivanov–Shoenthal]

4.11∗. No short embedding. Construct a length-metric on $\mathbb{R}^{3}$ which
admits no local _short_ embeddings into $\mathbb{R}^{3}$.
[Burago–Ivanov–Shoenthal]

4.12$\displaystyle{}^{{}^{{}_{+}}}$. Sub-Riemannian sphere. Prove that any
_sub-Riemannian metric_ on the $n$-sphere is isometric to the intrinsic metric
of a hypersurface in $\mathbb{R}^{n+1}$.

4.13$\displaystyle{}^{{}^{{}_{+}}}$. Path isometry. Show that there is no
_path isometry_ $\mathbb{R}^{2}\to\mathbb{R}$.

4.14$\displaystyle{}^{{}^{{}_{+}}}$. Minkowski plane. Let $\mathbb{M}^{2}$ be
a _Minkowski plane_ which is not isometric to the Euclidean plane. Show that
$\mathbb{M}^{2}$ does not admit a _path isometry_ to $\mathbb{R}^{3}$.

4.15. Hyperbolic space. Show that the hyperbolic $3$-space is _quasi-
isometric_ to a subset of product of two hyperbolic planes. ???

4.16. Kirszbraun’s theorem. Let $X\subset\mathbb{R}^{2}$ be an arbitrary
subset and $f\colon X\to\mathbb{R}^{2}$ be a _short map_. Show that $f$ can be
extended as a short map to whole $\mathbb{R}^{2}$; i.e. there is a short map
$\bar{f}\colon\mathbb{R}^{2}\to\mathbb{R}^{2}$ such that its restriction to
$X$ coinsides with $f$.
???

4.17. Hilbert problem. Let $F$ be a convex plane figure. Construct a complete
Finsler metric $d$ on the interior of $F$ such that any line segment in $F$
forms a geodesic of $d$. ???

4.18. Straight geodesics. Let $\rho$ be a length-metric on $\mathbb{R}^{n}$,
which is bi-Lipschitz equivalent to the canonical metric. Assume that any
_geodesic_ $\gamma$ in $(\mathbb{R}^{d},\rho)$ is a linear (i.e. it can be
described as $\gamma(t)=v+w{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}t$ for some
$v,w\in\mathbb{R}^{n}$). Show that $\rho$ is induced by a norm on
$\mathbb{R}^{n}$. ???

##  5 Topology

5.1. Milnor’s disks. Construct two “topologically different” smooth immersions
of the disk into the plane which coincide near the boundary. (Two immersions
$f_{1},f_{2}\colon D\to\mathbb{R}^{2}$ are topologically different if there is
no diffeomorphism $h\colon D\to\nobreak D$ such that $f_{1}=f_{2}\circ h$) [M.
Gromov, 2; ???]

5.2∘. Positive Dehn twist. Let $\Sigma$ be an oriented surface with non empty
boundary. Prove that any composition of _positive Dehn twists_ of $\Sigma$ is
not homotopic to identity _rel_ boundary. R. Matveyev

5.3♯. Function with no critical points. Given $n\geqslant 2$, construct a
smooth function $f$ defined on a neighborhood of closed unit ball $B^{n}$ in
$\mathbb{R}^{n}$ which has no critical points and which can not be presentes
in the form $\ell\circ\varphi$, where $\ell\colon\mathbb{R}^{n}\to\mathbb{R}$
is a linear function and $\varphi\colon B^{n}\to\mathbb{R}^{n}$ is a smooth
embedding. P. Pushkar

5.4. Conic neighborhood. Let $p\in X$ be a point in a topological space $X$.
We say that an open neighborhood $U_{p}$ of $p\in X$ is conic if there is a
homeomorphism from a cone to $U_{p}$ which sends its vertex to $p$. Show that
any two conic neighborhoods of $p$ are homeomorphic to each other. [K. Kwun]

Note that for two cones $\mathop{\rm Cone}(\Sigma_{1})$ and $\mathop{\rm
Cone}(\Sigma_{2})$ might be homeomorphic while $\Sigma_{1}$ and $\Sigma_{2}$
are not.

5.5. Knots in $C^{0}$-topology. Prove that space of $C^{\infty}$-smooth
embeddings $f\colon\SS^{1}\to\nobreak\mathbb{R}^{3}$ is connected in the
$C^{0}$-topology.

5.6∘. Simmetric square. Let $X$ be a connected topological space. Note that
$X{\times}X$ admits natural $\mathbb{Z}_{2}$-action by $(x,y)\mapsto(y,x)$.
Show that fundamental group of $X{\times}X/\mathbb{Z}_{2}$ is commutative. R.
Matveyev

5.7∘. Sierpinski triangle. Find the group of homeomorphisms of Sierpinski
triangle. B. Kliener

5.8. Simple stabilization. Construct two compact subsets
$K_{1},K_{2}\subset\mathbb{R}^{2}$ such that $K_{1}$ is not homeomorphic to
$K_{2}$, but $K_{1}\times[0,1]$ is homeomorphic to $K_{2}\times\nobreak[0,1]$.
???

5.9. Knaster’s circle. Construct a bounded open set in $\mathbb{R}^{2}$ whose
boundary does not contain a _simple curve_. [L. Wayne]

5.10∘. Boundary in $\mathbb{R}$. Construct three disjoined non-empty sets in
$\mathbb{R}$ which have the same boundary.

##  6 Descrete geometry

It is suggested to do Kirszbraun’s theorem (4) before doing problem 6. One of
the solutions of 6 uses mixed volumes. In order to solve problem 6, it is
better to know what is the genus of complex curve of degree $d$. To solve
problem 6 one has to use axiom of choice.

6.1∘. 4-polyhedron. Give an example of a convex $4$-dimensional polyhedron
with $100$ vertices, such that any two vertices are connected by an edge. ???

6.2. Pecewise linear isometry I. Let $P$ be a compact $m$-dimensional
_polyhedral_ _space_. Construct a _pecewise linear isometry_ $f\colon
P\to\mathbb{R}^{m}$. [V. Zalgaller]

6.3$\displaystyle{}^{{}^{{}_{+}}}$. Pecewise linear isometry II. Prove that
any _short map_ to $\mathbb{R}^{2}$ which is defined on a finite subset of
$\mathbb{R}^{2}$ can be extended to a _pecewise linear isometry_
$\mathbb{R}^{2}\to\mathbb{R}^{2}$. [U. Brehm]

6.4. Minimal polyhedron. Consider the class of polyhedral _surfaces_ in
$\mathbb{R}^{7}$ with fixed boundary curve such that each (1) is homeomorphic
to a 2-disc and (2) is glued out $n$ triangles. Let $\Sigma_{n}$ be a surface
of minimal area in this class. Show that $\Sigma_{n}$ is a _saddle surface_.

Note that it is not longer true if $\Sigma$ minimizes area only in the class
of polyhedral surfaces with fixed triangulation.

6.5. Convex triangulation. A triangulation of a convex polygon is called
convex if there is a convex function which is linear on each triangle and
changes the gradient if you come trough any edge of the triangulation.

Find a non-convex triangulation. [Gelfand–Kapranov–Zelevinsky]

6.6. Inscrebed triangulation. Let $Q$ be a unit square and $f\colon
Q\to\mathbb{R}_{>}$ be an arbitrary (not nesessury continuous) function. Prove
that there is a triangulation $\mathcal{T}$ of $Q$ such that each triangle
$\triangle xyz$ in $\mathcal{T}$ is covered by three discs $B_{f(x)}(x)$,
$B_{f(y)}(y)$ and $B_{f(z)}(z)$.

6.7∗. A sphere with one edge. Let $P$ be a finite 3-dimensional simplicial
complex with _spherical polyhedral metric_. Let us denote by $P_{s}$ the
subset of singular222A point is called _regular_ if it has a neighborhood
isometric to an open set of standard sphere; it is called singular point
_otherwise_. points of $P$.

Construct $P$ which is homeomorphic to $\SS^{3}$ and such that $P_{s}$ is
formed by a knotted circle. Show that in such an example the total length of
$P_{s}$ can be arbitrary large and the angle around $P_{s}$ can be made
strictly less than $2\pi$.
[D. Panov, 2]

6.8. Monotonic homotopy. Let $F$ be a finite set and $h_{0},h_{1}\colon
F\to\mathbb{R}^{m}$ be two maps. Consider $\mathbb{R}^{m}$ as a subspace of
$\mathbb{R}^{2m}$. Show that there is a homotopy $h_{t}:F\to\mathbb{R}^{2m}$
from $H_{1}$ to $h_{2}$ such that for any $x,y\in F$ the function
$t\mapsto\nobreak|h_{t}(x)-h_{t}(y)|$ is monotonic. [R. Alexander]

6.9♯. Box in a box. Assume that one rectangular box with sizes $a,b,c$ is
inside another with sizes $A,B,C$. Show that $A+B+C\geqslant a+b+c$. [A. Shen]

6.10∗. Besicovitch’s set. Show that one can cut a unit plane disc by radii
into sectors and then move each sector by a parallel translation on such a way
that its union will have arbitrary small area. [A. Besicovitch]

6.11. Boys and girls in a Lie group. Let $L_{1}$ and $L_{2}$ be two discrete
subgroups of a Lie group $G$, $h$ be a left invariant metric on $G$ and
$\rho_{i}$ be the induced left invariant metric on $L_{i}$. Assume
$L_{i}\backslash G$ are compact and moreover

$\text{vol}(L_{1}\backslash(G,h))=\text{vol}(L_{2}\backslash(G,h)).$

Prove that there is bi-Lipschitz one-to-one mapping (not necessarily a
homomorphism) $f\colon(L_{1},\rho_{1})\to(L_{2},\rho_{2})$. D. Burago

6.12. Universal group. Given a group $\Gamma$, let us denote by $Q(\Gamma)$
its minimal normal subgroup which contains all elements of finite order.

Construct a hyperbolic group, $\Gamma$ such that for any finitely presented
group $G$ there is a subgroup $\Gamma^{\prime}\subset\Gamma$ such that $G$ is
isomorphic to $\Gamma^{\prime}/Q(\Gamma^{\prime})$

6.13∘. Round circles in $\SS^{3}$. Suppose that you have a finite collection
of round circles in round $\SS^{3}$, not necessarily all of the same radius,
such that each pair is linked exactly once (in particular, no two intersect).
Prove that there is an isotopy in the space of such collections of circles so
that afterwards, they are all great circles. Thurston or Conway or Viro or ???

6.14$\displaystyle{}^{{}^{{}_{+}}}$. Harnack’s circles. Prove that a smooth
algebraic curve of degree $d$ in $\mathbb{R}\mathrm{P}^{2}$ consists of at
most $(d^{2}-3d+4)/2$ circles. ???

6.15$\displaystyle{}^{{}^{{}_{+}}}$. Two points on each line. Construct a set
in the Euclidean plane, which intersect each line at exactly 2 points.

##  7 Dictionary

Busemann function. Let $X$ be a metric spaces and $\gamma\colon[0,\infty)\to
X$ is a geodesic ray; i.e. it is a one side infinite _geodesic_ which is
minimizing on each interval. The Busemann function of $\gamma$ is defined by

$b_{\gamma}(p)=\lim_{t\to\infty}(|\gamma(t)\,p|-t).$

From the triangle inequality, it is clear that the limit above is well
defined.

Curvature operator. The Riemannian curvature tensor $R$ can be viewed as an
operator R on bi-vectors defined by

$\langle\mathbf{R}(X\wedge Y),Z\wedge T\rangle=\langle R(X,Y)Z,T\rangle,$

The operator $\mathbf{R}\colon\bigwedge^{2}T\to\bigwedge^{2}T$ is called
_curvature operator_ and it is said to be _positively defined_ if
$\langle\mathbf{R}(\varphi),\varphi\rangle>0$ for all non zero bi-vector
$\varphi\in\bigwedge^{2}T$.

Dehn twist. Let $\Sigma$ be a surface and
$\gamma\colon\mathbb{R}/\mathbb{Z}\to\Sigma$ be noncontractible closed _simple
curve_. Let $U_{\gamma}$ be a neighborhood of $\gamma$ which admits a
homeomorphism $h\colon U_{\gamma}\to\mathbb{R}/\mathbb{Z}\times(0,1)$. Dehn
twist along $\gamma$ is a homeomorphism $f\colon\Sigma\to\Sigma$ which is
identity outside of $U_{\gamma}$ and $h\circ f\circ
h^{-1}\colon(x,y)\mapsto(x+y,y)$.

If $\Sigma$ is orientable, then the Dehn twist described above is called
_positive_ if $h$ is orientation preserving.

Doubling of a manifold $M$ with boundary $\partial M$ is is two copies of
$M_{1},M_{2}$ identified along corresponding points on the boundary $\partial
M_{1},\partial M_{2}$.

Equidistant subsets. Two subsets $A$ and $B$ in a metric space are called
equidistant if $\operatorname{dist}_{A}$ is constant on $B$ and
$\operatorname{dist}_{B}$ is constant on $A$.

Geodesic. Let $X$ be a metric space and $\mathbb{I}$ be a real interval. A
locally isometric immersion $\gamma\colon\mathbb{I}\to X$ is called geodesic.
In other words, $\gamma$ is a geodesic if for any $t_{0}\in\mathbb{I}$ we have
$|\gamma(t)\gamma(t^{\prime})|=|t-t^{\prime}|$ for all
$t,t^{\prime}\in\mathbb{I}$ sufficiently close to $t_{0}$. Note that in our
definition geodesic has unit speed (that is not quite standard).

Length space. A complete metric space $X$ is called length space if the
distance between any pair of points in $X$ is equal to the infimum of lengths
of curves connecting these points.

Minimal surface. Let $\Sigma$ be a $k$-dimensional smooth surface in a
Riemannian manifold $M$ and $T(\Sigma)$ and $N(\Sigma)$ correspondingly
tangent and normal bundle. Let $s\colon T\otimes T\to N$ denotes the second
fundamental form of $\Sigma$. Let $e_{i}$ is an orthonormal basis for $T_{x}$,
set $H_{x}=\sum_{i}s(e_{i},e_{i})\in N_{x}$; it is the mean curvature vector
at $x\in\Sigma$.

We say that $\Sigma$ is _minimal_ if $H\equiv 0$.

Minkowski space — $\mathbb{R}^{m}$ with a metric induced by a norm.

Nil-manifolds form the minimal class of manifolds which includes a point, and
has the following property: the total space of any oriented $\SS^{1}$-bundle
over a nil-manifold is a nil-manifold.

It also can be defined as a factor of a connected nilpotent Lie group by a
lattice.

Path isometry A map $f:X\to Y$ of _length spaces_ $X$ and $Y$ is a path
isometry if for any path $\alpha:[0,1]\to X$, we have

$\operatorname{length}(\alpha)=\operatorname{length}(f\circ\alpha).$

Polyhedral space — a simplicial complex with a metric such that each simplex
is isometric to a simplex in a Euclidean space.

It admits the following generalizations:

spherical (hyperbolic) polyhedral space — a simplicial complex with a metric
such that each simplex is isometric to a simplex in a unit sphere (corresp.
hyperbolic space of constant curvature $-1$).

Polynomial volume growth. A Riemanninan manifold $M$ has polynomial volume
growth if for some (and therefore any) $p\in M$, we have
$\operatorname{vol}B_{r}(p)\leqslant\nobreak C{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}(r^{k}+1)$, where $B_{r}(p)$ is the ball in $M$ and $C$, $k$ are real
constants.

Proper metric space. A metric space $X$ is called _proper_ if any closed
bounded set in $X$ is compact.

Pecewise linear isometry — a piecewise linear map from a polyhedral space
which is isometric on each simplex. More precisely: Let $P$ and $Q$ be
polyhedral spaces, a map $f\colon P\to Q$ is called piecewise linear isometry
if there is a triangulation $\mathcal{T}$ of $P$ such that at any simplex
$\Delta\in\mathcal{T}$ the restriction $f|_{\Delta}$ is globally isometric.

Quasi-isometry. A map $f\colon X\to Y$ is called a quasi-isometry if there is
a constant $C<\infty$ such that $f(X)$is a $C$-net in $Y$ and

$\frac{|xy|}{C}-C\leqslant|f(x)f(y)|\leqslant C{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}|xy|+C$

Note that a quasi-isometry is not assumed to be continuous, for example any
map between compact metric spaces is a quasi-isometry.

Saddle surface. A smooth surface $\Sigma$ in $\mathbb{R}^{3}$ is saddle
(correspondingly strictly saddle) if the product of the principle curvatures
at each point is $\leqslant 0$ (correspondingly $<0$).

It admits the following generalization to non-smooth case and arbitrary
dimension of the ambient space: A surface $\Sigma$ in $\mathbb{R}^{n}$ is
saddle if the restriction $\ell|_{\Sigma}$ of any linear function
$\ell\colon\mathbb{R}^{3}\to\mathbb{R}$ has no strict local minima at interior
points of $\Sigma$.

One can generalize it further to an arbitrary ambient space, using convex
functions instead of linear functions in the above definition.

Short map — a distance non increasing map.

Simple curve — an image of a continuous injective map of a real segment or a
circle.

Sub-Riemannian metric.

Variation of turn. Let $\gamma\colon[a,b]\to\mathbb{R}^{n}$ be a curve. The
variation of turn of $\gamma$ is defined as supremum of sum of ??? angles for
broken lines inscribed in $\gamma$. Namely,

$\sup\left\\{\,\left.{\sum_{i=1}^{n-1}\alpha_{i}}\vphantom{a=t_{0}<t_{1}<\dots<t_{n}=b}\,\right|\,{a=t_{0}<t_{1}<\dots<t_{n}=b}\,\right\\},$

where
$\alpha_{i}=\pi-\measuredangle\gamma(t_{i-1})\gamma(t_{i})\gamma(t_{i+1})$.

## References

  * [Alexander–Hoffman–Osserman] Alexander, H.; Hoffman, D.; Osserman, R. Area estimates for submanifolds of Euclidean space. Symposia Mathematica, Vol. XIV, pp. 445–455. Academic Press, London, 1974.
  * [Alexander–Osserman] Alexander, H.; Osserman, R. Area bounds for various classes of surfaces. Amer. J. Math. 97 (1975), no. 3, 753–769.
  * [R. Alexander] Lipschitzian mappings and total mean curvature of polyhedral surfaces, no. I, Trans. Amer. Math. Soc. 288 (1985), no. 2, 661–678.
  * [S. Alexander] Proc. Amer. Math. Soc. 64 (1977), no. 2, 321–325;
  * [F. Almgren] Optimal isoperimetric inequalities. Indiana Univ. Math. J. 35 (1986), no. 3, 451–547.
  * [B. Andrews] Contraction of convex hypersurfaces in Riemannian spaces. J. Differential Geom. 39 (1994), no. 2, 407–431.
  * [D. Berg] An estimate on the total curvature of a geodesic in Euclidean 3-space-with-boundary. Geom. Dedicata 13 (1982), no. 1, 1–6.
  * [V. Bangert] On the existence of escaping geodesics. Comment. Math. Helv. 56 (1981), no. 1, 59–65.
  * [U. Brehm] Extensions of distance reducing mappings to piecewise congruent mappings on $R^{m}$. J. Geom. 16 (1981), no. 2, 187–193.
  * [Burago–Burago–Ivanov] Burago, D.; Burago, Yu.; Ivanov, S., A course in metric geometry. Graduate Studies in Mathematics, 33. American Mathematical Society, Providence, RI, 2001. xiv+415 pp. ISBN: 0-8218-2129-6
  * [A. Besicovitch] The Kakeya Problem. American Mathematical Monthly 70: 697–706
  * [Burago–Ivanov–Shoenthal] Burago, D.; Ivanov, S.; Shoenthal, D. Two counterexamples in low dimensional length geometry, St.Petersburg Math. J. Vol. 19 (2008), No. 1, Pages 33–43
  * [Böhm–Wilking] Böhm, C.; Wilking, B., Manifolds with positive curvature operators are space forms. International Congress of Mathematicians. Vol. II, 683–690, Eur. Math. Soc., Zürich, 2006.
  * [A. Całka] On conditions under which isometries have bounded orbits. Colloq. Math. 48 (1984), 219–227
  * [C. Croke] Small volume on big $n$-spheres. Proc. Amer. Math. Soc. 136 (2008), no. 2, 715–717
  * [T. Frankel] On the fundamental group of a compact minimal submanifold. Ann. of Math. (2) 83 1966 68–73.
  * [V. Ginzburg] On the existence and non-existence of closed trajectories for some Hamiltonian flows. Math. Z. 223 (1996), no. 3, 397–409.
  * [Gelfand–Kapranov–Zelevinsky] Gelfand, I. M.; Kapranov, M. M.; Zelevinsky, A. V., Discriminants, resultants, and multidimensional determinants, Mathematics: Theory & Applications, Birkhäuser Boston Inc., Boston, MA, 1994, x+523, 0-8176-3660-9.
  * [M. Gromov]
    1. 1.

Gromov’s Appendix in Milman, Vitali D.; Schechtman, Gideon Asymptotic theory
of finite-dimensional normed spaces. Lecture Notes in Mathematics, 1200.
Springer-Verlag, Berlin-New York, 1986. viii+156 pp.

    2. 2.

Partial Differential relations

    3. 3.

Sign and geometric meaning of curvature. Rend. Sem. Mat. Fis. Milano 61
(1991), 9–123 (1994).

    4. 4.

Metric structures for Riemannian and non-Riemannian spaces. Modern Birkhäuser
Classics. Birkhäuser Boston, Inc., Boston, MA, 2007. xx+585 pp. ISBN:
978-0-8176-4582-3; 0-8176-4582-9

  * [G. Guzhvina] Gromov’s pinching constant, arXiv:0804.0201v1
  * [J. Eschenburg] Local convexity and non-negative curvature — Gromov’s proof of the sphere theorem. Invent. Math. 84 (1986), no. 3, 507–522.
  * [Hang–Wang] Hang, F.; Wang, X., A Rigidity Theorem for the Hemisphere arXiv:0711.4595
  * [S. Ivanov] an answer at http://mathoverflow.net/questions/7732
  * [K. Kwun] Uniqueness of the open cone neighborhood, Proc. Araer. Math. Soc. 15 (1964) 476–473
  * [J. Liberman] Geodesic lines on convex surfaces. C. R. (Doklady) Acad. Sci. URSS (N.S.) 32, (1941). 310–313.
  * [J. Lohkamp] Lohkamp, J. ???
  * [A. Lytchak] ???
  * [A. Milka] Multidimensional spaces with polyhedral metric of non-negative curvature. I. (Russian) Ukrain. Geometr. Sb. Vyp. 5–6 1968 103–114.
  * [Micallef–Moore] Micallef, M. J.; Moore, J. D., Minimal two-spheres and the topology of manifolds with positive curvature on totally isotropic two-planes. Ann. of Math. 127 pp.199–227 1988
  * [Ovsienko–Tabachnikov] Ovsienko, V., Tabachnikov, S., Projective differential geometry, old and new: from Schwarzian derivative to cohomology of diffeomorphism groups, Cambridge Univ. Press, 2005.
  * [D. Panov]
    1. 1.

Parabolic curves and gradient mappings. Local and global problems of
singularity theory (Russian). Tr. Mat. Inst. Steklova 221 (1998), 271–288.

    2. 2.

Polyhedral Käler Manifolds. Geometry and Topology. ???

  * [G. Perelman] Proof of the soul conjecture of Cheeger and Gromoll. J. Differential Geom. 40 (1994), no. 1, 209–212.
  * [V. Sahovic] Approximations of Riemannian Manifolds with Linear Curvature Constraints, Dissertation 2009.
  * [A. Shen] ??? Math. Intelligencer 21 (1999), no. 3.
  * [S. Tabachnikov] The tale of a geometric inequality, MASS selecta: teaching and learning advanced undergraduate mathematics, AMS Bookstore, 2003, 257–262
  * [L. Wayne] The Pseudo-Arc, Bol. Soc. Mat. Mexicana Volume 5. (1999), 25–77.
  * [A. Weinstein]
    1. 1.

A fixed point theorem for positively curved manifolds. J. Math. Mech. 18
1968/1969 149–153.

    2. 2.

Positively curved $n$-manifolds in $\mathbb{R}^{n+2}$. J. Differential
Geometry 4 1970 1–4.

  * [B. Wilking] On fundamental groups of manifolds of nonnegative curvature. Differential Geom. Appl. 13 (2000), no. 2, 129–165.
  * [S. Yau] Non-existence of continuous convex functions on certain Riemannian manifolds. Math. Ann. 207 (1974), 269–270.
  * [V. Zalgaller] Isometric embedding of polyhedra. (Russian) Dokl. Akad. Nauk SSSR 123 1958 599–601.


# Marking: Visual Grading with
Highlighting Errors and Annotating Missing Bits

Shashank Sonkar
Rice University
Houston, TX
<EMAIL_ADDRESS>
Naiming Liu11footnotemark: 1
Rice University
Houston, TX
<EMAIL_ADDRESS>
Debshila B. Mallick
Rice University
Houston, TX
<EMAIL_ADDRESS>
Richard G. Baraniuk
Rice University
Houston, TX
<EMAIL_ADDRESS>
Equal contribution.

###### Abstract

In this paper, we introduce “Marking”, a novel grading task that enhances
automated grading systems by performing an in-depth analysis of student
responses and providing students with visual highlights. Unlike traditional
systems that provide binary scores, “marking” identifies and categorizes
segments of the student response as correct, incorrect, or irrelevant and
detects omissions from gold answers. We introduce a new dataset meticulously
curated by Subject Matter Experts specifically for this task. We frame
“Marking” as an extension of the Natural Language Inference (NLI) task, which
is extensively explored in the field of Natural Language Processing. The gold
answer and the student response play the roles of premise and hypothesis in
NLI, respectively. We subsequently train language models to identify
entailment, contradiction, and neutrality from student response, akin to NLI,
and with the added dimension of identifying omissions from gold answers. Our
experimental setup involves the use of transformer models, specifically BERT
and RoBERTa, and an intelligent training step using the e-SNLI dataset. We
present extensive baseline results highlighting the complexity of the
“Marking” task, which sets a clear trajectory for the upcoming study. Our work
not only opens up new avenues for research in AI-powered educational
assessment tools, but also provides a valuable benchmark for the AI in
education community to engage with and improve upon in the future. The code
and dataset can be found at https://github.com/luffycodes/marking.

##  1 Introduction

Recent advancements in Artificial Intelligence (AI) have revolutionized the
approach to automated grading in educational settings, offering scalable
solutions for evaluating student work[1]. Despite these advances, most systems
prioritize binary, right-or-wrong assessments, lacking the subtlety and depth
of feedback that educators typically provide. Recognizing this limitation, our
work introduces a new dimension to automated grading, moving towards a more
detailed form of assessment.

We introduce “Marking”, an innovative task designed to push the capabilities
of automated grading systems beyond their current scope. ‘Marking’ leverages
AI to perform an in-depth analysis of student responses by evaluating them
against a gold standard. The task involves training a language model to
meticulously highlight text segments in the student’s response, categorizing
them as correct, incorrect, or irrelevant. Concurrently, it includes
identifying and flagging content in the gold standard that the student has
omitted. This two-fold assessment approach ensures a rigorous examination of
what students express in their answers and highlights what they fail to
include, offering a detailed and balanced view of their knowledge and
understanding. By doing so, “Marking” provides a more nuanced insight into
student learning, comparable to the detailed feedback typically provided by
experienced educators.

Figure 1: An illustration of the “Marking” task, which is formulated as NLI
where the “gold answer” represents the premise and the “student response” is
the hypothesis. The correct parts of the student response is classified as
entailment, the incorrect parts as contradiction, and irrelevant part as
neutral.

In our “Marking” framework, the evaluation of student responses draws on
principles similar to Natural Language Inference (NLI) [2], a core task in
Natural Language Processing (NLP). Traditionally, in NLI, a hypothesis (the
student response) is tested against a premise (the gold answer) to determine
if it is true (entailment), false (contradiction), or indeterminate (neutral).
In the context of ‘Marking,’ we segment the student response into three parts:
ones that accurately reflect the gold answer is tagged as “entailment”, ones
that misrepresent the gold answer as “contradiction,” and those unrelated to
the question as “neutral.”

To evaluate the effectiveness of our “Marking” framework, we conduct a series
of experiments using transformer models, specifically BERT [3] and RoBERTa
[4], which have shown remarkable performance in various NLP tasks. We treat
the task of “Marking” as a classification problem, where the objective is to
label the words in the student response as correct, incorrect, or irrelevant
based on the gold standard answer. In our experimental setup, we fine-tune the
aforementioned masked language models by adding an inference label classifier
on top, thereby adapting these models to our specific task of marking. Our
experiments investigate the impact of two preprocessing steps, Dual Instance
Pairing (DIP) and stopword removal, and establish baselines for different
label settings. Our results indicate that both DIP and stopword removal
contribute positively to the model performance, which provides valuable
insights into the potential of our “Marking” framework for enhancing automated
grading systems.

In pursuit of realizing such an AI-driven marking system, this paper makes the
following contributions to the field of AI in education:

  1. 1.

We conceptualize and define the task of “Marking,” delineating its scope and
significance as a more granular and informative assessment method than
currently prevalent automated grading approaches.

  2. 2.

We introduce a novel dataset, BioMarking, meticulously curated by biology
Subject Matter Experts, specifically designed to train and evaluate AI models
on the “Marking” task. This dataset also serves as a benchmark for the
community in the upcoming study.

  3. 3.

Through extensive experiments on our dataset, we provide the baseline
performance of our “Marking” task with various settings. This baseline results
highlight the complexity and challenge of “Marking”, thus setting a clear
trajectory for future research.

The rest of the paper begins with a review of related work that contextualizes
our approach within the existing landscape of AI-powered grading tools.
Subsequent sections detail the problem statement, dataset creation,
experimental results, and a discussion that collectively underscores the
potential of “Marking” to transform AI-based educational assessment.

##  2 Related Work

###  2.1 Automated Grading and Feedback

LLMs have made a significant impact in the field of AI-enhanced education [5,
6, 7] in recent years. One notable area where LLMs have been applied is
automated grading. Automated grading systems have gained popularity in recent
years, especially with the advent of natural language processing and
transformer-based models [8] such as BERT [3] and GPT models [9, 10].
Furthermore, the integration of automated feedback generation with grading in
education has also accelerated [11, 12]. Such automated feedback generation
approaches are usually applied to structured questions that require well-
defined answers, such as multiple-choice questions [13], fill-in-the-blank
[14], or programming assignments [15]. However, this automated feedback has
some drawbacks as it increases the complexity of measuring the feedback
quality compared to manual graders [16]. Our novel “Marking” task can resolve
the challenge of feedback generation as it provides immediate and easy-to-
follow feedback to students directly based on their responses, without
requiring extra steps to evaluate the quality of the feedback.

###  2.2 Natural Language Inference

Natural language inference (NLI) is the task of determining whether a
“hypothesis” is true (entailment), false (contradiction), or undetermined
(neutral) given a “premise.” Early research in the field of NLI focused on
handcrafted features and classic machine learning techniques [17, 18]. Models
using these classical methods tend to require extensive feature engineering
and domain knowledge. The integration of transformer models with NLI [19, 3]
has effectively gained considerable attention in recent years, which offers a
significant enhancement over former methods. NLI has broad applications, such
as information retrieval, semantic parsing, and commonsense reasoning [20,
21]. In this paper, we frame the “Marking” approach as NLI tasks, which
perceives the incorrect portion of the student response as “contradiction”
against the gold standard answer, while the correct portion as “entailment”.
This approach characterizes the possibilities for a more dynamic grading
system, where graders can denote parts of students’ responses as either
correct or incorrect, generating detailed and layered feedback.

##  3 Problem Formulation

###  3.1 Problem Statement

Given a dataset $\mathcal{D}=\\{(R_{i},A_{i},G_{i})\\}_{i=1}^{N}$, where
$R_{i}$ represents a student’s response, $A_{i}$ represents the annotations
for the correct, incorrect, and irrelevant portions of $R_{i}$, and $G_{i}$ is
the gold answer for the $i^{th}$ question, the task of “Marking” is to learn a
function $f:(R,G)\rightarrow A$ that predicts the annotations $A$ for a pair
of student response $R$ and gold answer $G$.

The annotation $A_{i}$ is structured as follows:

  * •

$A_{i}^{entail}\subseteq R_{i}$: The subset of the student’s response that
correctly aligns with the information in the gold answer, representing
“entailment”.

  * •

$A_{i}^{contradict}\subseteq R_{i}$: The subset of the student’s response that
incorrectly contradicts the information in the gold answer, representing
“contradiction”.

  * •

$A_{i}^{neutral}\subseteq R_{i}$: The subset of the student’s response that is
irrelevant or tangential to the gold answer, representing “neutral”.

Additionally, the task requires the identification of omissions from gold
answer:

  * •

$A_{i}^{omission}\subseteq G_{i}$: The subset of the gold standard that
contains key concepts or information not present in the student’s response,
representing “omission”.

The objective of “Marking” is to optimize the function $f$ based on a suitable
performance metric, such as F1 score, across the annotations. Formally, the F1
score for each category is defined as:

$F1_{category}=2\times\frac{Precision_{category}\times
Recall_{category}}{Precision_{category}+Recall_{category}}$

where $category$ can be ‘entailment’, ‘contradiction’, ‘neutral’, or
‘omission’, and $Precision$ and $Recall$ are calculated based on the true
positives (TP), false positives (FP), and false negatives (FN) for each
category:

$Precision_{category}=\frac{TP_{category}}{TP_{category}+FP_{category}}$

$Recall_{category}=\frac{TP_{category}}{TP_{category}+FN_{category}}$

The overall performance of the “Marking” system could be evaluated using the
precision, recall and the weighted average of F1 scores across the different
categories, accounting for their relative importance or frequency in the
dataset.

###  3.2 Neutral condition in Omissions

In the standard NLI tasks, the “neutral” category is used to classify
statements (hypotheses) that neither clearly support (entail) nor contradict
the reference statement (premise); they are essentially unrelated or cannot be
verified based on the given information. In the ‘Marking” task, the “neutral”
category is repurposed. It is no longer just a label for content that is
neither right nor wrong in the student’s response. Instead, it is now actively
used to identify key concepts or information that are present in the gold
answer but are missing from the student’s response. In other words, “neutral”
in this context is being used to flag omissions — important elements that the
student did not include in their answer but should have, according to the gold
answer.

By redefining the “neutral” category in this way, the AI system can provide
feedback that is not only about what the student wrote but also about what the
student failed to write. This proactive use of the “neutral” category
effectively transforms it into a diagnostic tool that can provide
comprehensive feedback to students, pointing out gaps in their knowledge or
understanding that need to be addressed.

To summarize, the “neutral” category is being proactively used to enhance the
depth of analysis in grading by identifying and highlighting missing elements
in student responses, thereby offering a more complete and informative
assessment.

##  4 Dataset

We developed the BioMarking dataset to fill in the blanks of the current
“Marking” tasks. Our dataset contains 11 college-level biology questions along
with 318 student responses. In the remainder of this section, we report the
dataset construction process and its key statistics.

###  4.1 Dataset Construction

Question Selection We select 11 biology questions from OpenStax 111OpenStax:
https://openstax.org/ test bank with college-level multiple choice questions.
The tutoring system adopted by OpenStax is that the students first answer the
biology multiple-choice questions as if they were free-response questions
without seeing the choices. Then the system displays the choices and the
students pick the answer from the multiple-choice options. The two-step
question-answering strategy is designed to help the students learn the
materials better. In order to ensure the quality of our dataset, we only
extract the responses of the students who select incorrect multiple choices.
Additionally, we carefully curate the gold answer of each question based on
the correct multiple-choice option, explanation for each choice, and solution
to ascertain its accuracy and comprehensiveness. These answers are then
thoroughly reviewed and approved by experts in the field of biology to ensure
their validity.

Table 1: Examples of the SME annotated dataset (best viewed in color).

Question Gold Standard Answer Student Response Grade Fiber is not really a
nutrient, because it passes through our body undigested. Why can’t fiber be
digested and why is it important to our diet? {Fiber is a type of carbohydrate
that cannot be digested by the enzymes in the human body}. Despite this, it is
an important part of our diet because it can help to bulk up our stools, slow
down the absorption of sugar and cholesterol, and promote the growth of
beneficial bacteria in our gut. Fiber promotes <regular bowel movement by
adding bulk>, and it <regulates the blood glucose consumption rate>. It
<removes excess cholesterol from the body>. It binds to the cholesterol in the
small intestine, then attaches to the cholesterol and prevents the cholesterol
particles from entering the bloodstream Fiber-rich diets also have {a
protective role in reducing the occurrence of colon cancer} 0.5 Fiber is not
really a nutrient, because it passes through our body undigested. Why can’t
fiber be digested and why is it important to our diet? Fiber is a type of
carbohydrate that cannot be digested by the enzymes in human body. Despite
this, it is an important part of our diet because {it can help to bulk up our
stools, slow down the absorption of sugar and cholesterol, and promote the
growth of beneficial bacteria in our gut}. Fiber can’t be digested because it
actually [absorbs water so its important to push waste out of the body] 0

Annotation Process The annotation task was entrusted to a dedicated team of
six Subject Matter Experts (SMEs). All of the SMEs have graduate-level
education in biology. Leveraging their respective depths of understanding and
expertise, they engaged in the meticulous process of marking all the student
answers based on the provided gold answers. Each question is graded by two
SMEs simultaneously. We instruct the SMEs to try to avoid labeling the whole
sentence, but only the phrases that are incorrect. We provide three types of
labels for the SMEs to identify in the student responses:

  * •

Use <> to identify the correct parts and color them in green.

  * •

Use [] to identify the incorrect parts and color them in red.

  * •

Use {} to identify irrelevant parts and color them in yellow.

where the correct/incorrect part refers to the section of student answers that
agree/contradict with what actually present in the provided gold answers. The
definition of irrelevant is the information in the student response unrelated
to the question or the solution, regardless of the correctness.

We also provide a type of label to mark the solutions:

  * •

Use {} to highlight parts in the gold answer that are missing in the student
response and color them in blue.

In addition to marking the sections of the student responses, we also ask the
SMEs to provide a grade from {0, 0.5, 1} to evaluate whether the responses
correctly address the solution, where 0 means the student response is
incorrect, 0.5 means partially correct and 1 means correct response. We also
recommend the SMEs provide some feedback on why the markings are given only
based on incorrect parts, such as a misconception of a fact that leads to
students’ incorrect reasoning or a counterfactual statement, etc. Examples of
the annotated dataset can be found in Table 1.

Annotator training We provide the SME annotators with detailed instructions on
the grading task. To demonstrate their understanding and application of these
instructions, they were first given a practice set of three questions and six
student responses. Upon receiving their completed practice sets, we reviewed
the marked responses for consistency and accuracy. We identify the
discrepancies based on the gold answer created by the expert supervisors and
provide them with feedback. The process was essential to ensure minimal
disagreement between annotators during the actual grading process.

###  4.2 Dataset Statistics

The BioMarking dataset comprises 11 college-level biology questions with 318
distinct student responses. Two SME annotators grade each question, and we
provide both annotated student responses to ensure the completeness of our
dataset.. Each question received an average of 29 student responses, with a
standard deviation of 7.6. It is worth noting that the questions are initially
presented as multiple-choice, with an average accuracy rate of 82.8%. However,
individual questions varied in difficulty, as demonstrated by a minimum
accuracy rate of 55.5% and a maximum of 91.5%.

After the annotation process, we find that 34% of the student short answer
responses are incorrect (assigned a grade 0). 47% of student responses are
partially correct (grade 0.5), and the remaining 19% of answers are completely
accurate (grade 1). Additionally, the average number of words used in the gold
standard answer is 66, while the student responses are more concise, with an
average of 36 words per response.

##  5 Experiments and Baselines

###  5.1 Experimental Setup

The task of “Marking”, as conceptualized in this study, is approached as a
classification problem. Given a student response and a gold standard answer,
our objective is to label each word in the student response as either correct,
incorrect, or irrelevant. To accomplish this, we employ transformer models,
specifically BERT (base/large) [3] and RoBERTa (base/large) [4], which have
demonstrated remarkable performance in various NLP tasks.

####  5.1.1 Classifier Design

Our classifier design is built upon a pre-trained, masked language model with
an inference label classifier head on the top layer. The transformer model,
denoted by $T$, takes a sequence of words $S=\\{w_{0},w_{1},..,w_{n-1}\\}$ as
input and outputs embeddings for each token in the sequence. The embeddings
are given by $T(S)=\\{\mathbf{e}_{0},\mathbf{e}_{1},..,\mathbf{e}_{n-1}\\}$,
where $\mathbf{e}_{i}\in\mathbb{R}^{D}\,,\ (0\leq i<n-1)$ is the token
embedding, and $D$ is its dimension.

The inference classifier uses a weight matrix
$\mathbf{W}\in\mathbb{R}^{D\times|\mathcal{N}|}$ that takes the computed token
embeddings as input, where $\mathcal{N}$ represents the set of all possible
inference classes. The classifier outputs scores for all inference labels for
each token in the sentence. Passing these scores through a softmax
nonlinearity provides probabilities
$\mathbf{p}_{i}\in\mathbb{R}^{|\mathcal{N}|}$ for all inference classes in
$\mathcal{N}$ for a given token $i$ in $S$:

$\mathbf{p}_{i}=\rm{softmax}\Bigl{(}\mathbf{W}\bigl{(}\mathbf{e}_{{i}}\bigl{)}\Bigl{)}.$
(1)

The overall model $\mathcal{M}$ is then given by:

$\mathcal{M}(T,\mathbf{W},S,i)=\mathbf{p}_{i},\,0\leq i<2n.$ (2)

In our experiments, the sequence of input is the gold answer concatenated with
the student response, and the labels are the annotations $A_{i}$ for the
student response. The label set $\mathcal{N}$ consists of five labels:
entailment (0), contradiction (1), neutral (2), none of these (3), and a
special token (<sep>) (4). The labels are assigned to each word in the student
response based on the annotations $A_{i}$. The special token (<sep>) is used
to separate the gold standard answer and the student response in the input
sequence.

####  5.1.2 Training Methodology

The model is trained using the e-SNLI [22] dataset, which provides premise and
hypothesis pairs along with inference labels (entailment, neutral, or
contradiction) and word-level annotations for the hypotheses. This dataset is
particularly suited for our task as it allows the model to learn the nuances
of entailment, contradiction, and neutrality at a word level, which is crucial
for “Marking” task. After training on e-SNLI, we test our model on our marking
dataset, with the objective of providing a baseline for future research.

####  5.1.3 Data Processing and Label Settings

In our experimental setup, we treat the gold answer as the premise and the
student response as the hypothesis. The task is to predict the inference label
of each word in the hypothesis, where the inference label can be either
entailment, neutral, contradiction, or none of these. For a given premise
sentence of arbitrary $n$ words $\\{p_{0},p_{1},..p_{n}\\}$ and a hypothesis
sentence of $m$ words $\\{h_{0},h_{1},..h_{m}\\}$, we separate them by a
special token [sep]. Each word is then assigned a label $l=\\{0,1,2,3,4\\}$,
where [sep] has the label 4, words marked as entailed are 0, words marked as
contradicted are 1, words marked as neutral are 2, and the rest are marked 3.
The task of the transformer is then to predict the labels of each word given
the sentence. This setup allows language models to learn the relationship
between the student response and the gold standard answer at a granular level,
thereby enabling a more detailed and accurate assessment of the student’s
understanding.

In the context of our classifier design, the sequence $S$ is the concatenation
of the premise (gold standard answer) and the hypothesis (student response),
separated by the special token [sep]. Formally,
$S=\\{p_{0},p_{1},...,p_{n},\texttt{[sep]},h_{0},h_{1},...,h_{m}\\}$, where
$p_{i}$ and $h_{i}$ are the words in the premise and hypothesis respectively.

We consider three different label settings (including one described earlier)
to cater to different assessment needs:

  * •

Generic Setting (0-1-2): This is the standard setting where entailment,
contradiction, and neutrality are assigned distinct labels (0, 1, and 2
respectively). The rest of the words are assigned the label 3, and the special
token [sep] is assigned the label 4. This setting allows for a comprehensive
assessment of the student’s response.

  * •

Contradiction-focused Setting (0-1-0): In this setting, we are primarily
interested in identifying the incorrect parts of the student’s response.
Therefore, both entailment and neutrality are assigned the same label (0),
while contradiction is assigned a distinct label (1). The rest of the words
are assigned the label 3, and the special token [sep] is assigned the label 4.
This setting is useful when the focus of the assessment is to identify
misconceptions.

  * •

Error-focused Setting (0-1-1): This setting is designed to identify both
incorrect and irrelevant parts of the student’s response. Therefore,
entailment is assigned the label 0, while both contradiction and neutrality
are assigned the same label (1). The rest of the words are assigned the label
3, and the special token [sep] is assigned the label 4. This setting is useful
when the assessment aims to provide a more stringent evaluation of the
student’s response.

These label settings provide flexibility in the assessment process, allowing
educators to choose the setting that best aligns with their assessment
objectives.

####  5.1.4 Training Parameters

We use cross-entropy loss to train the classifier. The training parameters are
set as follows: learning rate of 2e-5, weight decay of 0.1, warmup ratio of
0.05, Adam optimizer [23], and 3 epochs. These parameters were chosen based on
their performance in previous studies using transformer models for similar NLI
tasks.

####  5.1.5 Special Preprocessing Contributions

Our preprocessing step introduces two key contributions to the experimental
setup, which are designed to optimize the performance of our model and ensure
the consistency of our training and testing procedures.

Dual Instance Pairing (DIP)  In the e-SNLI dataset, each premise-hypothesis
pair is associated with a single label. However, in the “Marking” task, words
in the student response can exhibit multiple labels simultaneously. This
discrepancy between the training and testing conditions could potentially
hinder the performance of our model. To address this issue, we introduce a
novel preprocessing step where we pair two instances belonging to two
different labels as one training sample. We refer to this technique as “Dual
Instance Pairing”.

Mathematically, we denote two instances from the e-SNLI dataset as
$P1\texttt{[sep]}H1$ and $P2\texttt{[sep]}H2$, where $P$ represents the
premise, $H$ represents the hypothesis, and [sep] is the special token
separating the premise and hypothesis. In our preprocessing step, we combine
these two instances into a single training sample as $P1P2\texttt{[sep]}H1H2$.
This preprocessing step allows us to leverage the large e-SNLI dataset for
transfer learning, while ensuring that our training procedure closely aligns
with the conditions of our “Marking” task.

Table 2: Performance of the RoBERTa-large model on the “Marking” task under
different preprocessing conditions and label settings. The results demonstrate
the positive impact of the Dual Instance Pairing (DIP) and stopword removal
preprocessing steps on the model performance.

Label Stopwords Pairs Precision $\uparrow$ Recall $\uparrow$ F1 $\uparrow$
Accuracy $\uparrow$ Ent Con Neu 0 1 2 Yes Yes 0.425 0.421 0.423 0.625 Yes No
0.407 0.382 0.394 0.638 No Yes 0.303 0.368 0.332 0.609 No No 0.332 0.327 0.33
0.613 0 1 0 Yes Yes 0.819 0.429 0.563 0.904 Yes No 0.918 0.399 0.556 0.908 No
Yes 0.557 0.419 0.478 0.885 No No 0.701 0.303 0.423 0.896 0 1 1 Yes Yes 0.747
0.778 0.762 0.704 Yes No 0.718 0.805 0.756 0.708 No Yes 0.702 0.796 0.746
0.690 No No 0.709 0.76 0.734 0.685

Stop Word Removal  Our second preprocessing contribution involves the
exploration of stopword removal. Stopwords are commonly occurring words in a
language (such as “the”, “a”, “in”) that are often filtered out before or
after processing text. While they carry little semantic content, their removal
can sometimes lead to significant changes in the performance of NLP models.

In the context of our marking task, stop words in the student response could
potentially be associated with any of the labels (correct, incorrect,
irrelevant). Therefore, their removal could impact the performance of our
model. In our experiments, we investigate the effect of stop word removal on
the performance of our model, providing valuable insights into the role of
stop words in the “Marking” task.

Table 3: Performance of different models (RoBERTa and BERT, base and large) on
the “Marking” task under three label settings: Generic (0-1-2), Contradiction-
focused (0-1-0), and Error-focused (0-1-1). The table reports the evaluation
scores for each combination of model and label setting. The results highlight
the superior performance of the RoBERTa-large model and the effectiveness of
the Error-focused label setting.

Model Label Precision $\uparrow$ Recall $\uparrow$ F1 $\uparrow$ Accuracy
$\uparrow$ Ent Con Neu Roberta-large 0 1 2 0.425 0.421 0.423 0.625 0 1 0 0.819
0.429 0.563 0.904 0 1 1 0.747 0.778 0.762 0.704 Roberta-base 0 1 2 0.380 0.372
0.376 0.611 0 1 0 0.684 0.43 0.528 0.889 0 1 1 0.721 0.774 0.746 0.699 Bert-
large 0 1 2 0.405 0.402 0.379 0.593 0 1 0 0.577 0.462 0.513 0.873 0 1 1 0.718
0.741 0.729 0.685 Bert-base 0 1 2 0.292 0.384 0.331 0.564 0 1 0 0.531 0.423
0.471 0.863 0 1 1 0.728 0.695 0.711 0.679

###  5.2 Experiments and Discussion

We conduct two main experiments in this study. The first experiment
investigates the impact of our two preprocessing steps: Dual Instance Pairing
(DIP) and stopword removal. The second experiment establishes baselines for
the RoBERTa and Bert models for different label settings. Of the evaluation
metrics provided, we emphasize the F1 score over accuracy due to varying
datapoint numbers in each class as label settings changes. Accuracy is only
included for comprehensiveness.

####  5.2.1 Impact of Preprocessing Steps

In the first experiment, we train the RoBERTa-large model on the e-SNLI
dataset and test it on BioMarking. We evaluate the performance under all three
label settings: Generic, Contradiction-focused, and Error-focused. Our results
in table 2 indicate that both DIP and stopword removal preprocessing steps
contribute positively to the model performance.

For instance, in the Generic setting, the RoBERTa-large model with both DIP
and stopword removal achieves an F1 score of 0.423. When we remove the DIP
preprocessing step, the F1 score drops to 0.394, indicating a decrease in
performance. Similarly, when we remove the stopword removal preprocessing
step, the F1 score decreases to 0.332.

These results suggest that DIP and stopword removal are beneficial
preprocessing steps that enhance the model’s ability to accurately assess
student responses.

####  5.2.2 Performance of Different Models and Label Settings

In the second experiment, we train RoBERTa (base and large) and BERT (base and
large) models on the e-SNLI dataset and test them on BioMarking dataset, as
shown in Table 3. We evaluate the performance of these models under all three
label settings: Generic, Contradiction-focused, and Error-focused.

Finding 1: Our results indicate that the RoBERTa-large model outperforms the
other models in all three settings. For instance, in the Generic setting, the
RoBERTa-large model achieves an F1 score of 0.423, while the RoBERTa-base,
BERT-large, and BERT-base models achieve F1 scores of 0.376, 0.379, and 0.331,
respectively. This finding is consistent with the literature, which generally
reports superior performance of RoBERTa models over BERT models in NLI tasks.

Finding 2: We find that the Error-focused setting yields the best performance
across all models. For the RoBERTa-large model, the F1 scores for the Generic,
Contradiction-focused, and Error-focused settings are 0.423, 0.563, and 0.762,
respectively. These results suggest that the Error-focused setting, which aims
to identify both incorrect and irrelevant parts of the student’s response,
provides a more stringent and comprehensive evaluation of the student’s
understanding.

The superior performance of the Error-focused setting can be attributed to its
unique approach of treating both incorrect and irrelevant parts of the
student’s response as errors. This approach aligns well with educational
objectives, as it encourages students to provide precise and relevant
responses.

Firstly, by marking incorrect parts as errors, the model helps identify and
rectify misconceptions in students’ understanding. This behavior is crucial in
education since unaddressed misconceptions can hinder the learning process.
Secondly, by marking irrelevant parts as errors, the model discourages
students from including extraneous information in their responses. This
behavior is important as it promotes clarity and precision in student
responses, which are critical skills in effective communication.

Therefore, the Error-focused setting not only provides a more stringent
evaluation of the student’s understanding but also promotes critical
educational objectives. This finding underscores the potential of our proposed
label settings in enhancing the effectiveness of automated grading systems in
education.

##  6 Conclusion

In this paper, we introduced the task of “Marking” as a novel approach to
automated grading in educational settings. By leveraging AI, we aimed to move
beyond binary assessments and provide a more nuanced and detailed form of
feedback, similar to what is provided by experienced educators. Our approach
involved evaluating student responses against a gold standard, meticulously
highlighting text segments as correct, incorrect, or irrelevant, and
identifying key concepts or information the student omitted. Our primary
contribution is the introduction of a novel dataset, BioMarking, meticulously
curated by Subject Matter Experts for the “Marking” task. This dataset also
serves as a benchmark for the AI in the education community to engage with and
improve upon. We also presented initial baseline performance using state-of-
the-art NLP techniques, adapted to “Marking” task. While these initial results
are promising, they also highlight the complexity and challenge of the
“Marking”, setting a clear path for future research. Additionally, the task of
“Marking” holds significant potential for enhancing the learning experience
for students. By providing detailed feedback on their responses, it can help
students identify their strengths and weaknesses, gain a deeper understanding
of the subject matter, and guide their learning process. For educators, it
offers a scalable solution for grading, reducing their workload while ensuring
a high level of feedback quality. We believe that our dataset will stimulate
further research in this area, leading to the development of more
sophisticated models capable of providing detailed and nuanced feedback to
students.

## Acknowledgments

This work was supported by NSF grants 1842378, ONR grant N0014-20-1-2534,
AFOSR grant FA9550-22-1-0060, and a Vannevar Bush Faculty Fellowship, ONR
grant N00014-18-1-2047.

## References

  * [1] Salvatore Valenti, Francesca Neri, and Alessandro Cucchiarelli.  An overview of current research on automated essay grading.  Journal of Information Technology Education, 2(1):319–330, 2003.
  * [2] Ido Dagan, Oren Glickman, and Bernardo Magnini.  The pascal recognising textual entailment challenge.  In Machine learning challenges., pages 177–190. Springer, 2006.
  * [3] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  arXiv:1810.04805, 2018.
  * [4] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov.  Roberta: A robustly optimized bert pretraining approach.  arXiv preprint arXiv:1907.11692, 2019.
  * [5] Shashank Sonkar, Naiming Liu, Debshila Mallick, and Richard Baraniuk.  Class: A design framework for building intelligent tutoring systems based on learning science principles.  In Findings of the Association for Computational Linguistics: EMNLP 2023, pages 1941–1961, 2023.
  * [6] Shashank Sonkar, Xinghe Chen, Myco Le, Naiming Liu, Debshila Basu Mallick, and Richard Baraniuk.  Code soliloquies for accurate calculations in large language models.  In Proceedings of the 14th Learning Analytics and Knowledge Conference, pages 828–835, 2024.
  * [7] Shashank Sonkar, Kangqi Ni, Sapana Chaudhary, and Richard G Baraniuk.  Pedagogical alignment of large language models.  arXiv preprint arXiv:2402.05000, 2024.
  * [8] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  Advances in Neural Information Processing Systems, 30, 2017.
  * [9] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  Advances in neural information processing systems, 33:1877–1901, 2020.
  * [10] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al.  Language models are unsupervised multitask learners.  OpenAI blog, 1(8):9, 2019.
  * [11] Anderson Pinheiro Cavalcanti, Rafael Ferreira Leite de Mello, Vitor Rolim, Máverick André, Fred Freitas, and Dragan Gaševic.  An analysis of the use of good feedback practices in online learning courses.  In 2019 IEEE 19th ICALT, volume 2161, pages 153–157. IEEE, 2019.
  * [12] Dadi Ramesh and Suresh Kumar Sanampudi.  An automated essay scoring systems: a systematic literature review.  Artificial Intelligence Review, 55(3):2495–2527, 2022.
  * [13] Sankaran Narayanan, Vamsi Sai Kommuri, Sethu N Subramanian, and Kamal Bijlani.  Question bank calibration using unsupervised learning of assessment performance metrics.  In 2017 International Conference on Advances in Computing, Communications and Informatics (ICACCI), pages 19–25. IEEE, 2017.
  * [14] Archana Sahu and Plaban Kumar Bhowmick.  Feature engineering and ensemble-based approach for improving automatic short-answer grading performance.  IEEE Transactions on Learning Technologies, 13(1):77–90, 2019.
  * [15] Sagar Parihar, Ziyaan Dadachanji, Praveen Kumar Singh, Rajdeep Das, Amey Karkare, and Arnab Bhattacharya.  Automatic grading and feedback using program repair for introductory programming courses.  In Proceedings of the 2017 ACM Conference on Innovation and Technology in Computer Science Education, pages 92–97, 2017.
  * [16] Ghader Kurdi, Jared Leo, Bijan Parsia, Uli Sattler, and Salam Al-Emari.  A systematic review of automatic question generation for educational purposes.  International Journal of Artificial Intelligence in Education, 30:121–204, 2020.
  * [17] Shuohang Wang and Jing Jiang.  Learning natural language inference with lstm.  arXiv preprint arXiv:1512.08849, 2015.
  * [18] Qian Chen, Xiaodan Zhu, Zhenhua Ling, Si Wei, Hui Jiang, and Diana Inkpen.  Enhanced lstm for natural language inference.  arXiv preprint arXiv:1609.06038, 2016.
  * [19] Sawan Kumar and Partha Talukdar.  Nile: Natural language inference with faithful natural language explanations.  arXiv preprint arXiv:2005.12116, 2020.
  * [20] Johan Bos and Katja Markert.  Recognising textual entailment with logical inference.  In Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing, pages 628–635, 2005.
  * [21] Bill MacCartney and Christopher D Manning.  An extended model of natural logic.  In Proceedings of the eight international conference on computational semantics, pages 140–156, 2009.
  * [22] Oana-Maria Camburu, Tim Rocktäschel, Thomas Lukasiewicz, and Phil Blunsom.  e-snli: Natural language inference with natural language explanations.  Advances in Neural Information Processing Systems, 31, 2018.
  * [23] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.


# Efficient Heterogeneous Video Segmentation at the Edge

Jamie Menjay Lin Siargey Pisarchyk Juhyun Lee David Tian Tingbo Hou
Karthik Raveendran Raman Sarokin George Sung Trent Tolley Matthias Grundmann
Google, Mountain View, CA, USA
<EMAIL_ADDRESS>
###### Abstract

We introduce an efficient video segmentation system for resource-limited edge
devices leveraging heterogeneous compute. Specifically, we design network
models by searching across multiple dimensions of specifications for the
neural architectures and operations on top of already light-weight backbones,
targeting commercially available edge inference engines. We further analyze
and optimize the heterogeneous data flows in our systems across the CPU, the
GPU and the NPU. Our approach has empirically factored well into our real-time
AR system, enabling remarkably higher accuracy with quadrupled effective
resolutions, yet at much shorter end-to-end latency, much higher frame rate,
and even lower power consumption on edge platforms.

##  1 Introduction

Video segmentation is a foundational technology powering various computer
vision tasks in business and entertainment use cases, such as video editing in
augmented reality (AR) and background blur and replacement in video
conferencing. Machine learning (ML) inference for high-quality real-time video
segmentation has been a challenging problem particularly on resource-limited
edge devices,  _e.g_. smartphones, with model accuracy, real-time latency, and
power consumption being the key areas for improvement.

We present practical techniques for real-time high-quality video segmentation
at the edge (Figure 1). We describe i) our advances made to common light-
weight network architectures,  _e.g_. MobileNetV3 [18] and EfficientNetLite
[9], and ii) our optimizations to the inference pipelines at the edge, such as
WebGL-based [4] browsers and the NPU inference pipelines on mobile devices.

Figure 1: Real-time video segmentation comparison on Google Pixel 6
smartphone. Left column: Baseline ML inference at $89.5\%$ mIoU [2]
(segmentation quality metric) and 2.03 Watts. Right column: Our ML inference
at $95.1\%$ mIoU and 1.84 Watts.

##  2 Related Work

In the course of neural network-based model development for semantic
segmentation, fully convolutional networks [30] were introduced as an earlier
progress. Numerous follow-up works continued to improve on accuracy and
efficiency, proposing various types of model architectures for segmentation,
such as DeepLab [15], Vortex Pooling [17], PSPNet [36], and HRNet [31, 35].
Another recent line of work targets the problem of image matting for
foreground-background separation, which typically requires either the
availability of a trimap [13, 23, 32] or a pre-captured background image [13,
29, 23]. Dynamic routing [22] was introduced on a generalized view over
various architectures for segmentation. Neural architecture search techniques
have been another line of work in searching for optimized segmentation model
architectures [14, 24, 27], as well as particular types of model improvements
such as transformer-based segmentation models [16, 26].

##  3 Edge Segmentation Model Design

Neural networks running on edge devices are often tailored to the available
computational resources. As a baseline for the segmentation task, we consider
a commonly used fully convolutional U-net architecture based on a MobileNetV3
backbone. Running CPU model inference with an input resolution of $256\times
256$ takes over 50ms on an Intel Celeron N3060 as used in common EDU-targeted
Chromebooks, suggesting that even a low-quality segmentation model is too
expensive to run at real-time on older hardware.

To allow for larger models while still supporting real-time video, we targeted
GPU and NPU that can deliver the required FLOPS [1] or TOPS [3] for the task
of high resolution video segmentation. We analyze the impact of our design
choices including the structure of the encoder and decoder blocks, convolution
types, input resolutions, and width and depth multipliers. Table 1 summarizes
the full ablation study discussed in this section.

Figure 2: Left: The bottleneck block paralleled with a squeeze-and-excitation
operation, which increases GPU latency due in part to the global pooling
operations. Right: Our decoder with the MLP operation, which does not involve
global pooling operations.

While the squeeze-and-excitation blocks[19] in MobileNetV3 are efficient on
the CPU, they increase the latency on GPUs due to the global average pooling
of large tensors. We re-base our architecture on EfficientNetLite where each
encoder block comes with an inverted residual bottleneck and produces an
output tensor that is $1/32$ of the input. The decoder then begins with a
bottleneck block that predicts a coarse segmentation mask as shown in Sec. 4.
In this instance, the global average pooling only needs to operate on a much
smaller tensor and the prediction accuracy benefits from such channel
attention mechanism.

Next, we explore three variants for the decoder design:

  1. 1.

Bilinear Upsampling: Upsamples bilinearly the lower resolution tensor to match
the resolution of the next higher encoder block. This applies a non-linearity
and sum with the tensor from the encoder skip connection.

  2. 2.

Channel Attention: Applies squeeze-and-excitation blocks after upsampling,
followed by a set of $1\times 1$ convolutions and a $3\times 3$ depth-wise
convolution.

  3. 3.

Multilayer Perceptron (MLP): Applies upsampling followed by a sequence of
$1\times 1$ convolutions (MLPs).

We found that $1\times 1$ convolutions make a significant difference to the
accuracy of the model when it comes to finer details, and that the MLP block
serves as a reasonable performance compromise compared to the more expensive
attention block. We also considered the effect of various convolution types on
the network, ranging from standard convolutions to other types of
convolutions. We found while separable convolutions are a natural fit for
modern GPUs, certain hardware such as NPUs can benefit from group convolutions
due to increased chip utilization, enhancing the model expressivity without
increasing the latency. Finally, we performed a hyperparameter search for the
EfficientNetLite family and settled on a multiplier of $1.0$.

Having settled on an architecture, we measured the trade-offs between input
resolution, latency, and accuracy. In each of these cases, we trained the
network using images down-scaled to the specified input resolution and
measured the IoU by down-scaling the ground truth mask to the output
resolution. We found that resolution has the largest impact on the quality of
segmentation, but observed rapidly diminishing returns to increasing the
resolution beyond $640\times 640$.

Ablation Study Parameter Model Inf Time (ms) Model Size (MB) OPs (109) Segment
IOU (%) Pose IOU (%) Convolution Type Depthwise Conv 4.7 1.7 1.5 97.19 89.60
Group Conv* 4.7 7.2 4.8 97.41 90.20 Width Multiplier 1.0* 5.7 9.4 5.3 97.50
91.40 1.5 8.2 21.0 12.1 97.89 92.37 2.0 11.4 37.0 20.6 97.96 92.63 Decoder
Type Bilinear Upsampling 6.5 8.7 7.4 97.65 90.65 Channel Attention 8.2 8.7 7.5
97.75 91.81 Multilayer Perceptron* 6.9 8.7 7.6 97.81 91.80 Image Resolution
256x256 1.6 8.7 1.9 96.94 87.23 384x384 3.1 8.7 4.3 97.51 90.10 512x512* 6.9
8.7 7.6 97.79 91.80 640x640 9.5 8.7 12.0 97.98 92.94

Table 1: Ablation study over edge segmentation model design parameters.
“$\ast$” denotes our final choice in each ablation category.

##  4 E2E Heterogeneous Pipeline Optimization

One of the most important performance criteria of a video segmentation system
for AR applications is the E2E frame rate, which is directly perceivable by
the application users. In this section, we discuss our particular
considerations for ML inference pipeline optimization on web browsers and
mobile devices leveraging the GPU and the NPU, respectively.

GPU for the Web: In browsers, ML frameworks with WebGL support [6, 11, 10]
were our natural choices for hardware-aided ML inference in the browser, as
NPUs currently lack a web standard. Since these implementations ran
significantly slower than native OpenGL [21], we wrote our own WebGL inference
engine that can run at near-native OpenGL performance. In our WebGL
implementation, performance-critical operations,  _e.g_. convolutions,
leverage a modern GPU feature called Multiple Render Targets (MRT) [34], which
allows rendering multiple textures at once, substantially reducing the
overhead of multiple draw calls. For efficient MRT, we separate logical
tensors and physical GPU objects, which have a $1$-to-$1$ correspondence in
other frameworks, and allow tensors to take flexible layouts instead of one
hard-coded layout.

NPU for Mobile Devices: Advanced mobile-optimized video processing frameworks,
such as MediaPipe [25], offer streamlined pipelines primarily targeting image
and video processing along with downstream co-processor interactions and GPU
execution, typically for the tasks of image acquisition, pre-/post-processing,
and rendering. For NPU-accelerated ML inference use cases, the system can
benefit from a processing chain that is tightly coupled with the NPU. A naive
replacement of GPU inference with its NPU counterpart can introduce major
inefficiencies such as indirect inter-processor data flow and latency from
inter-processor synchronization. We streamline the former with Native Hardware
Buffers [5] supporting shared access by both the GPU and the NPU, and reduce
the latter with sync fences in the Android Synchronization API [12].

##  5 Results

Our segmentation models are trained with a standard Jaccard [20, 33] loss on
annotated datasets totaling 250k images that cover a wide range of video
scenarios, from video conferencing to human activities. We evaluate our models
on proprietary datasets,  _e.g_. “video meeting” ($800$ samples) and “full-
body poses” ($947$ samples), and report their mean Intersection over Union
(mIoU) [2], J Mean [28] for region similarity, and F Mean [28] for contour
accuracy.

GPU for the Web: For video segmentation in web apps designed for desktop and
laptop web browsers, we run our EfficientNetLite- and MobileNetV3-based
segmentation models with the baseline CPU (XNNPACK [7] with WebAssembly SIMD
[8]) and with the GPU (our WebGL implementation). Tab. 3 presents the
direction for ML inference in the web browser: (a) to employ the GPU for Web
ML when possible, and (b) to prefer EfficientNetLite over MobileNetV3 for GPU-
accelerated video segmentation on the web. In fact, the latter observation led
to us confidently pursuing EfficientNetLite-based models for the NPU below.

NPU for Mobile Devices: With our model improvement and pipeline optimization
as discussed in Sections 3 and 4, we have achieved significantly higher
accuracy and enabled much shorter inference latency, while reducing power
consumption compared to the baseline. For end-to-end performance evaluation,
we run video segmentation tasks with 512x512 input image resolution and 7.6B
FLOPS in various architectures on a Google Pixel 6 smartphone. As shown in
Tab. 2, the Model System #M4 (Final) with configurations of the NPU, shared
data buffer, and asynchronous GPU-NPU execution along with other choices
indicated in the ablation study of Sec. 3, outperforms all other variants in
both latency and power consumption. Remarkably, our final model #M4 achieves
higher accuracy with a speed up by $81\%$ (at $42.7$ inf/sec) while consuming
only $74\%$ power of #M1 with the baseline ML model as shown in Tab. 2.

##  6 Conclusion

In this paper, we showcase a development for edge-based video segmentation
with our improvements and optimizations of ML model, inference acceleration
and E2E heterogeneous compute pipeline. We visit our deliberations that cover
the scope of model architecture design and system pipeline analysis, targeting
specifically resource-limited edge ML. We present our design and optimization
methodology in the ML model architecture and in the end-to-end ML pipeline
with efficient use of resources and APIs to maximize the throughput for
production-ready, heterogeneous edge ML solutions. We demonstrate that our
methodology enables higher accuracy across various datasets, lower end-to-end
inference latency, and lower power consumption. We expect our methodology to
be beneficial and extensible to a wider range of edge CV/ML systems and real-
time AR/VR applications.

## References

  * [1] FLOPS.  https://en.wikipedia.org/wiki/FLOPS.
  * [2] Intersection over Union.  https://en.wikipedia.org/wiki/Jaccard_index.
  * [3] TOPS.  https://semiengineering.com/tops-memory-throughput-and-inference-efficiency/.
  * [4] WebGL.  https://khronos.org/webgl, 2011.
  * [5] Native Hardware Buffer.  https://developer.android.com/ndk/reference/group/a-hardware-buffer, 2017\.
  * [6] TensorFlow JS.  https://tensorflow.org/js, 2018.
  * [7] XNNPACK.  https://github.com/google/XNNPACK, 2018.
  * [8] WebAssembly Core Specification.  https://www.w3.org/TR/wasm-core-1/, 2019.
  * [9] EfficientNet-lite.  https://github.com/tensorflow/tpu/tree/master/models/official/efficientnet/lite, 2020\.
  * [10] Paddle.js.  https://github.com/PaddlePaddle/Paddle.js, 2020.
  * [11] ONNX Runtime Web.  https://github.com/microsoft/onnxruntime, 2021.
  * [12] Android Synchronization Framework.  https://source.android.com/devices/graphics/sync, 2022.
  * [13] Yagiz Aksoy, Tunç Ozan Aydin, and Marc Pollefeys.  Designing Effective Inter-Pixel Information Flow for Natural Image Matting.  In 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 228–236, 2017.
  * [14] Liang-Chieh Chen, Maxwell D. Collins, Yukun Zhu, George Papandreou, Barret Zoph, Florian Schroff, Hartwig Adam, and Jonathon Shlens.  Searching for Efficient Multi-Scale Architectures for Dense Image Prediction.  In NeurIPS, pages 8713–8724, 2018.
  * [15] Liang-Chieh Chen, George Papandreou, Iasonas Kokkinos, Kevin Murphy, and Alan L. Yuille.  Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 40(4):834–848, 2018.
  * [16] Mingyu Ding, Xiaochen Lian, Linjie Yang, Peng Wang, Xiaojie Jin, Zhiwu Lu, and Ping Luo.  HR-NAS: Searching Efficient High-Resolution Neural Architectures with Lightweight Transformers.  In 2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 2981–2991, 2021.
  * [17] Jiansheng Dong, Jingling Yuan, Lin Li, Xian Zhong, and Weiru Liu.  An efficient semantic segmentation method using pyramid shufflenet V2 with vortex pooling.  In ICTAI, pages 1214–1220. IEEE, 2019.
  * [18] Andrew Howard, Mark Sandler, Bo Chen, Weijun Wang, Liang-Chieh Chen, Mingxing Tan, Grace Chu, Vijay Vasudevan, Yukun Zhu, Ruoming Pang, Hartwig Adam, and Quoc Le.  Searching for MobileNetV3.  In 2019 IEEE/CVF International Conference on Computer Vision (ICCV), pages 1314–1324, 2019.
  * [19] Jie Hu, Li Shen, and Gang Sun.  Squeeze-and-Excitation Networks.  In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 7132–7141, 2018.
  * [20] Paul Jaccard.  The Distribution of the Flora in the Alpine Zone.  New Phytologist, 11(2):37–50, 1912.
  * [21] Juhyun Lee, Nikolay Chirkov, Ekaterina Ignasheva, Yury Pisarchyk, Mogan Shieh, Fabio Riccardi, Raman Sarokin, Andrei Kulik, and Matthias Grundmann.  On-Device Neural Net Inference with Mobile GPUs.  In CVPR Workshop ECV, 2019.
  * [22] Yanwei Li, Lin Song, Yukang Chen, Zeming Li, Xiangyu Zhang, Xingang Wang, and Jian Sun.  Learning Dynamic Routing for Semantic Segmentation.  In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 8550–8559, 2020.
  * [23] Shanchuan Lin, Andrey Ryabtsev, Soumyadip Sengupta, Brian Curless, Steve Seitz, and Ira Kemelmacher-Shlizerman.  Real-Time High-Resolution Background Matting.  In 2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 8758–8767, 2021.
  * [24] Chenxi Liu, Liang-Chieh Chen, Florian Schroff, Hartwig Adam, Wei Hua, Alan L. Yuille, and Li Fei-Fei.  Auto-DeepLab: Hierarchical Neural Architecture Search for Semantic Image Segmentation.  In 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 82–92, 2019.
  * [25] Camillo Lugaresi, Jiuqiang Tang, Hadon Nash, Chris McClanahan, Esha Uboweja, Michael Hays, Fan Zhang, Chuo-Ling Chang, Ming Guang Yong, Juhyun Lee, Wan-Teh Chang, Wei Hua, Manfred Georg, and Matthias Grundmann.  MediaPipe: A Framework for Building Perception Pipelines.  In CVPR Workshop on Computer Vision for AR/VR, 2019.
  * [26] Eslam Mohamed and Ahmad El Sallab.  Spatio-Temporal Multi-Task Learning Transformer for Joint Moving Object Detection and Segmentation.  In 2021 IEEE International Intelligent Transportation Systems Conference (ITSC), pages 1470–1475, 2021.
  * [27] Vladimir Nekrasov, Hao Chen, Chunhua Shen, and Ian Reid.  Fast Neural Architecture Search of Compact Semantic Segmentation Models via Auxiliary Cells.  In 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 9118–9127, 2019.
  * [28] Federico Perazzi, Jordi Pont-Tuset, Brian McWilliams, Luc Van Gool, Markus Gross, and Alexander Sorkine-Hornung.  A Benchmark Dataset and Evaluation Methodology for Video Object Segmentation.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
  * [29] Soumyadip Sengupta, Vivek Jayaram, Brian Curless, Steven M. Seitz, and Ira Kemelmacher-Shlizerman.  Background Matting: The World Is Your Green Screen.  In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 2288–2297, 2020.
  * [30] Evan Shelhamer, Jonathan Long, and Trevor Darrell.  Fully Convolutional Networks for Semantic Segmentation.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 39(4):640–651, 2017.
  * [31] Ke Sun, Bin Xiao, Dong Liu, and Jingdong Wang.  Deep high-resolution representation learning for human pose estimation.  In 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 5686–5696, 2019.
  * [32] Yanan Sun, Guanzhi Wang, Qiao Gu, Chi-Keung Tang, and Yu-Wing Tai.  Deep Video Matting via Spatio-Temporal Alignment and Aggregation.  In 2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 6971–6980, 2021.
  * [33] Taffee T Tanimoto.  Elementary mathematical theory of classification and prediction.  1958\.
  * [34] Wikipedia contributors.  Multiple render targets — Wikipedia, the free encyclopedia.  https://en.wikipedia.org/w/index.php?title=Multiple_Render_Targets&oldid=574813172, 2013\.  [Online; accessed 6-April-2022].
  * [35] Changqian Yu, Bin Xiao, Changxin Gao, Lu Yuan, Lei Zhang, Nong Sang, and Jingdong Wang.  Lite-HRNet: A Lightweight High-Resolution Network.  In 2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 10435–10445, 2021.
  * [36] Hengshuang Zhao, Jianping Shi, Xiaojuan Qi, Xiaogang Wang, and Jiaya Jia.  Pyramid scene parsing network.  In 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 6230–6239, 2017.