Monthly Archives: October 2008

机器学习推荐论文和书籍(转载)

发信人: zibuyu (得之我幸), 信区: NLP
标  题: 机器学习推荐论文和书籍
发信站: 水木社区 (Thu Oct 30 21:00:39 2008), 站内

我们组内某小神童师弟通读论文,拟了一个机器学习的推荐论文和书籍列表。
经授权发布在这儿,希望对大家有用。:)

======================================
基本模型:
HMM(Hidden Markov Models):
      A Tutorial on Hidden Markov Models and Selected Applications in
Speech Recognition.pdf

ME(Maximum Entropy):
      ME_to_NLP.pdf

MEMM(Maximum Entropy Markov Models):
      memm.pdf

CRF(Conditional Random Fields):
      An Introduction to Conditional Random Fields for Relational Learning.pdf
      Conditional Random Fields: Probabilistic Models for Segmenting and
Labeling Sequence Data.pdf

SVM(support vector machine):
      *张学工<<统计学习理论>>

LSA(or LSI)(Latent Semantic Analysis):
      Latent semantic analysis.pdf

pLSA(or pLSI)(Probablistic Latent Semantic Analysis):
      Probabilistic Latent Semantic Analysis.pdf

LDA(Latent Dirichlet Allocation):
      Latent Dirichlet Allocaton.pdf(用variational theory + EM算法解模型)
      Parameter estimation for text analysis.pdf(using Gibbs Sampling 解模)

Neural Networksi(including Hopfield Model& self-organizing maps &
Stochastic networks & Boltzmann Machine etc.):
      Neural Networks – A Systematic Introduction

Diffusion Networks:
      Diffusion Networks, Products of Experts, and Factor Analysis.pdf

Markov random fields:

Generalized Linear Model(including logistic regression etc.):
      An introduction to Generalized Linear Models 2nd

Chinese Restraunt Model (Dirichlet Processes):
      Dirichlet Processes, Chinese Restaurant Processes and all that.pdf
      Estimating a Dirichlet Distribution.pdf

=================================================================
Some important algorithms:

EM(Expectation Maximization):
      Expectation Maximization and Posterior Constraints.pdf
      Maximum Likelihood from Incomplete Data via the EM Algorithm.pdf

MCMC(Markov Chain Monte Carlo) & Gibbs Sampling:
      Markov Chain Monte Carlo and Gibbs Sampling.pdf
      Explaining the Gibbs Sampler.pdf
      An introduction to MCMC for Machine Learning.pdf

PageRank:

矩阵分解算法:
      SVD, QR分解, Shur分解, LU分解, 谱分解

Boosting( including Adaboost):
      *adaboost_talk.pdf

Spectral Clustering:
      Tutorial on spectral clustering.pdf

Energy-Based Learning:
      A tutorial on Energy-based learning.pdf

Belief Propagation:
      Understanding Belief Propagation and its Generalizations.pdf
      bp.pdf
      Construction free energy approximation and generalized belief
propagation algorithms.pdf
      Loopy Belief Propagation for Approximate Inference An Empirical Study.pdf
      Loopy Belief Propagation.pdf

AP (affinity Propagation):

L-BFGS:
      <<最优化理论与算法 2nd>> chapter 10
      On the limited memory BFGS method for large scale optimization.pdf
IIS:
      IIS.pdf

=================================================================
理论部分:
概率图(probabilistic networks):
      An introduction to Variational Methods for Graphical Models.pdf
      Probabilistic Networks
      Factor Graphs and the Sum-Product Algorithm.pdf
      Constructing Free Energy Approximations and Generalized Belief
Propagation Algorithms.pdf
      *Graphical Models, exponential families, and variational inference.pdf

Variational Theory(变分理论,我们只用概率图上的变分):
      Tutorial on varational approximation methods.pdf
      A variational Bayesian framework for graphical models.pdf
      variational tutorial.pdf

Information Theory:
      Elements of Information Theory 2nd.pdf

测度论:
      测度论(Halmos).pdf
      测度论讲义(严加安).pdf

概率论:
      ……
      <<概率与测度论>>

随机过程:
      应用随机过程 林元烈 2002.pdf
      <<随机数学引论>>

