0
$\begingroup$

This could be a simple question but I don't have a satisfying answer.

Setup. Suppose that we have $K$ different classes, and consider cross entropy loss which maps a probability vector in the probability simplex ($K$-dimensions) and a label $y \in [K]$ to a loss as follows:

$\ell(p, y) = -\log p_y$

Now suppose that we have a discrete random variable $\Phi$, and we want to find $w$ that maps $\Phi$ to probability simplex, and solve the following optimization problem

$\min_w \mathbb{E}[\ell(w(\Phi), Y)]$

We know that, by essentially Gibbs' inequality, the optimal solution $w^*$ must satisfy:

$w^*(r) = \Pr[Y=y\ |\ \Phi=r]$

My question. What happens if $\Phi$ is a continuous random variable? What is the characterization of the optimal solution?

$\endgroup$

1 Answer 1

1
$\begingroup$

$\newcommand{\Si}{\Sigma}$ It does not matter whether the random variable (r.v.) $R:=\Phi$ is discrete or continuous or neither; it can be any r.v. whatsoever, with values in any measurable space $(S,\Si)$. Indeed, let $Y$ be any $[K]$-valued r.v. defined on the same probability space as $R$. For each $y\in[K]$, let $g_y\colon S\to\mathbb R$ be a $\Si$-measurable function such that $$g_y(R):=g_y\circ R=E(I\{Y=y\}|R)[=P(Y=y|R)], \tag{1} $$ where $I$ denotes the indicator and $E(\cdot|R)$ denotes the conditional expectation given the r.v. $R$. So, for each measurable map $w$ from $S$ to the probability $K$-simplex (say $V_K$), \begin{align} E\ell(w(R),Y)&=E\sum_{y\in[K]}\ell(w(R),y)I\{Y=y\} \\ &=\sum_{y\in[K]}E\ell(w(R),y)I\{Y=y\} \\ &=\sum_{y\in[K]}EE(\ell(w(R),y)I\{Y=y\}|R) \\ &=\sum_{y\in[K]}E\ell(w(R),y)E(I\{Y=y\}|R) \\ &=\sum_{y\in[K]}E\ell(w(R),y)g_y(R) \\ &=E\sum_{y\in[K]}\ell(w(R),y)g_y(R) \\ &=\int_S P(R\in dr)\sum_{y\in[K]}\ell(w(r),y)g_y(r) \\ &=-\int_S P(R\in dr)\sum_{y\in[K]}g_y(r)\ln w(r)_y \\ &=-\int_S P(R\in dr)H_r(w(r)), \end{align} where $$H_r(v):=\sum_{y\in[K]}g_y(r)\ln v_y $$ for $v\in V_K$. So, the minimization of $E\ell(w(R),Y)$ in all measurable functions $w\colon S\to V_K$ boils down to the maximization, for each $r\in S$, of $H_r(v)$ in $v\in V_K$. We can choose the versions of the conditional expectations $g_1(R),\dots,g_K(R)$ of $I\{Y=1\},\dots,I\{Y=K\}$ so that these conditional expectations are everywhere nonnegative and sum to $1$. That is, $g_y(r)\ge0$ for all $r\in S$ and $y\in[K]$, and $\sum_{y\in[K]}g_y(r)=1$ for all $r\in S$.

Then it is easy to see that $H_r(v)$ is minimized in $v\in V_K$ if $v_y=g_y(r)$; this is just the nonnegativity of the Kullback-Leibler divergence. That is, the risk $E\ell(w(R),Y)$ is minimized in $w$ if for all $r\in S$ and $y\in[K]$ we have $$w(r)_y=g_y(r),$$ and $g_y(r)$ could be (generally, only symbolically) written as $P(Y=y|R=r)$ -- cf. (1).

$\endgroup$
10
  • $\begingroup$ My question is how is $\Pr[Y=y|R=r]$ well defined for a continuous random variable? According to the common definition of conditional probability, this is $\Pr[Y=y, R=r]/\Pr[R=r] = 0/0$ because $\Pr[R=r] = 0$? $\endgroup$
    – Xi Wu
    Commented Dec 2, 2019 at 4:30
  • $\begingroup$ Ok -- I see that it is indeed $g_y(r)$ and it is only symbolically written as $\Pr[Y=y|R=r]$ so my first comment should be viewed as to confirm that "normally, $\Pr[Y=y|R=r]$ is undefined after all". Second, in your (1) in the bracket $[=\Pr[Y=y|R]]$, for that if we conditioned on $R=r$ would it again be that things are undefined? Finally, you mentioned that "We can choose the versions of the conditional expectations $g_1(R), ..., g_K(R) so that...$ What does that mean? I have no issue with KL divergence part. In fact, my confusion is only about how $\Pr[Y=y|R=r]$ is defined. $\endgroup$
    – Xi Wu
    Commented Dec 2, 2019 at 5:11
  • $\begingroup$ My final question is that I do know a definition of $\Pr[Y=y|R=r]$ via disintegration. See Definition 1.1.23 of terrytao.files.wordpress.com/2011/08/matrix-book.pdf. If I use that definition, would it be possible to directly work out a proof similar to the discrete case? What is the relationship between that definition and your $g_y(r)$? $\endgroup$
    – Xi Wu
    Commented Dec 2, 2019 at 5:28
  • $\begingroup$ (i) In my answer, $P(Y=y|R=r)$ is defined as $g_y(r)$. (ii) Concerning "We can choose the versions of the conditional expectations $g_1(R),\dots,g_K(R)$ of $I\{Y=1\},\dots,I\{Y=K\}$ so that these conditional expectations are everywhere nonnegative and sum to $1$", I am not sure what is unclear to you here. Maybe, "versions"? $\endgroup$ Commented Dec 2, 2019 at 15:49
  • $\begingroup$ Previous comment continued: If so, note that the conditional expectation is defined only almost surely (a.s.): if $E(Z|X)$ is a (version of the) conditional expectation of $Z$ given $X$, then $E(Z|X)+u(X)$ is also such a version, for any measurable function $u$ such that $u(X)=0$ a.s., and all versions of $E(Z|X)$ are of this form, $E(Z|X)+u(X)$ with $u(X)=0$ a.s. This is somewhat similar to the notion of an antiderivative, where any two different versions of the antiderivative differ just by an additive constant. I have added details on this to the answer. $\endgroup$ Commented Dec 2, 2019 at 15:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .