# Backward martingale transport maps in pseudo-Euclidean spaces

Dmitry Kramkov111Carnegie Mellon University, Department of Mathematical
Sciences, 5000 Forbes Avenue, Pittsburgh, PA, 15213-3890, USA,
<EMAIL_ADDRESS>The author also has a research position at the University of
Oxford. and Mihai Sîrbu222The University of Texas at Austin, Department of
Mathematics, 2515 Speedway Stop C1200, Austin, Texas 78712,
<EMAIL_ADDRESS>The research of this author was supported in part by
the National Science Foundation under Grant DMS 1908903.

###### Abstract

We consider an optimal transport problem with backward martingale constraint.
The objective function is given by the scalar product of a pseudo-Euclidean
space $S$. We show that the supremum over maps equals the supremum over plans
provided that the law $\nu$ of the input random variable $Y$ is atomless. An
optimal map $X$ exists if $\nu$ does not charge any $c-c$ surface (the graph
of a difference of convex functions) with strictly positive normal vectors in
the sense of the $S$-space. The optimal map $X$ is unique if, in addition,
$\nu$ does not charge $c-c$ surfaces with positive and nearly isotropic normal
vectors in the $S$-space. In the latter case, the joint law of $(X,Y)$ is the
unique optimal backward martingale plan.

Keywords:

martingale optimal transport, pseudo-Euclidean space, optimal maps.

AMS Subject Classification (2010):

60G42, 91B24, 91B52.

##  1 Introduction

Let $S$ be an symmetric invertible $d\times d$ matrix with
$m\in\left\\{{0,1,\dots d}\right\\}$ positive eigenvalues. We interpret the
bilinear form

$S(x,y):=\left\langle x,Sy\right\rangle=\sum_{i,j=1}^{d}x^{i}S_{ij}y^{j},\quad
x,y\in\real{d},$

as the scalar product of a pseudo-Euclidean space, called later the $S$-space.

Let $Y$ be a $d$-dimensional random variable with finite second moments
defined on a probability space $(\Omega,\mathcal{F},\mathbb{P})$. We consider
the Monge-type optimal transport problem:

$\text{maximize~{}}\frac{1}{2}\mathbb{E}\left(S(X,Y)\right)\text{~{}over~{}}X\in\mathcal{X}(Y),$

where $\mathcal{X}(Y)$ is the family of backward martingale _maps_ :

$\mathcal{X}(Y):=\left\\{{{X}\;|\;X\text{~{}is $Y$-measurable
and~{}}\mathbb{E}\left(\left.Y\right\lvert{X}\right)=X}\right\\}.$

The Kantorovich-type relaxation of this problem is to maximize the same
objective over backward martingale _plans_. By possibly enlarging the
probability space, we can represent such plans as the joint laws of $(X,Y)$
for random variables $X$ satisfying the martingale constraint:
$\mathbb{E}\left(\left.Y\right\lvert{X}\right)=X$. The maps have the
additional $Y$-measurability property: $X=f(Y)$ for some Borel function $f$.

The plan problem is easier to study due to the convexity of the optimization
set. As shown in [9] for $d=2$ and the _standard_ matrix
$S=\begin{pmatrix}0&1\\\ 1&0\end{pmatrix}$, and in [7] for the general case,
it has the same value as its dual counterpart:

$\text{minimize~{}}\mathbb{E}\left(\psi_{G}(Y)\right)\text{~{}over~{}}G\in\mathfrak{M}\left({S}\right),$

and both problems have solutions. Here $\mathfrak{M}\left({S}\right)$ is the
family of all maximal monotone sets in the $S$-space and $\psi_{G}$ is the
Fitzpatrick function:

$\psi_{G}(y):=\sup_{x\in G}\left({S(x,y)-\frac{1}{2}S(x,x)}\right),\quad
y\in\real{d}.$

A closed set $G\subset\real{d}$ is called $S$-monotone or $S$-positive if

$S(x-y,x-y)\geq 0,\quad x,y\in G.$

The set $G$ is called maximal $S$-monotone if it is not a strict subset of
another $S$-monotone set. The Fitzpatrick function $\psi_{G}$ plays the role
of the Kantorovich potential from the classical optimal transport.

Any backward martingale map yields a plan, so the supremum over plans is
always greater or equal than the supremum over maps. Theorem 2.1 shows that if
the law of $Y$ is atomless, then these supremums coincide. Its proof is based
on a result of independent interest, the _pointwise uniform_ approximation of
plans by maps in Theorem A.1.

Let $G\in\mathfrak{M}\left({S}\right)$ be _any_ dual minimizer and

$P_{G}(y):=\operatorname*{arg\>min}_{x\in G}S(x-y,x-y),\quad y\in\real{d},$

be the projection multi-function on $G$. Theorem 3.4 and Lemma 3.5 show that
if $P_{G}(Y)$ takes values (almost surely) in convex closed $S$-isotropic
subsets of $G$, then

$X:=\mathbb{E}\left(\left.Y\right\lvert{P_{G}(Y)}\right)$

is an optimal map and the law of $(X,Y)$ is an optimal plan. Here a set $A$ is
called $S$-isotropic if

$S(x-y,x-y)=0,\quad x,y\in A.$

By Theorem 3.8, $P_{G}(Y)$ indeed takes values in convex closed $S$-isotropic
subsets of $G$ provided that

  1. (a)

The law of $Y$ does not charge any $c-c$ surface (the graph of a difference of
convex functions) having _strictly_ $S$-positive $S$-normal vectors $w$ at
every point: $S(w,w)>0$.

If $P_{G}(Y)$ is single-valued, then Theorem 4.1 shows that

$X:=P_{G}(Y)$

is the unique optimal map and the law of $(X,Y)$ is the unique optimal plan.
By Theorem 4.2, $P_{G}(Y)$ is indeed single-valued provided that (a) and
either (b) or (c) hold:

  1. (b)

If $m=1$, ($m$ is the number of positive eigenvalues for $S$), then the law of
$S(w,Y)=\left\langle w,Sy\right\rangle$ is atomless for every nonzero
$S$-isotropic vector $w$: $\left\lvert w\right\rvert>0$ and $S(w,w)=0$.

  2. (c)

If $m>1$, then the law of $Y$ does not charge any $c-c$ surface having
$S$-positive and “almost” $S$-isotropic $S$-normal vectors $w$ at every point.

We point out that (b) is weaker than (c) stated for $m=1$ and that (a)+(b) or
(a)+(c) are the first known conditions for the uniqueness of optimal plans in
the case of general invertible matrix $S$.

For $d=2$ and the standard matrix $S$, Theorems 3.8 and 4.2 improve the
existence and uniqueness criteria from [9], where the covering in (a) is
accomplished with Lipschitz (not $c-c$) surfaces.

The original motivation for the backward martingale transport comes from the
Kyle’s equilibrium for insider trading introduced in [10]. The paper [9]
studies a version of such equilibrium from Rochet and Vila [12] and shows its
connection to the map problem for $d=2$ and the standard matrix $S$. The
current paper sets up the base for the study of a multi-asset version of the
Rochet and Vila’s equilibrium.

Under the conditions of Theorem 4.2, an optimal set $G$ becomes a pseudo-
Euclidean version of a _principal surface_ from Hastie and Stuetzle [5] and
Hastie and Tibshirani [6]: $G$ passes through the “middle” of the law of the
input random variable $Y$ in the sense that $Y$ is uniquely projected on $G$
and its projection $X=P_{G}(Y)$ has the martingale property:
$X=\mathbb{E}\left(\left.Y\right\lvert{X}\right)$. An Euclidean principal
surface is not unique even for the case of a standard Gaussian law and, at
least at this moment, there are no general conditions for its existence. The
pseudo-Euclidean $S$-structure is more tractable. It naturally arises in some
applications (like the study of equilibrium above). Moreover, being
$S$-monotone, the optimal set $G$ is an _Euclidean-type_ subset of the
$S$-space. As a result, $G$ has qualitative properties of an Euclidean
principal surface and can be used as a substitute.

### Notations

The scalar product and the norm in the Euclidean space $\real{d}$ are written
as

$\left\langle x,y\right\rangle:=\sum_{i=1}^{d}x_{i}y_{i},\quad\left\lvert
x\right\rvert:=\sqrt{\left\langle x,x\right\rangle},\quad x,y\in\real{d}.$

For a Borel probability measure $\mu$ on $\real{d}$, a $\mu$-integrable
$m$-dimensional Borel function $f=(f_{1},\dots,f_{m})$, and an $n$-dimensional
Borel function $g=(g_{1},\dots,g_{n})$, the notation $\mu(f|g)$ stands for the
$m$-dimensional vector of conditional expectations of $f_{i}$ given $g$ under
$\mu$:

$\mu(f|g)=(\mu(f_{1}|g_{1},\dots,g_{n}),\dots,\mu(f_{m}|g_{1},\dots,g_{n})).$

In particular, we write $\mu(f)$ for the vector of expected values:

$\mu(f)=\int fd\mu=(\int f_{1}d\mu,\dots,\int
f_{m}d\mu)=(\mu(f_{1}),\dots,\mu(f_{m})).$

We write $\operatorname{supp}{\mu}$ for the support of $\mu$, the smallest
closed set of full measure.

Similarly, if $(\Omega,\mathcal{F},\mathbb{P})$ is a probability space, $X$
and $Y$ are respectively, $m$\- and $n$-dimensional random variables, and $Y$
is integrable, then

$\mathbb{E}\left(\left.Y\right\lvert{X}\right)=\left({\mathbb{E}\left(\left.Y_{1}\right\lvert{X_{1},\dots,X_{m}}\right),\dots,\mathbb{E}\left(\left.Y_{n}\right\lvert{X_{1},\dots,X_{m}}\right)}\right),$

denotes the $n$-dimensional vector of conditional expectations of $Y_{i}$ with
respect to $X$. All relations between random variables are understood in the
$\mathbb{P}-a.s.$ sense. In particular, $X$ is $Y$-measurable if and only if
$X=f(Y)$ ($\mathbb{P}-a.s.$) for a Borel function
$f:\;\real{m}\rightarrow\real{d}$.

For a closed (equivalently, lower-semicontinuous) convex function
$f:\;\real{d}\rightarrow\mathbb{R}\cup\left\\{{+\infty}\right\\}$, we denote
by $\partial f$ its subdifferential and by $f^{*}$ its convex conjugate:

$\displaystyle\partial f(x)$
$\displaystyle=\left\\{{{z\in\real{d}}\;|\;f(y)-f(x)\geq\left\langle
z,y-x\right\rangle,\;y\in\real{d}}\right\\},\quad x\in\real{d},$
$\displaystyle f^{*}(y)$
$\displaystyle:=\sup_{x\in\real{d}}\left({\left\langle
y,x\right\rangle-f(x)}\right),\quad y\in\real{d}.$

The domains of $f$ and of $\partial f$ are defined as

$\displaystyle\operatorname{dom}f$
$\displaystyle:=\left\\{{{x\in\real{d}}\;|\;f(x)<\infty}\right\\},$
$\displaystyle\operatorname{dom}\partial f$
$\displaystyle:=\left\\{{{x\in\operatorname{dom}f}\;|\;\partial
f(x)\not=\emptyset}\right\\}.$

##  2 Equality of values of plan and map problems

We denote by $\mathcal{S}^{d}_{m}$ the family of symmetric $d\times
d$-matrices of full rank with $m\in\left\\{{0,1,\dots,d}\right\\}$ positive
eigenvalues. For $S\in\mathcal{S}^{d}_{m}$, the bilinear form

$S(x,y):=\left\langle x,Sy\right\rangle=\sum_{i,j=1}^{d}x^{i}S_{ij}y^{j},\quad
x,y\in\real{d},$

defines the scalar product on a pseudo-Euclidean space $\real{d}_{m}$ with
dimension $d$ and index $m$, which we call the $S$-space. The quadratic form
$S(x,x)$ is called the _scalar square_ ; its value may be negative.

Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space and $Y$ be a
$d$-dimensional random variable with finite second moment:
$Y\in{\mathcal{L}_{2}\left({\real{d}}\right)}$. Our goal is to

$\text{maximize}\quad\frac{1}{2}\mathbb{E}\left(S(X,Y)\right)\quad\text{over}\quad
X\in\mathcal{X}(Y),$ (1)

where

$\mathcal{X}(Y):=\left\\{{{X\in{\mathcal{L}_{2}\left({\real{d}}\right)}}\;|\;X\text{~{}is
$Y$-measurable
and~{}}\mathbb{E}\left(\left.Y\right\lvert{X}\right)=X}\right\\}.$

The Kantorovich-type relaxation of the optimal _map_ problem (1) is the
optimal _plan_ problem:

$\text{maximize}\quad\frac{1}{2}\int
S(x,y)d\gamma\quad\text{over}\quad\gamma\in\Gamma(\nu),$ (2)

where $\nu:=\operatorname{{Law}}(Y)$ belongs to
$\mathcal{P}_{2}\left({\real{d}}\right)$, the family of Borel probability
measures on $\real{d}$ with finite second moments, and

