表格整理

图片主要来源于官方的讲义PDF以及Wikipedia

监督学习

线性回归

将输入数据，如图中的红点，求得一条直线表示数据中的线性关系，并且这条直线在概率期望上达到最佳(后面算法省略这句)。

梯度下降

找函数极值小值点，图中相同颜色线为等高线，越靠近中心高度越低，运用高数的梯度运算和梯度下降能够得到如图中蓝色x标记的逐步逼近的极值点。

Normal Equation

同样是解决线性回归问题，和梯度下降不同的是，运用矩阵运算，直接得到参数的表达式

Logistics 回归

分类算法，对一侧数据0，另一侧数据1的训练数据建立分类器，图中的点是 训练输入，线是得到的logistics函数

高斯切线法

高数知识，二次收敛，加速点的收敛，如图 通过计算切线与坐标轴的交点作为下一次的迭代起始值。

广义线性模型GLM

按照所提出的假设模型，能够直接得到所需要的 拟合函数，可以用来证明上面 的线性回归中最小二乘法是最优，以及Logistics 回归中的函数选取。

softmax 回归

分类到对互斥的k个类别,公式推导采用带入GLM

高斯判别分析GDA

对0分布满足高斯分布，1分布也满足高斯分布的分布进行线性分类。

朴素贝叶斯

整体与特征来判断整体的分类，如垃圾邮件根据出现的词汇进行分类，很暴力直接计算概率

拉普拉斯平滑

解决朴素贝叶斯中可能出现的0除以0的情况，分子+1，分母+可分的种类数k

最优线性分类器

如图能够找到将 数据分开，并且离分割线最近的点的距离值最大的分类器。

拉格朗日对偶、KKT

用于具体解决 最优线性分类器的支撑方法

核函数

将变量非线性变化映射到高维空间，减小计算量，表示量，配合其它算法使用能获得高维空间性质。

支持向量机SVM

将低维不可线性分割的 通过核函数映射到高维度，再在高维中进行最优线性分割

L1 Regularization

在有部分异常点时的分割,通过添加惩罚项解决如下图异常点导致变化过大的问题。

SMO

对于多个参数 每次选一个参数进行取极值点，SMO能在带等式与不等式的约束限定情况下，每次两个参数逐步逼近。

均方误差MSE

能够用于分析 过拟合 还是 欠拟合

错误分析

按步骤替代/隔离分析，逐个增加或逐个减少。按训练误差 方差，实验 误差方差分析。

VC维、hoeffding不定式

用于证明概率下训练集和误差的上下界存在性。

验证方式、模型选择

将部分的训练数据不用于训练而用于检验模型

感知器

感知器：转换后的值小于0输出-1，大于等于0输出

无监督学习

k-means

对无标记的点进行分类(寻找分类的中心)

高斯混合模型GMM

可以看作类似前面的高斯判别模型GDA，但是现在的输入数据是无标记的

EM算法

用于GMM等无标记的混合模型的分离，先假设隐含变量Z以及它的分布Q，和k-means的思想类似，E-step优化Q，M-step优化参数，重复直到收敛 [使用Jensen不等式],分离效果见上图

因子分析

对训练集量少，维数大，分类的类别少的分布进行分类，思想是建立隐含低维度变量z，通过矩阵转化投影到高维，再加上高斯扰动误差

主成分分析PCA

对于高维空间的数据，找到其前k个相互正交的关键维度的向量，可用线性代数奇异值分解SVD进行快速计算。可以用于降维度，作为其它算法的预处理步骤，或找到关系的主要方面。

独立成分分析ICA

对于多维度，相互独立的非高斯分布成分，找到每个成分的轴，并将所有轴转换为正交轴。可用于特征提取，特征分离，如音频分离，计算人脸识别面部特征向量，对脑电波数据分离预处理去除眨眼和心跳信号。

马尔科夫模型

马尔科夫决策过程 MDP

能够学习带有状态，和基于状态动作的一类事情，学出一个策略集，如自动驾驶，需要设置奖励函数，概率函数等参数函数。策略迭代和值迭代

离散化连续状态的MDP

