Machine Learning
  • Introduction
  • man
  • Linear model
    • Linear Regression
    • Generalized Linear Models
    • Nonlinear regression
  • bayes
    • bayesian network
    • Variational Bayesian inference
    • Gaussian Process Regression
  • Logistic Regression
    • L1 regularization
    • L2 regularization
    • softmax
    • Overflow and Underflow
  • SVM
    • C-SVM
    • C-SVM求解
  • EM
    • GMM
  • Maximum Entropy
    • IIS
  • HMM
    • viterbi algorithm
  • CRF
  • Random Forest
    • bagging
    • random forest
  • boosting
    • catboost
    • gradient boosting
    • Newton Boosting
    • online boosting
    • gcForest
    • Mixture models
    • XGBoost
    • lightGBM
    • SecureBoost
  • LDA
  • rank
    • RankNet
    • LambdaRank
    • SimRank
  • Factorization Machine
    • Field-aware Factorization Machine
    • xdeepFM
  • Clustering
    • BIRCH
    • Deep Embedding Clustering
  • Kalman filtering
  • word2vec
  • 关联规则挖掘
  • MATH-Mathematical Analysis
    • measure
  • MATH-probability
    • Variational Inference
    • Dirichlet分布
    • Gibbs Sampling
    • Maximum entropy probability distribution
    • Conjugate prior
    • Gaussian Process
    • Markov process
    • Poisson process
    • measure
    • Gumbel
  • MATH-Linear Algebra
    • SVD
    • SVD-推荐
    • PCA
    • Linear Discriminant Analysis
    • Nonnegative Matrix Factorization
  • MATH-Convex optimization
    • 梯度下降
    • 随机梯度下降
    • 牛顿法
    • L-BFGS
    • 最速下降法
    • 坐标下降法
    • OWL-QN
    • 对偶问题
    • 障碍函数法
    • 原对偶内点法
    • ISTA
    • ADMM
    • SAG
  • MATH-碎碎念
    • cost function
    • Learning Theory
    • sampling
    • Entropy
    • variational inference
    • basis function
    • Diffie–Hellman key exchange
    • wavelet transform
    • 图
    • Portfolio
    • 凯利公式
  • ML碎碎念
    • 特征
    • test
    • TF-IDF
    • population stability index
    • Shapley Values
  • 课件
    • xgboost算法演进
  • Time Series
  • PID
  • graph
    • SimRank
    • community detection
    • FRAUDAR
    • Anti-Trust Rank
    • Struc2Vec
    • graph theory
    • GNN
  • Anomaly Detection
    • Isolation Forest
    • Time Series
  • Dimensionality Reduction
    • Deep Embedded Clustering
  • Federated Learning
  • automl
  • Look-alike
  • KNN
  • causal inference
Powered by GitBook
On this page
  • 正交投影与最小二乘法
  • 解析解
  • 梯度与迹
  • gradient descent
  • Ridge regression
  • 贝叶斯线性回归
  • 带权重的线性回归
  • 非线性的处理

Was this helpful?

  1. Linear model

Linear Regression

PreviousLinear modelNextGeneralized Linear Models

Last updated 5 years ago

Was this helpful?

hθ(x)=θ0+θ1x1+θ2x2=∑i=02θixi=θTXh_{\theta}(x) = \theta_0 +\theta_1 x_1 +\theta_2 x_2 = \sum_{i=0}^2 \theta_i x_i = \theta^T Xhθ​(x)=θ0​+θ1​x1​+θ2​x2​=i=0∑2​θi​xi​=θTX

损失函数:需要一个机制评估 θ\thetaθ 是否比较好。

为何选择平方和作为错误估计函数,假设根据特征的预测结果与实际结果有误差 ϵi\epsilon_iϵi​ ,即yi=θTxi+ϵiy_i = \theta^T x_i + \epsilon_iyi​=θTxi​+ϵi​ 一般误差 ϵi\epsilon_iϵi​ 满足正态分布,那么x和y的条件概率

