数学基础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.