斯坦福算法专项课程Course1 week4内容回顾
这周的内容主要是介绍了Linear Time Selection以及图的基本知识。
课程地址:https://www.coursera.org/specializations/algorithms
Course 1 Week 4Linear Time Selection考虑如下问题
Input: 有$n$个数字的数组$A$以及一个数字$i$(这里假设数字都不同)
Output: 输出第$i$小的数字
如果我们先使用排序,再处理这个问题,那么需要的时间为$O(n\log n)$,现在的问题是能否找到更好的算法,我们先介绍Randomized Selection
Randomized Selection回顾快速排序,在Partion之后,pivot左边的元素都小于pivot,pivot右边的元素都大于pivot,所以可以判断出pivot从小到大的次序$j$(等于小于pivot的元素个数加$1$):
如果$i=j$,那么直接输出pivot。
如果$i<j$,那么在小于pivot的$j-1$个元素中找第$i$小的元素。
如果$i>j$,那么在大于pivot的$n-j$个 ...
Neural Networks for Machine Learning Lecture 12
课程地址:https://www.coursera.org/learn/neural-networks
老师主页:http://www.cs.toronto.edu/~hinton
备注:笔记内容和图片均参考老师课件。
这一周的内容主要是讲玻尔兹曼机,老师叙述的角度太高层次了,导致完全没听懂,所以我专门写了一篇博客对受限玻尔兹曼机进行讲解,可以看完那篇再学习这周的内容,传送门/),这里主要回顾习题。
习题选择题 1玻尔兹曼机与前馈神经网络的区别在于:
玻尔兹曼机定义了数据的概率分布,但神经网络定义了数据的确定性转换。
玻尔兹曼机中隐藏单元的状态是随机变量,但在神经网络中,它是输入的确定性函数。
玻尔兹曼机没有神经网络的隐藏单位。
玻尔兹曼机中隐藏单元的状态是输入的确定性函数,并且难以精确计算,但在神经网络中,通过正向传递很容易计算。
玻尔兹曼机是概率模型,定义了概率分布,而前馈神经网络是确定性的转换,所以第一项正确。
由玻尔兹曼机是概率模型可知隐藏单元是随机变量,神经网络中,隐藏单元是确定值,所以第二项正确。
第三项显然是错的。
由玻尔兹曼机是概率模型可得第四项是错的。
选择题 ...
受限玻尔兹曼机(Restricted Boltzmann Machines, RBM)
Coursera上Hinton课程第12周内容为受限玻尔兹曼机,这一讲可以说是完全没听懂,网上中文的资料不够详尽,所以决定自己整理一份,主要是根据Youtube上一个视频及其课件整理。
参考资料如下:
视频地址:
https://www.youtube.com/watch?v=FJ0z3Ubagt4
课件地址:
https://uwaterloo.ca/data-analytics/sites/ca.data-analytics/files/uploads/files/dbn2.pdf
课程主页:
https://uwaterloo.ca/data-analytics/deep-learning
受限玻尔兹曼机介绍受限玻尔兹曼机是非监督学习算法,它是最常见的一些深度概率模型的构建块,包含一层可观察变量以及一层潜在变量的无向的的概率图形模型,可以用下图表示:
上图$v$为可见层(输入层),$h$为隐藏层,输入层一般是二进制数,我们后面只讨论二进制的输入,而之所以叫它“受限”玻尔兹曼机,是因为可见层内部以及隐藏层内部之间的节点没有连接。
受限玻尔兹曼机模型接下来我们来看具体模型:
p ...
斯坦福算法专项课程Course1 week3习题解析
这一部分将带来Course1 week3的习题解析。
选择题选择题 1令 $0<α<0.5 $是一个常数(与输入数组长度$n$无关)。回想一下QuickSort算法采用的Partition子程序,如讲座中所述。通过随机选择的pivot,Partition分割的两个子列中较小者的长度 $≥α$ 倍于原始数组的长度的概率?
$ 1 - 2\alpha$
$ \alpha$
$1-\alpha$
$2-2\alpha$
可以画个图,要使得这个事件发生,那么$\text{pivot}\in [\alpha n, (1-\alpha)n]$,所以该事件发生的概率为
\frac 1 n (1-2\alpha) n = 1-2\alpha选择题 2现在假设您在每次递归调用中都实现了上面的近似平衡拆分 - 也就是说,假设当递归调用给出一个长度为$k$的数组,那么Partition后子数组的长度都介于 $\alpha k$ 和$(1-\alpha)k$之间(其中$\alpha$是一个位于$0$到$0.5$之间的常数。在遇到base case之前会发生多少次递归调用?等价地,哪层的递归 ...
Coursera Cpp程序设计 week 3
这一周主要是介绍类运算符重载,下面回顾下。
课程地址:
coursera:C++程序设计
https://www.coursera.org/learn/cpp-chengxu-sheji
中国大学MOOC:程序设计与算法(三)C++面向对象程序设计
程序设计与算法(三)C++面向对象程序设计
运算符重载运算符重载的含义
运算符重载,就是对已有的运算符(C++中预定义的运算符)赋予多 重的含义,使同一运算符作用于不同类型的数据时导致不同类型的 行为。
运算符重载的目的是:扩展C++中提供的运算符的适用范围,使之能作用于对象。
同一个运算符,对不同类型的操作数,所发生的行为不同。
complex_a + complex_b 生成新的复数对象
5 + 4 = 9
运算符重载的形式
运算符重载的实质是函数重载
可以重载为普通函数,也可以重载为成员函数
把含运算符的表达式转换成对运算符函数的调用。
把运算符的操作数转换成运算符函数的参数。
运算符被多次重载时,根据实参的类型决定调用哪个运算符函数。
形式如下:
返回值类型 operator 运算符(形 ...
斯坦福算法专项课程Course1 week3内容回顾
这周的内容主要是介绍了Quick Sort并分析其平均运行时间。
课程地址:https://www.coursera.org/specializations/algorithms
Course 1 Week 3回顾排序问题
Input: n个数字的未排序数组
Output: 数组按递增顺序排列
这里假设元素都不相同。
这周来讨论Quick Sort,它是一种和Merge Sort不同的排序算法,在实际中更常用,下面详细回顾下:
Quick Sort在介绍Quick Sort之前,先考虑一种叫Partition的方法:
Partition选择一个pivot,对数组进行重新排列,使得pivot左边的元素都小于pivot,pivot右边的元素都大于pivot,这个过程叫Partition。
Partition的特点
1.可以在$O(n)$时间内完成,并且不需要额外的空间
2.减小了问题的规模
这里重点说下第一点。
我们先考虑空间的问题,我们使用交换元素的方式来处理,问了叙述方便,我们假设第一个元素为pivot(如果不是,和第一个元素交换即可),我们将数组分成三个部分:pivot,Al ...
Introduction to Deep Learning week 1
这一周开始学习Coursera Advanced Machine Learning 专项课程,这个专项课程一共由7门课,后续应该会学习完,每周会整理一些笔记,下面进入第一门课Introduction to Deep Learning第一周的内容回顾,第一周的内容主要是为神经网络的学习做铺垫。
Linear regression这部分非常熟悉了,直接给出公式
向量形式:a(x) =w^Tx\\
矩阵形式:a(X) = Xw\\
X= \left(
\begin{matrix}
x_{11}& ... & x_{1d} \\
... & ... & ... \\
x_{\ell1} &...& x_{\ell d}
\end{matrix}
\right)衡量这个模型需要用到平方误差损失函数(Mean squared error,简称MSE):
\begin{aligned}
L(w) &= \frac 1 \ell \sum_{i=1}^{\ell} (w^Tx_i-y_i)^2\\
&=\frac 1 \ell ||Xw - y||^2
\end{ ...
斯坦福算法专项课程Course1 week2习题解析
这一部分将带来Course1 week2的习题解析。
选择题选择题1$T(n) = 7T(n/3) + n^2$,那么$T(n)$的近似时间为
$\theta(n^2)$
$\theta(n^2\log n)$
$\theta(n^{2.81})$
$\theta(n \log n)$
应用主定理,$a= 7,b=3, d=2$,$a=7<9 = b^d$,所以时间复杂度为
\theta (n^d) = \theta(n^2)选择题2$T(n) = 9T(n/3) + n^2$,那么$T(n)$的近似时间为
$\theta(n^{2})$
$\theta(n \log n)$
$\theta(n^{3.17})$
$\theta(n^2 \log n)$
应用主定理,$a= 9,b=3, d=2$,$a=9 = b^d$,所以时间复杂度为
\theta(n^d \log n) = \theta(n^2 \log n)选择题3$T(n) = 5T(n/3) + 4n$,那么$T(n)$的近似时间为
$\theta(n^{\log_3 5})$
$\theta(n^{ ...
斯坦福算法专项课程Course1 week2内容回顾
这周的内容主要是再介绍了几个Divide and Conquer的例子,最后给出了分析时间复杂度的Master Method。
课程地址:https://www.coursera.org/specializations/algorithms
Course 2 Week 2The Closest Pair Problem
Input:$\mathbb R^2$中$n$个点$P=\{p_1,…,p_n\}$
Notation:$d(x_i,x_j)$为欧几里得距离
Output:$P$中两个距离最近的点$p,q$
这里我们假设每个点的横坐标,纵坐标均不相同。
这个问题的一维情形可以用排序解决,时间复杂度为$O(n\log n)$,二维情形如果暴力求解,那么时间复杂度为$\theta(n^2)$,现在的目标是把二维情形的时间复杂度降低到$O(n\log n)$。
我们先把这些点按$x$排序为$P_x$,按$y$排序为$P_y$,这一步需要$O(n\log n)$的时间,但这样做显然是不够的,后面还需要Divide+Conquer,伪代码如下:
备注:$Q_x$为$P_x$的前半部分,按 ...
Coursera Cpp程序设计 week 2
第二周的内容比较多,主要是介绍类的一些重要概念,下面回顾下。
课程地址:
coursera:C++程序设计
https://www.coursera.org/learn/cpp-chengxu-sheji
中国大学MOOC:程序设计与算法(三)C++面向对象程序设计
程序设计与算法(三)C++面向对象程序设计
类和对象类成员的可访问范围在类的定义中,用下列访问范围关键字来说明类成员 可被访问的范围:
private: 私有成员,只能在成员函数内访问
public : 公有成员,可以在任何地方访问
protected: 保护成员,以后再说
设置私有成员的机制,叫“隐藏” ,“隐藏”的目的是强制对成员变量的访问一定要通过成员函数进行,那么以后成员变量的类型等属性修改后,只需要更改成员 函数即可。否则,所有直接访问成员变量的语句都需要修改。
构造函数构造函数有如下特性
名字与类名相同,可以有参数,不能有返回值(void也不行)
作用是对对象进行初始化,如给成员变量赋初值
如果定义类时没写构造函数,则编译器生成一个默认的无参数 的构造函数,默认构造函数无参 ...
Neural Networks for Machine Learning Lecture 11
课程地址:https://www.coursera.org/learn/neural-networks
老师主页:http://www.cs.toronto.edu/~hinton
备注:笔记内容和图片均参考老师课件。
这一章中间一部分感觉完全没听懂在干嘛,这里就总结下Hopfield Nets的定义以及玻尔兹曼机。
Hopfield NetsHopfield Nets是由二进制神经元组成的递归神经网络,非线性递归神经网络往往很难分析,John Hopfield等人注意到如果链接是对称的,存在一个全局能量函数(这里能量的含义为一种度量的意思),来看能量函数的定义:
E = − \sum _is_ib_i-\sum_{i< j} s_is_j w_{ij}\\
s_i \in \{0,1\}这个公式让我们能够计算开关某个神经元对于能量的影响:
\text{Energy gap} = \Delta E_i = E(s_i=0) -E(s_i=1)=b_i+\sum_{j} s_j w_{ij}找到能量最低的点的方法为从一个随机的初始状态开始,每次以随机的顺序改变一个神经元,来看如下 ...
Coursera Cpp程序设计 week 1
这里开始总结下北大郭炜老师的C++课程,课程地址如下,在两个地方分别开课,但是内容基本一致,这里会按照coursera上的内容按周进行总结回顾,以下是第一周的内容。
课程地址:
coursera:C++程序设计
https://www.coursera.org/learn/cpp-chengxu-sheji
中国大学MOOC:程序设计与算法(三)C++面向对象程序设计
程序设计与算法(三)C++面向对象程序设计
从C到C++函数指针定义形式 :
类型名 (* 指针变量名)(参数类型1, 参数类型2,…);
例如: int (*pf)(int ,char);
表示pf是一个函数指针,它所指向的函数,返回值类型应是int, 该函数应有两个参数,第一个是int 类型,第二个是char类型。
看一个具体例子
#include <stdio.h>
void PrintMin(int a,int b) {
if( a<b )
printf("%d",a);
else
printf("%d",b);
}
int ...