$\Gamma(\nu):=\left\\{{{\gamma\in\mathcal{P}_{2}\left({\real{2d}}\right)}\;|\;\gamma(\real{d},dy)=\nu(dy)\text{~{}and~{}}\gamma(y|x)=x}\right\\}.$

Theorem 2.5 in [7] shows that an optimal plan for (2) always exists. Clearly,
$\operatorname{{Law}}(X,Y)\in\Gamma(\nu)$ for every $X\in\mathcal{X}(Y)$.
Thus,

$\sup_{X\in\mathcal{X}(Y)}\mathbb{E}\left(S(X,Y)\right)\leq\max_{\gamma\in\Gamma(\nu)}\int
S(x,y)d\gamma.$

Notice that the inequality may be strict and an optimal map may not exist, as
Examples 5.2 and 5.3 in [9] show.

The following theorem is similar to that of Pratelli [11] obtained for the
classical unconstrained optimal transport problem. For $d=2$ and the
_standard_ $S=\begin{pmatrix}0&1\\\ 1&0\end{pmatrix}\in\mathcal{S}^{2}_{1}$,
see Example 3.1 below, it has been proved in [9].

######  Theorem 2.1.

Let $S\in\mathcal{S}^{d}_{m}$, $Y\in{\mathcal{L}_{2}\left({\real{d}}\right)}$,
and suppose that $\nu:=\operatorname{{Law}}(Y)$ is atomless. Then the problems
(1) and (2) have the same values:

$\sup_{X\in\mathcal{X}(Y)}\mathbb{E}\left(S(X,Y)\right)=\max_{\gamma\in\Gamma(\nu)}\int
S(x,y)d\gamma.$

###### Proof.

Let $\gamma$ be an optimal plan for (2). By extending, if necessary, the
underlying probability space we can assume that
$\gamma=\operatorname{{Law}}(X,Y)$ for some random variable $X$. As
$\gamma(y|x)=x$, we have that
$X=\mathbb{E}\left(\left.Y\right\lvert{X}\right)$.

Let $\epsilon>0$. Theorem A.1 yields a $d$-dimensional random variable
$Z=Z(\epsilon)$ such that

$\operatorname{{Law}}(Z)=\operatorname{{Law}}(Y),\quad\left\lvert
Z-Y\right\rvert\leq\epsilon,\quad X\text{~{}is $Z$-measurable}.$

Since $X$ is $Z$-measurable, the conditional expectation
$V:=\mathbb{E}\left(\left.Z\right\lvert{X}\right)$ is $Z$-measurable as well.
Thus, there is a Borel function $f:\;\real{d}\rightarrow\real{d}$ such that
$V=f(Z)$. Since $Y$ and $Z$ have identical laws,

$U:=f(Y)=\mathbb{E}\left(\left.Y\right\lvert{U}\right).$

For all $x,y,v,z$ in $\real{d}$, we have that

$\displaystyle\left\lvert S(x,y)-S(v,z)\right\rvert$
$\displaystyle\leq\left\lvert S(x-v,y)\right\rvert+\left\lvert
S(v,z-y)\right\rvert$ $\displaystyle\leq\lVert S\rVert(\left\lvert
y\right\rvert\left\lvert x-v\right\rvert+\left\lvert v\right\rvert\left\lvert
z-y\right\rvert),$

where $\lVert S\rVert:=\max_{\left\lvert x\right\rvert=1}\left\lvert
Sx\right\rvert$, the norm of $S$. Since $\left\lvert
Z-Y\right\rvert\leq\epsilon$ and

$\displaystyle\left\lvert V-X\right\rvert$
$\displaystyle=\left\lvert\mathbb{E}\left(\left.Z-Y\right\lvert{X}\right)\right\rvert\leq\mathbb{E}\left(\left.\left\lvert
Z-Y\right\rvert\right\lvert{X}\right)\leq\epsilon,$

we have that

$\displaystyle\left\lvert S(X,Y)-S(V,Z)\right\rvert\leq\epsilon\lVert
S\rVert(\left\lvert Y\right\rvert+\left\lvert V\right\rvert).$

As $\mathbb{E}\left(\left\lvert
V\right\rvert\right)=\mathbb{E}\left(\left\lvert\mathbb{E}\left(Z|X\right)\right\rvert\right)\leq\mathbb{E}\left(\left\lvert
Z\right\rvert\right)\leq\mathbb{E}\left(\left\lvert
Y\right\rvert\right)+\epsilon$ and
$\operatorname{{Law}}(U,Y)=\operatorname{{Law}}(V,Z)$, we obtain that

$\int
S(x,y)d\gamma=\mathbb{E}\left(S(X,Y)\right)\leq\mathbb{E}\left(S(U,Y)\right)+\epsilon\lVert
S\rVert(2\mathbb{E}\left(\left\lvert Y\right\rvert\right)+\epsilon).$

The result follows, because $U\in\mathcal{X}(Y)$ and $\epsilon$ is any
positive number. ∎

##  3 Existence of optimal maps

Let $S\in\mathcal{S}^{d}_{m}$. A set $G\subset\real{d}$ is called
$S$-_monotone_ or $S$-_positive_ if

$S(x-y,x-y)\geq 0,\quad x,y\in G.$

An $S$-monotone set $G$ is called _maximal_ if it is not a strict subset of an
$S$-monotone set.

######  Example 3.1 (Standard form).

If $d=2m$ and

$S(x,y)=\sum_{i=1}^{m}\left({x^{i}y^{m+i}+x^{m+i}y^{i}}\right),\quad
x,y\in\real{2m},$

then $S\in\mathcal{S}^{2m}_{m}$ and the $S$-monotonicity means the standard
monotonicity in $\real{2m}=\real{m}\times\real{m}$.

######  Example 3.2 (Canonical form).

If $S$ is the _canonical_ quadratic form in $\mathcal{S}^{d}_{m}$:

$S(x,y)=\sum_{i=1}^{m}x^{i}y^{i}-\sum_{i=m+1}^{d}x^{i}y^{i},\quad
x,y\in\real{d},$

then a closed set $G$ is $S$-monotone if and only if

$G=\operatorname{graph}{f}:=\left\\{{{(u,f(u))}\;|\;u\in D}\right\\},$

where $D$ is a closed set in $\real{m}$ and $f:\;D\rightarrow\real{d-m}$ is a
$1$-Lipschitz function:

$\left\lvert f(u)-f(v)\right\rvert\leq\left\lvert u-v\right\rvert,\quad u,v\in
D.$

In view of the Kirszbraun Theorem, [4, 2.10.43], $G$ is maximal $S$-monotone
if and only if $D=\real{m}$.

It has been shown in [7, Theorem 2.5], that a dual problem to (2) is to

$\text{minimize}\quad\mathbb{E}\left(\psi_{G}(Y)\right)=\int\psi_{G}(y)d\nu\quad\text{over}\quad
G\in\mathfrak{M}\left({S}\right),$ (3)

where $\mathfrak{M}\left({S}\right)$ is the family of all maximal $S$-monotone
sets and

$\psi_{G}(y):=\sup_{x\in G}\left({S(x,y)-\frac{1}{2}S(x,x)}\right),\quad
y\in\real{d},$

is a _Fitzpatrick_ function in the $S$-space. We refer the reader to [7,
Appendix A] for the basic facts about the Fitzpatrick functions in the
$S$-space. Theorem 2.5 in [7] shows that an optimal set for (3) always exists
and

$\max_{\gamma\in\Gamma(\nu)}\frac{1}{2}\int
S(x,y)d\gamma=\min_{G\in\mathfrak{M}\left({S}\right)}\int\psi_{G}(y)d\nu.$

Let $G\in\mathfrak{M}\left({\real{d}}\right)$. We denote by $P_{G}$ the
projection on $G$ in the $S$-space:

$P_{G}(y):=\operatorname*{arg\>min}_{x\in G}S(x-y,x-y),\quad y\in\real{d}.$

We write $P_{G}^{-1}(A)$ for the pre-image of a set $A\subset\real{d}$ under
$P_{G}$:

$P_{G}^{-1}(A):=\left\\{{{y\in\real{d}}\;|\;P_{G}(y)\cap
A\not=\emptyset}\right\\}.$

Theorem A.4 in [7] states that

$\displaystyle P_{G}(y)$ $\displaystyle=\left\\{{{x\in
G}\;|\;Sx\in\partial\psi_{G}(y)}\right\\},\quad y\in\real{d},$ $\displaystyle
P_{G}^{-1}(x)$
$\displaystyle:=P_{G}^{-1}(\left\\{{x}\right\\})=\partial\psi_{G}^{*}(Sx),\quad
x\in G,$ $\displaystyle\operatorname{dom}{P_{G}}$
$\displaystyle:=P_{G}^{-1}(\real{d})=\operatorname{dom}{\partial\psi_{G}}:=\left\\{{{x\in\real{d}}\;|\;\partial\psi_{G}(x)\not=\emptyset}\right\\},$

where $\partial\psi_{G}$ and $\partial\psi^{*}_{G}$ are the subdifferentials
of $\psi_{G}$ and its convex conjugate $\psi^{*}_{G}$. In particular,
$P_{G}^{-1}(x)$ is a closed convex set for every $x\in G$.

For $x\in G$, we denote by $Q_{G}(x)$ the largest closed convex subset of
$P^{-1}_{G}(x)$ whose relative interior contains $x$. Lemma 2.12 in [7] shows
that such a set exists, and $y\in Q_{G}(x)$ if and only if there are
$z\in\real{d}$ and $t\in(0,1)$ such that

$x=ty+(1-t)z\quad\text{and}\quad x\in P_{G}(y)\cap P_{G}(z).$

The following result is an immediate corollary of Theorem 2.5 in [7]. We
remind the reader that all relations between random variables (as in items (b)
and (c) below) are understood in the $\mathbb{P}-a.s.$ sense.

######  Theorem 3.3.

Let $S\in\mathcal{S}^{d}_{m}$,
$X,Y\in{\mathcal{L}_{2}\left({\real{d}}\right)}$,
$X=\mathbb{E}\left(Y|X\right)$, $\nu=\operatorname{{Law}}(Y)$, and
$G\in\mathfrak{M}\left({S}\right)$. The following conditions are equivalent:

  1. (a)

The law of $(X,Y)$ is an optimal plan for (2) and $G$ is an optimal set for
(3).

  2. (b)

(Backward evolution) $X\in P_{G}(Y)$.

  3. (c)

(Forward evolution) $X\in G$ and $Y\in Q_{G}(X)$.

Under these conditions, $X$ is an optimal map for (1) if and only if it is
$Y$-measurable.

###### Proof.

Let $\gamma:=\operatorname{{Law}}(X,Y)$. We recall that
$\operatorname{supp}{\gamma}$ stands for the support of $\gamma$. By [7,
Theorem 2.5], the optimality of $\gamma$ for (2) and $G$ for (3) is equivalent
to each of the following conditions:

  1. (b’)

$x\in P_{G}(y)$ for any $(x,y)\in\operatorname{supp}{\gamma}$.

  2. (c’)

$x\in G$ and $y\in Q_{G}(x)$, $\gamma-a.s.$.

Clearly, (c) is equivalent to (c’). Condition (b’) can be equivalently written
as

$\displaystyle\operatorname{supp}{\gamma}\subset F:=\left\\{{{(x,y)}\;|\;x\in
P_{G}(y),y\in\operatorname{dom}{P_{G}}}\right\\}.$

Observe now that if $y_{n}\to y$ and $P_{G}(y_{n})\ni x_{n}\to x$, then $x\in
P_{G}(y)$. In other words, $F$ is a closed set. Thus,
$\operatorname{supp}{\gamma}\subset F$ if and only if $\gamma(F)=1$, which is
exactly (b).

The last assertion of the theorem is straightforward. ∎

Let $G\in\mathfrak{M}\left({S}\right)$. Following [2, p. 59], we denote by
$\sigma\left({P_{G}}\right)$ the $\sigma$-algebra generated by the pre-images
$P_{G}^{-1}(U)$ of open sets $U\subset\real{d}$. In particular,
$\sigma(P_{G})$ contains $\operatorname{dom}{P_{G}}=P_{G}^{-1}(\real{d})$.
Lemma 3.6 shows that every $A\in\sigma(P_{G})$ is a Borel set in $\real{d}$.

If $Y$ is a $d$-dimensional random variable, then $\sigma(P_{G}(Y))$ stands
for the $\sigma$-algebra of all the events $\left\\{{Y\in A}\right\\}$,
$A\in\sigma(P_{G})$, or, equivalently, generated by the events $\left\\{{Y\in
P_{G}^{-1}(U)}\right\\}=\left\\{{P_{G}(Y)\cap U\not=\emptyset}\right\\}$,
where $U$ is any open set in $\real{d}$. Clearly, $\sigma(P_{G}(Y))$ is a
sub-$\sigma$-algebra of $\sigma(Y)$. In particular, a conditional expectation
with respect to $\sigma(P_{G}(Y))$ is a $Y$-measurable random variable.

A point $y\in\operatorname{dom}{P_{G}}$ is called _singular_ , if $P_{G}(y)$
is not a singleton. We decompose the set of singular points of $P_{G}$ as

