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
    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
    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
    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$ 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$ Dec 2, 2019 at 15:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.