月度归档:2012年05月

Coursera公开课笔记: 斯坦福大学机器学习第六课“逻辑回归(Logistic Regression)”

Deep Learning Specialization on Coursera

斯坦福大学机器学习第六课"逻辑回归“学习笔记,本次课程主要包括7部分:

1) Classification(分类)

2) Hypothesis Representation

3) Decision boundary(决策边界)

4) Cost function(代价函数,成本函数)

5) Simplified cost function and gradient descent(简化版代价函数及梯度下降算法)

6) Advanced optimization(其他优化算法)

7) Multi-class classification: One-vs-all(多类分类问题)

以下是每一部分的详细解读。

1) Classification(分类)

分类问题举例:

  1. 邮件:垃圾邮件/非垃圾邮件?
  2. 在线交易:是否欺诈(是/否)?
  3. 肿瘤:恶性/良性?

以上问题可以称之为二分类问题,可以用如下形式定义:

二分类问题-我爱公开课-52opencourse.com

其中0称之为负例,1称之为正例。

对于多分类问题,可以如下定义因变量y:

y \in \{0, 1, 2, 3, ..., n\}

如果分类器用的是回归模型,并且已经训练好了一个模型,可以设置一个阈值:

  • 如果h_\theta(x) \geq 0.5,则预测y=1,既y属于正例;
  • 如果h_\theta(x) < 0.5,则预测y=0,既y属于负例;

如果是线性回归模型,对于肿瘤这个二分类问题,图形表示如下:

线性回归二分类问题-我爱公开课-52opencourse.com

但是对于二分类问题来说,线性回归模型的Hypothesis输出值h_\theta(x)可以大于1也可以小于0。

这个时候我们引出逻辑回归,逻辑回归的Hypothesis输出介于0与1之间,既:

0 \leq h_\theta(x) \leq 1

注: 以下引自李航博士《统计学习方法》1.8节关于分类问题的一点描述:

分类是监督学习的一个核心问题,在监督学习中,当输出变量Y取有限个离散值时,预测问题便成为分类问题。这时,输入变量X可以是离散的,也可以是连续的。监督学习从数据中学习一个分类模型或分类决策函数,称为分类器(classifier)。分类器对新的输入进行输出的预测(prediction),称为分类(classification).

2) Hypothesis Representation

逻辑回归模型:

上一节谈到,我们需要将Hypothesis的输出界定在0和1之间,既:

0 \leq h_\theta(x) \leq 1

但是线性回归无法做到,这里我们引入一个函数g, 令逻辑回归的Hypothesis表示为:

h_\theta(x) = g(\theta^T x)

这里g称为Sigmoid function或者Logistic function, 具体表达式为:

g(z) = \frac{1}{1+e^{-z}}

Sigmoid 函数在有个很漂亮的“S"形,如下图所示(引自维基百科):

Sigmoid function-我爱公开课-52opencourse.com

综合上述两式,我们得到逻辑回归模型的数学表达式:

h_\theta(x) = \frac{1}{1+e^{-\theta^Tx}}

其中\theta是参数。
Hypothesis输出的直观解释:

h_\theta(x) = 对于给定的输入x,y=1时估计的概率

例如,对于肿瘤(恶性/良性),如果输入变量(特征)是肿瘤的大小:

肿瘤分类例子-我爱公开课-52opencourse.com

这里Hypothesis表示的是”病人的肿瘤有70%的可能是恶性的“。

较正式的说法可以如下表示:

给定输入x,参数化的\theta(参数空间), y=1时的概率。

数学上可以如下表示:

h_\theta(x) = P(y=1| x;\theta)

对于因变量y=0或1这样的二分类问题:

P(y=0|x;\theta) + P(y=1|x;\theta) = 1

P(y=0|x;\theta) = 1 - P(y=1|x;\theta)

3) Decision boundary(决策边界)

如上节所述,逻辑回归模型可以如下表示:

逻辑回归模型表达式-我爱公开课-52opencourse.com

假设给定的阈值是0.5,当h_\theta(x) \geq 0.5时, y = 1;

h_\theta(x) < 0.5时,y = 0;

再次回顾sigmoid function的图形,也就是g(z)的图形:

sigomoid function g(x) -我爱公开课-52opencourse.com

g(z) \geq 0.5时, z \geq 0;

