数学基础W13:概率基础

2020-06-04

概率基础

用概率来描述数据的不确定性

概率论课上都学过Orz

贝叶斯的先验和后验概率。

展开全文 >>

让hexo 博客显示markdown渲染

2020-06-04

markdown渲染

哈哈哈哈哈看到以前说要好好配置博客，结果从2月11日第一次捣鼓了别人5分钟就配置好的hexo 博客，经历了一系列的拼凑，终于也算建成了。

原来学期开始前，想在b站上宣传博客，可是！即没有渲染，也长得这么丑，笔记的质量也参差不齐！

我才不会说，很多记录到一半的笔记，就是因为我上课听不下去了，然后笔记就夭折了。

现在来搞一波markdown渲染~

其实就是在yilia主题配置的_config.yml文件中将MathJax渲染更新为true.

但是有时候会崩掉，就哭辣。

more >>

展开全文 >>

数学基础W13:向量值函数和矩阵值函数的梯度

2020-06-04

前面的回顾

运算法则
向量函数和矩阵函数的微分
迹微分的性质。

向量值函数和矩阵值函数的梯度 $R^n->R^m/R^{m\times n}->R^{n\times n}$

可以用这些微分来解决什么？

链式法则：复合函数的梯度和导数。

定义5

Output是一个向量。

Jacobian矩阵

梯度在向量与向量之间的变化关系上的推广。

将矩阵向量化：

向量函数微分

$df=\frac{\part f^T}{\part x}^T dx$

从分量的角度去考虑。

多远正态分布的推广

定理8

当f和x是相同大小:

$\frac{\part f^T}{\part x}^{-1}=\frac{\part x^T}{\part f}$

这个结论很适用于变量替换。

Hessian矩阵

当一阶导数求完后， $\frac{\part f}{\part x_1}$

其还要关于 $x^T$ 进行求。(行向量？)

Hessian 矩阵在机器学习优雅上有很多应用，

Hessian是对称矩阵，二阶优化算法：牛顿法。

18.4链式法则与一些有用的梯度公式

定理9

假设我们有n个列向量。

定理10

例16

例17

$(x-\mu)^T\Sigma^{-1}(x-\mu)$ 关于 $\mu$ 求导。

一些常用的梯度计算公式

18.3/18.4有符号的错误

18.5 反向传播与自动微分

神经网络中的梯度与链式法则。

例18

考虑 $f(x)=\sqrt{x^2+exp(x^2)}+cos(x^2+exp(x^2))$

这样的微分的计算会很冗余

正向传播过程中，我们需要每层的偏导数。

每层的偏导数计算兜涉及到链式法则。

此部分笔记，在专业英语反向传播的那篇博客中也有涉及。

$e=(a+b)(b+1)$

求a=2,b=1时的e 的梯度：

$\part e/\part a=b+1$

$\part e/\part b=(b+1)+(b+a)$

引入中间变量c/d

c=b+1

d=b+a

展开全文 >>

ML3.5 Optimization for DL

2020-06-03

前注：

本讲的内容按照学习路线上Gradient Descent的补充知识

New Optimization

New Optimizers for Deep Learning

What you have known before?

常见Optimization的方法

SGD(随机梯度下降)
SGD with momentum
Adagrad
RMSProp
Adam

一些Notation

Momentum：History

送进一个 $x_t$ ，送入 $\theta_t$ 得到， $y_t$ ，会与送入的label比较a.k.a $\hat{y_t}$

Why Optimization

使损失函数最小(优化问题)

如何sumover所有的dataset？

On-line v.s. Off-line

Off-line : pour all into model at every time step.

On-line: one pair of $(x_t,\hat{y_t})$ at a time step.

SGD

SGDM

把momentum累计

时间上的weighted Sum。

考虑到过去的momentum的影响。

为啥要SGDM呢？

当某一个gradientj接近0的时候，或local minimum的时候，有可能有卡住不动的情况出现。

以为我们前面的移动(左1梯度大)会我们累加过来使我们继续移动，虽然这一点(左2)的gradient很小，

Adagrad

实时调整learning rate。

RMSProp

与adgrad唯一的差别在于分母的算法。

确保 $v_t$ 不会永无止境的变大，而是在时间上有weighted sum，不会因为前几步的步伐太大而停下来。给之前的vt乘上一个系数 $\alpha$ 就不会出现前几步grad太大，造成的分母太大，更新为0。