$\displaystyle\Sigma(P_{G})$
$\displaystyle:=\left\\{{{x\in\operatorname{dom}{P_{G}}}\;|\;P_{G}(x)\text{~{}is
not a point}}\right\\}=\Sigma_{0}(P_{G})\cup\Sigma_{1}(P_{G}),$
$\displaystyle\Sigma_{0}(P_{G})$
$\displaystyle:=\left\\{{{x\in\Sigma(P_{G})}\;|\;S(y_{1}-y_{2},y_{1}-y_{2})=0\text{~{}for
\emph{all}~{}}y_{1},y_{2}\in P_{G}(x)}\right\\},$
$\displaystyle\Sigma_{1}(P_{G})$
$\displaystyle:=\left\\{{{x\in\Sigma(P_{G})}\;|\;S(y_{1}-y_{2},y_{1}-y_{2})>0\text{~{}for
\emph{some}~{}}y_{1},y_{2}\in P_{G}(x)}\right\\}.$

Clearly, $\Sigma_{0}(P_{G})\cap\Sigma_{1}(P_{G})=\emptyset$. Lemma 3.5
provides an equivalent description of $\Sigma_{0}(P_{G})$. Lemma 3.6 shows
that the singular sets $\Sigma_{0}(P_{G})$ and $\Sigma_{1}(P_{G})$ belong to
$\sigma(P_{G})$. In particular, they are Borel sets in $\real{d}$.

We recall that an optimal set $G\in\mathfrak{M}\left({S}\right)$ for the dual
problem (3) always exists, [7, Theorem 2.5].

######  Theorem 3.4.

Let $S\in\mathcal{S}^{d}_{m}$, $Y\in\mathcal{L}_{2}(\real{d})$, and denote
$\nu:=\operatorname{{Law}}(Y)$. Let $G\in\mathfrak{M}\left({S}\right)$ be an
optimal set for (3) and assume that $Y\not\in\Sigma_{1}(P_{G})$, i.e.
$\nu\left({\Sigma_{1}(P_{G})}\right)=0$. Then

$X:=\mathbb{E}\left(\left.Y\right\lvert{P_{G}(Y)}\right):=\mathbb{E}\left(\left.Y\right\lvert{\sigma(P_{G}(Y))}\right)$

is an optimal map for (1) and the law of $(X,Y)$ is an optimal plan for (2).

The direct use of Theorem 3.4 requires the knowledge of a dual minimizer $G$.
An obvious sufficient condition is to assume that $Y\not\in\Sigma_{1}(P_{G})$
for _every_ $G\in\mathfrak{M}\left({\real{d}}\right)$ such that
$\mathbb{E}\left(\psi_{G}(Y)\right)<\infty$. A stronger, but more convenient
sufficient condition is stated in Theorem 3.8.

The proof of Theorem 3.4 relies on some lemmas.

######  Lemma 3.5.

Let $G\in\mathfrak{M}\left({S}\right)$ and $y\in\operatorname{dom}{P_{G}}$.
Then $P_{G}(y)$ is a convex set if and only if

$S(u-v,u-v)=0,\quad u,v\in P_{G}(y).$

In other words, the singular set $\Sigma_{0}(P_{G})$ admits the equivalent
description:

$\displaystyle\Sigma_{0}(P_{G})=\left\\{{{y\in\Sigma(P_{G})}\;|\;P_{G}(y)\text{~{}is
a convex set}}\right\\}.$

###### Proof.

Let $u,v\in P_{G}(y)$ and denote $w=\frac{1}{2}(u+v)$. We have that

$\displaystyle\psi_{G}(y)$
$\displaystyle=S(y,u)-\frac{1}{2}S(u,u)=S(y,v)-\frac{1}{2}S(v,v)$
$\displaystyle=S(y,w)-\frac{1}{2}S(w,w)-\frac{1}{4}\left({S(u,u)+S(v,v)-2S(w,w)}\right)$
$\displaystyle=S(y,w)-\frac{1}{2}S(w,w)-\frac{1}{8}S(u-v,u-v).$

In particular,

$\psi_{G}(y)=S(y,w)-\frac{1}{2}S(w,w)\iff S(u-v,u-v)=0.$

If $P_{G}(y)$ is convex, then $w\in P_{G}(y)$, which implies that
$S(u-v,u-v)=0$.

Assume now that $S(u-v,u-v)=0$. Direct computations show that

$S(x-w,x-w)=\frac{1}{2}\left({S(x-u,x-u)+S(x-v,x-v)}\right)\geq 0,\quad x\in
G.$

As $G\in\mathfrak{M}\left({S}\right)$, we obtain that $w\in G$, and,
necessarily, $w\in P_{G}(y)$. ∎

######  Lemma 3.6.

Let $S\in\mathcal{S}^{d}_{m}$ and $G\in\mathfrak{M}\left({S}\right)$. Then

  1. (a)

Every $A\in\sigma(P_{G})$ is a Borel set in $\real{d}$.

  2. (b)

For every $s\in\real{d}$ the function

$g_{s}(y):=\sup_{x\in P_{G}(y)}\left\langle
s,x\right\rangle\in\mathbb{R}\cup\left\\{{-\infty}\right\\}\cup\left\\{{+\infty}\right\\},\quad
y\in\real{d},$

is $\sigma(P_{G})$-measurable, where we used the usual convention that $\sup$
over an empty set is $-\infty$.

  3. (c)

The singular sets $\Sigma_{0}(P_{G})$ and $\Sigma_{1}(P_{G})$ belong to
$\sigma(P_{G})$.

###### Proof.

(a): We first show that the inverse image of a compact set $K$ by $P_{G}$ is
closed. Since

$P^{-1}_{G}(K)=\left\\{{{y\in\real{d}}\;|\;P_{G}(y)\cap
K\not=\emptyset}\right\\}=P^{-1}_{G}(K\cap G),$

we can assume that $K$ is a subset of $G$. The Fitzpatrick-type function

$\displaystyle\psi_{K}(y):=\sup_{x\in
K}\left({S(x,y)-\frac{1}{2}S(x,x)}\right),\quad y\in\real{d}.$

is convex and finite, therefore continuous. In addition, $K\subset G$ ensures
that $\psi_{K}\leq\psi_{G}$. We observe that

$P^{-1}_{G}(K)=\left\\{{{y\in\real{d}}\;|\;\psi_{K}(y)=\psi_{G}(y)}\right\\}=\left\\{{{y\in\real{d}}\;|\;\psi_{G}(y)\leq\psi_{K}(y)}\right\\}.$

Since $\psi_{G}$ is lower semi-continuous and $\psi_{K}$ is continuous,
$P^{-1}_{G}(K)$ is closed.

As every open set $U$ is a countable union of compact sets $(K_{n})$ and

$P^{-1}_{G}\left({U}\right)=P^{-1}_{G}\left({\bigcup_{n}K_{n}}\right)=\bigcup_{n}P^{-1}_{G}\left({K_{n}}\right),$

we deduce that $P^{-1}_{G}(U)$ is a $F_{\sigma}$-set. In particular,
$P^{-1}_{G}(U)$ is a Borel set.

(b): Fix $s\in\real{d}$. For every $a\in\real{}$ we have that

$\left\\{{{y\in\real{d}}\;|\;g_{s}(y)>a}\right\\}=P^{-1}_{G}\left({\left\\{{{x\in\real{d}}\;|\;\left\langle
s,x\right\rangle>a}\right\\}}\right)\in\sigma(P_{G}).$

The $\sigma(P_{G})$-measurability of $g_{s}$ readily follows.

(c): Fix a sequence $x_{i}$, $i=1,2,\dots$ dense in $\real{d}$. Denote by
$r_{k}$, $k=1,2,\dots$ an enumeration of all positive rationals. Denote by
$\alpha:=(i,j,k,l)$, and set

$B^{\alpha}_{1}:=\left\\{{{x\in\real{d}}\;|\;|x-x_{i}|<r_{k}}\right\\},\quad
B^{\alpha}_{2}:=\left\\{{{x\in\real{d}}\;|\;|x-x_{j}|<r_{l}}\right\\}.$

Restrict the set of countable indexes $\alpha=(i,j,k,l)$ to those for which

$B^{\alpha}_{1}\cap B^{\alpha}_{2}=\emptyset.$

We further denote by $\beta$ the indexes $\alpha$ with the additional
property:

$\inf_{u\in B^{\beta}_{1},v\in B^{\beta}_{2}}S(u-v,u-v)>0.$ (4)

The conclusion follows from the definition of $\sigma(P_{G})$, once we observe
that

$\displaystyle\Sigma(P_{G})$
$\displaystyle=\bigcup_{\alpha}\left({P^{-1}_{G}(B^{\alpha}_{1})\cap
P^{-1}_{G}(B^{\alpha}_{2})}\right),$ $\displaystyle\Sigma_{1}(P_{G})$
$\displaystyle=\bigcup_{\beta}\left({P^{-1}_{G}(B^{\beta}_{1})\cap
P^{-1}_{G}(B^{\beta}_{2})}\right).$

For the last relation, to show the inclusion $\subset$, we use the joint
continuity of $S(u-v,u-v)$ to choose small enough rational $r_{k}$ and $r_{l}$
for (4) to hold. ∎

Let $x\in G$. We recall that $Q_{G}(x)$ denotes the largest closed convex
subset of $P^{-1}_{G}(x)$ whose relative interior contains $x$.

######  Lemma 3.7.

Let $S\in\mathcal{S}^{d}_{m}$, $G\in\mathfrak{M}\left({S}\right)$, $x\in G$,
and $y\in Q_{G}(x)$. Then $P_{G}(x)\subset P_{G}(y)$. If, in addition,
$P_{G}(y)$ is convex, then $P_{G}(x)=P_{G}(y)$.

###### Proof.

Let $v\in Q_{G}(x)$ and $z\in P_{G}(x)$. Then $x\in P_{G}(v)$ and

$\displaystyle 0$
$\displaystyle\leq\psi_{G}(v)-\left({S(z,v)-\frac{1}{2}S(z,z)}\right)$
$\displaystyle=S(x,v)-\frac{1}{2}S(x,x)-S(z,v)+\frac{1}{2}S(z,z)$
$\displaystyle=\frac{1}{2}S(x-z,x-z)+S(x-z,v-x)=S(x-z,v-x).$

Choosing $v=x\pm\epsilon(y-x)$ for some $\epsilon\in(0,1)$, which is possible
by the construction of $Q_{G}(x)$, we obtain that

$S(x-z,y-x)=0.$

Taking $v=y$, we deduce that

$\psi_{G}(y)=S(z,y)-\frac{1}{2}S(z,z).$

Hence, $z\in P_{G}(y)$, as required.

Assume now that $P_{G}(y)$ is a closed convex set and take $z\in P_{G}(y)$.
Lemma 3.5 shows that $S(x-z,x-z)=0$. Hence, $z\in P_{G}(x)$. ∎

###### Proof of Theorem 3.4.

Let $\gamma$ be an optimal plan for (2). By extending, if necessary, the
probability space, we can find a $d$-dimensional random variable $Z$ such that
$\gamma=\operatorname{{Law}}(Z,Y)$. As $x=\gamma(y|x)$, we have that
$Z=\mathbb{E}\left(\left.Y\right\lvert{Z}\right)$. Moreover, Theorem 3.3
yields that

$\displaystyle Z\in G,\quad Y\in Q_{G}(Z).$

It goes without saying that all pointwise relations are understood in the
almost sure sense. Using the assumption $Y\not\in\Sigma_{1}(P_{G})$, Lemma 3.5
shows that $P_{G}(Y)$ takes values in closed convex sets. Lemma 3.7 yields
that

$P_{G}(Y)=P_{G}(Z).$

The events that generate $\sigma(P_{G}(Y))$ and, respectively,
$\sigma(P_{G}(Z))$, differ by null sets. Therefore, conditioning on either of
the two $\sigma$-algebras yields the same result. In addition,
$\sigma(P_{G}(Z))\subset\sigma(Z)$. By the tower property of conditional
expectations we then have

$\displaystyle X$
$\displaystyle=\mathbb{E}\left(\left.Y\right\lvert{P_{G}(Y)}\right)=\mathbb{E}\left(\left.Y\right\lvert{P_{G}(Z)}\right)=\mathbb{E}\left(\left.\mathbb{E}\left(\left.Y\right\lvert{Z}\right)\right\lvert{P_{G}(Z)}\right)$
$\displaystyle=\mathbb{E}\left(\left.Z\right\lvert{P_{G}(Z)}\right)=\mathbb{E}\left(\left.Z\right\lvert{P_{G}(Y)}\right).$

Since $\sigma(P_{G}(Y))\subset\sigma(Y)$, we have that $X\in\mathcal{X}(Y)$.
By Theorem 3.3, the result holds if and only if $X\in P_{G}(Y)$. As $P_{G}(Y)$
takes values in closed convex sets,

$X\in P_{G}(Y)\iff\left\langle s,X\right\rangle\leq g_{s}(Y):=\sup_{z\in
P_{G}(Y)}\left\langle s,z\right\rangle,\quad s\in\real{d},$

where in showing the implication $\impliedby$, we choose an exceptional null
set that works for a dense countable subset of $s\in\real{d}$.

