AI汇总(长期汇总)

主要放一些自己看过的东西的汇总。

CV:

crowd counting:

1. CrowdNet: A Deep Convolutional Network for Dense Crowd Counting[paper]

2. CNN-based Cascaded Multi-task Learning of High-level Prior and Density Estimation for Crowd Counting[paper]

3. Crowd counting via scale-adaptive convolutional neural network[paper]

CrowdSourcing

1. Privacy-Preserving Aggregate Queries for Optimal Location Selection[paper]

2. (自己老师写的….)Efficient secure similarity computation on encrypted trajectory data[paper]

Recommend System

1. 推荐系统原理与实践[book]

2. 推荐系统(Recommender systems an introduction)[book]

3. 我制作的RS ppt[pdf]

4. 我制作的POI RS ppt[pdf]

cold start

本来是应该也有一份ppt的，没做完。

先放几篇看过的：

1. ExcUseMe: Asking Users to Help in Item Cold-start Recommendations[paper]
2. DropoutNet: Addressing Cold Start in Recommender Systems[paper]

nlp

sentiment analysis

1. Thumbs Up or Thumbs Down? Semantic Orientation Applied to Unsupervised Classification of Reviews[paper]

2. Thumbs up? Sentiment Classification using Machine Learning Techniques[paper]

ml

很杂，暂时不放。

CH1 词法”陷阱”

1. 第一个问题就是赋值=不同于==

如果出现e1 = e2这种表达式在循环语句中的条件判断部分时，编译器可能会给出警告。

1

if(x = y) foo();

类似这种的语句可以改成下面这种，更方便理解

1

if((x = y) != 0) foo();

经典语录:

作为程序员不能指望靠编译器来提醒，毕竟警告消息可以被忽略

关于Latex

最近由于需要自己重新制作一份模板，所以随机入门了Latex，摒弃了十分优秀的Markdown，最关键的原因主要有两个:

1. Latex 可以方便的生成目录和页码
2. 论文一般都用Latex排版(当然也有用Word)

由于Markdown确实只能做一些比较随意的东西，而且想做好某些东西确实会很难，不过typora里可以编写一些html代码，确实如果只是在电脑上阅览的话， export成html格式是十分舒服的。

网络流

基本概念

求解可行流: 给定一个网络流图, 初始时每个节点不一定平衡 (每个节点可以有盈余或不足), 每条边的流量可以有上下界, 每条边的当前流量可以不满足上下界约束. 可行流求解中一般没有源和汇的概念, 算法的目的是寻找一个可以使所有节点都能平衡, 所有边都能满足流量约束的方案, 同时可能附加有最小费用的条件 (最小费用可行流).

求解最大流: 给定一个网络流图, 其中有两个特殊的节点称为源和汇. 除源和汇之外, 给定的每个节点一定平衡. 源可以产生无限大的流量, 汇可以吸收无限大的流量. 标准的最大流模型, 初始解一定是可行的 (例如, 所有边流量均为零), 因此边上不能有下界. 算法的目的是寻找一个从源到汇流量最大的方案, 同时不破坏可行约束, 并可能附加有最小费用的条件 (最小费用最大流).

扩展的最大流: 在有上下界或有节点盈余的网络流图中求解最大流. 实际上包括两部分, 先是消除下界, 消除盈余, 可能还需要消除不满足最优条件的流量 (最小费用流), 找到一个可行流, 再进一步得到最大流. 因此这里我们的转化似乎是从最大流转化为可行流再变回最大流, 但其实质是将一个过程 (扩展的最大流) 变为了两个过程 (可行流 + 最大流).

最大流

关于网络流的问题，其重点在于如何建图，而对于算法细节，其实不太重要，一般常用Dinic， 建立分层图来增广，实现起来比较简单，也有isap的，其复杂度上线都是$O(n^2m)$, 不过实际上isap的算法时间非常占优势，不过没有Dinic容易实现。

数论退役帖

基本知识

最大公因数

找寻a,b的最大公因数, 利用辗转相除法：

1
2
3
4

int gcd(int a, int b){
    return b?gcd(b,a%b):a;
}
// 或者直接使用自带函数 __gcd(a, b)

常用定理

1. $ gcd(a^n - 1, a^m - 1) = a^{gcd(n, m)} -1$
2. 扩展 $a>b, gcd(a, b)=1 时 gcd(a^m-b^m, a^n- b^n) = a^{gcd(m, n)} - b^{gcd(m, n)}$
3. $G = gcd(C^1_n, C^2_n, …, C^{n-1}_n)$
   • n为质数时G=n
   • n有多个质因子时，G=1
   • n有一个质因子p，G=p
4. $F_n 为斐波那契额数列， gcd(F_n, F_m) = F_{gcd(n, m)}$
5. 给定两个互素的正整数A,B， 那么他们组合的数C=p*A+q*B>0， C最大为AB-A-B,不能组合的个数为$\frac{(A-1)*(B-1)}{2}$
6. $(n+1) lcm(C_n^0, C_n^1, .., C^n_n) = lcm(1, 2, 3, .. , n+1)$
7. 对于质数p,$(x+y+…+w)^p \%p == (x^p + y^p + … + w^p) % p$