对于h_\theta(x) = g(\theta^Tx) \geq 0.5, 则\theta^Tx \geq 0, 此时意味着预估y=1;

反之,当预测y = 0时,\theta^Tx < 0;

我们可以认为\theta^Tx = 0是一个决策边界,当它大于0或小于0时,逻辑回归模型分别预测不同的分类结果。例如,

h_\theta(x) = g(\theta_0 + \theta_1 x_1 + \theta_2 x_2)

\theta_0, \theta_1, \theta_2分别取-3, 1, 1,

则当-3 + x_1 + x_2 \geq 0时, y = 1; 则x_1 + x_2 = 3是一个决策边界,图形表示如下:

决策边界-我爱公开课-52opencourse.com

上述只是一个线性的决策边界,当h_\theta(x)更复杂的时候,我们可以得到非线性的决策边界,例如:

非线性的决策边界1-我爱公开课-52opencourse.com

这里当x^{2}_{1} + x^{2}_{2} \geq 1时,y=1,决策边界是一个圆形,如下图所示:

非线性决策边界2-我爱公开课-52opencourse.com

更复杂的例子,请参考官方PPT,这里就不再举例了。

4) Cost function(代价函数,成本函数)

逻辑回归概览:

逻辑回归是一种有监督的学习方法,因此有训练集:

训练集-我爱公开课-52opencourse.com

对于这m个训练样本来说,每个样本都包含n+1个特征:

训练样本-我爱公开课-52opencourse.com

其中x \in R^{n+1}, x_0 = 1, y \in \{0, 1\}.

Hypothesis可表示为:

h_\theta(x) = \frac{1}{1+e^{-\theta^Tx}}

与线性回归相似,我们的问题是如何选择合适的参数\theta?

Cost Function:

线性回归的Cost  Function定义为:

J(\theta) = \frac{1}{m}\sum_{i=1}^m{\frac{1}{2}(h_\theta(x^{(i)}) - y^{(i)})^2}