p(yi∣xi;θ)=12πδexp⁡(−(yi−θTxi)22δ2)L(θ)=log⁡∏i=1mp(yi∣xi;θ)=−mlog⁡2πσ−12σ2∑i=1m(yi−θTxi)2p(y_i | x_i;\theta) = \frac {1}{\sqrt{2\pi}\delta} \exp(-\frac{(y_i-\theta^Tx_i)^2}{2\delta^2}) \\ L(\theta) = \log \prod_{i=1}^m p(y_i | x_i;\theta) = -m \log \sqrt {2\pi} \sigma - \frac {1}{2 \sigma^2} \sum_{i=1}^m (y_i-\theta^Tx_i)^2p(yi​∣xi​;θ)=2π​δ1​exp(−2δ2(yi​−θTxi​)2​)L(θ)=logi=1∏m​p(yi​∣xi​;θ)=−mlog2π​σ−2σ21​i=1∑m​(yi​−θTxi​)2

Andrew Ng的讲义上的,它只是表示与正态分布等价,然后并没有说明为什么用最小二乘或选择正太分布。

正交投影与最小二乘法

最小二乘可以理解为正交投影。 MLAPP 7.3.2 Geometric interpretation(page 251)

y^∈span(X)y^=XwXT(y−y^)=0→XT(y−Xw)=0→w=(XTX)−1XTyy^=Xw=X(XTX)−1XTy\hat y \in span (X) \\ \hat y = Xw \\ X^T (y- \hat y) = 0 \to X^T (y- Xw) = 0 \to w= (X^T X)^{-1} X^Ty \\ \hat y = Xw = X (X^T X)^{-1} X^Ty \\y^​∈span(X)y^​=XwXT(y−y^​)=0→XT(y−Xw)=0→w=(XTX)−1XTyy^​=Xw=X(XTX)−1XTy

This corresponds to an orthogonal projection of y onto the column space of X.

这个几何意义,可见PRML3.1 。

求损失函数最小值,可以用梯度下降法。

解析解

将训练特征表示为X矩阵,结果表示为Y向量

Xθ−Y=[(x(1))Tθ…(x(m))Tθ]−[y(1)…y(m)]=[hθ(x(i))−y(i)…hθ(x(m))−y(m)]J(θ)=12m(Xθ−Y)T(Xθ−Y)=12m∣∣Xθ−Y∣∣2∂J∂θ=XT(Xθ−Y)=0XTXθ−XTY=0θ=(XTX)−1XTY此解析解需要X是列满秩的,故一般求θ=(XTX+λI)−1XTYI是单位阵,这个解形式等同于加了L2范数X {\theta} - Y = \begin{bmatrix} (x^{(1)})^T {\theta} \\ \ldots \\ (x^{(m)})^T {\theta} \\ \end{bmatrix} - \begin{bmatrix} y^{(1)} \\ \ldots \\ y^{(m)} \\ \end{bmatrix} = \begin{bmatrix} h_{\theta}(x^{(i)}) - y^{(i)} \\ \ldots \\ h_{\theta}(x^{(m)}) - y^{(m)} \\ \end{bmatrix} \\ J(\theta) = \frac {1}{2m} (X {\theta} - Y )^T (X {\theta} - Y ) = \frac {1}{2m} ||X {\theta} - Y ||^2 \\ \frac{\partial J}{\partial \theta} = X^T( X {\theta} - Y ) =0 \\ X^T X {\theta} - X^T Y =0 \\ \theta = (X^TX)^{-1}X^TY \\ \textbf{此解析解需要X是列满秩的,故一般求} \\ \theta = (X^TX + \lambda I)^{-1}X^TY \\ \textbf{I是单位阵,这个解形式等同于加了L2范数}Xθ−Y=​(x(1))Tθ…(x(m))Tθ​​−​y(1)…y(m)​​=​hθ​(x(i))−y(i)…hθ​(x(m))−y(m)​​J(θ)=2m1​(Xθ−Y)T(Xθ−Y)=2m1​∣∣Xθ−Y∣∣2∂θ∂J​=XT(Xθ−Y)=0XTXθ−XTY=0θ=(XTX)−1XTY此解析解需要X是列满秩的,故一般求θ=(XTX+λI)−1XTYI是单位阵,这个解形式等同于加了L2范数

若特征维度>样本数,XTXX^TXXTX则不会是列满秩,解析解无法求出。 对于维度特别高的,一般会加L1范数,会产生稀疏解。此时目标函数为 J(θ)=12m∣∣Xθ−Y∣∣2+λ∣∣θ∣∣1J(\theta) = \frac {1}{2m} ||X {\theta} - Y ||^2 + \lambda ||\theta||_1J(θ)=2m1​∣∣Xθ−Y∣∣2+λ∣∣θ∣∣1​,一般称为LASSO

