台大实分析单元 13 外测度 4
这一部分介绍了正则外测度的概念。
回顾之前的记号表示:
\Omega:全集\\
g:包含\varnothing的\Omega的子集类 \\
\tau:g上的准测度\\
\tau^*:利用\text{method 1}从准测度\tau构建的外测度接下来介绍正则(外)测度
正则(外)测度
假设\mu是\Omega上(外)测度,\mu被称为\Omega上正则(外)测度,\\
如果对于任意B\subset \Omega,存在A \in {\sum}^{\mu}(\mu可测集),使得\\
B\subset A,并且\mu(A) = \mu(B)例 1$\lambda$是$\mathbb R$上正则外测度,$\lambda$是上一讲介绍的$\mathbb R$上勒贝格外测度,因为根据定义,存在开集序列$\{A_n\}$(由下确界的定义),使得$B\subset \bigcap A_n$,且$\mu(B) = \mu(\bigcap A_n)$
Theorem 3
如果A_1 \subset A_2 \subset ...\subset A_n \subset A_{n+1} \subset ...
斯坦福算法专项课程Course3 week1内容回顾
这一周的内容主要介绍了贪心算法
Course 3 Week 1贪心算法的思路是总是选择“最优”的选择,“最优”可以人为定义,来看两个例子。
A Scheduling Application问题的背景是我们有一些共享的资源(例如处理器)以及很多工作去做,每个工作有权重$w_j$以及长度$l_j$,定义任务$j$的完成时间$C_j = \sum_{i\le j} l_i$,我们的目标是最小化$\sum_{j=1}^n w_j C_j$
关于$C_j$来看一个Quiz
Quiz 1$3$个工作,$l_1=1,l_2 =2 ,l_3=3$,按如下方式安排
$C_1, C_2,C_3$分别为多少?
利用定义即可,$C_1= 1,C_2= 3, C_3=6$
继续回到问题本身,考虑特殊情形:如果两个工作长度一样,那么权重大的显然要优先安排;如果两个工作权重一样,那么长度小的要优先安排。现在的问题是如果长度权重都不一样则如何处理,我们有如下贪心算法:
按照\frac {w_j}{l_j}从大到小排序,使得\\
\frac {w_1}{l_1} > \frac {w_2}{l_2}...>\fr ...
Unit 8 Linear Optimization And Unit 9 Integer Optimization
这两周主要介绍了线性规划以及整数规划。
课程地址:
https://www.edx.org/course/the-analytics-edge
这两周的内容主要在Excel中操作,以后可能用的比较少,这里略过。
最后对整个课程进行总结,这门课程算是edx上的明星课程,确实也讲的通俗易懂,主要介绍了以R为主的工具来解决预测分类等问题,学习完后,可以运用R中的包解决基本的问题。当初想学这门课一是看介绍中有一个期中比赛,想通过这个比赛来熟悉R,有空的话也用Python完成这个比赛,比较可惜的是这次开课并没有比赛;第二个原因就是因为这个MIT以及edx上评价颇高的课程,想领略一番。
Unit 7 Visualization
这一周主要介绍数据可视化。
课程地址:
[https://www.edx.org/course/the-analytics-edge]
setwd("E:\\The Analytics Edge\\Unit 7 Visualization")
读取数据
WHO = read.csv("WHO.csv")
str(WHO)
'data.frame': 194 obs. of 13 variables:
$ Country : Factor w/ 194 levels "Afghanistan",..: 1 2 3 4 5 6 7 8 9 10 ...
$ Region : Factor w/ 6 levels "Africa","Americas",..: 3 4 1 4 1 2 2 4 6 4 ...
$ Population ...
台大实分析单元 12 外测度 3
这一部分继续介绍外测度。
回顾上次内容:
Theorem 2
令\mu是全集\Omega上的测度(外测度),那么\Omega上全体\mu可测的子集构成的子集族{\Sigma}^{\mu}为\sigma代数,
\mu在{\Sigma}^{\mu}上\sigma可加\\
i.e. \mu是{\Sigma}^{\mu}上的测度Remark因为每个零集都可测,所以
(\Omega,{\Sigma}^{\mu},\mu)是完备的测度空间继续回顾上次结论
记\lambda为\mathbb R上勒贝格(外)测度,那么每个有限开区间是\lambda可测的定理2可以推出,$\mathbb R$上开集可测(因为开集为开区间的可列并),这也可以推出闭集可测,从而所有的Borel集合可测。
接下来介绍如何从准测度构造(外)测度
Constructing a measure from a premeasure
令\Omega为全集,g为包含\varnothing的\Omega的子集类,\\
\tau:g\to [0,\infty],并且\tau(\varnothing) =0注意$\tau$为之前定义的准 ...
台大实分析单元 11 外测度 2
这一部分继续介绍外测度。
回顾外测度的定义:
映射$\mu:2^{\Omega} \to [0,\infty]$被称为外测度如果满足如下三个条件:
\begin{aligned}
(i)&\mu(\varnothing) = 0 \\
(ii)&\mu(A) \le \mu(B),如果A\subset B \subset \Omega \\
(iii)&\mu(\bigcup_{n=1}^{\infty} A_n) \le \sum_{n=1}^{\infty} \mu(A_n)
对于\{A_n\} \subset 2^\Omega
\end{aligned}回顾$\mu$可测的概念:
给定\Omega上外测度\mu,定义\Omega的子集A为\mu可测,如果 \\
\mu(B) = \mu(B\bigcap A) +\mu(B\bigcap A^C),对于任意B\subset \Omega \\
或者\mu(C\bigcup D) = \mu(C) + \mu(D)对于任意C\subset A以及D\subset A^C注意到由外测度的定义可得:
\mu(B) = \m ...
台大实分析单元 10 外测度 1
这一部分介绍了外测度的基本概念。
Unit 4 Outer measure考虑全集$\Omega$,定义在$\Omega$的全体子集上的非负集合函数$\mu$被称为外测度,如果满足如下三个条件:
\begin{aligned}
(i)&\mu(\varnothing) = 0 \\
(ii)&\mu(A) \le \mu(B),如果A\subset B \subset \Omega \\
(iii)&\mu \left(\bigcup_{n=1}^{\infty} A_n \right) \le \sum_{n=1}^{\infty} \mu(A_n)
对于\{A_n\} \subset 2^\Omega
\end{aligned}$\Omega$上外测度常常被被简称为测度(注意之前的测度是定义在$\sigma$代数上的,所以这样称呼不会引起歧义)
给定$\Omega$上外测度$\mu$,定义$\Omega$的子集$A$为$\mu$可测,如果
\mu(B) = \mu(A\bigcap B) +\mu(B\bigcap A^C),对于任意B\subset \Omega \\ ...
台大实分析单元 9 度量空间 2
这一部分介绍了巴拿赫空间的概念。
给定一个度量$(M,\rho)$,按如下方式定义序列:
M中一个序列是从\mathbb N到M的映射,通常用\{x_n\}_{n\in \mathbb N}表示,简写为\{x_n\},
其中x_n是自然数n\in \mathbb N的象接着给出极限的定义:
令\{x_n\}是M中序列,那么\lim_{n\to \infty} x_n = x \Leftrightarrow
\lim_{n\to \infty} \rho(x_n, x) =0\\
其中x被称为\{x_n\}的极限仿照数学分析中定义柯西序列:
一个序列\{x_n\}被称为柯西序列,如果对于任意的\epsilon >0,存在N\in \mathbb N,\\
使得对于任意的n,m\ge N, \rho(x_n,x_m)
斯坦福算法专项课程Course2 week4习题解析
这一部分将带来Course2 week4的习题解析。
选择题选择题 1以下哪一项不是您期望精心设计的hash函数具有的属性?
hash函数应该“展开”大多数(即“非病理”)数据集(跨散列表的桶/槽)
hash函数应该易于计算(恒定时间或接近它)
hash函数应该易于存储(恒定空间或接近它)
hash函数应该“展开”每个数据集(跨散列表的桶/槽)
第四个选项的意思是希望hash函数将元素映射到每个bucket中,错误。
选择题 2假设我们使用哈希函数$H$将$n$个不同的键映射到长度为$m$的数组$T$中。假设简单的uniform hashing——也就是说,每个键独立且均匀地映射到随机桶中,那么映射到第一个桶的预期键数是多少?更准确地说,该集合元素数量$\{k:h(k)=1\}$
$m/(2n)$
$1/n$
$n/m$
$1/m$
$n/(2m)$
$m/n$
每个元素映射到第一个桶的概率为$\frac 1 m$,因为有$n$个元素,所以答案为$n/m$,第三项正确
选择题 3假设我们使用哈希函数$H$将$n$个不同的键映射到长度为$m$的数组$T$中。如果$h(x ...
台大实分析Unit 2习题解析
这一部分是第二单元的作业详解,作业可以在下面的网站下载。
http://ocw.aca.ntu.edu.tw/ntu-ocw/ocw/cou/105S109/9
Problem 1(a)分别验证3个性质即可
(i)
因为f(\Omega) = \overline {\mathbb R},所以
f^{-1}(\overline {\mathbb R}) = \Omega,从而\overline {\mathbb R} \in f_{\sharp} \sum(ii)
如果A \in f_{\sharp} \sum,那么 f^{-1} (A)\in \sum,即存在B\in \sum ,使得f^{-1} (A) = B\\
因此 f^{-1} (A^C) = (f^{-1} (A) )^C= B^C \in \sum,从而A^C\in f_{\sharp} \sum(iii)
任取 f_{\sharp} \sum中序列\{A_n\}_{n=1}^{\infty},所以存在\sum中序列\{B_n\}_{n=1}^{\infty},使得f^{-1} (A_n) = B_n\\
...
台大实分析Unit 1习题解析
这一部分是第一单元的作业详解,作业可以在下面的网站下载。
http://ocw.aca.ntu.edu.tw/ntu-ocw/ocw/cou/105S109/9
Problem 1先证明一个引理:
引理 1
A为不可数集,C_\alpha >0 (\alpha \in A) \\
那么\sum_{\alpha \in A} C_\alpha = \infty证明:
利用反证法,假设$\sum_{\alpha \in A} C_\alpha <\infty$,令
E_n =\{x|x>\frac 1 n, x\in A\}如果$\sum_{\alpha \in A} C_\alpha = \infty$,那么由调和级数的性质可知
对于任意n>0, A\bigcap E_n的元素个数最多有有限个这是因为,如果存在$n_0$使得$A\bigcap E_{n_0}$的元素个数有无限个,则$A\bigcap E_{n},n\ge n_0$的元素个数都有无限个,从而
C_\alpha >\sum_{n=n_0}^{\infty}\frac{1}{n} =\infty这与我们的假设矛盾 ...
斯坦福算法专项课程Course2 week4内容回顾
这一周的内容主要介绍了Hash表以及bloom-filters。
Course 2 Week 4Hash TableHash表是一种存放键值对的数据结构,时间复杂度几乎为$O(1)$,支持的操作如下:
High-Level IdeaHash表的原理是构造一个映射$h$,将元素映射到$h(x) \in \{0,1,2,…,n-1\}$,然后访问$A[h(x)]$,其中$A$是一个数组,$A$中每个元素可以是链表或者元素本身,这两者的区别如下:
如果$A$中每个元素是链表,那么一个格子中可以装很多元素。
hash表的运行时间为:
Resolving Collisions如果存在$x,y$使得$h(x)=h(y)$,那么称其为冲突,这是我们不想看到的,解决方法如下:
如果$A$中元素是链表,那么可以在$A[h(x)]$尾部直接添加元素(这种方法称为Chaining);否则可以根据某个规则让$x$找到下一个空位置,例如linear probing (这种方法称为Open addressing)
The Load of a Hash Table为了后续讨论,这里定义一个变量:
\a ...