这里可以把\frac{1}{2}(h_\theta(x^{(i)}) - y^{(i)})^2简写为Cost(h_\theta(x^{(i)}, y),更简化的表达式为:

Cost(h_\theta(x), y) = \frac{1}{2}(h_\theta(x) - y)^2

如果和线性回归相似,这里取 h_\theta(x) = \frac{1}{1+e^{-\theta^Tx}},会存在一个问题,也就是逻辑回归的Cost Function是“非凸”的,如下图所示:

非凸函数-我爱公开课-52opencourse.com

我们知道,线性回归的Cost Function是凸函数,具有碗状的形状,而凸函数具有良好的性质:对于凸函数来说局部最小值点即为全局最小值点,因此只要能求得这类函数的一个最小值点,该点一定为全局最小值点。

凸函数-我爱公开课-52opencouse.com

因此,上述的Cost Function对于逻辑回归是不可行的,我们需要其他形式的Cost Function来保证逻辑回归的成本函数是凸函数。

这里补充一段李航博士《统计学习方法》里关于Cost Function或者损失函数(loss function)的说明,大家就可以理解Cost Function不限于一种方式,而是有多种方式可选,以下摘自书中的1.3.2小节:

监督学习问题是在假设空间F中选取模型f作为决策函数,对于给定的输入X,由f(X)给出相应的输出Y,这个输出的预测值f(X)与真实值Y可能一致也可能不一致,用一个损失函数(loss function)或代价函数(cost function)来度量预测错误的程度。损失函数是f(X)和Y的非负实值函数,记作L(Y, f(X)).

统计学习中常用的损失函数有以下几种:

(1) 0-1损失函数(0-1 loss function):

L(Y,f(X)) = \left\{ \begin{array}{ll} 1, & Y \neq f(X)\\0, & Y = f(X)\end{array}\right.

(2) 平方损失函数(quadratic loss function)

L(Y,f(X)) = (Y - f(X))^2

(3) 绝对损失函数(absolute loss function)

L(Y,f(X)) = |Y - f(X)|

(4) 对数损失函数(logarithmic loss function) 或对数似然损失函数(log-likelihood loss function)

L(Y,P(Y|X)) = -logP(Y|X)

损失函数越小,模型就越好。

逻辑回归的Cost Function:

基于上节的描述和补充,这里我们选择对数似然损失函数作为逻辑回归的Cost Function:

逻辑回归之对数似然损失函数-我爱公开课-52opencourse.com

直观的来解释这个Cost Function,首先看当y=1的情况:

对数似然损失函数解释1-我爱公开课-52opencouse.com

直观来看, 如果y = 1, h_\theta(x)=1,则Cost = 0,也就是预测的值和真实的值完全相等的时候Cost =0;

但是,当h_\theta(x) \to 0时, Cost \to \infty

直观来看,由于预测的结果南辕北辙:

如果h_\theta(x) = 0, 也就是预测P(y = 1|x; \theta) = 0,也就是y=1的概率是0,但是实际上y = 1

因此对于这个学习算法给予一个很大的Cost的惩罚。

同理对于y=0的情况也适用:

对数似然损失函数解释2-我爱公开课-52opencourse.com

5) Simplified cost function and gradient descent(简化版代价函数及梯度下降算法)

逻辑回归的Cost Function可以表示为:

逻辑回归代价函数-我爱公开课-52opencourse.com

由于y 只能等于0或1,所以可以将逻辑回归中的Cost function的两个公式合并,具体推导如下:

逻辑回归代价函数推导-我爱公开课-52opencourse.com

故逻辑回归的Cost function可简化为:

逻辑回归代价函数简化公式-我爱公开课-52opencourse.com

对于这个公式,这里稍微补充一点,注意中括号中的公式正是对逻辑回归进行最大似然估计中的最大似然函数,对于最大似然函数求最大值,从而得到参数(\theta???????????????????????????Cost function?????</p>
<p>!min_\theta J(\theta)</p>
<p>???????x???????h_\theta(x)????????</p>
<p><img src=

?????????????????????????" />\theta???J(\theta):</p>
<p><img src=

??????" />J(\theta)????????????</p>
<p><img src=

?" />J(\theta)?????????????</p>
<p><img src=

?????????????????????????????" />h_\theta(x)??????</p>
<p><strong>6) Advanced optimization(??????)</strong></p>
<p>?????</p>
<p>????\theta?????????????</p>
<p><img src=

??????????????????

  • Conjugate gradient method(?????)
  • Quasi-Newton method(????)
  • BFGS method
  • L-BFGS(Limited-memory BFGS)

????????????????????????????????

??????????????

??????????????

????????-???????????????????????????????????52nlp??????????????????????????????????????????????

???????????Quasi-Newton Method??LBFGS???????????????????????????????????????????????????????????????????????????????????????????
1) Numerical Methods for Unconstrained Optimization and Nonlinear Equations?J.E. Dennis Jr. Robert B. Schnabel?
2) Numerical Optimization?Jorge Nocedal Stephen J. Wright?

7) Multi-class classification: One-vs-all(??????)

?????????

??????/??? ???????????????????

????(medical diagrams): ??????????

????????????

????????????

??????-?????-52opencourse.com

???????????

??????-?????-52opencourse.com

One-vs-all(one-vs-rest):

????????????????????????????????????????????????????

?????-one-vs-all-?????-52opencourse.com

????????????????????

one-vs-rest-?????-?????-52opencourse.com

??-One-vs-all?????

?????? i ??????????????" />h^{(i)}_\theta(x)$$,并且预测 y = i时的概率;

对于一个新的输入变量x, 分别对每一个类进行预测,取概率最大的那个类作为分类结果:

多分类问题预测-我爱公开课-52opencourse.com

参考资料:

第六课“逻辑回归”的课件资料下载链接,视频可以在Coursera机器学习课程上观看或下载: https://class.coursera.org/ml
PPT   PDF

李航博士《统计学习方法

http://en.wikipedia.org/wiki/Sigmoid_function

http://en.wikipedia.org/wiki/Logistic_function

无约束最优化

http://en.wikipedia.org/wiki/Loss_function

http://en.wikipedia.org/wiki/Conjugate_gradient_method

http://en.wikipedia.org/wiki/Quasi-Newton_method

http://en.wikipedia.org/wiki/BFGS_method

http://en.wikipedia.org/wiki/Limited-memory_BFGS

 

EMNLP-CoNLL 2012 List of accepted papers

Deep Learning Specialization on Coursera

EMNLP-CoNLL 2012(Conference on Empirical Methods in Natural Language Processing and Natural Language Learning)会议将于2012年7月12-14日在韩国济州岛举行,以下是会议录用文章的情况,原文请参考官方网站:http://emnlp-conll2012.unige.ch/papers.html