也就是字面意思离散化，在2维下工作一般不错，高维度后无论是维数灾难还是离散化难度，以及模型最终产物都难以普遍满意

MDP中的模型模拟器

用于概率状态未知时，用实验+拟合得到模型，从而代替概率函数的位置

线性二次型调节控制LQR

解决状态依赖于前一个状态前一个动作以及时间的策略选择，在有限时间内用动规(倒着递推)，多次实验线性拟合基于时间的。对于非线性函数仅能取较近的输入值，用近似的切线做近似的线性处理。通过加强奖励函数，初始值(时间T)矩阵，等限定。得出结论，动作与状态的线性相关，且计算过程中可以省去无关迭代

kalman滤波

将观测值转化为概率上的真实值

LQG

LQG=LQR+kalman滤波

微分动规DDP

根据当前决策选定轨迹，做LQR，更新决策，重复。从函数上理解是函数逐步靠近，即使是一个不那么好的模拟器

pegasus策略搜索

处理非线性模型函数的情况。选取随机序列并重复使用于模型训练，在模型选择时选取非线性的模型(如logistics 函数)，用极大似然去找该模型下的最优策略。

课程相关链接

网易Stanford机器学习

官方网站

Github整理

部分课件

练习

笔记和练习

说明

该课程能学到什么？

基于统计模型，概率公式的不同学习方法，不涉及神经网络。

本文档不按照课的分化记录，而按照内容的分化记录。

省去具体实现，毕竟已经有足够的他人整理的资料，以及我也在pad上手写过了，没有这个重复工作的必要了。不过我会尽量把知识点依赖写清，如果心情不错的话，再提供一个相关的优秀的讲解链接。这里还是以框架和思想为主。其中部分公式省略了取值限制，具体原公式请参照讲义

依赖知识

• 高等数学

  • 积分
  • 微分
  • 偏导数，梯度
  • 拉格朗日乘子法、KKT条件(拉格朗日对偶)
  • 牛顿切线

• 线性代数

  • 矩阵 乘法 转置 逆 秩 迹
  • SVD

• 概率统计

  • 贝叶斯
  • 高斯分布 多纬高斯分布
  • 0-1分布 泊松分布 等等常见分布
  • 极大似然估计

• 算法

  • 动态规划

内容

监督学习

• 提供样例(输入，输出(类别))数据进行训练，从而学习出一个分类器/学成一个带有功能的程序。

方法

辅助方法/定义

证明

无监督学习

• 无样例(输入，输出)样本进行学习，直接根据未分类数据的分布特征，对数据进行分类/建立带有功能的程序。

方法

辅助方法/定义

强化学习RL/马尔科夫模型MDP

上面的都是分类模型，强化学习要强行分类也可以说是无监督分类，或者半监督分类。

解释

马尔科夫决策过程 变形/问题

Debug 19

一句话能回答的知识点 TODO

梯度下降和梯度上升有什么区别？3

画三维图形，求它的梯度，从图像上看，梯度是指向上方的。所以梯度下降用减法，实际是逼近极小值，而梯度上升用加法，逼近极大值。

欠拟合与过拟合分别是什么？4

欠拟合：模型复杂度不够 训练数据少，未能真正获取主要内在关系，训练数据和测试数据得分都低。过拟合，模型过于复杂，训练数据方差小得分高，但是测试数据偏差大 方差大

判别学习法 和 生成学习方法 的区别？5

判别学习法直接对P(y|x)进行建模；生成学习方法对P(x|y) 和 p(y)进行建模 然后，y = 贝叶斯公式转换后最大的y 例如 隐马尔可夫模型HMM、朴素贝叶斯模型、高斯混合模型GMM、LDA。

GDA与Logistics模型比较？5

GDA按照概率转化的曲线和sigmoid,很相似。GDA更强的假设，对于正确的训练集，GDA效率更高 更好，但对于不正确的模型，logistic的健壮性robust更好

其它知识点 细节 TODO

LGM

对偶问题

KKT条件

核函数定义 证明 应用 具体核(高斯核)

SVM

EM

EM:Do, C. B., & Batzoglou, S. (2008). What is the expectation maximization algorithm?. Nature biotechnology, 26(8), 897.

其它TODO

添加配图