Let $s\in\real{d}$. By Lemma 3.6, the function $g_{s}$ is
$\sigma(P_{G})$-measurable and so, the random variable $g_{s}(Y)$ is
$\sigma(P_{G}(Y))$-measurable. As $Z\in P_{G}(Y)$, we have that $\left\langle
s,Z\right\rangle\leq g_{s}(Y)$. It follows that

$\left\langle s,X\right\rangle=\mathbb{E}\left(\left.\left\langle
s,Z\right\rangle\right\lvert{P_{G}(Y)}\right)\leq\mathbb{E}\left(\left.g_{s}(Y)\right\lvert{P_{G}(Y)}\right)=g_{s}(Y).$

Hence, $X\in P_{G}(Y)$, as required. ∎

Following [8], we now state sufficient conditions for the assertions of
Theorem 3.4 to hold that do not involve a dual minimizer. Let
$j\in\left\\{{1,\dots,d}\right\\}$ and $C$ be a compact set in $\real{d}$ such
that

$y^{j}=1,\quad y\in C.$

For $x\in\real{d}$, we denote by $x^{-j}$ its sub-vector without the $j$th
coordinate:

$x^{-j}:=\left({x^{1},\dots,x^{j-1},x^{j+1},\dots,x^{d}}\right)\in\real{d-1}.$

We write $\mathcal{H}^{j}_{C}$ for the family of functions $h=h(x)$ on
$\real{d}$ having the decomposition:

$h(x)=x^{j}+g_{1}(x^{-j})-g_{2}(x^{-j}),\quad x\in\real{d},$

where the functions $g_{1}$ and $g_{2}$ on $\real{d-1}$ are convex, have
linear growth:

$\left\lvert g_{i}(x)\right\rvert\leq K(1+\left\lvert x\right\rvert),\quad
x\in\real{d},\;i=1,2,$

for some constant $K>0$, and

$\nabla h(x)\in C,$

whenever the functions $g_{1}$ and $g_{2}$ are differentiable at $x^{-j}$.

Let $h\in\mathcal{H}^{j}_{C}$ and $H$ be the zero-level set of the composition
function $h\circ S$:

$H:=\left\\{{{x\in\real{d}}\;|\;h(Sx)=0}\right\\}.$

Lemma 4.4 in [8] shows that the surface $H$ has, at any point $x\in H$, an
$S$-normal vector $w\in C$. In the spirit of [13, Definition 6.3, p. 199], a
vector $w\in\real{d}$ is called $S$-_regular normal to $H$ at $x\in H$_ if

$\limsup_{\begin{subarray}{c}H\ni y\to x\\\
y\not=x\end{subarray}}\frac{S(w,y-x)}{\left\lvert y-x\right\rvert}\leq 0.$

A vector $w\in\real{d}$ is called $S$-_normal to $H$ at $x$_ if there exist
$x_{n}\in H$ and an $S$-regular normal vector $w_{n}$ to $H$ at $x_{n}$, such
that $x_{n}\rightarrow x$ and $w_{n}\rightarrow w$.

######  Theorem 3.8.

Let $S\in\mathcal{S}^{d}_{m}$, $Y\in\mathcal{L}_{2}(\real{d})$, and denote
$\nu:=\operatorname{{Law}}(Y)$. Assume that the convex hull of the support of
$\nu$ has a non-empty interior:

$\operatorname*{int}{\operatorname*{conv}{\operatorname{supp}{\nu}}}\not=\emptyset,$
(5)

and that $h(SY)\not=0$, i.e.
$\nu\left({\left\\{{{x\in\real{d}}\;|\;h(Sx)=0}\right\\}}\right)=0$, for every
function $h\in\mathcal{H}^{j}_{C}$ with index
$j\in\left\\{{1,\dots,d}\right\\}$ and compact set

$C\subset\left\\{{{x\in\real{d}}\;|\;x^{j}=1,\;S(x,x)>0}\right\\}.$ (6)

Then $Y\not\in\Sigma_{1}(P_{G})$ for every $G\in\mathfrak{M}\left({S}\right)$
such that $\mathbb{E}\left(\psi_{G}(Y)\right)<\infty$, and the assertions of
Theorem 3.4 hold.

###### Proof.

Let $G\in\mathfrak{M}\left({S}\right)$ be such that
$\mathbb{E}\left(\psi_{G}(Y)\right)<\infty$. Condition (5) implies that
$\psi_{G}$ has a non-empty interior. Theorem 4.5 in [8] then yields functions
$h_{n}\in\mathcal{H}_{C_{n}}^{j_{n}}$ with indexes
$j_{n}\in\left\\{{1,\dots,d}\right\\}$ and compact sets

$C_{n}\subset\left\\{{{x\in\real{d}}\;|\;x^{j_{n}}=1,\;S(x,x)>0}\right\\},\quad
n\geq 1,$

such that

$\Sigma_{1}(P_{G})\subset\bigcup_{n}\left\\{{{x\in\real{d}}\;|\;h_{n}(Sx)=0}\right\\}.$

The result readily follows. ∎

Assumption (5) does not restrict any generality, as we can work with the trace
of the original backward martingale problem on the affine hull of
$\operatorname{supp}{\nu}$.

Condition (6) means that the zero-level set
$H:=\left\\{{{x\in\real{d}}\;|\;h(Sx)=0}\right\\}$ of $h\circ S$ has, at every
point, an $S$-normal vector $w$ with $w^{j}=1$ which is strictly $S$-positive.

For $d=2$ and the standard form of $S$ from Example 3.1, the latter property
is equivalent to $H$ having at every point a strictly positive normal vector
in the classical Euclidean sense. In this case, $H$ is a graph of a strictly
decreasing $c-c$ function (the difference of two convex functions) and Theorem
3.8 improves Theorem 4.5 in [9], where $H$ was the graph of a strictly
decreasing Lipschitz function.

##  4 Uniqueness of optimal maps and plans

######  Theorem 4.1.

Let $S\in\mathcal{S}^{d}_{m}$, $Y\in\mathcal{L}_{2}(\real{d})$, and denote
$\nu:=\operatorname{{Law}}(Y)$. Let $G\in\mathfrak{M}\left({S}\right)$ be an
optimal set for (3) and assume that $Y\not\in\Sigma(P_{G})$, i.e., the
projection $P_{G}(Y)$ is (almost surely) single-valued. Then

$X:=P_{G}(Y)1_{\left\\{{Y\not\in\Sigma(P_{G})}\right\\}}$

is the unique optimal map for (1) and the law of $(X,Y)$ is the unique optimal
plan for (2).

###### Proof.

Lemma 3.6 shows that $X$ is $Y$-measurable.

Let $\gamma$ be an optimal plan for (2). Its existence has been established in
[7, Theorem 2.5]. By extending, if necessary, the probability space, we can
find a $d$-dimensional random variable $Z$ such that
$\gamma=\operatorname{{Law}}(Z,Y)$. As $x=\gamma(y|x)$, we have that
$Z=\mathbb{E}\left(\left.Y\right\lvert{Z}\right)$. Since
$Y\not\in\Sigma(P_{G})$, Theorem 3.3 yields that $Z=X$ and the result follows.
∎

The explicit knowledge of an optimal $G\in\mathfrak{M}\left({S}\right)$ is
needed in order to apply Theorem 4.1 directly. Theorem 4.2 contains convenient
sufficient conditions.

We denote by $\mathcal{E}_{0}(S)$ the collection of Borel sets
$D\subset\real{d}$ with the property that for any $\delta>0$, there are
functions $h_{n}\in\mathcal{H}^{j_{n}}_{C_{n}}$ with indexes
$j_{n}\in\left\\{{1,\dots,d}\right\\}$ and compact sets

$C_{n}\subset\left\\{{{x\in\real{d}}\;|\;x^{j_{n}}=1,\;0\leq
S(x,x)\leq\delta}\right\\},\quad n\geq 1,$

such that

$D\subset\bigcup_{n}\left\\{{{x\in\real{d}}\;|\;h_{n}(Sx)=0}\right\\}.$

Geometrically, the elements of $\mathcal{E}_{0}(S)$ are covered by a countable
number of surfaces, that have, at every point, $S$-normal vectors $w$ with
$w^{j}=1$ and $0\leq S(w,w)\leq\delta$.

The family $\mathcal{E}_{0}(S)$ contains hyperplanes

$H(w,c):=\left\\{{{y\in\real{d}}\;|\;S(y,w)=c}\right\\},$

where $c\in\real{}$ and the unique $S$-normal vector $w$ to $H$ is
$S$-_isotropic_ in the sense that $\left\lvert w\right\rvert>0$ and
$S(w,w)=0$. Thus, in Theorem 4.2, condition (a) is weaker than condition (b)
stated for $m=1$.

######  Theorem 4.2.

Let $S\in\mathcal{S}^{d}_{m}$, $Y\in\mathcal{L}_{2}(\real{d})$, and denote
$\nu:=\operatorname{{Law}}(Y)$. Assume (5) and that

  1. (a)

If the index $m=1$, then for every $S$-isotropic vector $w$, the random
variable $S(Y,w)$ has a continuous cumulative distribution function.

  2. (b)

If $m>1$, then $Y\notin D$, i.e. $\nu(D)=0$, for every
$D\in\mathcal{E}_{0}(S)$.

Then $Y\not\in\Sigma_{0}(P_{G})$ for every $G\in\mathfrak{M}\left({S}\right)$
such that $\mathbb{E}\left(\psi_{G}(Y)\right)<\infty$.

If in addition, $h(SY)\not=0$ for every $h\in\mathcal{H}^{j}_{C}$ with index
$j\in\left\\{{1,\dots,d}\right\\}$ and compact set $C$ as in (6), then
$Y\not\in\Sigma(P_{G})$ for every $G\in\mathfrak{M}\left({S}\right)$ such that
$\mathbb{E}\left(\psi_{G}(Y)\right)<\infty$ and the assertions of Theorem 4.1
hold.

###### Proof.

Let $G\in\mathfrak{M}\left({S}\right)$ be such that
$\mathbb{E}\left(\psi_{G}(Y)\right)<\infty$. From (5) we deduce that
$\psi_{G}$ has a non-empty interior, which enables us to use Theorems 4.7 and
4.6 in [8]. In view of Theorem 3.8, we only need to show that
$Y\not\in\Sigma_{0}(P_{G})$.

Let $m=1$. Theorem 4.7 in [8] yields $S$-isotropic $w_{n}\in\real{d}$ and
constants $c_{n}\in\real{}$, $n\geq 1$, such that

$\Sigma_{0}(P_{G})\subset\bigcup_{n}\left\\{{{x\in\real{d}}\;|\;S(x,w_{n})=c_{n}}\right\\}.$

Under (a), $Y\not\in\Sigma_{0}(P_{G})$.

Let $m>1$. For $j\in\left\\{{1,\dots,d}\right\\}$, we define
$\overline{\Sigma}^{j}_{0}(P_{G})$ as the set of
$x\in\operatorname{dom}{P_{G}}$ such that $S(y_{1}-y_{2},y_{1}-y_{2})=0$ for
_some_ $y_{1},y_{2}\in P_{G}(x)$ with $y_{1}^{j}\not=y_{2}^{j}$. Clearly,

$\Sigma_{0}(P_{G})\subset\bigcup_{j=1}^{d}\overline{\Sigma}^{j}_{0}(P_{G}).$

Fix $\delta>0$ and $j\in\left\\{{1,\dots,d}\right\\}$. By Theorem 4.6 in [8],
there are compact sets

$C_{n}\subset\left\\{{{x\in\real{d}}\;|\;x^{j}=1,\;0\leq
S(x,x)\leq\delta}\right\\}$

and functions $h_{n}\in\mathcal{H}^{j}_{C_{n}}$ such that

$\overline{\Sigma}^{j}_{0}(P_{G})\subset\bigcup_{n}\left\\{{{x\in\real{d}}\;|\;h_{n}(Sx)=0}\right\\}.$

By Lemma 3.6, $\Sigma_{0}(P_{G})$ is Borel measurable. Hence,
$\Sigma_{0}(P_{G})\in\mathcal{E}_{0}(S)$ and then, under (b),
$Y\not\in\Sigma_{0}(P_{G})$. ∎

For $d=2$ and the standard form of $S$ from Example 3.1, Theorem 4.2 improves
Theorem 4.6 in [9]. In this case, condition (a) means that each of the
components $Y_{i}$, $i=1,2$, has a continuous cumulative distribution
function.

From Theorem 4.2 we immediately obtain the following sufficient conditions for
the uniqueness of maps and plans.

######  Corollary 4.3.

Let $S\in\mathcal{S}^{d}_{m}$, $Y\in\mathcal{L}_{2}(\real{d})$, and denote
$\nu:=\operatorname{{Law}}(Y)$. Assume (5) and that $h(SY)\not=0$ for every
$h\in\mathcal{H}^{j}_{C}$ with index $j\in\left\\{{1,\dots,d}\right\\}$ and
compact set $C$

$C\subset\left\\{{{x\in\real{d}}\;|\;x^{j}=1,\;S(x,x)\geq 0}\right\\}.$

Then $Y\not\in\Sigma(P_{G})$ for every $G\in\mathfrak{M}\left({S}\right)$ such
that $\mathbb{E}\left(\psi_{G}(Y)\right)<\infty$ and the assertions of Theorem
4.1 hold.