因为Adagrad是前面所有的求和，所以 $v_t$ 会永无止境的变大，使步伐越来越小。

Adam

上两个也很难解决local mimum的问题

Adam=SGDM+RMSProp的优势结合。

[参考资料](SGD，SGDM，Adagrad，RMSProp，Adam，AdamW复习笔记 - 木吉子的文章 - 知乎 https://zhuanlan.zhihu.com/p/129702058)

还有没有别的Optimizer？

事实上，是很少再有了。

Optimizer的Real Application

2014年以后，很少有可以超越SGDM/Adam的算法。

视频没有看完，但现阶段对Adam和SGDM的优化暂且与我无瓜。

展开全文 >>

ML04 Classification

2020-06-03

Classification

基本模型：

Input:x

Output:Class n

Application

Credit Scoring
Medical Diagnosis
Handwritten character recognition

如何将我要分类的东西数值化？

Example Application

还是以宝可梦为例：

Total: how strong 整体程度

Attack

Defense

SP Atk

SP Def

Speed

即一只宝可梦，是7个数字组成的vector.

每个宝可梦都是用feature来描述。

How to do Classification？

收集数据 Training data for Classification.

（皮卡丘，type雷)/（杰尼龟，type水）/妙蛙种子，type木）

Classification v.s. Regression

机器学习定理：没有免费的午餐定理。

Regression: Output :realnumber

Classification:Output:Discrete(Some class)

回归方法：对数值型连续随机变量进行预测和建模。

房价预测、股票预测、成绩预测

1.1 线性回归：

拟合，wx+b,值是连续值。

$b+\sum_iw_ix_i$

1.2 回归树

1.3 深度学习

1.4 最近邻算法
分类方法：

邮件过滤，金融欺诈，预测雇员异动

2.1 逻辑回归

将线性回归的wx+b通过sigmoid函数映射到(0,1)，并利用threshold进行划分。

N分类问题：先得到N组w值不同的wx+b,归一化，最后变成N个类上的概率问题。

2.2 分类树（集成方法)CART算法

2.3 深度学习

2.4 支持向量机SVM

2.5 朴素贝叶斯
聚类：

3.1 k-means

3.2 Affinity Propagation

3.3 层次聚类

3.4 DBSCAN

Ideal Alternatives

这里的Loss function是无法用Gradient Descent。

Perceptron/SVM

给一个宝可梦x，统计从哪一个class中来的几率最大。

但是还有一个问题：

如何estimating the probabilities from training data.

Generative model

计算x出现的几率，得知x的distribution，然后利用distribution来generate一个x。

$P(x)=P(X|C_1)P(C_1)+P(X|C_2)P(C_2)$

Modelling Process using Genreative model

Gaussian Distribution

正态分布的由mean和variance来决定。

如何从sample来推断其背后的分布？

找 $\mu$ 和 $\sigma$

如何找 $\mu$ 和 $\sigma$ ?极大似然估计Maximum likelihood

其实这堆sample可以是任何一个正态分布都有可能sample出来的。

但是，每一个高斯分布能sample出这79个点的概率是(likelihood)不一样的。

即

Likelihood of a Gaussian with mean $\mu$ ,和协方差矩阵 $\Sigma$

=

the probability of the Gaussian samples $x^1,x^2,….,x^{79}$ ;

$Likelihood(\mu,\Sigma)=\Pi_i f_{\mu,\Sigma}(x_i)$

即likelihood of distribution是独立sample出这79个点的乘积。

接下来，要找 $Maximum \ likelihood$ 的那个Guassian

$\mu^,\Sigma^=arg \space max \space Likelihood(\mu,\Sigma) $

什么能让它最大呢？

平均值能让它最大：

$\mu^*=\frac{1}{n}\sum_ix^i$ ;

$\Sigma^=\frac{1}{n}\sum(x^i-\mu^)(x^i-\mu^*)^T$;

Now we can do classification

How’s the results?

把分类放到更到的维度上去。

但是放到了更高的维度上，好像也只有54%de accuracy。

那怎么提高accuracy呢？–Modifying Model

修改coveriance matrix：

即修改两个class分布的Gaussian，强迫其共用Convariance Matrix。

如此，如何计算likelihood呢？

这样就有140个sample point了，即变成了140个的乘积。