李航的《统计学习方法》刚翻了个开头，这本书先讲的泛的再具体的顺序不同，不过瞄了目录，似乎有新内容还是换了个名字？不懂2333，目前计划是先不看它，去看CSP，之后再看_(:з」∠)_。

老师建议把 证明过程盖住 自己再证明

2讲矩阵梯度公式

题目

题目大意

输入 k pa pb

最初空字符串，每次增加一个字符 a 或者 b, 当子串ab的个数>=k就停止,求停止时 子串ab的个数的期望。

子串的不需要连续 比如aab 是有两个ab子串

产生a的概率为 pa/(pa+pb), 产生b的概率为 pb/(pa+pb)

期望 计算过程中 不使用小数，而是用 逆模

所有值模1000 000 007

数据范围

1<=pa pb<=1 000 000

1<=k<=1 000

解答

官方题解

意思是用dp[i][j] 表示前缀 中 有i个a ，j个ab子串的子串个数的期望值

用的是从长的推短的 反过来，首先如果 j>=k 那么 dp[i][j] = j

递推表达式 dp[i][j] = (pa * dp[i+1][j] + pb * dp[i][i+j])/(pa+pb)

也就是 根据最后一个字符来进行分化

所以最后的结果就是dp[0][0] = dp[1][0]

其中一些问题

虽然j>=k已经解决了 但是 i还是可以无限大，根据递推表达式 和 级数 的办法 可以求得dp[k][j] here

不用小数用逆模运算 wiki的最后一条

实现

我的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define ten5 100000+10
#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<n;i++)
#define iif(c,t,f) ((c)?(t):(f))
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair

int intcmp(const void *v1,const void *v2){return *(int *)v1-*(int *)v2;}
long long minn(long long v1,long long v2){return v1<v2?v1:v2;}
long long maxx(long long v1,long long v2){return v1>v2?v1:v2;}

//https://zh.wikipedia.org/wiki/%E6%89%A9%E5%B1%95%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95
//https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
// [a p]       1
// [1 0] --->  ret(x1)
// [0 1]       x2
ll mul_inv(ll a,ll b=MOD ){
  ll matrix[3][2]={{a,b},{1,0},{0,1}};
  int itr = 0;
  while(matrix[0][itr^1] != 1){
    ll t = matrix[0][itr]/matrix[0][1^itr] ;
    rep(i,0,3)
      matrix[i][itr] -= t * matrix[i][1^itr];
    itr^=1;
  }
  return (matrix[1][itr^1] % b + b )%b;
}
int k;
// http://codeforces.com/blog/entry/56713
ll dp[1010][1010] = {0};
ll getdp(int i,int j){
  return j >= k? j : dp[i][j];
}
int main(){
  ll a,b;
  cin>>k>>a>>b;
  //http://codeforces.com/blog/entry/56713?#comment-404349
  rep(i,0,k)
    dp[k][i] = (i + k + a * mul_inv(b)) % MOD;
  int i,j;
  for(i=k-1;i>=1;i--)
    for(j=k-1;j>=0;j--){
      dp[i][j] = (a*getdp(i+1,j) + b * getdp(i,i+j))%MOD;
      dp[i][j] = (dp[i][j] * mul_inv(a+b))%MOD;
    }
  cout<<getdp(1,0)<<endl;
  return 0;
}

C大意

给一个有权无向图。进行q次询问，第i次询问ki个边，问所提到的ki个边能否同时出现在图的最小生成树上，返回YES或NO。

数据范围

图的边和点<=500'000

询问数q<=500'000,所有询问的边数的和sum(ki)<=500'000

时间空间(2s/256MB)

题解

不知道如果当时继续想下去，会不会想出解法，当时已经想到 并查集 和 边+未选取的边形成的环，已选取的 不能 大于max(未选取的)。感觉和正解的具体实现还差很远，但基础结论已经有了

标答说成那样，我也是没啥办法，我也想到了，没想到下一步。然后观摩了moejy0viiiiiv大佬的代码。 下面用举例来说明

首先，不要用官方的样例来想，想象图有且只有一个环，环上的边长是1,1,2,2,2