##  Appendix A Uniform approximation by maps

We continue to identify random variables on a probability space
$(\Omega,\mathcal{F},\mathbb{P})$ if they differ only on a set of measure zero
and interpret relations between them in the $\mathbb{P}-a.s.$ sense. In
particular, if $X$ and $Z$ are random variables taking values in Polish
(complete separable metric) spaces $(\mathbb{S}_{1},\rho_{1})$ and
$(\mathbb{S}_{2},\rho_{2})$, respectively, then $X$ is $Z$-measurable if and
only if $X=f(Z)$ ($\mathbb{P}-a.s.$) for a Borel function
$f:\;\mathbb{S}_{2}\rightarrow\mathbb{S}_{1}$.

######  Theorem A.1.

Let $X$ and $Y$ be random variables on $(\Omega,\mathcal{F},\mathbb{P})$
taking values in Polish spaces $(\mathbb{S}_{1},\rho_{1})$ and
$(\mathbb{S}_{2},\rho_{2})$, respectively. If the law of $Y$ is atomless, then
for every $\epsilon>0$ there is a random variable $Z=Z(\epsilon)$ taking
values in $(\mathbb{S}_{2},\rho_{2})$ such that
$\operatorname{{Law}}(Z)=\operatorname{{Law}}(Y)$,
$\rho_{2}\left({Y,Z}\right)\leq\epsilon$, and $X$ is $Z$-measurable.

###### Proof.

Let $\epsilon>0$. We take a dense sequence $y_{n}\in\mathbb{S}_{2}$,
$n=1,2,\dots$, and define

$B_{n}:=\left\\{{{z\in\mathbb{S}_{2}}\;|\;\rho_{2}(z,y_{n})\leq\frac{\epsilon}{2}}\right\\},\quad
D_{n}:=B_{n}\setminus\bigcup_{i=1}^{n-1}B_{i},\quad n\geq 1.$

By keeping only the terms having strictly positive probability, we obtain sets
$D_{n}\subset\mathbb{S}_{2}$, $n=1,2,\dots$, that are _mutually disjoint_ and
such that

$Y\in\bigcup_{n=1}^{\infty}D_{n},\quad\mathbb{P}\left({Y\in
D_{n}}\right)>0,\quad\operatorname{diam}(D_{n}):=\sup_{x,y\in
D_{n}}\rho_{2}(x,y)\leq\varepsilon.$

For each $n\geq 1$ we apply Lemma A.2 using the probability measure

$\mathbb{P}_{n}(A):=\mathbb{P}(A|Y\in
D_{n})=\frac{\mathbb{P}\left({A\cap\left\\{{Y\in
D_{n}}\right\\}}\right)}{\mathbb{P}\left({Y\in D_{n}}\right)},\quad
A\in\mathcal{F},$

instead of the original measure $\mathbb{P}$. As a result, we obtain a random
variable $Z_{n}$ taking values in $D_{n}$ and a Borel function
$f_{n}:\;\mathbb{S}_{2}\rightarrow\mathbb{S}_{1}$ such that $Z_{n}$ and $Y$
have the same law under $\mathbb{P}_{n}$ and

$\mathbb{P}_{n}(X=f_{n}(Z_{n}))=1.$

For a random variable $Z$ taking values in $\mathbb{S}_{2}$ and a Borel
function $f:\;\mathbb{S}_{2}\rightarrow\mathbb{S}_{1}$ such that

$Z(\omega)=Z_{n}(\omega)\text{~{}if~{}}Y(\omega)\in D_{n},\quad
f(y)=f_{n}(y)\text{~{}if~{}}y\in D_{n},\quad n\geq 1,$

we have that

$\operatorname{{Law}}(Y)=\operatorname{{Law}}(Z),\quad{X=f(Z)},\quad\rho_{2}\left({Y,Z}\right)\leq\epsilon,$

as required. ∎

######  Lemma A.2.

Let $X$ and $Y$ be random variables taking values in Polish spaces
$(\mathbb{S}_{1},\rho_{1})$ and $(\mathbb{S}_{2},\rho_{2})$, respectively. If
the law of $Y$ is atomless, then there is a random variable $Z$ taking values
in $(\mathbb{S}_{2},\rho_{2})$ such that
$\operatorname{{Law}}(Z)=\operatorname{{Law}}(Y)$ and $X$ is $Z$-measurable.

###### Proof.

Replacing $X$ with $(X,Y)$ we can assume from the start that the law of $X$ is
atomless. Using bijections $g:\;\mathbb{S}_{1}\rightarrow\real{}$ and
$h:\;\mathbb{S}_{2}\rightarrow\real{}$ that are Borel measurable together with
their inverses, we can also replace $X$ with $g(X)$ and $Y$ with $h(Y)$. For
the existence of such bijections we refer to [3, Theorem 13.1.1]. Thus, we
assume that both $X$ and $Y$ are real valued and their laws are atomless.

We denote by $F_{X}$ and $Q_{X}$ the cumulative distribution and quantile
functions of $X$:

$\displaystyle F_{X}(x)$ $\displaystyle:=\mathbb{P}\left({X\leq
x}\right),\quad x\in\real{},$ $\displaystyle Q_{X}(u)$
$\displaystyle:=\min\left\\{{{x\in\real{}}\;|\;u\leq F_{X}(x)}\right\\},\quad
u\in(0,1).$

As $F_{X}$ is continuous, the random variable $U:=F_{X}(X)$ has uniform
distribution on $(0,1)$ and $X=Q_{X}(U)$. Similarly, $V:=F_{Y}(Y)$ has uniform
distribution on $(0,1)$ and $Y=Q_{Y}(V)$, where $F_{Y}$ and $Q_{Y}$ are the
cumulative distribution and quantile functions of $Y$. Setting

$Z:=Q_{Y}(U)=Q_{Y}(F_{X}(X)),$

we deduce that $Z$ has the same law as $Y$, that $U=F_{Y}(Z)$, and
$X=Q_{X}(F_{Y}(Z)))$. ∎

######  Remark A.3.

Let $X$ and $Y$ be random variables on $(\Omega,\mathcal{F},\mathbb{P})$
taking values in $\real{d}$ and assume that the law of $Y$ is atomless. The
conditional law of $X$ given $Y$ describes the randomized transport from $Y$,
the “origin”, to $X$, the “target”. A classical question is to approximate
$(X,Y)$ by $(X^{\prime},Y^{\prime})$, where the transport from $Y^{\prime}$ to
$X^{\prime}$ is deterministic, that is, $X^{\prime}$ is
$Y^{\prime}$-measurable.

Theorem A.1 shows that the random variable $(X,Y)$ can be _pointwise
uniformly_ approximated by the elements of the family

$\mathcal{C}_{1}(X,Y):=\left\\{{{(X,Z)}\;|\;\operatorname{{Law}}(Z)=\operatorname{{Law}}(Y)\text{~{}and
$X$ is $Z$-measurable}}\right\\},$

where the _target_ random variable $X$ is kept frozen.

In a more traditional approach, see [11] and [1] among the others, the
approximating family is taken to be

$\mathcal{C}_{2}(X,Y):=\left\\{{{(Z,Y)}\;|\;\operatorname{{Law}}(Z)=\operatorname{{Law}}(X)\text{~{}and
$Z$ is $Y$-measurable}}\right\\},$

where the _origin_ random variable $Y$ remains unchanged. It has been shown
that the law of $(X,Y)$ can be _weakly_ approximated by the laws of the
elements of $\mathcal{C}_{2}(X,Y)$.

In general, $(X,Y)$ can not be pointwise approximated by the elements of
$\mathcal{C}_{2}(X,Y)$ even in the sense of convergence in probability. For
instance, if $X$ and $Y$ are independent identically distributed and
$(Z,Y)\in\mathcal{C}_{2}(X,Y)$, then $Z$ and $X$ are also independent ($Z$ is
a function of $Y$) identically distributed. It follows that

$\mathbb{P}\left({\left\lvert
Z-X\right\rvert\geq\epsilon}\right)=\mathbb{P}\left({\left\lvert
Y-X\right\rvert\geq\epsilon}\right)\geq\epsilon,$

for sufficiently small $\epsilon>0$.

## References

  * Beiglböck and Lacker [2018] Mathias Beiglböck and Daniel Lacker.  Denseness of adapted processes among causal couplings, 2018.  URL https://arxiv.org/abs/1805.03185.
  * Castaing and Valadier [1977] C. Castaing and M. Valadier.  _Convex analysis and measurable multifunctions_.  Lecture Notes in Mathematics, Vol. 580. Springer-Verlag, Berlin-New York, 1977.
  * Dudley [2002] R. M. Dudley.  _Real analysis and probability_ , volume 74 of _Cambridge Studies in Advanced Mathematics_.  Cambridge University Press, Cambridge, 2002.  ISBN 0-521-00754-2.  doi: 10.1017/CBO9780511755347.  URL https://doi.org/10.1017/CBO9780511755347.  Revised reprint of the 1989 original.
  * Federer [1969] Herbert Federer.  _Geometric measure theory_.  Die Grundlehren der mathematischen Wissenschaften, Band 153. Springer-Verlag New York, Inc., New York, 1969.
  * Hastie and Stuetzle [1989] Trevor Hastie and Werner Stuetzle.  Principal curves.  _J. Amer. Statist. Assoc._ , 84(406):502–516, 1989.  ISSN 0162-1459.  URL https://www.jstor.org/stable/2289936.
  * Hastie and Tibshirani [1993] Trevor Hastie and Robert Tibshirani.  Varying-coefficient models.  _J. Roy. Statist. Soc. Ser. B_ , 55(4):757–796, 1993.  ISSN 0035-9246.  URL https://www.jstor.org/stable/2345993.  With discussion and a reply by the authors.
  * Kramkov and Sîrbu [2022a] Dmitry Kramkov and Mihai Sîrbu.  Backward martingale transport and Fitzpatrick functions in pseudo-Euclidean spaces, 2022a.  URL https://arxiv.org/abs/2209.04664.
  * Kramkov and Sîrbu [2022b] Dmitry Kramkov and Mihai Sîrbu.  Singularities of Fitzpatrick and convex functions, 2022b.  URL https://arxiv.org/abs/2212.09954.
  * Kramkov and Xu [2022] Dmitry Kramkov and Yan Xu.  An optimal transport problem with backward martingale constraints motivated by insider trading.  _Ann. Appl. Probab._ , 32(1):294–326, 2022.  ISSN 1050-5164.  doi: 10.1214/21-AAP1678.
  * Kyle [1985] Albert S. Kyle.  Continuous auctions and insider trading.  _Econometrica_ , 53:1315–1335, 1985.
  * Pratelli [2007] Aldo Pratelli.  On the equality between Monge’s infimum and Kantorovich’s minimum in optimal mass transportation.  _Ann. Inst. H. Poincaré Probab. Statist._ , 43(1):1–13, 2007.  ISSN 0246-0203.  doi: 10.1016/j.anihpb.2005.12.001.  URL https://doi.org/10.1016/j.anihpb.2005.12.001.
  * Rochet and Vila [1994] Jean-Charles Rochet and Jean-Luc Vila.  Insider Trading without Normality.  _The Review of Economic Studies_ , 61(1):131–152, 01 1994.  ISSN 0034-6527.  doi: 10.2307/2297880.  URL https://doi.org/10.2307/2297880.
  * Rockafellar and Wets [1998] R. Tyrrell Rockafellar and Roger J.-B. Wets.  _Variational analysis_ , volume 317 of _Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]_.  Springer-Verlag, Berlin, 1998.  ISBN 3-540-62772-3.


# Counterexamples to a conjecture on matching Kneser graphs

Moharram N. Iradmusa Faculty of Mathematical Sciences, Shahid Beheshti
University, Tehran, Iran<EMAIL_ADDRESS>
###### Abstract

Let $G$ be a graph and $r\in\mathbb{N}$. The matching Kneser graph
$\textsf{KG}(G,rK_{2})$ is a graph whose vertex set is the set of
$r$-matchings in $G$ and two vertices are adjacent if their corresponding
matchings are edge-disjoint. In [Alishahi, M. and Hajiabolhassan, H., On the
Chromatic Number of Matching Kneser Graphs, Combin. Probab. and Comput. 29
(2020), no. 1, 1–21.] it was conjectured that for any connected graph $G$ and
positive integer $r\geq 2$, the chromatic number of $\textsf{KG}(G,rK_{2})$ is
equal to $|E(G)|-\textsf{ex}(G,rK_{2})$, where $\textsf{ex}(G,rK_{2})$ denotes
the largest number of edges in $G$ avoiding a matching of size $r$. In this
note, we show that the conjecture is not true for snarks.

