Training set：\(\{(x^i, y^i); i = 1, ..., n\}\)
\(x^i\in{X}\): input(features)
\(y^i\in{Y}\): output
(1)continuous values——Regression
(2)discrete values——Classification
Supervised learning主要任务为找function
Given a training set, learn a function (hypothesis) \(h: X\to{Y}\) so that \(h(x)\) is a good predictor for \(y\).
Linear regression:
\(h(x)=\sum_{i=0}^d\theta_ix_i\)
\(x_0=1\)
d: number of input variables
\(\theta_i\): parameters decide how to map \(X\) to \(Y\)
如果模型确定，即function结构确定，则主要任务转换为找一组参数\(\theta\)
Given a training set, learn parameters \(\theta\) to make \(h(x)\) close to \(y\)
怎么定义close或者怎么衡量\(h(x)\)和\(y\)之间的距离？Cost function \(J(\theta)\)
方法之一为Least-squares cost function【最小二乘】: \(J(\theta)=\frac{1}{2}\sum_{i=1}^n(h_\theta(x^i)-y^i)^2\)
为什么常用Least-squares cost function？
一句话总结为：Under a set of probabilistic assumptions, least-squares regression corresponds to finding the maximum likelihood estimate of \(\theta\).
以下是推导：
—————————————————————
在推导之前，先复习概率、似然、参数
1、似然函数
似然函数=likelihood function=\(L(\theta)\)：把样本的联合密度函数视为关于参数\(\theta\)的函数
\(L(\theta)=L(x_1,...,x_n;\theta)=\Pi_{i=1}^np(x_i;\theta)\)
*概率密度函数：\(x\to{p(x|\theta)}\)
*似然函数：\(\theta\to{p(x|\theta)}\)
2、最大似然估计
使得似然函数\(L(\theta)\)取值最大的一组参数\(\theta\)
直觉上理解，已知某组参数能使当前样本出现的概率最大，而其它参数使当前样本出现的概率减小，所以干脆就把这组参数作为参数估计的真实值
*参数估计：已知总体分布的形式，根据样本数据推断分布的参数值【模型已定，参数未知】。比如总体数据符合正态分布，可以根据样本数据推断其均值和方差。可以理解为我们想用较少的参数去描述总体的分布，从而简化解决问题的过程
*非参数估计：未知总体分布形式，通过样本数据推断总体分布情况
最大似然估计、贝叶斯估计、最大后验估计均属于基于概率的参数估计方法
3、介绍上述三种基于概率的参数估计方法前，先介绍概率论的基本知识：先验概率、后验概率、条件概率、全概率、贝叶斯公式
假设\(y\)是果，\(x_i\)是因（\(y\)发生的各种原因，比如高血压的危险因素包括年龄、三高、肥胖、遗传等）
先验概率：基于经验或调查得到的某事件发生概率\(P(x_i)\)。比如所有人群中糖尿病发病率
后验概率：由果及某一个因的概率\(P(x_i|y)\)，这就是一个条件概率。比如高血压人群中患有糖尿病的概率
一般来说，先验概率易得，后验概率难得，因此，常用贝叶斯公式由先验概率求后验概率
\(P(x_i|y)=\frac{P(y|x_i)P(x_i)}{P(y)}\)
左侧\(P(x_i|y)\)为后验概率
右侧分子\(P(x_i)\)为先验概率
右侧分母\(P(y)\)为全概率，\(P(y)=\sum_iP(y|x_i)P(x_i)\)，这是一个累积因子
4、最大似然估计、贝叶斯估计、最大后验估计
（1）最大似然估计：
求使得\(L(\theta)=L(x_1,...,x_n;\theta)=\Pi_{i=1}^np(x_i;\theta)\)取max时的\(\theta\)
连乘易造成浮点运算下溢，因此常取对数形式的max：\(logL(\theta)=\sum_{i=1}^nlogp(x_i;\theta)\)
\(\theta^*=argmax\{\sum_{i=1}^nlogp(x_i;\theta)\}\)
求解时，将大括号中的式子对\(\theta\)求导，令为0，即可求出\(\theta^*\)
总之：1-取对数；2-求导令为0；3-求得\(\theta^*\)
缺点：
1、点估计，只能得到待估计参数的一个值，但有时我们想知道整个\(\theta\)在已知样本数据\(X\)后的分布情况，即\(p(\theta|X)\)
2、样本数据量不大时，用最大似然估计由样本估计总体分布可能不准确。例如我们要估计人的平均体重，但是抽样的人都是小孩，这样我们得到的平均体重就不能反映总体的分布，而我们应该把“小孩占总人口20%”的先验考虑进去。\(\longrightarrow\)这时我们可以用贝叶斯估计
(2)贝叶斯估计
利用贝叶斯公式，不仅考虑样本数据，还结合先验知识，以确定后验概率——\(p(\theta|X)\)
\(p(\theta|X)=\frac{p(X|\theta)p(\theta)}{p(X)}\)
此时，根据先验概率\(p(\theta)\)，概率密度函数\(p(x_i|\theta)\)，全概率公式\(p(X)=\int_\theta{p(X|\theta)p(\theta)d\theta}\)，求\(p(\theta|X)\)，若使其取max，则得\(\theta_B^*\)
缺点：求\(p(\theta|X)\)的过程有些多余，能不能直接求\(\theta_B^*\)？\(\longrightarrow\)这时我们可以用最大后验估计
（3）最大后验估计MAP
贝叶斯公式右边的分母\(p(X)\)与\(\theta\)无关，可以看成常量，因此求\(p(\theta|X)\)的max，即等价于求\(p(X|\theta)p(\theta)\)的max，我们同样先取对数，转变为求\(logp(X|\theta)+logp(\theta)\)的max，即\(\theta_MAP^*=argmax{logp(X|\theta)+logp(\theta)}\)
总结：
对先验概率的估计没信心\(\longrightarrow\)推荐最大似然估计
对先验概率的估计有信心，且只需要知道使后验概率最大的那个\(\theta\longrightarrow\)最大后验估计
需要得到整个\(\theta\)在已知样本数据\(X\)后的分布情况，即后验概率的分布\(\longrightarrow\)贝叶斯估计
——————————————————————
复习完毕，开始推导：
首先再回顾一下：如果模型已定&参数未知，则主要任务为根据已知样本数据找一组参数\(\theta\)，即Given a training set, learn parameters \(\theta\) to make \(h(x)\) close to \(y\)。需要进行参数估计。那么我们假设已定的模型是线性回归模型，使用最大似然估计参数。
线性回归模型：\(y^i=\theta^Tx^i+\epsilon^i\)
\(\epsilon^i\)是error term，可能原因为1-unmodeled effects，比如一些与预测非常相关但被我们在回归中落下的特征；2-random noise。我们假定\(\epsilon^i\)符合高斯分布且为IID=independently and identically distributed，即\(\epsilon^i\sim{N(0,\sigma^2)}\)
那么\(p(\epsilon^i)=\frac{1}{\sqrt{2\pi}\sigma}exp(-\frac{(\epsilon^i)^2}{2\sigma^2})\)
因为\(\epsilon^i=y^i-\theta^Tx^i\)
所以\(p(y^i|x^i;\theta)=\frac{1}{\sqrt{2\pi}\sigma}exp(-\frac{(y^i-\theta^Tx^i)^2}{2\sigma^2})\)
上式是概率密度函数，a distribution of \(y^i\) given \(x^i\) and parameterized by \(\theta\)（fixed value）
如果看成关于\(\theta\)的函数，则为似然函数
\(L(\theta)=L(\theta;X,Y)=p(Y|X;\theta)=\Pi_{i=1}^n{p(y^i|x^i;\theta)}=\Pi_{i=1}^n{\frac{1}{\sqrt{2\pi}\sigma}exp(-\frac{(y^i-\theta^Tx^i)^2}{2\sigma^2})}\)
取对数后为
\(logL(\theta)=\sum_{i=1}^n{log{\frac{1}{\sqrt{2\pi}\sigma}exp(-\frac{(y^i-\theta^Tx^i)^2}{2\sigma^2})}}=nlog{\frac{1}{\sqrt{2\pi\sigma}}}-\frac{1}{\sigma^2}\cdot\frac{1}{2}\sum_{i=1}^n(y^i-\theta^Tx^i)^2\)
求上式的max，即求\(\frac{1}{2}\sum_{i=1}^n(y^i-\theta^Tx^i)^2\)的min，这个式子我们非常熟悉，就是least-squares cost function
因此，假定线性回归模型和\(\epsilon^i\sim{N(0,\sigma^2)}\)，我们用最大似然估计参数，等价于通过最小二乘法得到参数
但是注意，这里的一些assumptions并非必要，也可以通过别的assumptions来justify整个过程
———————————————————————
推导结束。既然我们确定了least-squares cost function的可靠性（无论是直觉理解上，还是数学推导上），那么如何求\(J(\theta)\)的min，以得到\(\theta\)？
1、梯度下降法Gradient Descent
\(\theta=\theta-\alpha\frac{\partial}{\partial{\theta}}J(\theta)\)
这个式子比较好理解，可以自己画一个图。式中\(\alpha\)为learning rate
（1）Batch Gradient Descent
\(\theta=\theta+\alpha\sum_{i=1}^n{(y^i-h_{\theta}(x^i))x^i}\)
\(\theta\)的每步更新都需要用到整个训练集。如果n很大，则非常耗时间和内存
（2）Stochastic Gradient Descent随机梯度下降
\(\theta=\theta+\alpha{(y^i-h_{\theta}(x^i))x^i}\)
\(\theta\)的每步更新只看一个训练样本。但是可能出现收敛问题：1-遇到山谷，会在两侧山壁之间来回震荡，导致收敛不稳定&收敛慢；2-遇到鞍点（一个方向上向两头翘上去，另一个方向上向两边垂下去）这种梯度几乎为0的区域，难以察觉出梯度微小变化时，则停滞
2、直接求导
求\(\Delta_{\theta}J(\theta)=0\)时的\(\theta\)
因为\(J(\theta)=\frac{1}{2}\sum_i{(h_{\theta}(x^i)-y^i)^2}=\frac{1}{2}(X\theta-Y)^T(X\theta-Y)\)
可求得（省略了几步，自己推一推）：\(\Delta_{\theta}J(\theta)=X^TX\theta-X^T{Y}\)，令为0
则得\(\theta=(X^T{X})^{-1}X^T{Y}\)
Locally weighted linear regression：
用最小二乘法求参数\(\theta\)，即求\(\sum_{i=1}^n(h_\theta(x^i)-y^i)^2\)的min，如果目标式改为\(\sum_{i=1}^n{w^i}(h_\theta(x^i)-y^i)^2\)，则为locally weighted linear regression
上式中\(w^i\)是非负的权重。常用的表达式为\(w^i=exp(-\frac{(x^i-x)^2}{2\tau^2})\)，取值范围为(0,1]，如果当前\(x\)与某个训练样本\(x^i\)越接近，则越靠近1，权重越大。参数\(\tau\)为bandwidth parameter，控制比例
此时，参数不再是固定数量，而是参数数量与训练集的量一致，并且推理时仍需用到训练集（non-parametric？）
*发现复习里我把i标在下标，其他部分的i都是上标（捂脸，凑合看
参考资料：
[1]CS229 lecture notes: https://cs229.stanford.edu/main_notes.pdf
[2]https://www.cnblogs.com/stevenbush/articles/3357803.html
[3]https://www.cnblogs.com/leezx/p/5822237.html
[4]https://blog.csdn.net/qq_44614524/article/details/114241259
附：
博客园插入公式，先在选项中勾选“启用数学公式支持”，相关教程：https://blog.csdn.net/dav74739/article/details/102403334