Matrix Theory:
      矩阵分析与应用.pdf

模式识别:
      <<模式识别 2nd>> 边肇祺
      *Pattern Recognition and Machine Learning.pdf

最优化理论:
      <<Convex Optimization>>
      <<最优化理论与算法>>

泛函分析:
      <<泛函分析导论及应用>>

Kernel理论:
      <<模式分析的核方法>>

统计学:
      ……
      <<统计手册>>

==========================================================
综合:

semi-supervised learning:
      <<Semi-supervised Learning>> MIT Press
      semi-supervised learning based on Graph.pdf

Co-training:

Self-training:

※ 来源:·水木社区 newsmth.net·[FROM: 166.111.138.*]

Dhaka 2007 解题报告

http://acmicpc-live-archive.uva.es/nuevoportal/region.php?r=as9&year=2007

A. Bachelor Arithmetic

简单题,不多说

B. Nested Squares

也是简单题

C. The Dumb Grocer

比较有意思也有一定难度的题。给定N(N为int范围),要求出一组砝码,使得这组砝码的总重恰为N,且1..N的每个重量都有且仅有一种方法表示。问这样的砝码能有多少组。如N=5,则结果为3:{1,1,1,1,1}, {1,2,2}, {1,1,3}

首先容易发现重量为1的砝码至少有一个,然后我们可以想,若有k-1个1,则剩下的最小的砝码必须是k,然后在k+1至2k-1这段里也不能有别的砝码,这样才能避免重复。这样,1..N就被分成了N/k段,变成了一个更小规模的问题N=N/k-1。另外因为要求总重必须为N,所以k必须满足(N+1) % k = 0。我们设原问题的解为F(N),那么即有

$$F(N) = Sigma_{k>1, k|(N+1)}F(frac{N+1}{k}-1)$$

依此式直接计算是TLE的,变换一下形式得

$$F(N-1) = Sigma_{k>1,k|N}F(frac{N}{k}-1)$$

令G(N) = F(N-1),于是得

$$G(N) = Sigma_{k>1, k|N}G(frac{N}{k})$$

可以发现对于具有相同因式分解形式的N,G(N)都是相同的。由此可以用N的素因子分解后的指数序列(底数无关,次序无关)作为状态进行dp,这样状态就大大减少了,2^31范围内的状态足够放得下。另外注意极限数据2^31-1的处理。

D. ACM Puzzles

给定3*N的格子,问用一些不同形状的俄罗斯方块覆盖有多少种方案。明显的状态压缩dp,有点繁琐,要仔细不然很容易出错。

E. Inspector’s Dilemma

加边使一个图存在欧拉路。就是统计一下度,再计算即可。注意多个连通块的情况。

*F. The Bells are Ringing

不会做,也不太喜欢这样的题型……

G. Photographic Tour

题目不详述了。方法是从起点终点两个方向dp两次,把从起点能到的点和能到终点的点作上标记,两个标记都有的就是符合要求的。

H. You are around me …

给一堆点,给定一个倾斜的椭圆的倾角、长短轴长度。现在要求每个点都在一个椭圆的中心,所有椭圆的大小相同,不能相互重叠。问椭圆的最大面积。

乍一看无法下手,实际上坐标变换一下,把椭圆转正了,拉直了,变成一个正圆,问题就变成了求所有点的最近点对问题了……

*I. Infinite Matrix

不会做 – –

J. Magnetic Train Tracks

给一堆平面上的点,没有任何三点共线。求所有C(n,3)个三角形里面有多少个锐角三角形。N<=1200

锐角是不好处理的,我们可以求它的补集,也就是直角/钝角三角形,这样只需要对每个点分别统计以其为顶点的直角/钝角有多少个就行了。那么我们可以对每个点O,把其它点按极角序排序,然后对每个起始点pi,可以找到一个区间[pj,pk],使得在这个区间内的所有点与o,pi形成的角为直/钝角,这个区间可以用线性的扫描来确定(如果用二分查找是超时的),那么总的复杂度是O(n^2)。

进步