很直接可以知道只要不是选了所有的2，那么 都是可以同时存在于一个MST上的，那么选三个2的情况发生了什么，也就是上面说的选了三个2以后，在这个环上，未选取的最大只是1了。然后换一个角度看，如果我们已经先把图上所有的长度为1的链接好了，那么在新增加2的时候，就不应该形成环。

同样可以想象环上是1,1,2,2,2,3的情况，现在 尝试添加2的时候，就算全添加了，也不会直接形成环，和结论全选了2也能同时存在于一个MST是一样的。

其中要注意的是对于第一种情况，就算 询问中没有1 1，也不能选取 所有的2

因此把上述方法转化为伪代码

1
2
3
4
5
6
7
8

首先读入,所有边和询问，将询问 每个拆分，按长度第一序，询问号第二序 排序

从空开始，分别处理每一个询问中的1，将它们连接(并查集) 检验是否成环，如果成环该询问不可行

将所有的1相连接(并查集)不论在不在查询中，分别处理每一个询问中的2，将它们连接(并查集) 检验是否成环，如果成环该询问不可行
将所有的1 2相连接(并查集)不论在不在查询中，分别处理每一个询问中的3，将它们连接(并查集) 检验是否成环，如果成环该询问不可行
...
将所有的1 2...499'999相连接(并查集)不论在不在查询中，分别处理每一个询问中的500'000，将它们连接(并查集) 检验是否成环，如果成环该询问不可行

整理上面成循环就是

1
2
3
4
5
6
7

