CS205A Lecture 4 Designing linear systems (incl. least-squares); special structure (Cholesky, sparsity)
课程主页:https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html
这次回顾第四讲,这一讲结束了LU分解的内容,介绍敏感性和病态性。
Chapter 3 设计和分析线性系统回归假设我们的函数有如下形式
f(\vec x) =\sum_{i=1}^m a_i f_i (\vec x)如果我们有$m$个观测值,那么可以得到如下线性系统:
\left(
\begin{matrix}
f_1(\vec x^{(1)}) & f_2(\vec x^{(1)}) & \ldots &f_m(\vec x^{(1)}) \\
f_1(\vec x^{(2)}) & f_2(\vec x^{(2)}) & \ldots &f_m(\vec x^{(2)}) \\
\vdots & \vdots & \vdots & \vdots \\
f_1(\vec x^{(m)}) & f_2(\vec x^{(m)}) & \ldots &f_m(\vec x^{(m)})
\end{mat ...
CS205A Lecture 3 More LU; conditioning and sensitivity
课程主页:https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html
这次回顾第三讲,这一讲结束了LU分解的内容,介绍敏感性和病态性。
更多的$LU$上一次的讨论中我们介绍了$LU$分解,但实际中并不是每个矩阵都能进行$LU$分解,实际中可能会交换列,于是有如下恒等式:
\underbrace {(E_k...E_1)}_{消除矩阵}.A.\underbrace {(P_1...P_l)}_{置换矩阵}
.\underbrace {(P_l^T...P_1^T)}_{置换矩阵的逆} \vec x = (E_k...E_1) \vec b经过操作后,${(E_k…E_1)}.A.{(P_1…P_l)}$为上三角矩阵,于是
A=LUP其中$L$是下三角矩阵,$U$是上三角矩阵,$P$是置换矩阵。
敏感性分析这一部分主要讨论扰动对于线性方程组的影响,具体来说,我们考虑
(A+\delta A)\vec x = \vec b +\delta \vec b讨论这个问题,我们需要度量大小的工具,这就引入了向量范数的概 ...
CS205A Lecture 2 Linear systems and LU
课程主页:https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html
这次回顾第二讲,这一讲主要讨论了线性方程组的求解以及LU分解。
Chapter 2 线性系统和LU分解线性系统的可求解性线性方程组的形式如下:
\begin{aligned}
A\vec x &=\vec b \\
A& \in \mathbb R^{m\times n}\\
\vec x& \in \mathbb R^{ n}\\
\vec b& \in \mathbb R^{m}
\end{aligned}解的情形一共以下三种:
唯一解:
\left(
\begin{matrix}
1 & 0 \\
0 & 1
\end{matrix}
\right) \left(
\begin{matrix}
x \\
y
\end{matrix}
\right) =\left(
\begin{matrix}
-1 \\
1
\end{matrix}
\right)
无解:
\left( ...
CS205A Lecture 1 Introduction; numerics; error analysis
之前一直想学数值分析,网上查阅了下,发现一个斯坦福的公开课还不错,讲义,作业,视频都有,所以决定10周时间学完,后续会做一些笔记。
课程主页:https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html
这次回顾第一讲,这一讲主要介绍数值分析的基本概念。
Chapter 1 数值与误差分析存储带小数的数字计算机中的数字都是以二进制形式存储,例如$463$可以表示为:
\begin{aligned}
463 &= 2^8 + 2^7 + 2^6 + 2^3 + 2^2 + 2^1 + 2^0 \\
&= 256 + 128 + 64 + 8 + 4 + 2 + 1
\end{aligned}表格的形式如下:
$1$
$1$
$1$
$0$
$0$
$1$
$1$
$1$
$1$
$2^8$
$2^7$
$2^6$
$2^5$
$2^4$
$2^3$
$2^2$
$2^1$
$2^0$
小数也同理,只要加上$2^{-n}$次方即可,例如$463.25$:
$1$
$1$
$1$
$0 ...
CS229 老版作业3
课程视频地址:http://open.163.com/special/opencourse/machinelearning.html
课程主页:http://cs229.stanford.edu/
更具体的资料链接:https://www.jianshu.com/p/0a6ef31ff77a
作业地址:https://github.com/Doraemonzzz/CS229
参考资料:https://github.com/zyxue/stanford-cs229
这部分回顾老版作业3。
1. Uniform convergence and Model Selection(a)由Hoeffding不等式,我们可得对每个$\hat h_i $,
P(|\epsilon(\hat h_i)-\hat \epsilon_{S_{\text{cv}}}(\hat h_i)|>\gamma )
\le 2 k e^{-2\gamma ^2 \beta m} \\
P(|\epsilon(\hat h_i)-\hat \epsilon_{S_{\text{cv}}}(\hat h_i)|\le ...
CS229 2017版作业3
课程视频地址:http://open.163.com/special/opencourse/machinelearning.html
课程主页:http://cs229.stanford.edu/
更具体的资料链接:https://www.jianshu.com/p/0a6ef31ff77a
作业地址:https://github.com/Doraemonzzz/CS229
参考资料:https://github.com/zyxue/stanford-cs229
这部分回顾2017版作业3。
1. A Simple Neural Network记第二层的输出为$g^{(i)}$
(a)由$w^{[1]}_{1,2}$的定义可知,我们需要先求出关于$h_2$的偏导数。
注意到我们有
o^{(i)} = f(w^{[2]}_{0}+w^{[2]}_{1} h_1^{(i)}+w^{[2]}_{2} h_2^{(i)} + w^{[2]}_{3} h_3^{(i)})其中$f$为sigmoid函数,那么先计算$l$关于$h_2^{(i)} $的偏导数可得
\begin{aligne ...
CS229 2017版作业2
课程视频地址:http://open.163.com/special/opencourse/machinelearning.html
课程主页:http://cs229.stanford.edu/
更具体的资料链接:https://www.jianshu.com/p/0a6ef31ff77a
作业地址:https://github.com/Doraemonzzz/CS229
参考资料:https://github.com/zyxue/stanford-cs229
这部分回顾2017版作业2。
1. Logistic Regression: Training stability(a)在数据A上训练logistic regression model很快就收敛了,在数据B上训练logistic regression model无法收敛。
(b)观察后可以发现$\theta$的模长来越大,回顾logistic regression model
h_θ(x) = g(θ^T x) ,g(z) = 1/(1 + e^{−z}),g(z)' = g(z)(1-g(z))当$\theta$的模长很 ...
搭建博客一周年
这篇是一篇随笔,主要对搭建博客一周年做一些小结。
不知不觉这个博客已经建立了一周年,算上今天刚上传的文章,正好两百篇,大部分文章篇幅都不短,应该算相当高产了。在这个一周年纪念日还是相当有感触的,起码去年的时候从没想过自己能坚持多久,没想到在这一年里写博客逐渐成为了习惯,也收获了很多,下面一一进行回顾。
起因其实最初做这个博客是因为看到某个大佬的博客:
http://www.hankcs.com/
这位大佬记录了自己一路学习的过程,当时看到的时候挺受触动的,那时恰逢考研复试之前,所以我自己也萌生了写博客的想法,想记录自己学习的过程,在收集一番资料后,于是有了我第一篇博客。
当时的计划是以后从事机器学习相关的工作,所以这部分是我主要学习的内容。但由于我本科是数学系,唯一学过的计算机课程是C语言,还学得稀烂,所以为了以后走的更远更稳,我给自己定了一个在硕士毕业前(约两年半时间)系统学完计算机课程的计划。目前机器学习部分的理论知识已经比较扎实了,这段时间要加强实战能力,准备参加kaggle的比赛,后续应该会写一些总结;计算机科学部分过去一年主要在学习各种语言,以及算法与数据结构,后续准备学一 ...
Michael Collins NLP Lecture 15
课程主页:http://www.cs.columbia.edu/~cs4705/
课程网盘地址:
链接:https://pan.baidu.com/s/1r0f7I2j6rtlK31VplwHa1Q提取码:pw02
这一讲介绍了用感知机算法解决依存句法分析(Dependency Parsing)。
依存句法分析(备注,这部分介绍的是没有标签的依存句法分析)
首先介绍依存句法分析,每个依存句由如下两个元素构成:
$\text{root}$是特殊的根符号。
每个依存句是一对$(h,m)$,其中$h$是首单词的索引,$m$是修饰词的索引。 在图中,我们通过从$h$到$m$的有向边表示依存关系$(h,m)$。
来看个例子:
上图中的依存关系为$(0, 2),(2,1),(2,4),(4,3)$,其中$0$表示根。句子$\text{John saw Mary}$的全部可能的依存关系如下:
我们讨论的依存结构有如下两个条件:
依赖关系弧形成有向树,$\text{root}$符号位于树的根部。(定义:以$\text{root}$为根的有向树是树,如果对于除根之外的每个单词$w$,都有从 ...
Michael Collins NLP Lecture 14
课程主页:http://www.cs.columbia.edu/~cs4705/
课程网盘地址:
链接:https://pan.baidu.com/s/1r0f7I2j6rtlK31VplwHa1Q提取码:pw02
这一讲介绍了用全局线性模型解决标注问题。
回顾标注问题:
在全局线性模型下,标注模型的元素如下:
输入$x$是句子$w_{[1:n]}= \{w_1…w_n\}$
定义$\mathcal T$为标注的集合
$\text{GEN}(w_{[1:n]}) =\mathcal T^n$,即所有长度为$n$的标注序列。
注意此时$\text{GEN}$和句子长度呈指数关系。接下来的问题是如何定义$f$?
我们首先回顾历史的概念:
历史是$4$元组$\langle t_{-2}, t_{-1}, w_{[1:n]},i \rangle$
$t_{-2},t_{-1}$是之前两个标注
$ w_{[1:n]}$是输入句子的$n$个单词
$i$是正在被标注的单词的索引
来看个具体例子:
局部特征向量表示给定历史/标注对$(h,t)$,$g_s(h,t), s=1,…,d$是 ...
Michael Collins NLP Lecture 13
课程主页:http://www.cs.columbia.edu/~cs4705/
课程网盘地址:
链接:https://pan.baidu.com/s/1KijgO7yjL_MVCC9zKZ7Jdg提取码:t1i3
这一讲介绍了全局线性模型(Global Linear Models)。
简要回顾基于历史的方法我们之前介绍的内容形式基本为推断从集合$\mathcal X$到集合$\mathcal Y$的映射$F$,例如:
问题
$x\in \mathcal X$
$y\in \mathcal Y$
解析
句子
解析树
机器翻译
法语句子
英语句子
词性标注
句子
标注序列
并且上述内容均为监督式学习:即我们有训练集$(x_i, y_i),i=1…m$。
之前大多数模型都是基于历史的模型:
我们将结构分解为衍生物(derivation)或决策序列。
每个决策都有一个相关的条件概率。
结构的概率是决策概率的之积。
使用最大似然估计的估计参数值。
函数$F:\mathcal X \to \mathcal Y$定义为
F(x)= \arg\max_ ...
Michael Collins NLP Lecture 12
课程主页:http://www.cs.columbia.edu/~cs4705/
课程网盘地址:
链接:https://pan.baidu.com/s/1KijgO7yjL_MVCC9zKZ7Jdg提取码:t1i3
这一讲介绍了Brown聚类算法。
Brown聚类算法简介首先看下算法的输入输出:
输入:大量单词的语料库。
输出1:将单词划分为单词类。
输出2(1的一般化):分层单词聚类。
来看下聚类结果:
第二张图的含义是给同一类的单词相似的编码,可以利用树做到这点。
Brown聚类模型算法的直觉很简单,即相似的单词的前后单词的分布相似,根据这个思路,构建如下模型:
$\mathcal V是语料库w_1,w_2,…,w_n$中的所有单词。
$C:\mathcal V \to \{1,2,…,k\}$是将词汇划分为$k$类的映射。
对每个$v\in \mathcal V,c\in \{1…k\}$,定义参数$e(v|c)$。
对每个$c\in \{1…k\},c’\in \{1…k\}$,定义参数$q(c’|c)$。
模型如下:
p(w_1,w_2,...,w_n ...