继续阅读

Coursera公开课笔记: 斯坦福大学机器学习第四课“多变量线性回归(Linear Regression with Multiple Variables)”

Deep Learning Specialization on Coursera

斯坦福大学机器学习第四课"多变量线性回归“学习笔记,本次课程主要包括7部分:

1) Multiple features(多维特征)

2) Gradient descent for multiple variables(梯度下降在多变量线性回归中的应用)

3) Gradient descent in practice I: Feature Scaling(梯度下降实践1:特征归一化)

4) Gradient descent in practice II: Learning rate(梯度下降实践2:步长的选择)

5) Features and polynomial regression(特征及多项式回归)

6) Normal equation(正规方程-区别于迭代方法的直接解法)

7) Normal equation and non-invertibility (optional)(正规方程在矩阵不可逆情况下的解决方法)

以下是每一部分的详细解读: 继续阅读

用了两个新插件: MathJax和多说评论

Deep Learning Specialization on Coursera

因为需要在“我爱公开课”插入数学公式的缘故,所以用上了MathJax;因为MathJax实在太酷了,所以考虑能在52nlp的wordpress博客上用上,于是Google了一把,发现国内的一个牛人已经贡献了这样的一个插件,具体信息和使用方法可见:在博客上写数学公式的插件LaTex for WordPress。这个插件早期用得是传统的将Latex转换为图片然后进行缓存的方式,目前也将MathJax集成,是我见过的Wordpress上最强到的数学公式插件,强烈推荐使用Wordpress博客的同学使用。具体在使用时,可直接在标题、文章内容和留言中使用LaTex代码输入公式,非常方便。

使用“多说”则是为了尝试一下社交化的评论系统,而这篇文章的目的也是想测试一下多说提供的一些功能,譬如自动同步到微博等等,另外读者如果使用中发现存在某些问题,也请告知,非常感谢!

Coursera公开课笔记: 斯坦福大学机器学习第二课“单变量线性回归(Linear regression with one variable)”

Deep Learning Specialization on Coursera

斯坦福大学机器学习第二课"单变量线性回归“学习笔记,本次课程主要包括7部分:

1) Model representation(模型表示)

2) Cost function(代价函数,成本函数)

3) Cost function intuition I(直观解释1)

4) Cost function intuition II(直观解释2)

5) Gradient descent(梯度下降)

6) Gradient descent intuition(梯度下降直观解释)

7) Gradient descent for linear regression(应用于线性回归的的梯度下降算法)

以下是第二课“单变量线性回归”的课件资料下载链接,视频可以在Coursera机器学习课程上观看或下载:
PPT   PDF
另外课程答题时间推迟一周,具体可参考:  Coursera机器学习课程作业截止时间推迟一周
如转载52opencourse上的任何原创文章,请务必注明出处,原文见:

Ph.D. Level Graduate Research Assistants in Machine Learning and NLP

Deep Learning Specialization on Coursera

The Machine Learning and Natural Language Processing lab at the Kno.e.sis
Center in the Department of Computer Science and Engineering at Wright State
University is recruiting two, or more, highly motivated Ph.D. students to work on
three projects: (1) Large Scale Distributed Language Modeling, (2) Semisupervised
Structured Prediction, and (3) Direct Loss Minimization for
Classification and Ranking Problems, that are funded by NSF, AFOSR and Google.
The students are expected to have strong a) programming skills (past/current
projects can serve as evidence), and b) analytical skills (knowledge in algorithms,
optimization and statistics is essential). The research team currently consists of one
faculty - Dr. Shaojun Wang (http://knoesis.wright.edu/faculty/swang/) and 4 Ph.D.
students. They work together, have face-to-face in-depth discussions on a topic on
a regular basis, and target publishing both technically strong and empirically solid
papers at top machine learning and natural language processing conferences such
as ICML, NIPS and ACL and journals such as Journal of Machine Learning
Research and Computational Linguistics. Students have the opportunity to work as
summer interns at IBM, Google, Microsoft, and others in their 3rd year after they
enter the Ph.D. program. In the long run, Ph.D. students are expected to do
independent research after graduation.
Please contact Dr. Shaojun Wang at shaojun.wang@wright.edu for details.
Also, please visit http://knoesis.wright.edu to learn more about the Kno.e.sis
Center, the Ohio Center of Excellence in Knowledge-enabled Computing at Wright
State University.