i=0
S(i) 表示连接完小于等于i的边的并查集
for(length=1~500'000):
  遍历每一查询
    选中一个包含该length的一个查询Q
    将Q中所有长length的边 和 S(length-1)相连 检查是否成环
  将所有长为length的边连入S(length-1)也就变成了S(length)

上面代码中 一个是既要利用已经连接的小于length的并查集，又要在每次 进行成环检测时 并查集能够复用，具体实现见下面moejy0viiiiiv大佬的代码，他用f来实现 可以逐渐增加利用的并查集，用p和mt来实现可复用 的每次检测。

代码

moejy0viiiiiv 的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
  using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head

const int N=501000;

int n,m,u[N],v[N],w[N],f[N],p[N],mt[N],T,wa[N];
int Q,k,id;
vector<int> eg[N];
vector<PII> qw[N];

int find(int x) {
  if (f[x]!=x) return f[x]=find(f[x]); else return x;
}
int find2(int x) {
  if (mt[x]!=T) mt[x]=T,p[x]=f[x];
  if (p[x]!=x) return p[x]=find2(p[x]); else return x;
}

int main() {
  scanf("%d%d",&n,&m);
  rep(i,0,m) {
    scanf("%d%d%d",u+i,v+i,w+i);
    eg[w[i]].pb(i);
  }
  rep(i,1,n+1) f[i]=i;
  scanf("%d",&Q);
  rep(i,0,Q) {
    scanf("%d",&k);
    rep(j,0,k) {
      scanf("%d",&id);
      --id;
      qw[w[id]].pb(mp(i,id));
    }
  }
  rep(i,1,500001) {
    sort(all(qw[i]));
    rep(j,0,SZ(qw[i])) {
      int x=u[qw[i][j].se],y=v[qw[i][j].se];
      find(x); find(y);
    }
    rep(j,0,SZ(qw[i])) {
      if (j==0||qw[i][j].fi!=qw[i][j-1].fi) T++;
      int x=u[qw[i][j].se],y=v[qw[i][j].se];
      if (find2(x)==find2(y))	wa[qw[i][j].fi]=1;
      p[find2(x)]=find2(y);
    }
    for (auto id:eg[i]) {
      int x=u[id],y=v[id];
      f[find(x)]=find(y);
    }
  }
  rep(i,0,Q) puts(wa[i]?"NO":"YES");
}

参考

题目

官方题解

E

给平面上n个点，在每个点可以，画一条竖直线，画一条横直线，什么都不画，也就是不能画十字

这样n个点一共能画出多少种图形

数据范围

n<=100 000,点的坐标范围-1 000 000 000<=x,y<=1 000 000 000，

时间空间(2s/256MB)

输出答案MOD 1 000 000 007

题解

想了半天还想了递推，但是到横竖交叉我的递推就变得格外的复杂以至不可用。

我已经想到 如果有一群点可以通过横线和竖线连在一起，那么，我们只用考虑画出来的横线竖线的可能性

题解的意思是需要发现两个事实：

0. 如果 这一群点能够成环，那么方案数=2^(横线数+竖线数)

1. 如果 这一群点不能够成环，那么方案数=2^(横线数+竖线数) - 1

过程就是并查集之类的+找环就好了

所以我菜 就菜在 根本没有发现这两个 事实

代码/280ms/14368KB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

typedef long long ll;

#define shi5 100000+10
#define MOD 1000000007

#include <bits/stdc++.h>
using namespace std;
struct poi{
  ll x;
  ll y;
  int color;
};
// int structcmp(const void *v1,const void *v2){return ((mystruct *)v1)->v - ((mystruct *)v2)->v;}
int intcmp(const void *v1,const void *v2){return *(int *)v1-*(int *)v2;}
long long minn(long long v1,long long v2){return v1<v2?v1:v2;}
long long maxx(long long v1,long long v2){return v1>v2?v1:v2;}

poi p[100010]={0};
map<ll,vector<int> > x2index;
map<ll,vector<int> > y2index;

ll twopow(ll val){
  if(val == 1)
    return 2;
  ll ret = twopow(val/2);
  ret *= ret;
  ret %= MOD;
  if(val%2)
    ret *= 2;
  ret %= MOD;
  return ret;
}

ll getnocircle(int v){
  ll ret = twopow(v);
  if(ret == 0)
    return MOD-1;
  else
    return ret-1;
}

ll getcircle(int v){
  return twopow(v);
}

ll dolink(int index,int c){
  map<ll,ll> xlstartindex;
  map<ll,ll> ylstartindex;

  vector<ll> xlist;
  vector<ll> ylist;
  int xitr=0,yitr=0;
  bool iscircle=false;

  p[index].color=c;
  xlist.push_back(p[index].x);
  ylist.push_back(p[index].y);
  xlstartindex[p[index].x] = index;
  ylstartindex[p[index].y] = index;

  while(xitr != xlist.size() or yitr != ylist.size()){
    if(xitr != xlist.size()){
      for(auto indexeach:x2index[xlist[xitr]]){
        if(indexeach == xlstartindex[xlist[xitr]])
          continue;
        if(p[indexeach].color != 0)
          iscircle = true;
        else if(ylstartindex.count(p[indexeach].y)){
          p[indexeach].color = c;
          iscircle = true;
        }else{
          p[indexeach].color = c;
          ylist.push_back(p[indexeach].y);
          ylstartindex[p[indexeach].y] = indexeach;
        }
      }
      xitr++;
    }
    if(yitr != ylist.size()){
      for(auto indexeach:y2index[ylist[yitr]]){
        if(indexeach == ylstartindex[ylist[yitr]])
          continue;
        if(p[indexeach].color != 0)
          iscircle = true;
        else if(xlstartindex.count(p[indexeach].x)){
          p[indexeach].color = c;
          iscircle = true;
        }else{
          p[indexeach].color = c;
          xlist.push_back(p[indexeach].x);
          xlstartindex[p[indexeach].x] = indexeach;
        }
      }
      yitr++;
    }
  }
  if(iscircle)
    return getcircle(xlist.size()+ylist.size());
  else
    return getnocircle(xlist.size()+ylist.size());
}


int main(){
  int n;
  cin>>n;
  int i;
  for(i=0;i<n;i++){
    scanf("%lld %lld",&p[i].x,&p[i].y);
    x2index[p[i].x].push_back(i);
    y2index[p[i].y].push_back(i);
  }

  int nowcolor=1;
  ll ans = 1;
  for(i=0;i<n;i++){
    if(p[i].color == 0){
      ans *= dolink(i,nowcolor);
      ans %= MOD;
    }
    nowcolor++;
  }
  cout<<ans<<endl;

  return 0;
}

依旧代码丑陋126行

大佬们都写得十分精简 低头

oscillation

wdmmsyf

参考

题目

官方题解