梯度与迹

Ng讲义上求梯度时结合了矩阵的迹。

∇θJ(θ)=12∇θ(Xθ−Y)T(Xθ−Y)=12∇θ(θTXTXθ−YTXθ−θTXTY+YTY)=12∇θtr(θTXTXθ−YTXθ−θTXTY+YTY)=12[∇θtr(θTXTXθ)−∇θtr(YTXθ)−∇θtr(θTXTY)]=12∇θtr(θTXTXθ)−∇θtr(YTXθ)=12∇θtr(θθTXTX)−∇θtr(YTXθ)=12∇θtr(θIθTXTX)−∇θtr(YTXθ)=XTXθ−∇θtr(YTXθ)=XTXθ−XYT\begin{align} \nabla_{\theta} J(\theta) & = \frac {1}{2} \nabla_{\theta} (X {\theta} - Y )^T (X {\theta} - Y ) \\ & = \frac {1}{2} \nabla_{\theta} (\theta^T X^T X {\theta} - Y^T X \theta -\theta^T X^T Y + Y^T Y) \\ & = \frac {1}{2} \nabla_{\theta} tr (\theta^T X^T X {\theta} - Y^T X \theta -\theta^T X^T Y + Y^T Y) \\ & = \frac {1}{2} [ \nabla_{\theta} tr (\theta^T X^T X {\theta} ) - \nabla_{\theta} tr ( Y^T X \theta ) - \nabla_{\theta} tr (\theta^T X^T Y ) ] \\ & = \frac {1}{2} \nabla_{\theta} tr (\theta^T X^T X {\theta} ) - \nabla_{\theta} tr ( Y^T X \theta ) \\ & = \frac {1}{2} \nabla_{\theta} tr ({\theta} \theta^T X^T X ) - \nabla_{\theta} tr ( Y^T X \theta ) \\ & = \frac {1}{2} \nabla_{\theta} tr ({\theta} I \theta^T X^T X ) - \nabla_{\theta} tr ( Y^T X \theta ) \\ & = X^T X \theta - \nabla_{\theta} tr ( Y^T X \theta ) \\ & = X^T X \theta - X Y^T \end{align}∇θ​J(θ)​=21​∇θ​(Xθ−Y)T(Xθ−Y)=21​∇θ​(θTXTXθ−YTXθ−θTXTY+YTY)=21​∇θ​tr(θTXTXθ−YTXθ−θTXTY+YTY)=21​[∇θ​tr(θTXTXθ)−∇θ​tr(YTXθ)−∇θ​tr(θTXTY)]=21​∇θ​tr(θTXTXθ)−∇θ​tr(YTXθ)=21​∇θ​tr(θθTXTX)−∇θ​tr(YTXθ)=21​∇θ​tr(θIθTXTX)−∇θ​tr(YTXθ)=XTXθ−∇θ​tr(YTXθ)=XTXθ−XYT​​

矩阵的迹是它的所有特征值的和

gradient descent

θj:=θj−α∂J(θ)∂θj\theta_j := \theta_j - \alpha \frac {\partial J(\theta)}{\partial \theta_j}θj​:=θj​−α∂θj​∂J(θ)​

按照Ng的讲义思路来,当只有一个样本时:

∂J(θ)∂θj=∂∂θj12(hθ(x)−y)2=(hθ(x)−y)∂∂θj(hθ(x)−y)=(hθ(x)−y)∂∂θj∑i=0nθixi=(hθ(x)−y)xi\frac {\partial J(\theta)}{\partial \theta_j} = \frac {\partial }{\partial \theta_j} \frac 12 (h_{\theta}(x)-y)^2 = (h_{\theta}(x)-y) \frac {\partial }{\partial \theta_j} (h_{\theta}(x)-y) = (h_{\theta}(x)-y) \frac {\partial }{\partial \theta_j} \sum_{i=0}^n \theta_i x_i = (h_{\theta}(x)-y) x_i∂θj​∂J(θ)​=∂θj​∂​21​(hθ​(x)−y)2=(hθ​(x)−y)∂θj​∂​(hθ​(x)−y)=(hθ​(x)−y)∂θj​∂​i=0∑n​θi​xi​=(hθ​(x)−y)xi​

