蒙蒂大厅（Monty Hall）是非常有趣同时有争议的概率问题，问题看似简单，但正确答案如此有悖于常理以致很多人无法接受。

蒙蒂大厅游戏是这样的：你来参加节目，主持人蒙蒂向你展示三个关闭的门，并告诉你其中一扇门后有汽车作为奖励，另外两扇门后并没有任何奖励，现在你需要选择一扇门，此时，为了增加悬念，在你打开折扇门前，蒙蒂会从另外两扇门中随机选择一个没有奖品的打开，并且问你，是要坚持之前的选择还是换一扇门。

很多人会觉得这个时候，没开的两扇门肯定有一个有奖品，因此概率各为0.5，因此选哪个都一样，那么事实是否如此呢？

我们首先数学化这个故事：

设三个门分别问A，B和C，观众随机选择了门A，蒙蒂随机打开了门B，我们设三个门后面有奖品的概率为$P(H_A),P(H_B),P(H_C)$，那么可知$P(H_A)+P(H_B)+P(H_C) = 1$，另外，由于‘蒙蒂随机打开了门B’是结果事件，因此我们把该结果事件用$Y=B$表示，我们设在门A有奖品的条件下蒙蒂打开门B的概率为$P(Y=B|H_A)$，同理，在门B或门C有奖品的条件下，蒙蒂打开门B，门C的概率为$P(Y=B|H_B),P(Y=B|H_C)$。很显然，在门B后有奖品条件下蒙蒂不可能打开门B，因此$P(Y=B|H_B)=0$，那么我们的决策是要求，在蒙蒂打开门B的条件下，门A，门C后面有奖品的概率$P(H_A|Y=B),P(H_C|Y=B)$，很显然，这是一个贝叶斯概率问题，

$$P(H_A|Y)=\frac{P(Y|H_A)P(H_A)}{P(Y|H_A)P(H_A) + P(Y|H_C)P(H_C)}$$

$$P(H_C|Y)=\frac{P(Y|H_C)P(H_C)}{P(Y|H_A)P(H_A) + P(Y|H_C)P(H_C)}$$

计算可得，$P(H_A|Y=B)=\frac{1}{3},P(H_C|Y=B)=\frac{2}{3}$，由此可以看出，选A和C的概率并不一样。

《贝叶斯思维：统计建模的PYTHON学习法》：

很多人搞错的原因是，以为要求的是$P(H_A),P(H_C)$，确实，这两个是一样概率，但是实际要求得是$P(H_A|Y=B),P(H_C|Y=B)$，而这两个和似然概率$P(Y|H_A),P(Y|H_C)$有关，而这两个概率是不一样的。因此在求概率时候，一定要注意条件概率。

约束条件优化问题：

$$\min f_{0}(x)\\\begin{align}s.t. f_{i}(x)\leq 0,i=1,2......m \\h_{i}(x)=0,i=1,2......m\end{align}$$

记约束条件为可行域D:

$D=\{x|f_{i}(x)\leq0,i=1,2...m;h_{i}(x)=0,i=1,2...p\}$

引入：

Lagrangian 函数：

$L(x,\lambda,v)=f_{0}(x)+\sum_1^m\lambda_{i}f_{i}(x)+\sum_1^pv_{i}h_{i}(x) \;\;s.t.\lambda_{i}\leq0$

Lagrangian dual 函数：

$g(\lambda,v)=\min_{x}L(x,\lambda,v)$

 

则知当$x\in D,\lambda\geq0$时有，

$$L(x,\lambda,v)\leq f_{0}(x)$$

因为在满足约束条件$D$时，$f_{i}(x)\leq 0$且$h_{i}(x)\geq 0$，所以

$$L(x,\lambda,v)=f_{0}(x)+\sum_1^m\lambda_{i}f_{i}(x)+\sum_1^pv_{i}h_{i}(x)\leq f_{0}(x)$$

，因而

$$\min_{x\in R^{n}}L(x,\lambda,v)\leq \min_{x\in D}L(x,\lambda,v)\leq \min_{x\in D}f_{0}(x)=p^{*}$$

