斯坦福算法专项课程Course2 week1习题解析
这一部分将带来Course2 week1的习题解析。
选择题选择题1给定有向图的邻接列表表示，其中每个顶点记录其出去的边的数组（不是入边的数组），在最坏的情况下，需要多长时间来计算给定顶点的入度？
像往常一样，我们使用$n$和$m$分别表示给定图的顶点和边的数量。还有，让$k$表示顶点的最大入度。（回想一下顶点的入度是输入它的边数。）
无法确定
$\theta(k)$
$\theta(m)$
$\theta(n)$
只要遍历一遍全部的边，就可以计算出每个顶点的入度，所以为$\theta(m)$
选择题2考虑以下问题：给定有$n$个顶点$m$条边的无向图$G$以及两个顶点$s$和$t$，是否存在至少一个$s-t$路径？
如果$G$用邻接列表表示，则可以在$\theta(m+n)$时间解决上述问题 ，使用BFS或DFS。
如果$G$用邻接矩阵表示。在最坏的情况下，需要什么运行时间才能解决上述计算问题？（假使，假设$G$没有平行的边缘。）
$\theta(n^2)$
$\theta(m+n\log n )$
$\theta(m+n)$
$\theta(m\times n)$
可以先 ...
Neural Networks for Machine Learning Lecture 16
课程地址：https://www.coursera.org/learn/neural-networks
老师主页：http://www.cs.toronto.edu/~hinton
备注：笔记内容和图片均参考老师课件。
这周是课程的最后一次内容，介绍了几个新的应用。
Learning a joint model of images and captions这部分介绍了如何学习图像和标签的联合模型，效果是给每个图像一个标签，训练一共有三步：
1.训练图像的多层模型
2.训练词向量的多层模型
3.利用新的顶层把两个模型联合起来
可以从下图中看到步骤：
Hierarchical coordinate frames这部分主要是解决视角的问题，从下图中来看个例子：
老师指出CNN不太好解决这种问题，给出的方法是使用一组神经元来代表结合特征的形状及其相对于视网膜的姿势。简单来说就是增加神经元来表示特征的相对位置，如下图：
Bayesian optimization of neural network hyperparameters这部分是讲调参的，老师的意思是，如果超参数太多，那么手工调参 ...
台大实分析单元 6 测度与积分 2
这一讲开始介绍了单调收敛定理以及几乎处处的概念。
Therorem 2 单调收敛定理
\{f_n\}是一个单调非递减非负可测函数序列，那么\\
\int_{\Omega} \lim_{n\to \infty} f_n d\mu = \lim_{n\to \infty} \int_{\Omega}f_n d\mu证明：
由于$f_n\uparrow$，所以
f_1 \le ...\le f_n\le ... \le \lim_{n\to \infty} f_n又由于$f_n$非负，因此
\int_{\Omega}f_1d\mu \le ...\le \int_{\Omega}f_nd\mu\le ... \le \int_{\Omega} \lim_{n\to \infty} f_nd\mu \\
\lim_{n\to \infty} \int_{\Omega}f_n d\mu \le \int_{\Omega} \lim_{n\to \infty} f_n d\mu所以我们只要证明另一个方向的不等式即可。
为了证明
\lim_{n\to \infty} \int_{\Om ...
台大实分析单元 5 测度与积分 1
这一讲开始介绍测度与积分。
Unit 3 Measure and integration首先依旧给出以下记号：
\Omega :全集\\
2^{\Omega}:\Omega的幂集，i.e. 2^{\Omega}是\Omega的全体子集回忆：
\Phi \subset 2^{\Omega},\sigma: \Phi \to \overline {\mathbb{R}}^+\\
如果对于\varnothing \in \Phi， \sigma(\varnothing) =0，那么\sigma被称为集合函数\\
如果对于\Phi的子集A,B满足A\subset B,我们有\sigma(A) \le \sigma(B)，那么\sigma是单调的\\
如果对于非递增序列\{ A_n\} \subset \Phi且\bigcup_n A_n \in \Phi，我们有\sigma(\bigcup_n A_n) =\lim_{n\to \infty} \sigma(A_n)，那么\sigma是下连续的接着给出$\sigma$可加的定义：
\mathscr A是\Omega上的代数，\mu: \ ...
台大实分析单元 4 测度 2
这一讲继续讨论测度以及可测性，介绍了很多新的概念。
符号含义：
\Omega为全集，\Sigma为\Omega上\sigma代数 \\
\overline {\mathbb R} = \{-\infty\} \bigcup {\mathbb R} \bigcup \{\infty\}首先给出示性函数的定义：
A\subset \Omega，I_A(w)=\begin{cases}
1, & 如果w \in A\\
0, & 如果w \notin A
\end{cases}\\
称I_A为A的示性函数关于示性函数有如下命题：
I_A可测当且仅当A \in \Sigma这个结论只要根据定义验证即可。
关于$-\infty$和$\infty$的运算给出如下规则：
0\times \infty = 0\times (-\infty)=0 \\
如果a>0,a\times \infty = (-a)\times(-\infty) = \infty \\
如果a\alpha\}^C = \{f\le \alpha\} , \{f< \alpha\} =\bigcup_{n\in \ma ...
Coursera Cpp程序设计 week 6 Part 2
这一部分主要介绍函数模板和类模板。
课程地址：
coursera：C++程序设计
https://www.coursera.org/learn/cpp-chengxu-sheji
中国大学MOOC：程序设计与算法（三）C++面向对象程序设计
程序设计与算法（三）C++面向对象程序设计
函数模板和类模板函数模板函数模板样式：
template <class 类型参数1，class 类型参数2,……>
返回值类型 模板名 (形参表)
{
函数体
};
函数模板中可以有不止一个类型参数：
template <class T1, class T2>
T2 print(T1 arg1, T2 arg2)
{
cout<< arg1 << " "<< arg2<<endl;
return arg2;
}
不通过参数实例化函数模板：
#include <iostream>
using namespace std;
template <class T>
T Inc(T ...
t-SNE
t-SNE是一种降维算法，在可视化中经常使用，这里介绍其基本概念。
参考资料如下：
视频地址：
https://www.youtube.com/watch?v=4GBgqmq0XAY
介绍t-SNE之前，先介绍SNE
SNESNE的全称为Stochastic Neighbor Embedding，输入输出分别为：
X =[x_1,...,x_n] _{d\times n} \\
Y=[y_1,...,y_n]_{p\times n}一般来说，$p<d$，SNE算法将$X$映射到$Y$，起到了降维的作用，下面介绍具体算法：
对每个x_i,x_j，定义\\
p_{j|i} =\begin{cases}
\frac{\exp(-\frac{||x_i-x_j||^2}{2\sigma_i^2})}{\sum_{k\neq i}\exp(-\frac{||x_i-x_k||^2}{2\sigma_i^2}) } & i\ne j\\
0, & i= j
\end{cases} \\
对每个y_i,y_j，定义\\
q_{j|i} =\begin{cases}
\frac{\ex ...
Introduction to Deep Learning week 4
这一周主要介绍了Autoencoder,NLP以及GAN。
AutoencoderAutoencoders主要是将高维数据压缩，分为encode以及decode两个部分，如下图所示：
比较常用的就是PCA。
Deep autoencoder如果用更多层网络来训练的话，可以得到Deep autoencoder：
这里老师总结了需要autoencoder的原因：
压缩数据
降维
学习一些特征
Unsupervised pretraining
产生新数据
Natural language processing这一部分介绍了自然语言处理的基本概念。
Primer文本数据以下三部分组成：
Text:
A sequence of tokens(words).
Token/word:
A sequence of characters.
Character:
An atomic element of text. ¯_(ツ)_/¯
来看一个具体例子：
Bag of Words(BoW)文本处理的关键是把word转化为向量，方法叫做Bag of words：
...
Unit 4 Trees
这一周主要介绍了Cart以及randomForest的使用。
课程地址：
https://www.edx.org/course/the-analytics-edge
setwd("E:\\The Analytics Edge\\Unit 4 Trees")
stevens = read.csv("stevens.csv")
查看数据的结构。
str(stevens)
'data.frame': 566 obs. of 9 variables:
$ Docket : Factor w/ 566 levels "00-1011","00-1045",..: 63 69 70 145 97 181 242 289 334 436 ...
$ Term : int 1994 1994 1994 1994 1995 1995 1996 1997 1997 1999 ...
$ Circuit : Factor w/ 13 levels "10t ...
Neural Networks for Machine Learning Lecture 15
课程地址：https://www.coursera.org/learn/neural-networks
老师主页：http://www.cs.toronto.edu/~hinton
备注：笔记内容和图片均参考老师课件。
这周介绍了pre-train，这里主要回顾下选择题。
选择题 1The objective function of an autoencoder is to reconstruct its input, i.e., it is trying to learn a function $f$, such that $f(x) = x$ for all points $x$ in the dataset.It makes sense to learn a mapping from $x$ to some target $t$ for solving a classification or regression problem, but why do we want to learn a mapping that takes $x$ to $x$ ? It seems lik ...
斯坦福算法专项课程Course2 week1内容回顾
这一周的内容主要介绍了图算法。
课程地址：https://www.coursera.org/specializations/algorithms
Course 2 Week 1讨论之前，先规定记号的表示方法：令$n=$图中节点的个数，$m=$图中边的个数。
Introduction to Graph Search先来看最基本的图搜索算法：
这个图所搜算法基本上是对所有图算法的概括，下面介绍更具体的图算法。
BFSBreadth-First Search (BFS)有几个特点：
分层探索节点
可以计算最短路径
计算无向图的connected components
接下来来看具体算法：
Algorithm
来看一些BFS的特点。
Basic BFS Properties
Application: Shortest PathsBFS的一个应用是计算最短路径，只要在运行BFS算法同时计算层数即可。
Application: Undirected Connectivity计算connected components只要运行多次BFS即可。
DFSDepth-First Search ...
Introduction to Deep Learning week 3
第三周的内容介绍了CNN，这里主要回顾CNN的基本概念。
Introduction to CNNConvolutions如果使用第二周的MLP来进行图像识别，那么结果会和物体在图像中的位置有关，如下图：
所以我们不能直接使用MLP，解决的办法是卷积(Convolutions)：
Padding在做卷积运算的时候，处于角落位置的像素进行卷积运算的次数很小，为了解决这个问题，我们可以使用Padding，在原图片周围填充一些像素：
Backpropagation for CNN由于卷积运算会对许多像素进行重复运算，所以CNN中的反向传播和MLP中反向传播略有不同，需要进行累加：
StrideStride为步长，可以理解为kernel每次平移的像素数量，从一个例子中来看一下：
增加Stride主要是为了减少输出的维度。
PoolingPooling也是一种减少输出维度的方法，相当于直接把某些像素进行压缩，例如把每$2\times2$个像素取其中的最大值，来看一个例子：
Modern CNNs由于当$x$很大时，$\frac{1}{1+e^{-x}}$和$\tanh(x)$的梯度很 ...