$\mu_1,\mu_2$ 的计算方式仍不变。

如何选择概率几率模型呢？

You can always use the distribution you like
这里 $p(x|C_1)$ 的x可以是一个vector,所以 $p(x|C_1)=p(x_1|C_1)p(x_2|C_2)…p(x_k|C_1)$

拆解了以后，就变成了一维度的Gaussian了，此时可以更好的减少次数，但模型的正确率。即需要model 不同feature之间的covariance.
对于binary feature:是或不是，可以是Bernoulli distributions.

当你把这些维度拆开的时候，你就在假设各个维度之间没有相关性了。

当independent的时候，是Naive Bayes Classifier.

这也解释了为啥两个 $\Sigma$ 相等的时候是linear的boundary

如何理解先验概率和后验概率

设玩lol的是60%,不玩的是40%.

P(X=1)=0.6;P(X=0)=0.4;

玩lol中，0.8男性，0.2女性。

则不玩lol中，0.2男性，0.8女性。

P(Y=1|X=1)=0.8;

P(Y=0|X=1)=0.2;

P(Y=1|X=0)=0.2;

P(Y=0|X=0)=0.8;

P(X=1)=0.6;P(X=0)=0.4;这个概率是统计得到的，所以X的概率分布是已知的。

现在又来了一个样本，x,在他是男性的情况下，这里x取1的概率是多少：

P(x=1|Y=1)= $\frac{P(x=1\cap Y=1)}{P(Y=1)}$

$P(x=1\cap Y=1)/P(x=1)=P(Y=1|x=1)$

P(x=1|Y=1)= $\frac{P(Y=1| x=1)P(x=1)}{P(Y=1)}$

$P(Y=1)=P（Y=1|X=0)P(X=0)+P(Y=1|X=1)P(X=1)$

=0.2 $\times$ 0.4+0.8 $\times$ 0.6

P(x=1|Y=1)= $\frac{0.8*0.6}{0.56}$

最后算出的P(X=玩lol|Y=男性)称之为X的后验概率，即它获得是在观察到事件Y发生后得到的

展开全文 >>

DATA MINING03

2020-06-03

Data Mining process

什么是决策树？

结构树：数据模型；
通常的决策树以二叉树为主。
每个内部/叶子节点都会带一个label，作为数据如何划分的依据。

模型与结构

如何使用我的模型？Inference：将模型在树上过一遍

决策树的推断

所到数据的标签位置，从根节点往下走，走到叶子结点，拿叶子上的label，作为record上的标签。
如何学习？训练得到模型？
自定向下/自定向上

构造完成后的剪纸修正。

C4.5算法以及CART算法

通常使用决策树，使用贪心算法。

寻找最易将label划分开的属性
决策树用crossvalidation和loss进行评价。

APRORI

在不同的属性上数数。
关联规则挖掘

关联规则

打分规则

多维场景下的维度灾难？

维度高/稀疏/模型不可靠。

EM搜索方法

E-step
M-step

展开全文 >>

操作系统Project3:IOPS

2020-06-02

P3:I/O subsystem

目标

在MINIX3中安装一块X MB大小的RAM盘，可以挂载并且存取文件操作。

测试RAM和DISK盘的文件读写速度

分析读写速度有差异的原因。

安装盘–增加RAM盘

/*todo */

修改/usr/src/minix/drivers/storage/memory/memory.c

增加RAM盘数
1
#define RAMDISK 7
重新编译内核make build MKUPDATE=yes;重启reboot选择latest kernel
创建设备 mknod /dev/myram b 1 13;
1
2
/*mknod的使用方式*/
mknod DEVNAME{b|c} MAJOR MINOR
DEVNAME创建的设备文件名，这里为/dev/myram

b:块设备：系统从设备中读取数据的时候，直接从内存的buffer中读取数据，而不经过磁盘。

这里，我们的RAM盘，就是用内存来虚拟一个硬盘，所以这里选项应该是b。

MAJOR和MINOR表示主设备号和次设备号。
检测设备是否创建成功：ls /dev/ | grep ram

实现buildmyram初始化工具：

a. 在/usr/src/minix/commands/目录下新建buildmyram文件夹，参照/usr/src/minix/commands/ramdisk文件增加buildmyram也作为minix的内置命令。

b.编写buildmyram.c文件

