#!/usr/bin/env python
# coding: utf-8

# In[1]:


from IPython.display import Image
Image('../../Python_probability_statistics_machine_learning_2E.png',width=200)


# # Projection Methods
# <div id="ch:prob:sec:projection"></div>
# 
# The concept of
# projection is key to developing an intuition about conditional
# probability.  We
# already have a natural intuition of projection from looking at
# the shadows of
# objects on a sunny day. As we will see, this simple idea
# consolidates many
# abstract ideas in optimization and mathematics.  Consider
# [Figure](#fig:probability_001) where we want to find a point along the blue
# line
# (namely, $\mathbf{x}$) that is closest to the black square (namely,
# $\mathbf{y}$). In other words, we want to inflate the gray circle until it just
# touches the black line. Recall that the circle boundary is the set of points for
# which
# 
# $$
# \sqrt{(\mathbf{y}-\mathbf{x})^T(\mathbf{y}-\mathbf{x})}
# =\|\mathbf{y}-\mathbf{x} \| = \epsilon
# $$
# 
#  for some value of $\epsilon$. So we want a point $\mathbf{x}$ along
# the line
# that satisfies this for the smallest $\epsilon$.  Then, that point
# will be the
# closest point on the black line to the black square.
# It may be obvious from the
# diagram, but the closest point on the line
# occurs where the line segment from
# the black square to the black line is
# perpedicular to the line. At this point,
# the gray circle just touches the black
# line. This is illustrated below in
# [Figure](#fig:probability_002).
# 
# <!-- dom:FIGURE: [fig-
# probability/probability_001.png, width=500 frac=0.90] Given the point
# $\mathbf{y}$ (black square) we want to find the $\mathbf{x}$ along the line that
# is closest to it. The gray circle is the locus of points within a fixed distance
# from $\mathbf{y}$. <div id="fig:probability_001"></div> -->
# <!-- begin figure
# -->
# <div id="fig:probability_001"></div>
# 
# <p>Given the point $\mathbf{y}$ (black
# square) we want to find the $\mathbf{x}$ along the line that is closest to it.
# The gray circle is the locus of points within a fixed distance from
# $\mathbf{y}$.</p>
# <img src="fig-probability/probability_001.png" width=500>
# <!-- end figure -->
# 
# 
# **Programming Tip.**
# 
# [Figure](#fig:probability_001) uses
# the `matplotlib.patches` module.  This
# module contains primitive shapes like
# circles, ellipses, and rectangles that
# can be assembled into complex graphics.
# After importing a particular shape, you
# can apply that shape to an existing axis
# using the `add_patch` method.  The
# patches themselves can by styled using the
# usual formatting keywords like
# `color` and `alpha`.
# 
# 
# 
# <!-- dom:FIGURE: [fig-
# probability/probability_002.png, width=500 frac=0.90] The closest point on the
# line occurs when the line is tangent to the circle. When this happens, the black
# line and the line (minimum distance) are perpedicular.  <div
# id="fig:probability_002"></div> -->
# <!-- begin figure -->
# <div
# id="fig:probability_002"></div>
# 
# <p>The closest point on the line occurs when
# the line is tangent to the circle. When this happens, the black line and the
# line (minimum distance) are perpedicular.</p>
# <img src="fig-
# probability/probability_002.png" width=500>
# 
# <!-- end figure -->
# 
# 
#  Now that we
# can see what's going on, we can construct the the solution
# analytically. We can
# represent an arbitrary point along the black line as:
# 
# $$
# \mathbf{x}=\alpha\mathbf{v}
# $$
# 
#  where $\alpha\in\mathbb{R}$ slides the point up and down the line with
# 
# $$
# \mathbf{v} = \left[ 1,1 \right]^T
# $$
# 
#  Formally, $\mathbf{v}$ is the *subspace* onto which we want to
# *project*
# $\mathbf{y}$. At the closest point, the vector between
# $\mathbf{y}$ and
# $\mathbf{x}$ (the *error* vector above) is
# perpedicular to the line. This means
# that
# 
# $$
# (\mathbf{y}-\mathbf{x} )^T \mathbf{v} = 0
# $$
# 
#  and by substituting and working out the terms, we obtain
# 
# $$
# \alpha = \frac{\mathbf{y}^T\mathbf{v}}{ \|\mathbf{v} \|^2}
# $$
# 
#  The *error* is the distance between $\alpha\mathbf{v}$ and $
# \mathbf{y}$.  This
# is a right triangle, and we can use the Pythagorean
# theorem to compute the
# squared length of this error as
# 
# $$
# \epsilon^2 = \|( \mathbf{y}-\mathbf{x} )\|^2 = \|\mathbf{y}\|^2 - \alpha^2
# \|\mathbf{v}\|^2 = \|\mathbf{y}\|^2 -
# \frac{\|\mathbf{y}^T\mathbf{v}\|^2}{\|\mathbf{v}\|^2}
# $$
# 
#  where $ \|\mathbf{v}\|^2 = \mathbf{v}^T \mathbf{v} $. Note that since
# $\epsilon^2 \ge 0 $, this also shows that
# 
# $$
# \| \mathbf{y}^T\mathbf{v}\| \le \|\mathbf{y}\|  \|\mathbf{v}\|
# $$
# 
#  which is the famous and useful Cauchy-Schwarz inequality which we
# will exploit
# later. Finally, we can assemble all of this into the *projection*
# operator
# 
# $$
# \mathbf{P}_v = \frac{1}{\|\mathbf{v}\|^2 } \mathbf{v v}^T
# $$
# 
#  With this operator, we can take any $\mathbf{y}$ and find the closest
# point on
# $\mathbf{v}$ by doing
# 
# $$
# \mathbf{P}_v \mathbf{y} = \mathbf{v} \left( \frac{  \mathbf{v}^T \mathbf{y}
# }{\|\mathbf{v}\|^2} \right)
# $$
# 
#  where we recognize the term in parenthesis as the $\alpha$ we
# computed earlier.
# It's called an *operator* because it takes a vector
# ($\mathbf{y}$) and produces
# another vector ($\alpha\mathbf{v}$). Thus,
# projection unifies geometry and
# optimization.
# 
# ## Weighted distance
# 
# We can easily extend this projection
# operator to cases where the measure of
# distance between $\mathbf{y}$ and the
# subspace $\mathbf{v}$ is weighted. We can
# accommodate these weighted distances
# by re-writing the projection operator as
# 
# <!-- Equation labels as ordinary links -->
# <div id="eq:weightedProj"></div>
# 
# $$
# \begin{equation}
# \mathbf{P}_v=\mathbf{v}\frac{\mathbf{v}^T\mathbf{Q}^T}{\mathbf{v}^T\mathbf{Q v}}
# \end{equation}
# \label{eq:weightedProj} \tag{1}
# $$
# 
#  where $\mathbf{Q}$ is positive definite matrix.  In the previous
# case, we
# started with a point $\mathbf{y}$ and inflated a circle centered at
# $\mathbf{y}$
# until it just touched the line defined by $\mathbf{v}$ and this
# point was
# closest point on the line to $\mathbf{y}$. The same thing happens
# in the general
# case with a weighted distance except now we inflate an
# ellipse, not a circle,
# until the ellipse touches the line.
# 
# <!-- # @@@CODE src-
# probability/Projection.py fromto: ^theta@^fig,ax -->
# 
# <!-- dom:FIGURE: [fig-
# probability/probability_003.png, width=500 frac=0.95] In the weighted case, the
# closest point on the line is tangent to the ellipse and is still perpedicular in
# the sense of the weighted distance. <div id="fig:probability_003"></div> -->
# <!-- begin figure -->
# <div id="fig:probability_003"></div>
# 
# <p>In the weighted
# case, the closest point on the line is tangent to the ellipse and is still
# perpedicular in the sense of the weighted distance.</p>
# <img src="fig-
# probability/probability_003.png" width=500>
# 
# <!-- end figure -->
# 
# 
# Note that the
# error vector ($\mathbf{y}-\alpha\mathbf{v}$) in [Figure](#fig:probability_003)
# is still perpendicular to the line (subspace
# $\mathbf{v}$), but in the space of
# the weighted distance.  The difference
# between the first projection (with the
# uniform circular distance) and the
# general case (with the elliptical weighted
# distance) is the inner product
# between the two cases.  For example, in the first
# case we have $\mathbf{y}^T
# \mathbf{v}$ and in the weighted case we have
# $\mathbf{y}^T \mathbf{Q}^T
# \mathbf{v}$. To move from the uniform circular case
# to the weighted ellipsoidal
# case, all we had to do was change all of the vector
# inner products.  Before we
# finish, we need a formal property  of projections:
# 
# $$
# \mathbf{P}_v \mathbf{P}_v = \mathbf{P}_v
# $$
# 
#  known as the *idempotent* property which basically says that once we
# have
# projected onto a subspace, subsequent projections leave us in the
# same subspace.
# You can verify this by computing Equation [1](#eq:weightedProj).
# 
# Thus,
# projection ties a minimization problem (closest point to a line) to an
# algebraic
# concept (inner product). It turns out that these same geometric ideas
# from
# linear algebra [[strang2006linear]](#strang2006linear) can be translated to the
# conditional
# expectation. How this works is the subject of our next  section.