分类


Classification

分类问题, Email: Spam/NotSpam, Tumor: 恶性/良性

y { 0 , 1 }
  • 0:”Negative Class”(e.g., benign tumor)
  • 1: “Positive Class”(e.g., malignant tumor)

对于分类场景,使用线性回归模型不适合,原因是 hθ 的值区间不能保证在[0,1]之间,因此需要一种新的模型,叫做 logistic regression,逻辑回归。

Logistic Regression Model

逻辑回归 wiki

在给出模型前,先不考虑 y 的取值是离散的,我们希望能使:0hθ(x)1,可以将式子做一些变换:

  • 线性函数:hθ(x)=θTX
  • 做如下变换:hθ(x)=g(θTx), 另z=θTx,g(z)=11+ez

  • 得到函数:g(θTx)=11+eθTx 函数曲线如下:

函数g(z), 如上图将所有实数映射到了(0,1]空间内,这使他可以将任意一个 h(x)的值空间转化为适合分类器取值的空间, g(z)也叫做Sigmoid Functionhθ(x)的输出是结果是1的概率,比如hθ(x)=0.7表示 70%的概率我们的输出结果为1,因此输出是0的概率则是 30%:

h θ ( x ) = P ( y = 1 | x ; θ ) = 1 P ( y = 0 | x ; θ ) , P ( y = 0 | x ; θ ) + P ( y = 1 | x ; θ ) = 1

Decision Boundary

对函数hθ(x)=g(θTx),假设:

  • "y=1"

    if hθ(x)0.5

  • "y=0"

    if hθ(x)<0.5

通过观察函数g(z)=11+ez上一节的曲线可以发现,当z大于 0 的时候g(z)≥0.5,因此只需要θTx > 0即可,即:

θ T x 0 y = 1 θ T x < 0 y = 0

g(z)小于0.5的情况同理。

linear decision boundaries

举个例子,假设有一个线性预测函数hθ(x)=g(θ0+θ1x1+θ2x2),其中θ的值已经确定为[-3,1,1],则问题变为求如果要y=1,那么需要h(x)=-3+x1+x20,即找到x1,x2满足x1+x23

如下图所示:

由上图可看出:x1+x2=3可作为Boundary Function,也叫Decision Boundary

Non-linear decision boundaries

对于非线性的预测函数,例如:

h θ ( x ) = g ( θ 0 + θ 1 x 1 + θ 2 x 2 + θ 3 x 1 2 + θ 4 x 2 2 )

假设θ值已经确定[-1,0,0,1,1],同上,变为求如果要y=1,那么需要-1+x12+x220,即找到x1,x2满足x12+x220,则边界函数为x12+x22=0,如下图所示

则落在圈外的样本点,可以预测y=1

Cost Function

由上面可知,给定:

  • 训练集{(x(1),y(1)),(x(2),y(2)),...,(x(m),y(m))},m 个样本,其中:x[ x1 x2 ... xn ]x0,y{0,1}

  • 预测函数: hθ(x)=11+eθTx

问题还是怎么求解θ,如果使用之前先行回归的 cost function,即 J(θ)=12mi=1m (hθ(x i)yi )2

这时会出现J(θ)不是 convex function 的情况,原因是h(x)变成了复杂的非线性函数,因此梯度下降无法得到最小值(得到极小值的概率更高)。

  • 逻辑回归的 Cost Function:
J ( θ ) = 1 m i = 1 m C o s t ( h θ ( x ( i ) ) , y ( i ) ) C o s t ( h θ ( x ) , y ) = log ( h θ ( x ) ) if y = 1 C o s t ( h θ ( x ) , y ) = log ( 1 h θ ( x ) ) if y = 0

y=1的时候,J(θ) = 0 -> h(x)=1J(θ) = ∞ -> h(x)=0,如下图所示

y=0的时候,J(θ) =0 -> h(x)=0J(θ) = ∞ -> h(x)=1,如下图所示

图上可以看出J(θ)有极值点,接下来的问题就是分别求解h(x)=0h(x)=1两种情况下的θ

Simplifed Cost Function

上述 Cost Function 可以简化为一行:

C o s t ( h θ ( x ) , y ) = y log ( h θ ( x ) ) ( 1 y ) log ( 1 h θ ( x ) )

之所以将上述式子简化为一行,其目的是方便使用概率论中的最大似然估计求解,接下来还是通过梯度下降法求解min>J(θ)J(θ)可完整写为:

J ( θ ) = 1 m i = 1 m [ y ( i ) log ( h θ ( x ( i ) ) ) + ( 1 y ( i ) ) log ( 1 h θ ( x ( i ) ) ) ]

向量化的实现为:

h = g ( X θ ) J ( θ ) = 1 m y T log ( h ) ( 1 y ) T log ( 1 h )

Gradient Descent

前面可知梯度下降公式为:

R e p e a t { θ j := θ j α θ j J ( θ ) }

J(θ)求偏导,得到梯度下降公式:

R e p e a t { θ j := θ j α m i = 1 m ( h θ ( x ( i ) ) y ( i ) ) x j ( i ) }

注意到上述公式和线性回归使用的梯度下降公式相同,不同的是h(θ),上述公式向量化表示为:

θ := θ α m X T ( g ( X θ ) y )

Advanced Optimization

对于求解J(θ)的最小值,目前的做法是使用梯度下降法,对θ求偏导,除了梯度下降之外,还有其它几种优化算法:

  • Conjugate gradient
  • BFGS
  • L-BFGS

这三种算法的优点是:

  • 不需要人工选择α
  • 比低度下降更快

缺点是:比较复杂

开发者不需要自己实现这些算法,在一般的数值计算库里都有相应的实现,例如 python,Octave 等。我们只需要关心两个问题,如何给出:

J ( θ ) θ j J ( θ )

我们可以使用 Octave 写这样一个函数:

function [jVal, gradient] = costFunction(theta)
  jVal = [...code to compute J(theta)...];
  gradient = [...code to compute derivative of J(theta)...];
end

然后使用 Octave 自带的fminunc()优化算法计算出θ的值:

options = optimset('GradObj', 'on', 'MaxIter', 100);
initialTheta = zeros(2,1);
   [optTheta, functionVal, exitFlag] = fminunc(@costFunction, initialTheta, options);

fminunc()函数接受三个参数:costFunction,初始的 θ 值(至少是 2x1 的向量),还有 options

Multiclass classification

前面我们解决的问题都是针对两个场景进行分类,即 y = {0,1} 实际生活中,常常有多个场景需要归类,例如

  • Email foldering/tagging:Work,Friends,Family,Hobby
  • Weather:Sunny,Cloudy,Rain,Snow

即分类结果不只是 0 或 1,而是多个 y = {0,1…n},解决多个分类我们使用 one-vs-all 的方式,即选取某一个场景进行归类时,将其他场景合并为起对立的场景。如图:

上图可知我们先取一个 class 进行计算,将其他的归类为另一个 class,这样就可以使用前面提到的 binary regression model 进行计算,即

y { 0 , 1 . . . n } h θ ( 0 ) ( x ) = P ( y = 0 | x ; θ ) h θ ( 1 ) ( x ) = P ( y = 1 | x ; θ ) h θ ( n ) ( x ) = P ( y = n | x ; θ ) p r e d i c t i o n = max i ( h θ ( i ) ( x ) )
  • One-vs-all(one-vs-rest):

Train a logistic regression classifierhθ(i)(x) for each class i to predict the probability that y=i.

On a new input x, to make a prediction, pick the class i that maximizes

  • 总结一下就是对每种分类先计算他的hθ(x),当有一个新的x需要分类时,选一个让hθ(x)值最大的分类器。

附录:Regularization

The problem of overfitting

以线性回归的预测房价为例,如下图所示:

可以看到:

  • 通过线性函数预测房价不够精确(underfit),术语叫做”High Bias”,其原因主要是样本的 feature 太少了。
  • 通过二次函数拟合出来的曲线刚好可以贯穿大部分数据样本,术语叫做”Just Right”
  • 通过四阶多项式拟合出来的曲线虽然能贯穿所有数据样本,但是曲线本身不够规则,当有新样本出现时不能很好的预测。这种情况我们叫做Over Fitting(过度拟合),术语叫做”High variance”。If we have too many features, the learned hypothesis may fit the training set very well(J(θ)=0), but fail to generalize to new examples(predict prices on new examples) Over Fitting 的问题在样本少,feature 多的时候很明显

  • Addressing overfitting: - Reduce number of features - Manually select which features to keep. - Model selection algorithm - Regularization - Keep all features, but reduce magnitude/values of parameters θj - Works well when we have a lot of features, each of which contributes a bit to predictingy

Regularization Cost Function

如果要减少 overfitting 的情况,我们可以降低一些参数的权重,假设我们想要让下面的函数变成二次方程:

θ 0 + θ 1 x + θ 2 x 2 + θ 3 x 3 + θ 4 x 4