类比ramdisk.c，但要注意但没和修改PATH变量。

#include <minix/paths.h>

#include <sys/ioc_memory.h>
#include <stdio.h>
#include <fcntl.h>
#include <stdlib.h>
#define _PATH_MYRAMDISK "/dev/myram"//注意这里修改了路径

main(int argc, char *argv[])
{
	int fd;
	signed long size;
	char *d;

	if(argc < 2 || argc > 3) {
		fprintf(stderr, "usage: %s <size in MB> [device]\n",
			argv[0]);
		return 1;
	}

	d = argc == 2 ? _PATH_MYRAMDISK : argv[2];
	if((fd=open(d, O_RDONLY)) < 0) {
		perror(d);
		return 1;
	}
	long int MFACTOR=1024*1024;//注意这里的MFACTOR

	size = atol(argv[1])*MFACTOR;//size是我输入的参数成kb,mb 就再乘1024嘛

	if(size < 0) {
		fprintf(stderr, "size should be non-negative.\n");
		return 1;
	}

	if(ioctl(fd, MIOCRAMSIZE, &size) < 0) {
		perror("MIOCRAMSIZE");
		return 1;
	}

	fprintf(stderr, "size on %s set to %ldMB\n", d, size/MFACTOR);

	return 0;
}

c. 将buildmyram.c修改完毕以后，新建buildmyram文件下的Makefile文件（此新建也同样类比于ramdisk），同时修改commands目录下的Makefile文件（此修改类比于Project2）

在ram盘上创建内存文件系统：

mkfs.mfs /dev/myram
将ram盘挂载到用户目录下：

mount /dev/myram /root/myram
检验挂载是否成功，输入命令df进行检测：

可以看出，有了dev/myram即我们挂载成功。

重启后用户自定义的ram盘内容会丢失，需要重新设置大小，创建文件系统，并挂载。

性能测试

采用多进程并发的同步读写。
concurrency的数目要增加到设备接近“饱和”状态。
总吞吐量：fileSize(总文件大小)/执行时间(spend time)
饱和：吞吐量难以继续提升，同时I/O延时恶化。

性能测试的变量：“block size“和块扫描方式。

P3-test的编写

P3-test的框架结构：

void write_file(int blocksize,int isrand,char *filename,int fs){
  //todo
}
void write_file(int blocksize,int isrand,char *filename,int fs){
  //todo
}
long get_time_left(long starttime,long endtime){
  //todo
}
int main(){
  
  time_t starttime=time(NULL);//开始时间。
  for(int i=0;i<concurrency;i++){
    while(iter<10000){
      write_file();
      read_file();
    }//将读/写延续一定的时间。
    
  }
  wait();
  time_t endtime=time(NULL);
  printf("throughput:",throughput);
  return 0;
}

还有什么更好的测试方式嘛….

展开全文 >>

ML03 Gradient Descent(1)

2020-06-01

Gradient Descent

找一个最好的function，需要解决一个Optimization Problem.

随机地选取一个起始点
如何update参数呢？

$\theta_1=\theta_0-learningRate\nabla\theta_0$ ;

此时我们获得了 $\theta_1$ 的位置，这是一个新的位置，此时,我们再获取 $\nabla\theta_1$ ，即获取了我们要走的方向，继续走下去。
即梯度是我们要走的方向，走下去。

more >>

展开全文 >>

ML01-Regression-2

2020-06-01

Basic concept

Error从何而来？

来自于 bias and variance of estimator.

如何估算？

估算随机变量X的平均值：
- 假设x的均值是 $\mu$
- 假设x的方差是 $\sigma^2$
Estimator of mean $\mu$
- Sample N points : { $x^1,x^2,…,x^N$ }
  
  用抽样的平均去估计/逼近真实的平均值：
  
  $m=\frac{1}{N}\sum_nx^n\neq\mu$
  
  $E[m]=\frac{1}{N}\sum_nE[x^n]=\mu$
- 可以类比打靶,靶心是真实值。
- Var[m]= $\frac{\sigma^2}{N}$ ，
- $s^2=\frac{1}{N}=\sum_n(x^n-m)^2$ ,用 $s^2$ 来估计。
- $E[s^2]=\frac{N-1}{N}\sigma^2\neq\sigma^2$ ;

不考虑方差：瞄的时候就没有瞄准/即使我瞄准了但仍是有偏离了。