Given two positive integers $n$ and $r$, the Kneser graph $\textsf{KG}(n,r)$,
is the graph whose vertices represent the $r$-subsets of $\\{1,\ldots,n\\}$,
and where two vertices are adjacent if and only if they correspond to disjoint
subsets. This graph introduced by Lovász in 1978 [3]. The matching Kneser
graph was introduced as a generalization of Kneser graph [1]. Precisely,
$\textsf{KG}(nK_{2},rK_{2})\cong\textsf{KG}(n,r)$. Also, by a simple greedy
coloring, it was proved that
$\chi(\textsf{KG}(G,rK_{2}))\leq|E(G)|-\textsf{ex}(G,rK_{2})$ for any graph
$G$ and positive integer $r$. This upper bound is tight when $G$ satisfies
some certain properties as is claimed in the main result of [1] and is shown
throughout the paper. Finally the following conjecture was introduced
according to the results of the paper.

######  Conjecture 1.

For any connected graph $G$ and positive integer $r\geq 2$,

$\chi(\textsf{KG}(G,rK_{2}))=|E(G)|-\textsf{ex}(G,rK_{2}).$

We show that the conjecture is false when $G$ is a snark. A snark is a simple,
connected, bridgeless cubic graph with chromatic index equal to four [2]. Let
$G$ be a snark of order $2r$. Petersen’s Theorem from 1891 [4], states that
every bridgeless cubic graph has a perfect matching. Further, Schönberger in
1934 has proved that every bridgeless cubic graph has a perfect matching not
containing two arbitrarily prescribed edges [5]. Therefore,
$\textsf{ex}(G,rK_{2})\leq|E(G)|-3$. In addition, by removing three edges
incident with an arbitrary vertex, the resulting graph has no matching of size
$r$. Therefore $\textsf{ex}(G,rK_{2})=|E(G)|-3$. In addition, since
$\chi^{\prime}(G)=4$, the intersection of any two perfect matchings of $G$ is
nonempty. Therefore, $\textsf{KG}(G,rK_{2})$ has no edge and so
$\chi(\textsf{KG}(G,rK_{2}))=1\neq|E(G)|-\textsf{ex}(G,rK_{2})=3$.

## References

  * [1] Alishahi, M. and Hajiabolhassan, H. (2020) On the Chromatic Number of Matching Kneser Graphs. Combin. Probab. and Comput. 29, no. 1, 1–21.
  * [2] Gardner, M. (1976) Mathematical Games. Scientific American 4 (234), 126–130.
  * [3] Lovász, L. (1978) Kneser’s conjecture, chromatic number, and homotopy. J. Combin. Theory Ser. A 25, 319–324.
  * [4] Petersen, J. (1891) Die Theorie der regulären graphs. Acta Mathematica 15, 193–220.
  * [5] Schöonberger, T. (1934) Ein Beweis des Petersenschen Graphensatzes. Acta Litt. Sci. Szeged 7, 51–57.


# Inform Product Change through Experimentation with Data-Driven Behavioral
Segmentation

Zhenyu Zhao, Yan He, Miao Chen  Yahoo Inc.
Sunnyvale, USA
Email<EMAIL_ADDRESS>
###### Abstract

Online controlled experimentation is widely adopted for evaluating new
features in the rapid development cycle for web products and mobile
applications. Measurement on overall experiment sample is a common practice to
quantify the overall treatment effect. In order to understand why the
treatment effect occurs in a certain way, segmentation becomes a valuable
approach to a finer analysis of experiment results. This paper introduces a
framework for creating and utilizing user behavioral segments in online
experimentation. By using the data of user engagement with individual product
components as input, this method defines segments that are closely related to
the features being evaluated in the product development cycle. With a real-
world example we demonstrate that the analysis with such behavioral segments
offered deep, actionable insights that successfully informed product decision
making.

###### Index Terms:

Segmentation; User behavior; Controlled experiment; A/B testing; Unsupervised
learning; Product development

##  I Introduction

The art of fast failure has been called the true secret of Silicon Valley’s
success [1]. Web product development is often composed of a build-measure-
learn cycle [2]. During this cycle, new ideas, e.g., product changes in either
front-end design or back-end algorithms, are evaluated and implemented at a
fast pace. Online controlled experiments, also known as A/B tests, are widely
used to evaluate these ideas [3, 4, 5, 6, 7, 8, 9, 10, 11].

A standard experiment analysis measures the overall test effect by comparing
all the test users with all the control users. The result of such analysis
answers the “what” question - what will happen if the feature being tested is
launched. However, it falls short of answering the “why” question - why the
treatment effect occurs in a certain way.

In order to answer the “why” question, segmentation is required to study the
impact on individual user subgroups. Owing to the different intents and
preferences of users, their reaction to product change can differ, which is
often overlooked in experiment analyses involving only the overall population.
Conducting experiment analysis at the user segment level will help the
stakeholders understand 1) how the treatment effect varies among user
subgroups, and 2) how much each subgroup contributes to the overall treatment
effect. The answers to these questions are indispensable for guiding product
development.

It can be challenging to define user segments that are useful and relevant to
experiment analyses. Common dimensions, such as device, browser, operating
system, location, demographics, user tenure and referral source, are static
and relatively easy to implement. In some cases these dimensions are useful
for analysis and debugging. Additional dimensions that are directly related to
the feature being evaluated in the experiment can add value to inform the
development of products.

Behavioral segmentation using distance-based clustering and probability-based
mixture models has been extensively studied in the fields including user
targeting in marketing [12], online advertising [13] [14], personalizing
content serving [15], identifying user behavior on social networks [16], and
modeling shared interests of e-commerce users [17]. Applying segmentation in
experimentation was also discussed in previous literature. Segmentation has
been used as an experiment inclusion criteria for targeting subpopulations
based on static and dynamic user attributes ([18]). When data quality issues
or unexpected results arise from an experiment, segmenting the experiment
results (e.g. by browser type) can help identify the root cause ([19]).
Segmentation was also used in a stratified sampling method for enhancing
experiment accuracy ([20]).

In this paper, we present an approach to behavioral segmentation designed for
experiment analysis. Users are clustered according to their level of
engagement with individual product functional components. These mutually
exclusive and collectively exhaustive segments are closely related to the
features being evaluated and facilitate a finer analysis of experiment
results.

The contribution of this paper includes:

  * •

A novel framework is introduced for developing and utilizing behavioral
segments tailored for experiment analysis. In particular, we design
segmentation features that describe user intent and needs which are critical
to guide the development of product features.

  * •

We demonstrate that the application of this method led to a successful product
decision in a real-world example for Yahoo Finance.

  * •

Potential caveats and pitfalls are discussed when behavioral segmentation is
used together with experimentation.

This paper is organized as follows: Section II presents the procedure for
developing behavioral segmentation using a data-driven algorithm; Section III
describes how to draw actionable insights through segment-level analyses in
experimentation; Section IV discusses a study with the proposed method applied
in the Yahoo Finance website redesign experiment, which led to a product
decision with significant improvement of user engagement. Section V summarizes
our research and discusses the potential pitfalls in practice.

##  II Developing Data-Driven Behavioral Segmentation for Online
Experimentation

###  II-A Behavioral Segmentation Features

The first step is to define a list of user behavior features to be used in the
clustering algorithm. Various types of behavior dimensions are available to
choose. As an example, users can be divided into high/medium/low engagement
groups based on their visiting frequency. For evaluating product features, we
found using the engagement with product functional components is particularly
relevant. By using such dimensions we are able to measure the experiment
effect by segments and guide product development with actionable insights.

As an example, Yahoo Finance website is a product with multiple web pages
providing different utilities to users. Users coming to Yahoo Finance are
looking for financial news articles, stock quotes, stock portfolio
performance, market data, communication with other users on message boards, or
personal finance advice. User behavior and utility needs can be characterized
by the page views on different functional web pages. Therefore, the behavioral
features for segmentation consist of finance homepage page views, quotes page
views, watchlist (or portfolio) page views, article page views, stock charts
page views, message board page views, personal finance page views, and other
page views.

###  II-B Segment Definition Period

After defining the list of behavioral features, we collect the data for
calculating such features. It is critical to define user segments based on the
data from the pre-experiment period instead of the experiment period. This
setup enables us to carry out a fair comparison and measure the treatment
effect on each user segment. Otherwise, bias can be introduced as the
treatment effect may shift user behavior and user segments in the treatment
group. In the segment definition period, a data set containing user behavioral
features is collected to define user segments before experiments start. In the
experiment period, a data set containing experiment metrics is collected to
measure treatment effects at both the overall level and the segment level. The
length of the segment definition period may vary from one to multiple weeks.

###  II-C Feature Transformation and Dimension Reduction

A series of feature engineering procedures, including data transformation and
dimension reduction, are applied to prepare the user features as inputs for
the segmentation algorithm. This process can be summarized in following six
steps.

  * •

Step 1: Feature extraction from raw data.

Suppose there are $n$ users and $p$ features; let $x^{(1)}_{ij}$ denote the
value of the $j$th feature for the $i$th user ($i=1,...,n$ and $j=1,...,p$),
with the notation (s) indicating the features at Step $s$.

  * •

Step 2: Orthogonalization. Segmentation features in the original scale are
highly correlated with the visiting frequency of the users. To reduce the
dominant effect of visiting frequency, we adopted an orthogonal design with:
1) the number of visiting days per week, 2) the number of sessions per
visiting day, and 3) module-specific engagement per session.

Days visited per week: $x^{(2)}_{i1}=x^{(1)}_{i1}/w$, where $x^{(1)}_{i1}$ is
the number of days visited for user $i$ calculated in Step 1, and $w$ denotes
the number of weeks during the segment definition period;

Sessions per visited day: $x^{(2)}_{i2}=x^{(1)}_{i2}/x^{(1)}_{i1}$, where
$x^{(1)}_{i2}$ is the number of sessions for user $i$ calculated in Step 1;

Per-session engagement features: $x^{(2)}_{ij}=x^{(1)}_{ij}/x^{(1)}_{i2}$,
with $j=3,...,p$, where $x^{(1)}_{ij}$ is the module-specific engagement
feature calculated in Step 1.

  * •

Step 3: Data cleaning. We remove outliers (users with extremely high values
for page views, clicks, etc.) from the segmentation training data set ([21]).

$x^{(3)}_{ij}$ denotes the cleaned feature data, with $j=1,...,p$ and
$i=1,...,n^{\prime}$, after removing $n-n^{\prime}$ outliers and re-indexing
the users.

  * •

Step 4: Log transformation. Many clustering algorithms are based on the
Euclidean distance in the feature space. Measuring on the original scale may
not accurately represent the behavioral difference among the users. For
example, users with one page view should be more distant from those with zero
page views than from those with two page views. To accommodate this nonlinear
relationship, we transform the original feature space into log scale:
$x=\log(1+x)$ for each feature $x$.

$x^{(4)}_{ij}=\log(1+x^{(3)}_{ij})$ for $i=1,...,n^{\prime}$ and $j=1,...,p$.

  * •

Step 5: Normalization. In order to assign equal weight (in the loss function)
to each feature in the segmentation algorithm, we normalize the log-
transformed features to have mean $0$ and standard deviation $1$.

$x^{(5)}_{ij}=\frac{x^{(4)}_{ij}-\frac{1}{n}\sum_{k=1}^{n}x^{(4)}_{kj}}{\sqrt{\frac{1}{n-1}(x^{(4)}_{ij}-\frac{1}{n}\sum_{k=1}^{n}x^{(4)}_{kj})^{2}}}$

for $i=1,...,n^{\prime}$ and $j=1,...,p$.

  * •

Step 6: Dimension reduction. To avoid the curse of dimensionality ([22]) and
reduce the correlation among features, principle component analysis (PCA,
[23]) is applied before clustering. Only the top principle components are
included for model development, with a sufficient proportion of the variance
from the original feature space explained.

$x^{(6)}_{ij}$ denotes the $j$th principle component score for user $i$, for
$i=1,...,n^{\prime}$ and $j=1,...,p^{\prime}$ ($p^{\prime}<=p$ as the first
$p^{\prime}$ principle components are selected).

Let $X^{(5)}$ denote the $n\times p$ feature matrix with element
$x^{(5)}_{ij}$ at the $i$th row and $j$th column. The principle component
score matrix can be calculated by

$X^{(6)}=X^{(5)}W$

where matrix $W$ is the $p\times p$ loading matrix whose columns are the
eigenvectors of $X^{(5)T}X^{(5)}$. Further, $x^{(6)}_{ij}$ is the element of
the matrix at the $i$th row and $j$th column.

###  II-D Clustering Algorithm

Various clustering algorithms are available for developing the segments based
on user behavioral features. We hereby summarize the criteria for choosing the
optimal algorithm.

  * •

Scalability. Computation requirements for large-scale web data-based
segmentation can be intense. For this reason, some clustering algorithms are
disqualified owing to computational inefficiency. For instance, the
Agglomerative clustering algorithm ([24]), as a bottom-up hierarchical
approach, is not scalable for online experimentation because of the heavy
computational load in pair-wise distance computations between users.

  * •

Goodness of fit. Each model has either an explicit or implicit assumption of
the underlying data. The goodness of fit between the actual data and the model
assumption is an important criterion for model evaluation. For example, GMMs
(Gaussian mixture models [25]) assume that the data of each segment follows a
multi-variate Gaussian distribution in the feature space, and the quality of
the segmentation depends on whether the data is close to a Gaussian shape. In
addition, some geometry clustering models, such as DBSCAN (Density-based
spatial clustering of applications with noise, [26]), are useful when the
clusters have a specific shape. However, DBSCAN assumes the densities are
similar among different clusters such that an appropriate parameter can be
specified to define neighborhood. In addition, DBSCAN may encounter difficulty
for defining the neighborhood distance threshold when the dimension of feature
space is high (curse of dimensionality). In contrast, k-means does not have a
strong assumption of the underlying data structure, and can outperform other
models when the data does not fit their assumptions.

  * •