我们想要在不去掉 θ3 和 θ4 的前提下,降低θ3x3θ4x4的影响,我们可以修改 cost function 为:

m i n θ   1 2 m i = 1 m ( h θ ( x ( i ) ) y ( i ) ) 2 + 1000 θ 3 2 + 1000 θ 4 2

我们在原来的 cost function 后面增加了两项,为了让 cost function 接近 0,我们需要让θ3,θ4近似为 0,这样即会极大的减少θ3x3θ4x4的值,减少后的曲线如下图粉色曲线,更接近二次函数:

Small values for parameters θ0,θ1,...,θn

  • “Simpler” hypothesis,选取更小的θ值能得到更简单的预测函数,例如上面的例子,如果将 θ3,θ4近似为 0 的话,那么上述函数将变为二次方程,更贴近合理的假设函数
  • Housing example: - Feature: x0,x1,...,θ100 - Parameters: θ0,θ1,...,θ100

100 个 feature,如何有效的选取这些θ呢,改变 cost function:

J ( θ ) = 1 2 m i = 1 m ( h θ ( x ( i ) ) y ( i ) ) 2 + λ j = 1 n θ j 2

参数 λ 叫做regularization parameter,它的作用是既要保证曲线的拟合程度够高同时又要确保 θ 的值尽量小。如果 λ 的值选取过大,例如λ=1010,会导致计算出的所有的 θ 值都接近 0,从而使hθ(x)=θ0 即产生”Under fitting”

Regularized linear regression

有了上面的式子,我们可以将它应用到线性回归:

  • 修改梯度下降公式为:
Repeat   {         θ 0 := θ 0 α   1 m   i = 1 m ( h θ ( x ( i ) ) y ( i ) ) x 0 ( i )         θ j := θ j α   1 m   i = 1 m ( h θ ( x ( i ) ) y ( i ) ) x j ( i ) + λ m θ j                     j { 1 , 2... n } }

λmθj提出来,得到:

θ j := θ j ( 1 α λ m ) α 1 m i = 1 m ( h θ ( x ( i ) ) y ( i ) ) x j ( i )

上述式子中1αλm必须小于 1,这样就减小了θj的值,后面的式子和之前梯度下降的式子相同

  • 应用到 Normal Equation

和之前的公式相比,增加了一项:

θ = X T X + λ L 1 X T y where     L = 0 1 1 1

L 是一个(n+1)x(n+1)的对单位阵,第一项是 0。在引入 λ.L 之后XTX+λL保证可逆

Regularized logistic regression

逻辑回归也有 overfitting 的问题,如图所示

处理方式和线性回归相同,之前知道逻辑回归的 cost function 如下:

J ( θ ) = 1 m i = 1 m [ y ( i )   log ( h θ ( x ( i ) ) ) + ( 1 y ( i ) )   log ( 1 h θ ( x ( i ) ) ) ]

我们可以在最后加一项来 regularize 这个函数:

J ( θ ) = 1 m i = 1 m [ y ( i )   log ( h θ ( x ( i ) ) ) + ( 1 y ( i ) )   log ( 1 h θ ( x ( i ) ) ) ] + λ 2 m j = 1 n θ j 2

第二项:j=1nθj2是排除了θ0的,因此,计算梯度下降要对θ0单独计算:

  • Octave Demo
function [J, grad] = lrCostFunction(theta, X, y, lambda{

%LRCOSTFUNCTION Compute cost and gradient for logistic regression with
%regularization
%   J = LRCOSTFUNCTION(theta, X, y, lambda) computes the cost of using
%   theta as the parameter for regularized logistic regression and the
%   gradient of the cost w.r.t. to the parameters.

% Initialize some useful values
m = length(y); % number of training examples

% You need to return the following variables correctly
J = 0;
grad = zeros(size(theta));



h = sigmoid(X*theta); %  X:118x28, theta:28x1 h:118x1

%向量化实现
J = 1/m * (-y'*log(h)-(1-y)'*log(1-h)) + 0.5*lambda/m * sum(theta([2:end]).^2);
%代数形式实现
%J = 1/m * sum((-y).*log(h) - (1-y).*log(1-h)) + 0.5*lambda/m * sum(theta([2:end]).^2);

grad = 1/m * X'*(h-y);

r = lambda/m .* theta;
r(1) = 0; %skip theta(0)
grad = grad + r;


% =============================================================

grad = grad(:);

}

function g = sigmoid(z)
	g = 1.0 ./ (1.0 + exp(-z));
end