综上：错误来自bias有多大(你瞄准的位置)，variance有多大(你的水平有多稳定)

简单的model受data影响会变小。

Consider the extreme case f(x)=c

Bias

bias= $E[f^*]=\overline{y}$

靶心: $\hat{f}$ ；

根据测试，可以intuitively地直观感觉到，模型越复杂，bias越小，模型越简单，bias越大？

那如何直观的理解这一现象呢？

可以很直观的从图中看到，当模型简单的时候，即我打飞镖时点落的范围，因为它简单，所以他的表示的范围有限，范围集中在那个蓝框框里，所以有可能 它甚至自己本身就不包含那个target( $\hat{f}$ )，而当我的模型复杂的时候，我复杂，可表示的范围就变大了，bias就可能包含我的 $\hat{f}$ 了。

Bias与variance

当然，简单模型，方差小，bias大，可表示的涵盖的范围小。

当然，复杂模型，方差大，bias小，可表示的涵盖的范围大。

这些都可以intuitively的去理解。

Overfitting 与 underfitting

那过拟合和欠拟合都来自于什么情况呢？

如果你的误差来自于bias，那就可能是欠拟合，类比于直线本身涵盖不到target靶心，甚至无法拟合完整的一个模型。

如果你的误差来自于variance，那就可能是过拟合，因为复杂模型离靶心bia很少，那就肯定拟合了，但复杂的方差大，可能拟合的太好了，那就是过拟合了。

Bias 大

redesign your model

Variance大

More data

Very effective, but not always practical.

Regularization

Model Selection

There is usually a trade-off between bias and variance
Select a model that balances two kinds of error to minimize the total error
What you should Not do:

不要认为，自己手上的testing set就一定是最好，即你本身挑model的时候就考虑了自己手上的testing set，此时，在真正的testing set上不一定是最好的error.

但如何避免在testing set 上也以某种意义过拟合呢？

Cross validation

$Traing Set = \begin{cases}Training Set\ValidationSet\end{cases}$

$Testing Set=\begin{cases}Testing SetPublic\TestingSetPrivate\end{cases}$

就不要用在public testing set 作为选择模型的标准。

N-fold CrossValidation

即，当你不相信一次分割做validation的结果的时候时候，可以分很多次。

展开全文 >>

专业英语W12反向传播算法可以解决什么问题

2020-05-31

专业英语W12:反向传播算法可以解决什么问题

What problem does backpropagation solve? Explain it in your own words.

more >>

展开全文 >>

概率基础

markdown渲染

前面的回顾

向量值函数和矩阵值函数的梯度Rn−>Rm/Rm×n−>Rn×nR^n->R^m/R^{m\times n}->R^{n\times n}

定义5

Jacobian矩阵

向量函数微分

定理8

Hessian矩阵

18.4链式法则与一些有用的梯度公式

定理9

定理10

例16

例17

一些常用的梯度计算公式

18.5 反向传播与自动微分

例18

New Optimizers for Deep Learning

What you have known before?

一些Notation

Why Optimization

SGD

SGDM

为啥要SGDM呢？

Adagrad

RMSProp

Adam

还有没有别的Optimizer？

Optimizer的Real Application

Classification

如何将我要分类的东西数值化？

Example Application

How to do Classification？

Classification v.s. Regression

Ideal Alternatives

Generative model

Modelling Process using Genreative model

Gaussian Distribution

如何从sample来推断其背后的分布？

如何找μ\mu和σ\sigma?极大似然估计Maximum likelihood

Now we can do classification

How’s the results?

那怎么提高accuracy呢？–Modifying Model

如何选择概率几率模型呢？

如何理解先验概率和后验概率

Data Mining process

什么是决策树？

模型与结构

决策树的推断

APRORI

打分规则

EM搜索方法

P3:I/O subsystem

目标

安装盘–增加RAM盘

性能测试

Gradient Descent

Basic concept

Error从何而来？

如何估算？

Bias

Bias与variance

Overfitting 与 underfitting

Bias 大

Variance大

Model Selection

Cross validation

N-fold CrossValidation

专业英语W12:反向传播算法可以解决什么问题

向量值函数和矩阵值函数的梯度 $R^n->R^m/R^{m\times n}->R^{n\times n}$

如何找 $\mu$ 和 $\sigma$ ?极大似然估计Maximum likelihood