则

θj:=θj−α(hθ(x)−y)xi\theta_j := \theta_j - \alpha (h_{\theta}(x)-y) x_iθj​:=θj​−α(hθ​(x)−y)xi​

当用m个训练样本时,

θj:=θj−α∑i=1m(hθ(x(i))−y(i))xi(i)\theta_j := \theta_j - \alpha \sum_{i=1}^m (h_{\theta}(x^{(i)})-y^{(i)}) x_i^{(i)}θj​:=θj​−αi=1∑m​(hθ​(x(i))−y(i))xi(i)​

Ridge regression

就是带L2正则,可以理解为均值为0高斯分布作为先验概率:p(w)=∏jN(wj∣0,τ2)p(w) = \prod_j N(w_j|0,\tau^2)p(w)=∏j​N(wj​∣0,τ2) 则MAP:

arg⁡max⁡w ∑i=1Nlog⁡p(yi∣xi,w)p(w)=∑i=1Nlog⁡N(yi∣w0+wTxi,σ2)+∑j=1Dlog⁡N(wj∣0,τ2)\begin{align} \arg \max_w\ &\sum_{i=1}^N \log p(y_i|x_i,w) p(w) \\ = &\sum_{i=1}^N \log N(y_i|w_0+w^Tx_i,\sigma^2) + \sum_{j=1}^D \log N(w_j|0,\tau^2) \\ \end{align}argwmax​ =​i=1∑N​logp(yi​∣xi​,w)p(w)i=1∑N​logN(yi​∣w0​+wTxi​,σ2)+j=1∑D​logN(wj​∣0,τ2)​​

简化下得:J(w)=1N∑i=1N(yi−(w0+wTxi))2+λ∣∣w∣∣22J(w) = \frac{1}{N}\sum_{i=1}^N(y_i-(w_0+w^Tx_i))^2 + \lambda||w||_2^2J(w)=N1​∑i=1N​(yi​−(w0​+wTxi​))2+λ∣∣w∣∣22​ 解为: w=(XTX+λI)−1XTYw = (X^TX + \lambda I)^{-1}X^TYw=(XTX+λI)−1XTY

from MLAPP 7.5 Ridge regression (page 255)

贝叶斯线性回归

上面对参数加了先验,可以从贝叶斯的角度去看待,就成了贝叶斯线性回归。这时,在贝叶斯模型下我们需要去计算的是W的分布,而不是W的point estimation。

带权重的线性回归

基本假设是

  • min⁡θJ(θ)=∑i=1mωi(yi−θTxi)2\min_{\theta} J(\theta) = \sum_{i=1}^m \omega_i (y_i - \theta^Tx_i)^2minθ​J(θ)=∑i=1m​ωi​(yi​−θTxi​)2

  • Output θTX\theta^TXθTX

其中假设ωi\omega_iωi​符合公式

ωi=exp⁡(−(xi−x)22τ2)τ是波长参数\omega_i = \exp(-\frac {(x_{i}-x)^2}{2\tau^2}) \\ \tau \text{是波长参数}ωi​=exp(−2τ2(xi​−x)2​)τ是波长参数

这个假设的道理是离要预测的X越近的样本权重越大,越远的影响越小。 这个公式与正态分布类似,但ωi\omega_iωi​不是随机变量。 在学习的过程中,不仅要学习现行回归的参数,还是学习波长参数。

这个算法的问题在于,对于每一个要查询的点,都要重新从数据中训练一个模型出来,代价很高。

非线性的处理

线性回归和logistic回归中都要求数据线性,但是现实中可能会遇到数据非线性的问题, 从本质出发,两种解决思路:

  • 自变量间的非相关性: 例 y=w1∗x1+w2∗x2+w3∗x1∗x2y=w_1*x_1+w_2*x_2+ w_3*x_1*x_2y=w1​∗x1​+w2​∗x2​+w3​∗x1​∗x2​

  • 自变量的线性变化,因变量却没有线性相关: 对自变量离散化。

在进行线性回归时,为什么最小二乘法是最优方法?
投影矩阵与最小二乘
正交性和最小二乘法
迹的几何意义是什么
https://www.zhihu.com/question/22007264
回归分析
Sparsity and Some Basics of L1 Regularization
最大似然估计和最小二乘法怎么理解?