Interpretation. In order to inform product decisions, the developed segments
must represent distinct user groups and bear clear business meaning. For
example, a good segmentation algorithm is expected to create clusters of
relatively similar sizes (instead of one dominant giant cluster with many tiny
clusters), and distinguishable clusters (instead of two clusters with similar
behavior patterns and business meaning).

After evaluating multiple clustering algorithms (including the Agglomerative
algorithm, DBSCAN, k-means, and GMM), we chose k-means for our products. The
reasons are: 1) k-means is scalable for massive data sets; 2) k-means has weak
assumptions of the data structure which allows us to apply this method in
various use cases; 3) the segments created by k-means effectively represent
our distinct user groups. We encourage the other practitioners to determine
their best algorithm based on their own use cases.

However, the selection of the clustering algorithm is meant to be made on a
case-by-case basis: k-means can be suboptimal to other algorithms in other
applications and data settings.

The data input for k-means is composed of the principle component features
defined in previous feature engineering steps. The output of the algorithm
contains the centroids of each cluster in the feature space, and a cluster
label for each user.

The number of clusters $K$ is a tuning parameter in the k-means algorithm.
Choosing an optimal $K$ is a key issue in building the model ([27]). There are
a few criteria for choosing this parameter value. For a given $K$, the
objective of the K-means algorithm is to reduce the loss function defined as
the sum of the squared distance from user points to cluster centroids.
However, this loss function is not directly applicable for optimizing $K$,
because it is a monotonic decreasing curve w.r.t. $K$ \- the greater the
number of clusters, the smaller the loss function. Instead, BIC (Bayesian
information criterion, [28]) and DaviesBouldin index ([29]) can be used to
determine the optimal $K$. A detailed evaluation is discussed in Section IV.

###  II-E Segment Name and Behavioral Representation

The user cluster label output from k-means is numerical, from $0$ to $K-1$,
which does not bear a business meaning. Each segment can be further named
after its unique user behavior pattern defined by per-user metrics described
in Step $2$ in Section II-C. As an example, for Yahoo Homepage web portal
site, one segment with high mail clicks and low article clicks can be named as
’Mail only’, or vice versa, as ’Content only’. The resultant segment names now
reflect user behavior patterns and their intent coming to the site.

##  III Segmentation Analysis for Experimentation

We have discussed the creation of the behavioral segments. This section will
introduce a series of analyses using these segments in experimentation.

###  III-A Preliminary Segment Analysis

In order to understand how important each segment means for the product, the
percentage of overall engagement and/or revenue contributed by each segment
can be quantified. Here we define experiment metrics that will be used for
decisions. Examples include user count, page views, sessions, clicks, time
spent, revenue, etc. For each of the experiment metrics, we calculate the
total for both overall and segment users. Percentage contribution by each
segment is calculated by dividing the total metric of segment users by that of
overall users. These percentages are additive and sum to $100\%$ across
segments. Note that some segments may have small size, but contribute to a
relatively large portion of user engagement and/or revenue.

###  III-B Segment-Level Treatment Effect

For a finer view of experiment analysis, segment-level treatment effect is
calculated as the mean difference between the test group and the control
group. Given that the segment definition period is separate from the
experiment period, we first define three types of user status:

  1. 1.

Users appearing in both the segment definition period and the experiment
period. These users have segment label assigned in segment definition period,
as well as experiment metrics measured in experiment period.

  2. 2.

Users appearing only in the segment definition period and not in the
experiment period. These users are assigned to a segment but do not have an
experiment metric value due to inactivity. Their experiment metric value is
assigned as $0$, indicating no engagement.

  3. 3.

Users only appearing in the experiment period, but not in the segment
definition period. These users are either new or returning users who were not
active during the segment definition period. They don’t have segment label
assigned, but do have experiment measurement. This group is named as segment
“unseen” and added to the original segment family for further analysis.

For segment “unseen” and each segment defined in Section II, both the metric
difference and statistical significance (in the form of a p-value) are
calculated to quantify segment-level treatment effect. It is not rare to
observe that segments react in opposite direction to the feature being tested.
Segment-level analysis on treatment effect uncovers such information buried in
overall measurement. It also offers unique insights into the opportunities
where product experience should be improved for specific groups of users.

###  III-C Identifying the Dominant Segments for the Overall Treatment Effect

This step helps identify the drivers of overall treatment effect if there is
one or a few dominant segments. The segments with a large treatment effect on
per-user metrics are not necessarily the ones that dominate the overall
treatment effect, because segment size is another factor. In order to evaluate
a segment’s impact on the overall metrics, we first calculate the within-
segment total metric difference between the control and test groups. Then, the
percentage of overall treatment effect explained by one segment is calculated
by dividing its within-segment total metric difference by the total metric
difference in the overall experiment population. Segments that contribute to a
high percentage of the overall treatment effect are important ones that worth
special attention in the iteration of product testing.

##  IV Example

Next we will illustrate how to apply the proposed methodology in practice. The
entire process from developing behavioral segments to the findings and
decisions based on the segmentation analysis is discussed in the setting of a
website redesign test for Yahoo Finance site. Empirical challenges, findings
and evaluation of the proposed methodology are also discussed with this
example. The data described in this example has been modified and rescaled.

###  IV-A Experiment Background

In Yahoo Finance redesign experiment, changes were applied to overall page
layout, module positions, content density and addition/removal of functional
modules. A functional module can be a navigational module with links to other
pages, an article module containing an article stream, or a quotes module
showing stock prices. The impact on user engagement was evaluated via
experimentation.

Measurement includes both page engagement and user visitation frequency.
Visitation frequency is quantified by days visited and sessions in the defined
experiment period. Page engagement is quantified by the number of page views.
There are two sub-categories of page views defined at Yahoo: (1) CPV (classic
page view) is defined as a page view event logged when the user open the web
page; (2) APV (additive page view) is defined as a different type of page view
event logged when the user scrolls down the web page for a certain number of
pixels, such that the user is viewing different content compared with the
initial screen when the page was initiated. Therefore, if there is an APV
logged on a page, there must be a preceding CPV. Although these two metrics
are often correlated, CPV measures how frequently a user visits a certain
page, while APV measures the depth of content consumption on the page.

The launch criteria for the new site was not met due to the decline observed
in the initial experiment results. There was a significant decline by $10.3\%$
in CPV, a significant increase by $14.0\%$ in APV, and insignificant decline
in days visited and sessions. The trade-off of CPV to increased APV was
expected with the change of page layout. However, the magnitude of CPV decline
was too large to neglect. Further analysis at segment level is required to
pinpoint the areas for improvement in future iteration.

###  IV-B Segment Definition Period and Experiment Period

Before the formal experiment (A/B test) started, we set up a so-called A/A
test [5]. In the A/A test, users were split into a control group and a test
group without any change applied. A/A test enabled us to validate if there was
any pre-existing difference between the test group and the control group. In
this example, two weeks of A/A testing was performed, and the A/A test period
was used as the segment definition period. A/B test started after the
completion of A/A testing. One week of A/B test data were used for the
experiment analysis.

###  IV-C User Features for Creating Segments

As described in Section IV-A, page engagement is measured by CPV and APV which
are used as segmentation features. In addition, frequency metrics days visited
per week and sessions per visited day, and search clicks are also included for
defining user segments in this example. Below is the list of segmentation
features measured for each user:

  * •

vdays_per_week: Average number of visiting days per week on Yahoo Finance
site.

  * •

sessions_per_vdays: Average sessions per days visited.

  * •

articles_cpv_per_session: Average CPVs on article page per session.

  * •

articles_apv_per_session: Average APVs on article page per session.

  * •

charts_cpv_per_session: Average CPVs on stock charts page per session.

  * •

charts_apv_per_session: Average APVs on stock charts page per session.

  * •

homepage_cpv_per_session: Average CPVs on Yahoo Finance homepage per session.

  * •

homepage_apv_per_session: Average APVs on Yahoo Finance homepage per session.

  * •

lookup_cpv_per_session: Average CPVs on stock ticker symbol lookup page per
session.

  * •

lookup_apv_per_session: Average APVs on stock ticker symbol lookup page per
session.

  * •

market_data_cpv_per_session: Average CPVs on market data page per session.

  * •

market_data_apv_per_session: Average APVs on market data page per session.

  * •

message_boards_cpv_per_session: Average CPVs on message boards (user forum)
per session.

  * •

message_boards_apv_per_session: Average APVs on message boards per session.

  * •

personal_finance_cpv_per_session: Average CPVs on personal finance page per
session.

  * •

personal_finance_apv_per_session: Average APVs on personal finance page per
session.

  * •

quotes_cpv_per_session: Average CPVs on individual stock quote page per
session.

  * •

quotes_apv_per_session: Average APVs on individual stock quote page per
session.

  * •

watchlist_cpv_per_session: Average CPVs on customized stock watch list page
per session.

  * •

watchlist_apv_per_session: Average APVs on customized stock watch list page
per session.

  * •

other_cpv_per_session: Other CPVs per session. Other CPVs are defined as CPVs
that do not belong to the pages in the categories above.

  * •

other_apv_per_session: Other APVs.

  * •

search_clicks_per_session: Number of clicks on the search button per session.

The feature engineering process described in Section II-C was applied to the
listed segmentation features. Out of the $23$ user features, $14$ principle
components were selected that explained $85\%$ of the variance in the original
feature space.

###  IV-D Creating Segments Using K-means

A k-means clustering algorithm was applied on the principle component feature
space to create the user clusters. As discussed, parameter $K$ must be chosen
based on certain criteria. Different $K$ values ($1,2,3,...,30$) are evaluated
by the BIC and DaviesBouldin index in Figure 1. When $K=14$, both loss
functions are close to the minimum; therefore, $K=14$ was chosen in this case
study. The remaining paper would assume $14$ clusters are adopted. Figure 2
shows $14$ clusters defined by k-means, and the average per-user metrics
measured in each cluster.

Figure 1: BIC and Davies-Bouldin Index for k-means with different number of
clusters K Figure 2: Average Per-User Metrics for Each Cluster Defined by
K-means Algorithm for Yahoo Finance. Green indicates high engagement, while
white denotes low engagement. There are a total of $14$ clusters defined by
the k-means algorithm. The x-axis shows the cluster label from k-means.

###  IV-E Behavioral Segment Name

Segments are named after the user engagement pattern defined in Figure 2. Note
that each segment is evaluated at different features in original scale,
instead of in the principle component space. For example, segment $1$ is named
as “Article Only” because it has a high number of article page views and low
engagement on other pages. Segment $2$ is named as “Tourist & Quotes” with a
relatively high quotes page CPV and generally low engagement everywhere. Table
I shows all the behavioral segment names inferred from the user engagement
pattern.

TABLE I: Behavioral Segment Names for k-means Clusters K-means Cluster | Behavioral Segment Name
---|---
Cluster 1 | Article Only
Cluster 2 | Tourists & Quotes
Cluster 3 | Homepage & Hybrid Moderate
Cluster 4 | Homepage & Hybrid High
Cluster 5 | Quotes Only
Cluster 6 | Quotes & Search
Cluster 7 | Watchlist Only
Cluster 8 | Quotes & Charts
Cluster 9 | Quotes & Message Board
Cluster 10 | Quotes & Other
Cluster 11 | Quotes & Lookup
Cluster 12 | Quotes & Market Data
Cluster 13 | Personal Finance
Cluster 14 | Lookup & Quotes

###  IV-F Preliminary Segment Analysis

Figure 3: Preliminary View of Segment Importance Measured by Contribution to
Experiment Metrics

Figure 3 shows the percentage of each segment’s contribution to four total
engagement metrics (user_count, days_visited, sessions, and CPV) during the
segment definition period. It is worth noting that the segments’ contribution
to user engagement is not proportional to segment size (user count). Some
larger segments including “Tourist & Quotes” and “Article Only” contribute to
a relatively small proportion of user engagement. Conversely, smaller segments
such as “Homepage & Hybrid High”, “Watchlist Only”, “Quotes & Message Board”
and “Quotes & Other” contribute to a large proportion of user engagement
relative to their size. This analysis revealed that “Homepage & Hybrid High”
is the main contributor to overall engagement (days_visited, sessions, and
CPV).

###  IV-G Segment-Level Treatment Effect