也就是说，无约束条件的拉格朗日函数最小值，要小于有约束条件的拉格朗日函数最小值，要小于原函数的最小值$p^{*}$，因此为了找到最优指（也就是拉格朗日下界中离原函数最近的点），再求对偶函数的最大值即可：

$$\max_{\lambda,v} \min_{x\in R^{n}}L(x,\lambda,v),\\s.t. \lambda\geq 0,$$

最后两个式子也成对偶问题的最优值$d^{*}$，对偶问题的最优值是原始问题的最优值$p^{*}$的一个下届，原始问题的最优值和对偶问题的最优值之差$p^{*}-d^{*}$称为原始问题的对偶间隙，且该间隙永远非负。间隙不为0时，称为弱对偶问题，间隙为0时，称为强对偶问题。

 

1. 直接计算
2. 共轭先验
3. gaussian approximation
4. MCMC

P224 "Machine learning: A probability perspective"

优化问题

在regression中通常要对参数求解，通过计算$\theta$使得loss function最小，或者MLE估计最大，在有函数形式的问题中，通常采用的是牛顿梯度下降法，或者拟牛顿法(BFGS)。下面我介绍下R中如何利用已有函数来求解参数，以及如何手工计算。

例1. 目标函数为Rosenbrock Banana function：
$f(x,y) = 100*(y-x^2)^2+(1-x)^2$
要求$f(x,y)$取最小值时的$x,y$，即一阶导为0的点，也就是一阶导数的根。方法采用牛顿梯度下降法，需要用到一阶导Jacobian矩阵，和二阶导Hessian矩阵。

手工计算：

Jacobian matrix:$J(x,y) = \begin{bmatrix}-400*x(y-x^2) -2*(1-x)\\200*(y-x^2) \end{bmatrix}$

Hessian matrix:$H(x,y)=\begin{bmatrix}800*x+2 & -400 \\-400*x & 200 \end{bmatrix}$

x,y 的迭代公式为：(P249, "Machine Learning: A probability perspective")

R code如下：

fr = function(x) {   ## Rosenbrock Banana function
  x1 = x[1]
  x2 = x[2]
  100 * (x2 - x1 * x1)^2 + (1 - x1)^2
}

library(numDeriv)
x = NULL
x0 = c(110,210)
x = rbind(x,x0)
i = 1
for(i in 2:100){
  gk = jacobian(fr,x[i-1,])
  hk = hessian(fr,x[i-1,])
  dk = -solve(hk) %*% t(gk)
  xnew = x[i-1,] + t(dk)
  x = rbind(x,xnew)
  rownames(x)[i] = paste0("x",i-1)
  if(abs(sum(x[i,] - x[i-1,])) < 0.00001){
    break
  }
}

结果如下：

可以看出，从起始点110, 210，通过迭代，到最后1, 1点收敛，说明极值点为(1,1)

optim() in R:

optim(par=c(3,3),fn=fr,method="BFGS")

结果如下：

optim中par表示待估参数初始值，fn表示目标函数，method为采用的方法，BFGS为较多使用的，拟牛顿法。注意不同的初始值可能收敛于不同点。

例2. logistics regression

负的MLE函数为:$l(w^{T}) = -\sum y_{i}log(p_{b})+(1-y_{i})log(1-p_{i})$

其中$p_{i}=\frac{1}{1+e^{-w^{T}X_{i}}}=sigmoid(x)$

因此我们可以写出目标函数的代码，并且利用optim进行参数优化：

手工计算：

f1 = function(data,w){
  p = 1/(1+exp(-w[1] - w[2]* data$gre - w[3]*data$gpa - w[4]*data$rank))
  mle = -sum(data$admit * log(p) + (1-data$admit )* log(1-p))
  mle
}

f2 = function(data,w){
  x = data[,1:3]
  y = data[,4]
  w = as.matrix(w)
  p = 1/(1+exp(-x%*%w))
  mle = -sum(y * log(p) + (1-y)* log(1-p))
  mle
}

mydata <- read.csv("http://pingax.com/wp-content/uploads/2013/12/data.csv")
m <- as.matrix(mydata)
m <- cbind(rep(1,nrow(m)),m)
optim(par=c(0,0,0),fn=f2,data=m,method="BFGS")

结果如下：

我们用glm logistics regression 来检验：

可以看出结果非常接近。