台大实分析单元 18 Caratheodory Measure 4
这一部分介绍了method2。
令$X$是一个度量空间,$\tau:\mathcal G \to [0,\infty]$为$\mathcal G \subset 2^X$上的准测度,对每个$\epsilon >0,A\subset X$,令
\tau_{\epsilon}(A)=\inf \sum_{j} \tau(C_j)\\
\text{其中}\{C_j\}\subset \mathcal G,\text{dim} C_j \le \epsilon, A\subset \bigcup_j C_j \\
\tau^d(A) =\lim_{\epsilon \to 0}\tau_{\epsilon}(A)$\tau^d$被称为$X$上由method 2从$\tau$构造的测度。注意由于$\epsilon$越小,满足条件的$\{C_j\}$越少,从而$\tau_{\epsilon}(A)$越大,所以我们有
\tau_{\epsilon}(A) \le \tau^d(A)Exercise 1
\tau^d是X上的\text{Caratheodory}测度Proposition ...
台大实分析单元 17 Caratheodory Measure 3
这一部分介绍了Lebesgue-Stieltjes测度以及Borel正则和Radom测度。
Unit 5 Caratheodory Measure回顾Lebesgue-Stieltjes测度的定义:
令g是\mathbb R 上单调非降函数,\mathcal G 是\mathbb R上全体有限开区间,\\
如果I=(a,b),令\tau(I) =g(b) -g(a),\\
\tau^*=\mu_g为从利用\text{method }1从准测度\tau构建的外测度, \\
\mu_g被称为\text{Lebesgue-Stieltjes}测度,\\
特别的,如果g(t)=t,那么\mu_g = \lambda我们有如下定理
Theorem 3
测度\mu_g是\text{Caratheodory}测度,并且在有界集上取有限值。\\
此外,存在开集序列\{G_k\}使得A\subset \bigcap_{k}G_k,并且\mu_g(A) =\inf_{k}\mu_g(G_k),\\
特别地,存在G_{\delta}集合B,使得A\subset B且\mu_g(A)=\mu_g(B)证 ...
CS229 Lesson 10 特征选择
课程视频地址:http://open.163.com/special/opencourse/machinelearning.html
课程主页:http://cs229.stanford.edu/
更具体的资料链接:https://www.jianshu.com/p/0a6ef31ff77a
笔记参考自中文翻译版:https://github.com/Kivy-CN/Stanford-CS-229-CN
这一讲介绍了VC维以及特征选择。
4 无限个假设(infinite $\mathcal H$)的情况介绍之前给出一些定义。
给定集合$S =\{x^{(1)} ,…,x^{(d)}\}$,其中$x^{(i)} \in \mathcal X$,我们称$\mathcal H$打散(shatter)$S$如果$\mathcal H$能实现$S$上任意一种标签。即对任意标签集$\{y^{(1)} ,…,y^{(d)}\}$,存在$h\in \mathcal H$,使得$h(x^{(i)}) = y^{(i)}$。给定集合$\mathcal H$,定义其VC维(VapnikChervonenk ...
浙大数据结构补充内容
课程地址:https://www.icourse163.org/course/ZJU-93001笔记中图片均来自此mooc中讲义。
之前发现新的课程中补充了KMP算法,这里做下回顾。
串的模式匹配串的模式匹配是找在文本中找到某个模式第一次出现的位置:
这里讨论的一般为字符串,设文本的长度为$n$,模式的长度为$m$,下面看下处理的方法。
蛮力算法
最基本的思路是蛮力算法,即让模式的头指针遍历文本的每个位置,然后比较后续对应位置的元素,不难看出,时间复杂度为$O(nm)$,这种时间复杂度是很难让人接受的,幸运的是,有人给出了KMP算法。
KMP算法蛮力算法中模式的头指针一次只移动一个位置,那么这种操作能否改进呢?回答是肯定的,来看下面的例子:
为了讨论方便,这里引进两个新的变量$s,p$,$s$为文本当前匹配位置,$p$为模式当前匹配位置,通过移动$s,p$来进行匹配操作。图中$s$指向$x$,$p$指向$c$,因为$c\neq x$,所以指针要移动,蛮力算法是将$s$回退到第一个$b$的位置,$p$回退到模式的头指针位置,但是我们观察上图不难发现pattern的头部$ab$和$p ...
CS229 Hoeffding不等式补充资料
课程视频地址:http://open.163.com/special/opencourse/machinelearning.html
课程主页:http://cs229.stanford.edu/
更具体的资料链接:https://www.jianshu.com/p/0a6ef31ff77a
笔记参考自中文翻译版:https://github.com/Kivy-CN/Stanford-CS-229-CN
这一部分主要回顾有关Hoeffding不等式的补充资料。
常用的概率不等式关于随机变量,人们往往对如下概率感兴趣
\mathbb P(Z\ge \mathbb E [Z] + t) ,\mathbb P(Z\le \mathbb E [Z] - t)Hoeffding不等式正是对这种概率的一个估计,在证明Hoeffding不等式之前,要介绍几个常用的命题。
命题 1 (马尔可夫不等式)令$Z\ge 0$是一个非负随机变量,那么对任意$t\ge 0$,
\mathbb P(Z\ge t) \le \frac{\mathbb E [Z]}{t}证明:注意到$\mathbb P(Z\g ...
CS229 Lesson 9 经验风险最小化
课程视频地址:http://open.163.com/special/opencourse/machinelearning.html
课程主页:http://cs229.stanford.edu/
更具体的资料链接:https://www.jianshu.com/p/0a6ef31ff77a
笔记参考自中文翻译版:https://github.com/Kivy-CN/Stanford-CS-229-CN
CS229是吴恩达老师在斯坦福教授的课程,内容比coursera更加深入,非常值得学习,之前学的时候没有仔细做笔记,感觉效果不是很好,决定从第九讲开始做一个详细的笔记,之前的部分后续补上。
Part V
学习理论(Learning Theory)1 偏差/方差的权衡(Bias/variance tradeoff )首先看下下图:
我们的目标函数是二次的,第一张图采用一次函数拟合,第三张图采用五次函数拟合,这两种情况的泛化误差都很大,但是产生的原因是不同的。第一张图在训练集上误差就很大,并且无论训练集有多少数据,得到的效果都不会太好,因为一次函数很难捕捉二次函数的特点,这种情形称为 ...
Introduction to Deep Learning week 5
这一周主要介绍了RNN,这里回顾下RNN的反向传播。
Recurrent Neural Network (RNN)RNN主要运用于序列数据,其架构如下:
右边是实际的架构,左边是拆开后的架构,方便理解,计算公式为:
h_t= f_t(Vx_t+Wh_{t-1} +b_h),\hat y _t =f_y(Uh_t+ b_y)损失函数为:
L = \sum_{i}
L_i(y_i, \hat y_i)Backpropagation Through Time (BPTT)下面介绍RNN的反向传播,我们借助下图进行理解:
可以看出我们要对两个方向进行反向传播,下面分别计算上图的偏导数。
$\frac{\partial L}{\partial U}$:
\frac{\partial L}{\partial U} =\sum_{t=0}^T\frac{\partial L_t}{\partial U}
=\sum_{t=0}^T\frac{\partial L_t}{\partial \hat y_t}
\frac{\partial \hat y_t}{\partial U} \\
\ ...
台大实分析单元 16 Caratheodory Measure 2
这一部分介绍了Lebesgue-Stieltjes测度。
Unit 5 Caratheodory Measure回顾上一讲的结论
Theorem 1
如果\mu是度量空间X上一个\text{Caratheodory}测度,那么X的每个闭集都\mu可测由于$X$的每个闭集都$\mu$可测,所以$X$的每个开集都$\mu$可测,从而包含$X$的Borel集都可测,因此有如推论
Collary
\mathcal B (X) \subset {\sum}^{\mu}Lebesgue-Stieltjes measure接下来介绍Lebesgue-Stieltjes测度,首先给出定义
令g是\mathbb R 上单调非降函数,\mathcal G 是\mathbb R上全体有限开区间,\\
如果I=(a,b),令\tau(I) =g(b) -g(a),\\
\tau^*=\mu_g为从利用\text{method }1从准测度\tau构建的外测度, \\
\mu_g被称为\text{Lebesgue-Stieltjes}测度,\\
特别的,如果g(t)=t,那么\mu_g = \lambda ...
台大实分析单元 15 Caratheodory Measure 1
这一部分介绍了Caratheodory Measure。
Unit 5 Caratheodory Measure这一讲开始将介绍Caratheodory Measure,下面给出Caratheodory Measure的定义:
X是一个度量空间,度量为\rho,X上的测度为\mu被称为\text{Caratheodory}测度,\\
如果\mu(A\bigcup B) = \mu(A) +\mu(B)只要\rho(A,B) = \inf_{x\in A,y\in B} \rho(x,y)>0Theorem 1
如果\mu是度量空间X上一个\text{Caratheodory}测度,那么X的每个闭集都\mu可测在证明之前,首先给出一个引理
Lemma 1
\mu是度量空间X上一个\text{Caratheodory}测度,\\
令A_1\subset A_2 \subset ...\subset A_n \subset A_{n+1}\subset ...为X中递增子集,使得对每个n,\rho(A_n ,A_{n+1}^C)>0,\\
那么\mu(\bigcup_{n=1}^{\in ...
斯坦福算法专项课程Course2 Final Exam
这里回顾下第二门课的期末考试。
课程地址:https://www.coursera.org/specializations/algorithms
选择题 1考虑边长非负的有向图$G=(V,E)$ 和两个不同的顶点$s,t$。让$P$表示$G$中$s$到$t$的最短的路径。如果我们在图中的每条边的长度上加$10$,那么:
如果$P$只有一条边, $P$绝对是$s-t$最短路径
$P$可能会也可能不会保持最短$s-t$最短路径(取决于图)
$P$绝对是$s-t$最短路径
$P$绝对不是$s-t$最短路径
因为每条边都增加$10$,所以总长度为原长度加上边的数量乘以$10$,不难看出前两项正确
选择题 2DFS的运行时间是多少,作为$n$和$m$的函数,如果是输入图$G=(V,E)$ ,图由邻接矩阵表示$n=|V|,m=|E|$?
$\theta(n+m)$
$\theta(n^2 \log m)$
$\theta(n^2)$
$\theta(n*m)$
每次要扫描和某个点相连的节点,判断是否有边存在,时间复杂度为$\theta(n^2)$,第三项正确
选择题 3对于有$n ...
斯坦福算法专项课程Course3 week1习题解析
这一部分将带来Course3 week1的习题解析。
选择题选择题 1我们作为输入给出了一组$n$请求(例如,使用礼堂),对于每个请求$i$有已知的开始时间$s_i$和完成时间$t_i$。假设所有开始和结束时间都是不同的。如果两个请求在时间上重叠,则会发生冲突 ——如果其中一个请求在另一个请求的开始和结束时间之间开始。我们的目标是选择不包含冲突的给定请求的最大子集。(例如,给定三个请求的时间区间为$[0,3]$, $[2,5]$,和$[4,7]$,我们想要返回第一个和第三个请求。)我们的目标是使用以下形式为此问题设计一个贪心算法:在每次迭代时,我们选择一个新请求$i$,将其加入到目前为止的解决方案,并在未来删除所有与之冲突的请求。
以下哪种贪婪规则可以保证始终能够计算出最佳解决方案?
在每次迭代中,选择与剩余请求冲突最少的剩余请求(重复时任意选取)。
在每次迭代时,使用最早的开始时间选择剩余的请求。
在每次迭代中,选择需要最少时间的剩余请求(具有最小$t_i-s_i$的剩余请求)(重复时任意选取)。
在每次迭代时,选择最早完成时间的剩余请求。
答案为最后一项,每次选择完 ...
台大实分析单元 14 外测度 5
这一部分继续介绍了正则外测度的概念。
继续上次的内容,给出如下推论:
Collary 1
给定一个测度空间(\Omega,\sum,\mu),\\利用\text{method 1}从准测度\tau构建的外测度\mu^*
是在\Omega上满足\mu^*(A)=\mu(A)的唯一的\sum-正则测度,A\in \sum\\
注意\sum\subset {\sum}^{\mu^*}证明:
因为$\sum$是$\sigma$代数($\sum_{\sigma\delta}= \sum$),所以由Proposition 2,$\mu^*$是$\sum-正则$,结论第一部分证毕。
接下来证明唯一性:
令$\nu$是$\Omega$上一个$\sum-正则$测度,使得$\nu(A)=\mu(A)$对于$A\in\sum$。
现在任取$B\subset \Omega$,存在$\sum$中$A_1$和$A_2$,使得$B\subset A_1,B\subset A_2$,并且
\mu^*(A_1)= \mu^*(B),\nu(A_2)= \nu(B)取$A= A_1\bigcap A_2\in \su ...