Hash

有时候我们要统计很大的数的个数时，但是这个时候我们又开不下这么大的数组，我们常常可以借助map，或者hash_table之类的工具。

Hash 统计数字个数

有时候map占用的数据也非常大， 我们可以利用链式前向星来代替链表实现一个简易的hash来统计每个数的个数，这个所占用的空间比map要小的多。

绪论

CH1 绪论

最重要的是一些常见的基本术语的掌握：

机器学习本身就是基于数据的，从data set开始到sample space, feature vector, dimensionality这种常见的概念，以及hypothesis(假设)， ground-truth, supervised learning, generalization， version space这种的。

通常面对样本空间，我们会做一个非常强的假设，就是获得的样本都是independent and identically(i.i.d)独立同分布的，这个简写要牢记。

归纳(induction)和演绎(deduction)是科学推理的两大手段，前者从特殊到一般，后者反之。从样本中学习显然是归纳学习。

算法在学习过程中对某种类型假设的偏好，称为”归纳偏好”(inductive bias),可以看作是在假设空间中对假设进行选择的启发式。奥卡姆剃刀(Occam’s razor)是常见的、自然科学中最基本的原则，偏好简单的。

NFL定理(No Free lunch Theorem)证明了无论学习算法多聪明，他们的期望性能是一样的。但NFL有一个重要前提：所有问题出现的机会相同。其寓意是脱离具体问题，空谈算法毫无意义。

NFL Theorem

CH2 模型评估与选择

错误率(error rate)+精度(accuracy)=1。学习器在训练集上得到的是training error / empirical error, 在新样本上得到的误差是generalization error. 前者高而后者高的现象即overfitting，而前者都没学好的即欠拟合。

考虑到样本的iid， 一般要求训练集与测试集互斥。常见的评估法:留出法，交叉验证法，自助法。

留出法(hold-out)将数据集分为互斥的两个集合(2/3~4/5作为训练)，要注意的是划分要注意保持数据分布的一致性，有保留类别比例的分层采样法。一般采用若干次随即划分、重复进行实验评估后取平均值作评估结果。

交叉验证(cross validation)将数据集D分为k个大小相似的互斥子集，每个子集保持数据分布的一致性(分层采样)，每次用k-1个训练，剩下的用来测试，可以进行k次训练，即k-fold cross validation。当k=|D|,则称为留一法(Leave-One-Out,LOO), 此时不受随机样本划分的影响。

自助法(bootstrapping)每次从D中挑选一个样本，重复|D|次，样本在m次不被采到的概率$(1-\frac{1}{|D|})^{|D|}$ 。约有36.8%的样本未被采样到，可以作为测试，这样的测试称为 包外估计(out-of-bag estimate),这对集成学习非常有帮助(能产生多个不同的训练集)。但自助法产生的数据集改变了初始数据的分布，会引入估计偏差。Introduction tp bootstrap书挺长的，这边放一篇短文。

性能度量

错误率与精度是最常用的性能度量。
$$
错误率:E(f; D) = \frac{1}{m}\sum_{i=1}^{m}I(f(x_i)\not=y_i) = 1 - acc(f; D)
\ E(f;D) = \int_{x~D}(f)
$$

K-Means(K-均值) ->聚类

K-Means 是一种使用广泛的聚类的算法，将各种聚类子集内的所有数据样本的均值作为该聚类的代表点。

算法主要思想：通过迭代把数据集划分为不同的类别，使得评价聚类性能的准则函数达到最优，从而使得生成的每个聚类类内紧凑，类间独立。

由于每次都要计算所有的样本与每一个质心之间的距离，在大规模数据集上收敛速度较慢。

算法思想及步骤

1. 设置 k ， 以及k个聚类中心$u_1, u_2, …, u_k$
2. 分组：
   • 将样本分配给距离最近的聚类中心
   • 由这些样本构造不相交(non-overlapping)的聚类
3. 确定中心： 用个聚类的均值向量作为新的聚类中心
4. 重复2，3直至算法收敛即聚类中心达到稳定。

算法要点

1. 选定某种距离作为数据样本间的相似性度量

   k-means聚类算法不适合处理离散型属性，对连续性属性比较适合

   计算样本之间的距离时，根据实际需要选择距离测度作为算法的相似性度量，如欧式距离，曼哈顿距离(各维差的绝对值之和)，马氏距离(两个服从同一分布并且其协方差矩阵为Σ的随机变量之间的差异程度)

2. 选择评价聚类性能的准则函数

   k-means聚类算法使用误差平方和准则函数来评价聚类性能。

   $$cost·Function = \sum_{i=1}^{k}\sum_{x_j \in S_i }(x_j - u_i)^2$$

3. 相似性的计算根据一个簇中对象的平均值(均值向量)来进行