4293053 RoBa 2727 Accepted 488K 125MS G++ 2979B 2008-10-29 22:01:53
4293005 RoBa 2727 Wrong Answer     G++ 2952B 2008-10-29 21:53:59
966432 RoBa 2727 Wrong Answer     G++ 3741B 2006-01-13 17:08:37
966412 RoBa 2727 Wrong Answer     G++ 4109B 2006-01-13 16:51:28
966383 RoBa 2727 Wrong Answer     G++ 4068B 2006-01-13 16:20:57
966374 RoBa 2727 Wrong Answer     G++ 3934B 2006-01-13 16:15:08
966362 RoBa 2727 Wrong Answer     GCC 3739B 2006-01-13 16:00:34
966359 RoBa 2727 Wrong Answer     GCC 3712B 2006-01-13 15:58:40
966328 RoBa 2727 Wrong Answer     GCC 3163B 2006-01-13 15:35:49
966294 RoBa 2727 Wrong Answer     GCC 2887B 2006-01-13 15:17:39

2005 Beijing的Special Judge那题,两年多以前的时候,我要酝酿很长时间才鼓起勇气写,写了多长时间这上面看不出来了,但可以看出WA了以后调了两个小时仍然无效。现在这道题对我来说只是40分钟的代码量+8分钟找出一个弱智错误而已,从代码长度上也可以看出代码实现也更加聪明了。

最近做一些以前的比赛题,屡屡有这种自我提升的感觉,很高兴。

Harbin 2008 解题报告

http://acm.hdu.edu.cn/listproblem.php?vol=15

打星号表示还没过的题。

A. Shell Pyramid

题意就是给一堆堆成金字塔状的小球编号,问某编号的球属于哪一层哪一行哪一列。题目不难,比较不容易错的方法应该是二分来判断。但是要注意一下溢出的情况。我是把除法变成乘法来判断的。HanoiTower他们说在场上是直接打了一个大表然后在里面二分查找,很赞。

B. K-dimension number

求约数个数为k的第n小的数(n<10000)。k为素数或素数的平方,这个素数不超过100。如果是素数的话,这个数就就p[n]^(k-1),其中p[n]表示第n小的素数。如果是平方的话略有麻烦,我的方法是生成出所有不同的素数对的乘积p[i]*p[j]中最小的n个(因为可以估算出一个上界剪枝,这里的复杂度远不到平方),再生成出p[i]^(k-1)的最小的n个(即p[i]取前n个素数个的情况),把这两个有序表合并,再找第n大的。

C. Mining Station on the Sea

就是裸的最优匹配。先floyd处理出所有station间最短路,然后可以用一个O(n^3)得到所有station到所有port的最短路,然后直接套模板。

D. Gauss Elimination

裸的高斯消元。因为最后要求分数形式,所以用整系数消元的方法是比较合适的,并不需要自己写分数的四则运算。具体来说就是消元的时候不做除法,而是把两行都乘成它们的最小公倍数后相减,这样就避免了分数或小数的运算。当然因为代码量的缘故,Java是首选。

*E. Searching Treasure in Deep Sea

暴繁。没人交。不想做。

F. Simple Addition Expression

给定n,问比n小的数里有多少数i满足:计算i+(i+1)+(i+2)这两次加法的时候不需要进位。n<10^10

容易发现i必须满足最低位为0..2,其余各位为0..3。然后一位位算就可以了,发现用递归写起来比较简便。

G. Navy maneuvers

一个DAG上的dp。也是简单题。用dp[N][2]记录两方的结果,一方只选最大的,另一方只选最小的。

H. Carry Out A Task

其实也并不很难,繁琐了一些,貌似现场很少队过。我用程序试了一下B能量的可用次数不超过100,所以可以把它作为状态的一个维度了。就是一个最短路问题,以 {x坐标,y坐标,B能量的次数} 三元组作为状态,以 {毁坏度,A能量的花费,时间} 这样的三元组做为值,Bellman-ford求解。HDU OJ上时间卡的比较紧,一开始一直TLE,后来我是先bfs一遍求出毁坏度的下界,然后用这个限制状态的扩展,这样才500+MS过了。另外有个地方关于A能量的花费读错题了,WA了好几次。

I. Degree Sequence of Graph G

结论题。见我以前写的文章

*J. Dividing Sea Area to Navigation-Triangle