TABLE II: Segment Treatment Effect: Difference in Average Per-User Metrics between Test and Control by Segment (n/a is shown for segments whose sample sizes are too small for analysis ($<1\%$)) Segment | Users | days_visited | sessions | cpv
---|---|---|---|---
Total | $100\%$ | $-1\%$ | $-2\%$ | $-10\%$
Article Only | $10\%$ | $0\%$ | $0\%$ | $3\%$
Homepage & Hybrid High | $15\%$ | $-2\%$ | $-5\%$ | $-15\%$
Homepage & Hybrid Moderate | $7\%$ | $-3\%$ | $-3\%$ | $-8\%$
Lookup & Quotes | $<1\%$ | n/a | n/a | n/a
Personal Finance | $<1\%$ | n/a | n/a | n/a
Quotes & Charts | $1\%$ | $-6\%$ | $-9\%$ | $-12\%$
Quotes & Lookup | $<1\%$ | n/a | n/a | n/a
Quotes & Market Data | $<1\%$ | n/a | n/a | n/a
Quotes & Message Board | $1\%$ | $-3\%$ | $-6\%$ | $-19\%$
Quotes & Other | $1\%$ | $2\%$ | $-1\%$ | $-20\%$
Quotes & Search | $1\%$ | $-5\%$ | $-10\%$ | $-26\%$
Quotes Only | $2\%$ | $0\%$ | $0\%$ | $-10\%$
Tourists & Quotes | $9\%$ | $-1\%$ | $2\%$ | $4\%$
Watchlist Only | $2\%$ | $-2\%$ | $-8\%$ | $-9\%$
Unseen | $49\%$ | $-1\%$ | $1\%$ | $-5\%$

During the experiment period, the treatment effect in each segment can be
measured by comparing the control and test users within the segment. In Table
II, the treatment effect is measured by three per-user metrics: days_visited,
sessions and CPV. Segments “Homepage & Hybrid High”, “Quotes & Charts”,
“Quotes & Message Board”, “Quotes & Search”, and “Watchlist Only” have higher-
than-average declines comparing to the overall population (“Total”). These
segments are highlighted in yellow. In contrast, other segments have smaller
decline or even an increase in user engagement, such as “Article Only”,
“Tourists & Quotes” and “Unseen”. Note that segments “Lookup & Quotes”,
“Personal Finance”, “Quotes & Lookup” and “Quotes & Market Data” have
extremely small sample sizes. As a result, the results of these segments are
labeled as “n/a”. This analysis indicated negative user experiences on
Homepage, Quotes, and Watchlist should be addressed and corrected.

###  IV-H Identifying High-impact Segments

Figure 4: Percentage Contribution to Total Drop in CPV by Segment

In this step we will determine the driver segments of the overall engagement
decline, particularly in CPV. Figure 4 shows the proportion of each segment’s
contribution to the overall CPV decline. The top three high-impact segments
are: “Homepage & Hybrid High” “Quotes & Message Board” and “Unseen”. The
“Unseen” segment has a large sample size but its average per-user decline is
relatively small as shown in Table II. Based on the results from this step and
Section IV-G, the team decided to identify and fix the user experience issues
for segments “Homepage & Hybrid High” and “Quotes & Message Board” as a
priority.

###  IV-I Follow-up Root Cause Analysis

Figure 5: CPV Difference between Test and Control by Page Type and Segment

In order to pinpoint the root cause of CPV drop for the two high-impact
segments identified in IV-H, we further measured CPV by page types. Figure 5
shows that segment “Homepage & Hybrid High” lost most CPV on quotes page.
Interestingly, the CPV decline on finance homepage itself was smaller for this
homepage segment. Because finance homepage is a main source of traffic
referral to quotes page, we suspected that path from finance homepage to
finance quotes page was blocked. Comparing the interface of new design to the
old, we determined that this drop was due to the removal of two quotes-related
modules. Original motivation of removing these two modules was to create space
for new features; however, the large drop in quotes CPV was critical and
should be fixed.

TABLE III: Overall Treatment Effect (% Difference is defined as the relative difference (using the control mean as a baseline) between the treatment mean and control mean of the per-user level metric) | Before Fix | After Fix
---|---|---
Metric | % Difference | Significant | % Difference | Significance
days_visited | $-0.7\%$ |  Not Significant ($p>0.05$) | $0.3\%$ |  Not Significant ($p>0.05$)
sessions | $-1.9\%$ |  Not Significant ($p>0.05$) | $-1.2\%$ |  Not Significant ($p>0.05$)
cpv | $-10.3\%$ |  Significant ($p<0.05$) | $-6.1\%$ |  Significant ($p<0.05$)
apv | $14.0\%$ |  Significant ($p<0.05$) | $35.1\%$ |  Significant ($p<0.05$)
TABLE IV: Segment Level Treatment Effect (% Difference is defined as the relative difference (using the control mean as a baseline) between the treatment mean and control mean of the per-user level metric) | % Difference in cpv
---|---
Segment | Before Fix | After Fix
Homepage & Hybrid High | $-15\%$ | $-9\%$
Homepage & Hybrid Moderate | $-8\%$ | $6\%$

For segment “Quotes & Message Board”, the decline was driven by the CPV loss
in message board as shown in Figure 5. There are separate message board forums
for test group and control group. Test group has a much smaller sample size
than control group by design, as a result, there are much less user-generated
content on the test message board compared to the control message board.
Therefore, the CPV drop observed in segment “Quotes & Message Board” can be
explained by this network effect. This decline is expected and should recover
when the new design is released to $100\%$ population.

###  IV-J Impact on Product Development

Based on the analysis described above, we added back two quote-related modules
on finance homepage. After the fix, another round of experiment was performed
to verify the result. Table III showed that the fix resulted in a sizable
recovery of CPV as well as a larger increase in APV. Table IV further verified
that significant improvement happened to homepage-related segments “Homepage &
Hybrid High” and “Homepage & Hybrid Moderate”.

##  V Conclusions

Controlled experimentation has become an integral part of iterative
development cycle of web products and mobile applications [2]. In this paper
we described how to define and utilize user behavioral segments in
experimentation. By using the data of user engagement with individual product
components as input, this method defines segments that are closely related to
the features being evaluated in an A/B test. Analysis with these segments
offers deep, actionable insights by answering the “why” question raised in
Section I. In comparison to a direct page view analysis by paths or referrals,
segmentation enables experiment owners to study a broader range of metrics
including frequency metrics such as sessions. In the example of Yahoo Finance
site redesign experiment, we demonstrated that the proposed method
successfully improved user engagement by informing a critical design fix on
Finance homepage.

When segmentation is used together with experimentation, several pitfalls have
been discussed in previous works. For example, running an analysis on a large
number of segments may lead to inflated false positives ([6]). Simpson’s
paradox may arise when combining segment results ([30]). Further, the
experiment effect on one segment cannot be simply generalized to the overall
population ([7]).

It is important to note that the defined segments must be independent of the
experiment treatment. Otherwise, it can introduce bias in the analysis. For
example, if user segments are created based on their behavior during the
experiment period, comparison between the treatment group and the control
group will become invalid at segment level. This is because the behavior
pattern of treatment group may be shifted in the experiment period. In the
framework proposed in this paper, this bias is prevented by defining user
segments using pre-experiment data which is not impacted by the treatment
effect.

In addition to the provided example, we have applied the same approach in
various product tests at Yahoo. In future research, we look to develop a
scalable, computationally economical solution to the integration of behavioral
segmentation with our experimentation platform.

## Acknowledgment

We would like to extend our thanks to Maria Stone and Jon Malkin for
insightful discussion on this study, to Don Matheson, Nikhil Mishra and
Abhinav Chaturvedi for implementing our work in an analytics pipeline, and to
Prashant Ramarao, Charles Hartel and Trang Le for setting up the Yahoo Finance
experiment and developing the redesigned product to validate the fix.

## References

  * [1] S. Thrun, “The art of fast failure,” 2014, [$https://www.linkedin.com/pulse/20140913214142-260012998-the-art-of-fast-failure$; accessed 19-Feb-2015].
  * [2] E. Ries, _The lean startup: How today’s entrepreneurs use continuous innovation to create radically successful businesses_. Random House LLC, 2011.
  * [3] G. Keppel, W. H. Saufley, and H. Tokunaga, _Introduction to design and analysis: A student’s handbook_. Cambridge Univ Press, 1992.
  * [4] R. Kohavi, R. M. Henne, and D. Sommerfield, “Practical guide to controlled experiments on the web: listen to your customers not to the hippo,” in _Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining_. ACM, 2007, pp. 959–967.
  * [5] R. Kohavi, R. Longbotham, D. Sommerfield, and R. M. Henne, “Controlled experiments on the web: survey and practical guide,” _Data mining and knowledge discovery_ , vol. 18, no. 1, pp. 140–181, 2009.
  * [6] R. Kohavi, A. Deng, B. Frasca, T. Walker, Y. Xu, and N. Pohlmann, “Online controlled experiments at large scale,” in _Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining_ , ser. KDD ’13. New York, NY, USA: ACM, 2013, pp. 1168–1176. [Online]. Available: http://doi.acm.org/10.1145/2487575.2488217
  * [7] R. Kohavi, A. Deng, R. Longbotham, and Y. Xu, “Seven rules of thumb for web site experimenters,” in _Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining_. ACM, 2014, pp. 1857–1866.
  * [8] D. Tang, “Experimentation at google,” _RecSys’14 Workshop: Controlled Experimentation_ , 2014.
  * [9] B. Frasca, “A brief history of bing a/b,” _RecSys’14 Workshop: Controlled Experimentation_ , 2014.
  * [10] C. Smallwood, “The quest for the optimal experiment,” _RecSys’14 Workshop: Controlled Experimentation_ , 2014.
  * [11] Z. Zhao, M. Chen, D. Matheson, and M. Stone, “Online experimentation diagnosis and troubleshooting beyond aa validation,” in _Data Science and Advanced Analytics (DSAA), 2016 IEEE International Conference on_. IEEE, 2016, pp. 498–507.
  * [12] M. Wedel and W. A. Kamakura, _Market segmentation: Conceptual and methodological foundations_. Springer Science & Business Media, 2012, vol. 8.
  * [13] S. Tu and C. Lu, “Topic-based user segmentation for online advertising with latent dirichlet allocation,” in _International Conference on Advanced Data Mining and Applications_. Springer, 2010, pp. 259–269.
  * [14] J. Yan, N. Liu, G. Wang, W. Zhang, Y. Jiang, and Z. Chen, “How much can behavioral targeting help online advertising?” in _Proceedings of the 18th international conference on World wide web_. ACM, 2009, pp. 261–270.
  * [15] P. I. Hofgesang, “Web personalisation through incremental individual profiling and support-based user segmentation,” in _Proceedings of the IEEE/WIC/ACM international conference on web intelligence_. IEEE Computer Society, 2007, pp. 213–220.
  * [16] M. Maia, J. Almeida, and V. Almeida, “Identifying user behavior in online social networks,” in _Proceedings of the 1st workshop on Social network systems_. ACM, 2008, pp. 1–6.
  * [17] Y. K. Zhou and B. Mobasher, “Web user segmentation based on a mixture of factor analyzers,” in _International Conference on Electronic Commerce and Web Technologies_. Springer, 2006, pp. 11–20.
  * [18] Y. Xu, N. Chen, A. Fernandez, O. Sinno, and A. Bhasin, “From infrastructure to culture: A/b testing challenges in large scale social networks,” in _Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_. ACM, 2015, pp. 2227–2236.
  * [19] R. Kohavi and R. Longbotham, “Unexpected results in online controlled experiments,” _ACM SIGKDD Explorations Newsletter_ , vol. 12, no. 2, pp. 31–35, 2011.
  * [20] H. Xie and J. Aurisset, “Improving the sensitivity of online controlled experiments: Case studies at netflix,” in _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_. ACM, 2016, pp. 645–654.
  * [21] Y. He and M. Chen, “A probabilistic, mechanism-indepedent outlier detection method for online experimentation,” in _Data Science and Advanced Analytics (DSAA), 2017 IEEE International Conference on_. IEEE, 2017.
  * [22] E. Keogh and A. Mueen, “Curse of dimensionality,” in _Encyclopedia of Machine Learning_. Springer, 2011, pp. 257–258.
  * [23] I. Jolliffe, _Principal component analysis_. Wiley Online Library, 2002.
  * [24] D. Beeferman and A. Berger, “Agglomerative clustering of a search engine query log,” in _Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining_. ACM, 2000, pp. 407–416.
  * [25] D. Reynolds, “Gaussian mixture models,” _Encyclopedia of biometrics_ , pp. 827–832, 2015.
  * [26] M. Ester, H.-P. Kriegel, J. Sander, X. Xu _et al._ , “A density-based algorithm for discovering clusters in large spatial databases with noise.” in _Kdd_ , vol. 96, no. 34, 1996, pp. 226–231.
  * [27] G. Hamerly, C. Elkan _et al._ , “Learning the k in k-means,” in _NIPS_ , vol. 3, 2003, pp. 281–288.
  * [28] R. E. Kass and L. Wasserman, “A reference bayesian test for nested hypotheses and its relationship to the schwarz criterion,” _Journal of the american statistical association_ , vol. 90, no. 431, pp. 928–934, 1995.
  * [29] D. L. Davies and D. W. Bouldin, “A cluster separation measure,” _IEEE transactions on pattern analysis and machine intelligence_ , no. 2, pp. 224–227, 1979.
  * [30] T. Crook, B. Frasca, R. Kohavi, and R. Longbotham, “Seven pitfalls to avoid when running controlled experiments on the web,” in _Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining_. ACM, 2009, pp. 1105–1114.