Doraemonzzz

本科的时候也学习过实分析，但那时候学的比较差，现在发现这门课真的很重要，所以决定重新学习一遍，网上找了一些资料后发现台大劉豐哲老师的课程不错，决定把这门课自学完，整理一些笔记，记录作业的解答，这部分是第一讲的内容。 附上课程地址： http://ocw.aca.ntu.edu.tw/ntu-ocw/ocw/cou/105S109/36 Unit 1. Introduction and Examples1.1 Summability of systems of real numbers我们先考虑求和的问题，考虑莱布尼茨级数 \sum_{n=1}^{\infty}\frac { (-1)^{n-1}} n我们知道这个级数收敛，但是这个级数按照不同的顺序相加得到的结果不同，这是一种不太好的性质，所以老师重新定义一种求和式，在这种定义下的收敛和求和顺序无关（相当于绝对收敛）。 考虑一个集合$\{C _\alpha \}_{\alpha \in I}$，$I$是一个指标集，后面为了叙述方便，将$\{C _\alpha \}_{\alpha \in I}$简写为$\{C _\alpha \}$ ...

这一周的内容主要是介绍继承和派生，下面回顾下。 课程地址： coursera：C++程序设计 https://www.coursera.org/learn/cpp-chengxu-sheji 中国大学MOOC：程序设计与算法（三）C++面向对象程序设计 程序设计与算法（三）C++面向对象程序设计 继承和派生基本概念继承：在定义一个新的类B时，如果该类与某个已有的类A相似(指的是B拥有A的全部特点)， 那么就可以把A作为一个基类，而把B作为基类的一个派生类(也称子类)。 派生类拥有基类的全部成员函数和成员变量，不论是private、protected、public并且在派生类的各个成员函数中，不能访问基类中的private成员。 来看一个学生类和大学生类，研究生类的例子： class CStudent { private: string sName; int nAge; public: bool IsThreeGood() { }; void SetName ...

第二周的内容介绍了多层感知机（MLP），反向传播以及TensorFlow的基本使用，这里主要回顾多层感知机（MLP）和反向传播的内容。 先来看最简单的神经网络，多层感知机（MLP） The simplest neural network: MLPMLP考虑如下问题： 我们的目标是区分出标记为$+,-$的点，之前的分类模型对应二维平面一条直线，这张图显然是无法用一条直线来分类，但是我们可以画出多条直线，如下所示： 其中$\sigma(x) =\frac{1}{1+e^{-z}}$。现在我们可以利用得到的$(z_1,z_2,z_3)$再进行分类，画图之后可以发现，这样就可以分类了，把上述过程的计算式写出来： z_i =\sigma(w_{0,i} +w_{1,i}x_1+w_{2,i}x_2) \\ a(x) = \sigma(w_0+w_1z_1(x)+w_2z_2(x)+w_3z_3(x))\\ \sigma(x) =\frac{1}{1+e^{-z}}上述过程可以用计算图表示出来： 我们的计算图被称为多层感知机(Multi-layer perceptron,MLP)，图中的 ...

这周的内容主要是介绍了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$个 ...

课程地址：https://www.coursera.org/learn/neural-networks 老师主页：http://www.cs.toronto.edu/~hinton 备注：笔记内容和图片均参考老师课件。 这一周的内容主要是讲玻尔兹曼机，老师叙述的角度太高层次了，导致完全没听懂，所以我专门写了一篇博客对受限玻尔兹曼机进行讲解，可以看完那篇再学习这周的内容，传送门/)，这里主要回顾习题。 习题选择题 1玻尔兹曼机与前馈神经网络的区别在于： 玻尔兹曼机定义了数据的概率分布，但神经网络定义了数据的确定性转换。 玻尔兹曼机中隐藏单元的状态是随机变量，但在神经网络中，它是输入的确定性函数。 玻尔兹曼机没有神经网络的隐藏单位。 玻尔兹曼机中隐藏单元的状态是输入的确定性函数，并且难以精确计算，但在神经网络中，通过正向传递很容易计算。 玻尔兹曼机是概率模型，定义了概率分布，而前馈神经网络是确定性的转换，所以第一项正确。 由玻尔兹曼机是概率模型可知隐藏单元是随机变量，神经网络中，隐藏单元是确定值，所以第二项正确。 第三项显然是错的。 由玻尔兹曼机是概率模型可得第四项是错的。 选择题 ...

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的习题解析。 选择题选择题 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：C++程序设计 https://www.coursera.org/learn/cpp-chengxu-sheji 中国大学MOOC：程序设计与算法（三）C++面向对象程序设计 程序设计与算法（三）C++面向对象程序设计 运算符重载运算符重载的含义 运算符重载，就是对已有的运算符(C++中预定义的运算符)赋予多 重的含义，使同一运算符作用于不同类型的数据时导致不同类型的 行为。 运算符重载的目的是：扩展C++中提供的运算符的适用范围，使之能作用于对象。 同一个运算符，对不同类型的操作数，所发生的行为不同。 complex_a + complex_b 生成新的复数对象 5 + 4 = 9 运算符重载的形式 运算符重载的实质是函数重载 可以重载为普通函数，也可以重载为成员函数 把含运算符的表达式转换成对运算符函数的调用。 把运算符的操作数转换成运算符函数的参数。 运算符被多次重载时，根据实参的类型决定调用哪个运算符函数。 形式如下： 返回值类型 operator 运算符（形 ...

这周的内容主要是介绍了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 ...

这一周开始学习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的习题解析。 选择题选择题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^{ ...

这周的内容主要是再介绍了几个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$的前半部分，按 ...