计算几何+DP。其实如果是求三角形的值和的话就不是很bt了。但现在要求的是最大与最小值的差最小,如果硬枚举一个最小值的话复杂度无法承受。怀疑要利用那个m较小的的条件,但不知道怎么做。-_-

Seoul 2007解题报告

http://acmicpc-live-archive.uva.es/nuevoportal/region.php?r=as4&year=2007

题目很好,共10题,除了最后一题都可做。现场冠军貌似是8道,我们去年的3队过了5道(还是6来着?)。我用了昨晚的几小时+今天下午的几小时搞定前九题了。

3900. A. Molar mass

简单水题

3901. B. Editor

裸的最长重复子串,但长度只有5000,所以用不着搬出什么后缀数组了,直接二分答案+hash O(nlogn)搞定。

3902. C. Network

不错的题目。给一棵树,要求在某些非叶子结点上放一些设备,这些设备可以覆盖距离不超过一个定值K的所有点。问要覆盖所有叶子结点最少要多少设备。

我的方法是贪心,任选一非叶子节点为根,把叶子节点按深度从深到浅处理。对每个未覆盖的叶子,将设备安装到比它高k层的位置(or根),然后把此设备能覆盖到的叶子都去掉,重复这个过程直至所有叶子都被覆盖。复杂度是O(n^2)。我不能证明任选根的正确性,直觉是对的,写了就过了。

3903. D. PHONE

有点小麻烦的模拟题,无数种方法可搞。

3904. E. Tile Code

简单递推题,问用1*2和2*2的两种骨牌覆盖2*N的格子有多少种方法。如果左右镜面反射后相同,认为是同一种方案。

首先如果没有后面的限制,那么有递推式f[n]=f[n-1]+2*f[n-2]。然后考虑这f[n]种里面有多少种是左右对称的,对于n是奇数的情况,这个数就是s[n]=f[n/2](即中间一块竖砖),对于n是偶数的情况,这个数是s[n]=f[n/2]+f[n/2-1]*2(三种情况,中间一块2*2方砖,中间两块1*2横砖,或者什么都没有)。于是最后的结果就是(f[n]+s[n])/2。

(这前五题过得很爽,全部1y,一共只花了一个半小时。当然,我这句话隐含的意思是,后面就开始囧了……)

3905. F. Meteor

给定一个矩形框及一些匀速直线运动的粒子,问什么时刻框内的粒子数最大。粒子在框边界上时不算。

思路很简单,对每个粒子可求得一个它在框内的时间区间[Si,Ei],把这些时间点排序以后扫描一遍就可以得出覆盖深数最多的区间即为所求。不过涉及到不少计算几何的计算,尤其那个在边界上时不算的条件比较恶心。写扯了,写了200行,犯了弱智错误一摞,WA了挺长时间。

3906. G. Singals

题意不好描述。就是一个表达式处理,是一个简化了的正则表达式形式,把所有能生成出来的结果都暴力出来即可。犯了个弱智错误是读数字的时候用了%s…然后就TLE了,多亏没盲目去优化算法,很快发现了错误改对了。

3907. H. Puzzle

给出字母表及一组禁止出现的串,要求出一个尽可能长的串使得不包括任何禁止串(也可能是无穷长度)。

思路就是AC自动机,自动机建立起来以后,把所有的禁止点去掉,如果有环就是无穷长,否则按拓扑序搞一下dp就行了。写的时候突发奇想用了记忆化搜索,把判环和dp直接一次完成了,感觉这个方法很不错。囧的是因为读错题挂了两次,一个是如果长度为0要输出No,一个是如果最长串很多,要求的是字典序最大的(我看到“字典序”那个词就自作主张地以为是求字典序最小了……囧)。

3908. I. Turtle Graphics

模拟题,题意叙述有点小烦。看上去比较麻烦,但仔细想想可以有比较简单的写法,我的程序只写了70行,但交上去TLE。怀疑是写死循环了,但找不到错,直接暴力生成随机小数据才发现了错误的地方。如果现场赛的话这种占机时的debug方法还是尽量少用为好。

3909. J. Number

不会做 -_-
可能是要加优化的dp? 看到过的人太少(两个),不怎么敢想了。