这就是amazon发明的“喜欢这个商品的人，也喜欢某某”算法。&br&其核心是数学中的“多维空间中两个向量夹角的余弦公式”，当初我的确是被这算法惊艳到了。&br&&br&============= 更新 =============================&br&不好意思，之前说的有误，特来更正兼补充。&br&&br&“商品推荐”系统的算法( &a href=&//link.zhihu.com/?target=http%3A//en.wikipedia.org/wiki/Collaborative_filtering& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Collaborative filtering&i class=&icon-external&&&/i&&/a& )分两大类，&br&第一类，以人为本，先找到与你相似的人，然后看看他们买了什么你没有买的东西。这类算法最经典的实现就是“多维空间中两个向量夹角的余弦公式”；&br&第二类, 以物为本直接建立各商品之间的相似度关系矩阵。这类算法中最经典是'斜率=1' (&a href=&//link.zhihu.com/?target=http%3A//en.wikipedia.org/wiki/Slope_One& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Slope One&i class=&icon-external&&&/i&&/a&)。amazon发明了暴力简化的第二类算法，‘买了这个商品的人，也买了xxx’。&br&&br&我们先来看看第一类，最大的问题如何判断并量化两人的相似性，思路是这样 -- &br&例子：&br&有3首歌放在那里，《最炫民族风》，《晴天》，《Hero》。&br&A君，收藏了《最炫民族风》，而遇到《晴天》，《Hero》则总是跳过；&br&B君，经常单曲循环《最炫民族风》，《晴天》会播放完，《Hero》则拉黑了&br&C君，拉黑了《最炫民族风》，而《晴天》《Hero》都收藏了。&br&&br&我们都看出来了，A,B二位品味接近，C和他们很不一样。&br&那么问题来了，说A，B相似，到底有多相似，如何量化？&br&&br&我们把三首歌想象成三维空间的三个维度，《最炫民族风》是x轴，《晴天》是y轴，《Hero》是z轴，对每首歌的喜欢程度即该维度上的坐标，&br&并且对喜欢程度做量化(比如： 单曲循环=5, 分享=4, 收藏=3, 主动播放=2 ,
跳过=-1 , 拉黑=-5 )。&br&那么每个人的总体口味就是一个向量，A君是 (3,-1,-1)，B君是(5,1,-5)，C君是(-5,3,3)。
(抱歉我不会画立体图)&br&我们可以用向量夹角的余弦值来表示两个向量的相似程度， 0度角(表示两人完全一致)的余弦是1， 180%角(表示两人截然相反)的余弦是-1。&br&&br&根据余弦公式,
&b& 夹角余弦 = 向量点积/ (向量长度的叉积)&/b& =
( x1x2 + y1y2 + z1z2) / (
跟号(x1平方+y1平方+z1平方 ) x
跟号(x2平方+y2平方+z2平方 ) )&br&可见 A君B君夹角的余弦是0.81 ， A君C君夹角的余弦是 -0.97 ，公式诚不欺我也。&br&以上是三维(三首歌)的情况，如法炮制N维N首歌的情况都是一样的。&br&假设我们选取一百首种子歌曲，算出了各君之间的相似值，那么当我们发现A君还喜欢听的《小苹果》B君居然没听过，相信大家都知道该怎么和B君推荐了吧。&br&&br&第一类以人为本推荐算法的好处我想已经很清楚了，那就是精准！&br&代价是运算量很大，而且对于新来的人(听得少，动作少)，也不太好使，&br&所以人们又发明了第二类算法。&br&&br&假设我们对新来的D君，只知道她喜欢最炫民族风，那么问题来了，给她推荐啥好咯？&br&&figure&&img src=&https://pic1.zhimg.com/f9b50aa7934b1bcebacb4e715d9f1190_b.jpg& data-rawwidth=&903& data-rawheight=&552& class=&origin_image zh-lightbox-thumb& width=&903& data-original=&https://pic1.zhimg.com/f9b50aa7934b1bcebacb4e715d9f1190_r.jpg&&&/figure&&br&如图，推荐《晴天》！&br&&br&呵呵，第二类算法的好处大家也看出来了，简单粗暴好操作(也适合map-reduce)，可精度差了点。&br&&br&所以，各家网站真正的推荐算法，是他们在综合上述两类算法的基础上，各自研制并且不断地改进调节的，外人不得而知！ ^_^&br&&br&===
再补充 ===&br&&br&多谢 @刘彦彬 给了一个非常专业的评论 ，不贴出来可惜了。&br&&i&“这个只能说是理论基础。歌曲不考虑热门冷门，同时不考虑用户数和歌曲数计算复杂度的话第一一天内离线数据计算不完的（当然网易云音乐用户量小全量暴力计算当我没说），实际应用起来复杂很多了。现在的推荐系统并不存在一种算法通吃，除了算法上的问题，还需要考虑基础数据的影响因素，比如两张歌单有多少歌曲重合，歌单的质量是怎么样的。” &/i&&br&&br&我上一帖也说了，&br&'向量夹角余弦' 解决的是‘量化顾客口味相似度’的问题(是最经典的解法，也有别的解法)，&br&不是有了它就能轻易实现第一类算法的，难处在后面咯。&br&我不是干‘CF/算法/数据挖掘/互联网’的，只是几年前偶尔瞄到过这方面文章被惊艳了一下，&br&见到这题就随口抖了个机灵，然后被评论区几位带板凳来的朋友给推上来了 ^_^&br&&br&既然大家都这么有兴趣，我在来抛块砖，说说‘有了理论基础之后咋整’的思(nao3)考(dong4)。&br&继续第一类算法的话题，目标“每日歌曲推荐”(其实题主感兴趣的是这个吧，旁边‘根据你喜欢的xxx推荐的yyy歌单’我觉得不咋样)。&br&首先就是如何定维度。
&br&直接用‘歌’当维度是不行的，第一是太多了算不过来，第二维度数一直猛涨也不是个事。&br&用‘歌单’或者‘专辑’，‘演唱/演奏者’呢？也有类似的困难。&br&说到这里大家应该都意识到了，咱不是还有‘tag’嘛！&br&云音乐初期，tag是可以由大家自己填的，我记得我填过‘莫扎特’，‘钢协’，‘交响’这样的tag，现在都不见了吧。&br&一段时间之后，tag无法自填了，只能从云音乐给的tag lib中选，这肯定有原因的。&br&我的推测就是，他们需要用tag来当作维度，所以不希望tag数经常变化。&br&第一阶段，他们需要搜集用户的输入来做出tag lib，&br&第二阶段，他们构建了多维度空间，就不希望再动维度了，因此关闭了自填tag的功能。&br&&br&假设就用tag做为维度，那么第二个难处在于，维度上的'刻度'必须有正有负才好使，&br&用户没有机会直接表达对tag的好恶(不能收藏，播放，跳过一个tag)，如何定刻度呢。&br&我认为每一首歌背后是有其所属tags这个属性的，这个属性在UI上看不到很可能是因为比较容易引起口水。&br&歌往往隶属于很多歌单，而那些歌单都是有tags的，根据那些歌单的播放数收藏数分享数可以决定其'权威性'，&br&取'权威性'高的歌单的tag，就可以得到每首歌的tag属性。&br&然后用户在表达对一首首歌的好恶的时候，其实就不知不觉地影响了他在相应维度上的刻度。&br&&br&假设维度和刻度都这样解决，那么我们可以对每个用户做出‘口味向量’了，接下来的难处是，&br&啥时候算/如何保存‘用户相似性’？&br&所有用户两两算一下相似性，存为一个NxN的矩阵，这种事情不是闹这玩的。&br&&br&其实到了这一步，不考虑‘以人为本’，直接根据我喜欢的tag，从各tag里挑一些人气高的，或者蹿升快的歌来推荐也算是能交差了。&br&不过那样的话，就容易同质化，也就不易让用户‘惊艳’了。&br&让我们继续沿着第一类算法的思路琢磨琢磨。&br&&br&多维度空间还有一大好处是，有‘像限’这种的概念，&br&比如我们可以粗暴地假设，和我同一个像限的人，就是和我‘相似’的人，&br&如果因为维度太多，或者初期用户太少等原因找不到同像限的人， 还可以去‘相邻’的像限找嘛。&br&OK，假设我们根据tag以及自己的像限，找到了一批和自己‘气味相投’的人。&br&再丛这批人中，选几个‘和我夹角余弦’最大(再综合一下个人名声比如星标，粉丝数，和我的互动度等，更好)的人，&br&从他们听过而我没听过的歌中，再选一批 他们喜欢，或者他们新听到，新收藏，或者总人气高的等等，&br&就可以说是“根据我的口味生成”的“每日歌曲推荐”了。&br&&br&以上内容，均是臆测，如果雷同，纯属巧合 ^_^
这就是amazon发明的“喜欢这个商品的人，也喜欢某某”算法。 其核心是数学中的“多维空间中两个向量夹角的余弦公式”，当初我的确是被这算法惊艳到了。 ============= 更新 ============================= 不好意思，之前说的有误，特来更正兼补…
谢邀。&br&&br&这道题怎么做，取决于我们如何从数学的角度理解题干中这句话：&br&&b&“他们的原则是先求保命，再去多杀人”。&/b&&br&&br&我的理解是：&br&&ol&&li&每个人采取方案，使得剩下的人在采取最佳方案的时候，自己的存活概率最大；&br&&/li&&li&如果有多种方案使得自己的存活概率最大且相同，则采取杀死人最多的方案；&br&&/li&&/ol&&br&假设我的理解正确，那么，&b&这道题将会有一个可怕的答案。&/b&&br&&br&&b&定义： &/b&&img src=&//www.zhihu.com/equation?tex=m_%7Bn%7D+& alt=&m_{n} & eeimg=&1&& 为第 &img src=&//www.zhihu.com/equation?tex=n& alt=&n& eeimg=&1&& 个人取走的绿豆数，而 &img src=&//www.zhihu.com/equation?tex=M_%7Bn%7D+& alt=&M_{n} & eeimg=&1&& 为前 &img src=&//www.zhihu.com/equation?tex=n& alt=&n& eeimg=&1&& 个人取走的总绿豆数&br&&br&&br&&b&引理 1&/b&：&br&当 &img src=&//www.zhihu.com/equation?tex=n& alt=&n& eeimg=&1&& 个人 (&img src=&//www.zhihu.com/equation?tex=1%5Cleq+n%5Cleq+3& alt=&1\leq n\leq 3& eeimg=&1&&) 取过绿豆时，如果被取走的绿豆数满足&br&&img src=&//www.zhihu.com/equation?tex=20n%3CM_%7Bn%7D%3C95%2Bn+& alt=&20n&M_{n}&95+n & eeimg=&1&&&br&则第 &img src=&//www.zhihu.com/equation?tex=n%2B1& alt=&n+1& eeimg=&1&& 个人应该取 &img src=&//www.zhihu.com/equation?tex=m_%7Bn%2B1%7D+%3D%5Cmin%5Cleft%28+96-M_%7Bn%7D%2Bn%2C%5Cleft%5B+%5Cfrac%7BM_%7Bn%7D-1+%7D%7Bn%7D++%5Cright%5D+++%5Cright%29+& alt=&m_{n+1} =\min\left( 96-M_{n}+n,\left[ \frac{M_{n}-1 }{n}
\right) & eeimg=&1&& 颗绿豆’&br&&br&&b&证明：&/b&&br&&br&这个方案，可以确保自己不死，同时剩下未取豆子的人死亡概率最大。&br&&br&其中：&br&&ul&&li&&img src=&//www.zhihu.com/equation?tex=96-M_%7Bn%7D%2Bn& alt=&96-M_{n}+n& eeimg=&1&& 是确保剩下的人至少有一颗绿豆可选，且自己至少取了 2 颗；&br&&/li&&li&&img src=&//www.zhihu.com/equation?tex=%5Cleft%5B+%5Cfrac%7BM_%7Bn%7D-1+%7D%7Bn%7D++%5Cright%5D+++& alt=&\left[ \frac{M_{n}-1 }{n}
& eeimg=&1&& 是确保自己取的绿豆数至少比前面取的最多的人少 1 ；&br&&/li&&/ul&&br&由于 &img src=&//www.zhihu.com/equation?tex=M_%7Bn%7D%3E20n& alt=&M_{n}&20n& eeimg=&1&&, 有&img src=&//www.zhihu.com/equation?tex=%5Cleft%5B+%5Cfrac%7BM_%7Bn%7D-1+%7D%7Bn%7D++%5Cright%5D++%5Cgeq+20& alt=&\left[ \frac{M_{n}-1 }{n}
\geq 20& eeimg=&1&&, 这不仅保证了自己取的豆子数不是最多的，并且其他人不可能都取到那么多，所以自己必然存活；&br&&br&&ul&&li&如果 &img src=&//www.zhihu.com/equation?tex=%5Cleft%5B+%5Cfrac%7BM_%7Bn%7D-1+%7D%7Bn%7D++%5Cright%5D++%3C+96-M_%7Bn%7D-n& alt=&\left[ \frac{M_{n}-1 }{n}
& 96-M_{n}-n& eeimg=&1&&，他在确保自己存活的情况下，使得剩下的豆子数最少，这样可以杀更多的人；&/li&&li&如果&img src=&//www.zhihu.com/equation?tex=+%5Cleft%5B+%5Cfrac%7BM_%7Bn%7D-1+%7D%7Bn%7D++%5Cright%5D++%5Cgeq++96-M_%7Bn%7D-n& alt=& \left[ \frac{M_{n}-1 }{n}
96-M_{n}-n& eeimg=&1&&，他在确保自己存活的情况下，剩下的人每个人只能取 1 颗豆子，确保杀死剩下的所有人；&br&&/li&&/ul&&br&&b&推论1&/b&：如果第 1 个人想要存活，那么他取的豆子数不能超过 20 颗，否则，后面的人只要采取引理1 的方案，将保证自己存活，且此时第 1 个人会因为取的绿豆数最多而死亡，而最后 1~3 个人（根据第 1 个人取的绿豆数）会因为自己取的豆子数最少而死亡；&br&&br&&br&&b&引理 2&/b&：当 &img src=&//www.zhihu.com/equation?tex=n%3D2%2C3& alt=&n=2,3& eeimg=&1&&时，若&img src=&//www.zhihu.com/equation?tex=M_%7Bn%7D%5Cleq+20n& alt=&M_{n}\leq 20n& eeimg=&1&&，&br&则第 &img src=&//www.zhihu.com/equation?tex=n%2B1& alt=&n+1& eeimg=&1&& 个人应该取 &img src=&//www.zhihu.com/equation?tex=m_%7Bn%2B1%7D+%3D%5Cleft%5B+%5Cfrac%7BM_%7Bn%7D%7D%7Bn%7D%2B0.5%5Cright%5D+& alt=&m_{n+1} =\left[ \frac{M_{n}}{n}+0.5\right] & eeimg=&1&& 颗绿豆’来确保自己的存活概率最高&br&&br&（其中，&img src=&//www.zhihu.com/equation?tex=%5Cleft%5B+%5Cfrac%7BM_%7Bn%7D%7D%7Bn%7D%2B0.5%5Cright%5D+& alt=&\left[ \frac{M_{n}}{n}+0.5\right] & eeimg=&1&& 是均值的四舍五入）&br&&br&因为当且仅当在这种情况下，只要前面的人取的绿豆数的最大最小值之差不小于 2，自己就确保能存活（否则存活范围会变窄）&br&&br&* &i&对于第 5 个人，这个条件可能不成立，比如见到前面四个人取了 62 颗， 可能是 14+16+16+16，也可能是 15+15+15+17，所以他无论取 15 颗还是 16 颗都有机会但不能确保自己存活。&/i&&br&&br&而所有人取绿豆的最大最小值的差不大于 1，所有人都得死；&br&&br&&b&引理3&/b&： 当大家都极度自私的情况下，前 2 个人没有存活的可能&br&&br&这是因为由引理2，如果第 3~5 个人都会采取对他们而言存活概率的方案，如果第 2 个人和第 1 个人取的绿豆数差超过 1 个，那前两个人就包揽了最大最小值，必须死，如果差不超过1，则所有人都得死；&br&&br&既然第 1 个人没有存活概率，那他的目标就很耐人寻味了：&br&&br&&b&如果自己没有存活概率——&/b&&br&&b&选择1：杀死尽可能多的人&/b&&br&&b&选择2：尽可能拯救更多的人&/b&&br&&br&按照我的假设，应该是前者。&br&&br&既然第 1 个人没有存活概率，不妨让大家都死得干净些——&b&取走 96 颗绿豆！&/b&&br&&br&但如果，第 1 个人有点恻隐之心，做出了选择 2：&br&&br&那，他会取走 21~33 的豆子数，根据 引理1， 第 2~4 个人会存活；&br&&br&&b&所以，本题根据对题意的不同理解，有两解：&/b&&br&&ul&&li&&b&所有人都死亡；&/b&&br&&/li&&li&&b&第 2~4 个人存活；&/b&&br&&/li&&/ul&&br&而对于第 1 个囚犯，他将面临一个哲学难题：&br&&b&如果自己不可能活下去，你会选择让别人陪葬，还是让其他人好好活下去？&/b&&br&&br&如果是你，会怎么选择呢？&br&&br&【完】
谢邀。 这道题怎么做，取决于我们如何从数学的角度理解题干中这句话： “他们的原则是先求保命，再去多杀人”。 我的理解是： 每个人采取方案，使得剩下的人在采取最佳方案的时候，自己的存活概率最大； 如果有多种方案使得自己的存活概率最大且相同，则采…
非常好的一个问题。这可能是我在知乎见到过的问编程有关的问题中问得最好的一个了。我非常喜欢这个问题。&br&&br&计算机科学有两类根本问题。一类是理论：算法，数据结构，复杂度，机器学习，模式识别，等等等。一类是系统：操作系统，网络系统，分布式系统，存储系统，游戏引擎，等等等等。&br&&br&理论走的是深度，是在追问在给定的计算能力约束下如何把一个问题解决得更快更好。而系统走的是广度，是在追问对于一个现实的需求如何在众多的技术中设计出最多快好省的技术组合。&br&&br&搞ACM的人，只练第一类。像你这样的更偏向于第二类。其实挺难得的，但很可惜的是第二类能力没有简单高效的测量考察方法，不像算法和数据结构有ACM竞赛，所以很多系统的苗子都因为缺少激励和正确引导慢慢就消隐了。&br&&br&所以比尔盖茨才会说，看到现在学编程的人经常都把编程看作解各种脑筋急转弯的问题，他觉得很遗憾。&br&&br&做系统，确实不提倡“重复发明轮子”。但注意，是不提倡“重复发明”，不是不提倡“重新制造”。恰恰相反的，我以为，系统的编程能力正体现在“重新制造”的能力。&br&&br&能把已有的部件接起来，这很好。但当你恰好缺一种关键的胶水的时候，你能写出来吗？当一个已有的部件不完全符合你的需求的时候，你能改进它吗？如果你用的部件中有bug，你能把它修好吗？在网上繁多的类似功能的部件中，谁好谁坏？为什么？差别本质吗？一个开源代码库，你能把它从一个语言翻译到另一个语言吗？从一个平台移植到另一个平台吗？能准确估计自己翻译和移植的过程需要多少时间吗？能准确估计翻译和移植之后性能是会有提升还是会有所下降吗？&br&&br&系统编程能力体现在把已有的代码拿来并变成更好的代码，体现在把没用的代码拿来并变成有用的代码，体现在把一个做好的轮子拿来能画出来轮子的设计蓝图，并用道理解释出设计蓝图中哪些地方是关键的，哪些地方是次要的，哪些地方是不容触碰的，哪些地方是还可以改进的。&br&&br&如果你一点不懂理论，还是应该学点的。对于系统性能的设计上，算法和数据结构就像在自己手头的钱一样，它们不是万能的，但不懂是万万不行的。&br&&br&怎么提高系统编程能力呢？土办法：多造轮子。就像学画画要画鸡蛋一样，不是这世界上没有人会画鸡蛋，但画鸡蛋能驯服手指，感受阴影线条和笔触。所以，自己多写点东西吧。写个编译器？渲染器？操作系统？web服务器？web浏览器？部件都一个个换成自己手写的，然后和已有的现成部件比一比，看看谁的性能好，谁的易用性好？好在哪儿？差在哪儿？为什么？&br&&br&更聪明一点的办法：多拆轮子。多研究别人的代码是怎么写的。然而这个实践起来经常很难。原因：大部分工业上用的轮子可能设计上的思想和技术是好的，都设计和制造过程都很烂，里面乱成一团，让人乍一看毫无头绪，导致其对新手来说非常难拆。这种状况其实非常糟糕。所以，此办法一般只对比较简单的轮子好使，对于复杂的轮子，请量力而行。&br&&br&轮子不好拆，其实是一个非常严重的问题。重复发明轮子固然是时间的浪费，但当轮子复杂而又不好拆的时候，尤其是原来造轮子的人已经不在场的时候，重新发明和建造轮子往往会成为无奈之下最好的选择。这是为什么工业界在明知道重复发明/制造轮子非常不好的情况下还在不断重复发明/制造轮子的根本原因。&br&&br&程序本质是逻辑演绎的形式化表达，记载的是人类对这个世界的数字化理解。不能拆的轮子就像那一篇篇丢了曲谱的宋词一样，能读，却不能唱。&br&&br&鄙人不才，正在自己研究怎么设计建造一种既好用又好拆的轮子。您没那么幸运，恐怕是等不到鄙人的技术做出来并发扬光大了。在那之前，多造轮子，多拆好拆的小轮子，应该是提高编程能力最好的办法了。&br&&br&以上。嗯。&br&&i&（文章属个人观点，与本人工作雇主无关。）&/i&
非常好的一个问题。这可能是我在知乎见到过的问编程有关的问题中问得最好的一个了。我非常喜欢这个问题。 计算机科学有两类根本问题。一类是理论：算法，数据结构，复杂度，机器学习，模式识别，等等等。一类是系统：操作系统，网络系统，分布式系统，存储…
神经网络很萌的！&br&&br&&b&0. 分类&/b&&br&神经网络最重要的用途是分类，为了让大家对分类有个直观的认识，咱们先看几个例子：&br&&ul&&li&垃圾邮件识别：现在有一封电子邮件，把出现在里面的所有词汇提取出来，送进一个机器里，机器需要判断这封邮件是否是垃圾邮件。&/li&&li&疾病判断：病人到医院去做了一大堆肝功、尿检测验，把测验结果送进一个机器里，机器需要判断这个病人是否得病，得的什么病。&/li&&li&猫狗分类：有一大堆猫、狗照片，把每一张照片送进一个机器里，机器需要判断这幅照片里的东西是猫还是狗。&/li&&/ul&这种能自动对输入的东西进行分类的机器，就叫做分类器。&br&&br&分类器的输入是一个数值向量，叫做特征（向量）。在第一个例子里，分类器的输入是一堆0、1值，表示字典里的每一个词是否在邮件中出现，比如向量(1,1,0,0,0......)就表示这封邮件里只出现了两个词abandon和abnormal；第二个例子里，分类器的输入是一堆化验指标；第三个例子里，分类器的输入是照片，假如每一张照片都是320*240像素的红绿蓝三通道彩色照片，那么分类器的输入就是一个长度为320*240*3=230400的向量。&br&&br&分类器的输出也是数值。第一个例子中，输出1表示邮件是垃圾邮件，输出0则说明邮件是正常邮件；第二个例子中，输出0表示健康，输出1表示有甲肝，输出2表示有乙肝，输出3表示有饼干等等；第三个例子中，输出0表示图片中是狗，输出1表示是猫。&br&&br&分类器的目标就是让正确分类的比例尽可能高。一般我们需要首先收集一些样本，人为标记上正确分类结果，然后用这些标记好的数据训练分类器，训练好的分类器就可以在新来的特征向量上工作了。&br&&br&&b&1. 神经元&/b&&br&咱们假设分类器的输入是通过某种途径获得的两个值，输出是0和1，比如分别代表猫和狗。现在有一些样本：&br&&figure&&img src=&https://pic3.zhimg.com/6ecf14a96fc508a0ce2c8c9f77a89662_b.jpg& data-rawwidth=&420& data-rawheight=&315& class=&content_image& width=&420&&&/figure&大家想想，最简单地把这两组特征向量分开的方法是啥？当然是在两组数据中间画一条竖直线，直线左边是狗，右边是猫，分类器就完成了。以后来了新的向量，凡是落在直线左边的都是狗，落在右边的都是猫。&br&&br&一条直线把平面一分为二，一个平面把三维空间一分为二，一个n-1维超平面把n维空间一分为二，两边分属不同的两类，这种分类器就叫做神经元。&br&&br&大家都知道平面上的直线方程是&img src=&//www.zhihu.com/equation?tex=ax%2Bby%2Bc%3D0& alt=&ax+by+c=0& eeimg=&1&&，等式左边大于零和小于零分别表示点&img src=&//www.zhihu.com/equation?tex=%28x%2Cy%29& alt=&(x,y)& eeimg=&1&&在直线的一侧还是另一侧，把这个式子推广到n维空间里，直线的高维形式称为超平面，它的方程是：&br&&img src=&//www.zhihu.com/equation?tex=h+%3D+a_1x_1%2Ba_2+x_2%2B...%2Ba_nx_n%2Ba_0%3D0& alt=&h = a_1x_1+a_2 x_2+...+a_nx_n+a_0=0& eeimg=&1&&&br&神经元就是当h大于0时输出1，h小于0时输出0这么一个模型，它的实质就是&b&把特征空间一切两半，认为两瓣分别属两个类&/b&。你恐怕再也想不到比这更简单的分类器了，它是McCulloch和Pitts在1943年想出来了。&br&&br&这个模型有点像人脑中的神经元：从多个感受器接受电信号&img src=&//www.zhihu.com/equation?tex=x_1%2C+x_2%2C...%2Cx_n& alt=&x_1, x_2,...,x_n& eeimg=&1&&，进行处理（加权相加再偏移一点，即判断输入是否在某条直线&img src=&//www.zhihu.com/equation?tex=h%3D0& alt=&h=0& eeimg=&1&&的一侧），发出电信号（在正确的那侧发出1，否则不发信号，可以认为是发出0），这就是它叫神经元的原因。&br&&br&当然，上面那幅图我们是开了上帝视角才知道“一条竖直线能分开两类”，在实际训练神经元时，我们并不知道特征是怎么抱团的。神经元模型的一种学习方法称为Hebb算法：&br&&br&先随机选一条直线/平面/超平面，然后把样本一个个拿过来，如果这条直线分错了，说明这个点&b&分错边了&/b&，就稍微把直线移动一点，让它靠近这个样本，争取跨过这个样本，让它跑到直线正确的一侧；如果直线分对了，它就暂时停下不动。因此训练神经元的过程就是这条直线不断在跳舞，最终跳到两个类之间的竖直线位置。&br&&br&&b&2. 神经网络&/b&&br&MP神经元有几个显著缺点。首先它把直线一侧变为0，另一侧变为1，这东西不可微，不利于数学分析。人们用一个和0-1阶跃函数类似但是更平滑的函数Sigmoid函数来代替它（Sigmoid函数自带一个尺度参数，可以控制神经元对离超平面距离不同的点的响应，这里忽略它），从此神经网络的训练就可以用梯度下降法来构造了，这就是有名的反向传播算法。&br&&br&神经元的另一个缺点是：它只能切一刀！你给我说说一刀怎么能把下面这两类分开吧。&br&&figure&&img src=&https://pic3.zhimg.com/28cd0deae5b9f80de4e4a_b.jpg& data-rawwidth=&420& data-rawheight=&315& class=&content_image& width=&420&&&/figure&解决办法是多层神经网络，底层神经元的输出是高层神经元的输入。我们可以在中间横着砍一刀，竖着砍一刀，然后把左上和右下的部分合在一起，与右上的左下部分分开；也可以围着左上角的边沿砍10刀把这一部分先挖出来，然后和右下角合并。&br&&br&&b&每砍一刀，其实就是使用了一个神经元&/b&，把不同砍下的半平面做交、并等运算，就是把这些神经元的输出当作输入，后面再连接一个神经元。这个例子中特征的形状称为异或，这种情况一个神经元搞不定，但是两层神经元就能正确对其进行分类。&br&&br&只要你能砍足够多刀，把结果拼在一起，什么奇怪形状的边界神经网络都能够表示，所以说神经网络&b&在理论上&/b&可以表示很复杂的函数/空间分布。但是真实的神经网络是否能摆动到正确的位置还要看网络初始值设置、样本容量和分布。&br&&br&神经网络神奇的地方在于它的每一个组件非常简单——把空间切一刀+某种激活函数(0-1阶跃、sigmoid、max-pooling)，但是可以一层一层级联。输入向量连到许多神经元上，这些神经元的输出又连到一堆神经元上，这一过程可以重复很多次。这和人脑中的神经元很相似：每一个神经元都有一些神经元作为其输入，又是另一些神经元的输入，数值向量就像是电信号，在不同神经元之间传导，每一个神经元只有满足了某种条件才会发射信号到下一层神经元。当然，人脑比神经网络模型复杂很多：人工神经网络一般不存在环状结构；人脑神经元的电信号不仅有强弱，还有时间缓急之分，就像莫尔斯电码，在人工神经网络里没有这种复杂的信号模式。&br&&br&&figure&&img src=&https://pic2.zhimg.com/df53fac99fc53ba5a90666abcca25e6d_b.jpg& data-rawwidth=&300& data-rawheight=&225& class=&content_image& width=&300&&&/figure&&br&&br&神经网络的训练依靠反向传播算法：最开始输入层输入特征向量，网络层层计算获得输出，输出层发现输出和正确的类号不一样，这时它就让最后一层神经元进行参数调整，最后一层神经元不仅自己调整参数，还会勒令连接它的倒数第二层神经元调整，层层往回退着调整。经过调整的网络会在样本上继续测试，如果输出还是老分错，继续来一轮回退调整，直到网络输出满意为止。这很像中国的文艺体制，武媚娘传奇剧组就是网络中的一个神经元，最近刚刚调整了参数。&br&&br&&b&3. 大型神经网络&/b&&br&&br&我们不禁要想了，假如我们的这个网络有10层神经元，第8层第2015个神经元，它有什么含义呢？我们知道它把第七层的一大堆神经元的输出作为输入，第七层的神经元又是以第六层的一大堆神经元做为输入，那么这个特殊第八层的神经元，它会不会代表了某种抽象的概念？&br&&br&就好比你的大脑里有一大堆负责处理声音、视觉、触觉信号的神经元，它们对于不同的信息会发出不同的信号，那么会不会有这么一个神经元（或者神经元小集团），它收集这些信号，分析其是否符合某个抽象的概念，和其他负责更具体和更抽象概念的神经元进行交互。&br&&br&2012年多伦多大学的Krizhevsky等人构造了一个超大型&a href=&//link.zhihu.com/?target=http%3A//www.cs.toronto.edu/%7Efritz/absps/imagenet.pdf& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&卷积神经网络&i class=&icon-external&&&/i&&/a&[1]，有9层，共65万个神经元，6千万个参数。网络的输入是图片，输出是1000个类，比如小虫、美洲豹、救生船等等。这个模型的训练需要海量图片，它的分类准确率也完爆先前&b&所有&/b&分类器。纽约大学的&a href=&//link.zhihu.com/?target=http%3A//web.engr.illinois.edu/%7Eslazebni/spring14/lec24_cnn.pdf& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Zeiler和Fergusi&i class=&icon-external&&&/i&&/a&[2]把这个网络中某些神经元挑出来，把在其上响应特别大的那些输入图像放在一起，看它们有什么共同点。他们发现中间层的神经元响应了某些十分抽象的特征。&br&&br&第一层神经元主要负责识别颜色和简单纹理&br&&figure&&img src=&https://pic4.zhimg.com/cbd8eee22dca8b0e67f84b3_b.jpg& data-rawwidth=&779& data-rawheight=&422& class=&origin_image zh-lightbox-thumb& width=&779& data-original=&https://pic4.zhimg.com/cbd8eee22dca8b0e67f84b3_r.jpg&&&/figure&&br&第二层的一些神经元可以识别更加细化的纹理，比如布纹、刻度、叶纹。&br&&figure&&img src=&https://pic4.zhimg.com/78fd60058ceabf34d8c77_b.jpg& data-rawwidth=&1060& data-rawheight=&531& class=&origin_image zh-lightbox-thumb& width=&1060& data-original=&https://pic4.zhimg.com/78fd60058ceabf34d8c77_r.jpg&&&/figure&&br&&br&第三层的一些神经元负责感受黑夜里的黄色烛光、鸡蛋黄、高光。&br&&figure&&img src=&https://pic3.zhimg.com/aae832d13b33f15ba97c358fdf7319d2_b.jpg& data-rawwidth=&1058& data-rawheight=&537& class=&origin_image zh-lightbox-thumb& width=&1058& data-original=&https://pic3.zhimg.com/aae832d13b33f15ba97c358fdf7319d2_r.jpg&&&/figure&&br&第四层的一些神经元负责识别萌狗的脸、七星瓢虫和一堆圆形物体的存在。&br&&figure&&img src=&https://pic4.zhimg.com/d456b0fda993b_b.jpg& data-rawwidth=&1058& data-rawheight=&489& class=&origin_image zh-lightbox-thumb& width=&1058& data-original=&https://pic4.zhimg.com/d456b0fda993b_r.jpg&&&/figure&&br&第五层的一些神经元可以识别出花、圆形屋顶、键盘、鸟、黑眼圈动物。&br&&figure&&img src=&https://pic3.zhimg.com/abff15f9ddb3eb716c7da6_b.jpg& data-rawwidth=&1060& data-rawheight=&601& class=&origin_image zh-lightbox-thumb& width=&1060& data-original=&https://pic3.zhimg.com/abff15f9ddb3eb716c7da6_r.jpg&&&/figure&&br&&br&这里面的概念并不是整个网络的输出，是网络中间层神经元的偏好，它们为后面的神经元服务。虽然每一个神经元都傻不拉几的（只会切一刀），但是65万个神经元能学到的东西还真是深邃呢。&br&&br&[1] Krizhevsky, A., Sutskever, I., & Hinton, G. E. (2012). Imagenet classification with deep convolutional neural networks. In &i&Advances in neural information processing systems&/i& (pp. ).&br&[2] Zeiler, M. D., & Fergus, R. (2013). Visualizing and understanding convolutional neural networks. &i&arXiv preprint arXiv:&/i&.
神经网络很萌的！ 0. 分类 神经网络最重要的用途是分类，为了让大家对分类有个直观的认识，咱们先看几个例子： 垃圾邮件识别：现在有一封电子邮件，把出现在里面的所有词汇提取出来，送进一个机器里，机器需要判断这封邮件是否是垃圾邮件。疾病判断：病人到…
&p&上大学的时候，有一次打印课程设计，要打印两份，打出来一摞是“...”排序的，于是我就在店门口左一张右一张的开始分成两摞。然后打印店老板过来看了一眼，一脸鄙视的从我手里接过一摞打印稿，左边两张，右边两张的分了起来...&/p&&p&这样[1,12,23,34,45...]一次两张也能分成有序的两摞，这是在生活中第一次让我感觉到算法好厉害。&/p&&p&--------------------------------&/p&&p&这不是“怎么快速打印两份文档”的算法，这是“不小心设置错了怎么努力补救更快一点”的算法啊！&/p&&p&我作为一个程序员因为这种答案上了日报，会不会很影响职业道路...&/p&&blockquote&HR：“同学，你就是那个连打印机都不会用的小傻瓜么...”&/blockquote&
上大学的时候，有一次打印课程设计，要打印两份，打出来一摞是“...”排序的，于是我就在店门口左一张右一张的开始分成两摞。然后打印店老板过来看了一眼，一脸鄙视的从我手里接过一摞打印稿，左边两张，右边两张的分了起来...这样[1,12,23,34,45…
&p&搅花式咖啡能不能复原我不知道，但是搅点别的东西，如果你技术足够好的话，是可以复原的。&/p&&p&具体怎么做呢？&/p&&p&首先，你得有一个杯子，最好不是一般的杯子，而是中间有个柱子的杯子；而且，搅的也不能是像咖啡那样的液体，要得黏一点，比如像洗手液什么的：&/p&&figure&&img src=&https://pic3.zhimg.com/v2-daebf05ee73ba_b.png& class=&content_image&&&/figure&&p&然后，为了看得清楚，滴上三滴带颜色的洗手液：&/p&&figure&&img src=&https://pic2.zhimg.com/v2-738ee301e3ae95ff08f5_b.png& class=&content_image&&&/figure&&p&接着，顺时针慢慢转动里面的柱子5圈，注意动作要慢：&/p&&p&第一圈：&/p&&figure&&img src=&https://pic4.zhimg.com/v2-c17e5fe208e91aa38fc3_b.png& class=&content_image&&&/figure&&p&第五圈：&/p&&figure&&img src=&https://pic1.zhimg.com/v2-52e731b37cf35a3bed4de0_b.png& class=&content_image&&&/figure&&p&接下来，就是见证奇迹的时刻了！逆时针转动圆柱5圈：&/p&&figure&&img src=&https://pic2.zhimg.com/v2-c8906bcdd44fda32bc0daf5_b.png& class=&content_image&&&/figure&&p&bang！回来啦~~~~&/p&&figure&&img src=&https://pic3.zhimg.com/v2-a3c0c0eb241f4b120e83e_b.png& class=&content_image&&&/figure&&p&这个实验其实是展示了层流的可逆性。而层流一般是指雷诺数（Re=密度*流速*特征长度/粘性）非常小的流动。这也是为什么要使用比较黏的液体，而且要慢慢转的原因。&/p&&p&---------------------------------------------------------------------------------------&/p&&p&图片来源：UNM physics and Astronomy - Laminar Flow (&a href=&//link.zhihu.com/?target=https%3A//www.youtube.com/watch%3Fv%3Dp08_KlTKP50& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://www.&/span&&span class=&visible&&youtube.com/watch?&/span&&span class=&invisible&&v=p08_KlTKP50&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&)&/p&&p&---------------------------------------------------------------------------------------&/p&&p&没想到这个答案得到了如此多的关注，这让我非常惭愧啊，毕竟实验是别人做的，我只是搬运一下……而且鉴于评论区有很多童鞋表示不相信，认为只是视频倒放的效果。所以我决定自己来做一下这个实验，也算对这800多个赞的一个交代。&/p&&p&首先找一胖一瘦两个杯子：&/p&&figure&&img src=&https://pic2.zhimg.com/v2-3ea2caeefe72d_b.jpg& class=&content_image&&&/figure&&p&然后组装起来，并用架子固定住避免左右移动：&/p&&figure&&img src=&https://pic4.zhimg.com/v2-f1a01f09b355aafa5984dda5f1eb08e7_b.jpg& class=&content_image&&&/figure&&p&接着倒入透明粘稠液体，滴入同种液体调色后的液滴（手抖了滴得有点糊……）：&/p&&figure&&img src=&https://pic1.zhimg.com/v2-fa_b.jpg& class=&content_image&&&/figure&&p&转转转转……（液体太黏了有点转不太开）：&/p&&figure&&img src=&https://pic3.zhimg.com/v2-c469cae286a5d83ace53ee_b.jpg& class=&content_image&&&/figure&&p&然后往回转转转转转……：&/p&&figure&&img src=&https://pic3.zhimg.com/v2-2f9dbbea_b.jpg& class=&content_image&&&/figure&&p&呼……基本上恢复了吧~~~&/p&&p&可以看到红色靠近液面的地方散得比较开，是因为在转的时候中间的圆柱没有完全稳定，有点向右挤压造成液面右侧抬升，没有转均匀。&/p&&p&接下来是一点简单的分析，可以跳过不看：&/p&&p&实验中用的液体是5000cSt的硅油（silicone oil）&img src=&//www.zhihu.com/equation?tex=%5Cmu%2F%5Crho& alt=&\mu/\rho& eeimg=&1&&=m^2s^-1，转速U估计在1cm/s，特征长度L约为1cm，所以可以计算得雷诺数Re = &img src=&//www.zhihu.com/equation?tex=%5Crho+UL%2F%5Cmu& alt=&\rho UL/\mu& eeimg=&1&&=0.02远远小于1，属于层流。&/p&&p&至于扩散的问题，可以用Stoke-Einstein Law来估计扩散常数D~2.5*10^-14m^2/s。所以扩散的特征时间t=L^2/D ~ 4*10^9s（这个值貌似有点偏大…），所以在实验过程中基本上是没有什么明显的扩散的。 &/p&&p&总算是把视频传好了，建议&b&3倍加速&/b&观看。&/p&&a class=&video-box& href=&//link.zhihu.com/?target=http%3A//www.tudou.com/programs/view/umR4FYnPlOI/& target=&_blank& data-video-id=&& data-video-playable=&& data-name=&可逆层流实验& data-poster=&http://g3.tdimg.com//diy_p_2.jpg& data-lens-id=&&&
&img class=&thumbnail& src=&http://g3.tdimg.com//diy_p_2.jpg&&&span class=&content&&
&span class=&title&&可逆层流实验&span class=&z-ico-extern-gray&&&/span&&span class=&z-ico-extern-blue&&&/span&&/span&
&span class=&url&&&span class=&z-ico-video&&&/span&http://www.tudou.com/programs/view/umR4FYnPlOI/&/span&
&/a&&p&提前祝大家春节快乐！谢谢观看！&/p&
搅花式咖啡能不能复原我不知道，但是搅点别的东西，如果你技术足够好的话，是可以复原的。具体怎么做呢？首先，你得有一个杯子，最好不是一般的杯子，而是中间有个柱子的杯子；而且，搅的也不能是像咖啡那样的液体，要得黏一点，比如像洗手液什么的：然后，…
在Matrix67的blog 上看的一道题：&br&有一个黑匣子，黑匣子里有一个关于 x 的多项式 p(x) 。我们不知道它有多少项，但已知所有的系数都是正整数。每一次，你可以给黑匣子输入一个整数，黑匣子将返回把这个整数代入多项式后的值。那么，最少需要多少次， 我们可以得到这个多项式每项的系数呢？&br&答案是两次。&br&/*-------------------------------------答案分界线------------------------------*/&br&&br&&br&&br&&br&&br&&br&&br&&br&&br&&br&&br&&br&&br&&p&第一次，输入 1 ，于是便得到整个多项式的所有系数之和。记作 S 。&/p&&p&第二次，输入 S + 1 ，于是黑匣子返回的是 &/p&&p&&img src=&//www.zhihu.com/equation?tex=a_n+%2A+%28S+%2B+1%29%5En+%2B+a_%7Bn-1%7D+%2A+%28S+%2B+1%29%5E%7Bn-1%7D+%2B+...+%2B+a_1+%2A+%28S+%2B+1%29+%2B+a_0& alt=&a_n * (S + 1)^n + a_{n-1} * (S + 1)^{n-1} + ... + a_1 * (S + 1) + a_0& eeimg=&1&& 的值。&/p&&p&我们要得到 &img src=&//www.zhihu.com/equation?tex=%7Ba_n%2C...%2Ca_0%7D& alt=&{a_n,...,a_0}& eeimg=&1&&，只需要把这个值换成 S+1 进制， 然后依次读出每一位上的数。 &/p&&br&&p&P.S. 第一次得到S是为了保证对于任意系数&img src=&//www.zhihu.com/equation?tex=a_i%2C++a_i%3C%3DS& alt=&a_i,
a_i&=S& eeimg=&1&&&/p&&p&---------------------------------------------------------------------------------------&/p&&br&&p&其实最大系数不超过N的多项式，本来就是N进制的本质&/p&
在Matrix67的blog 上看的一道题： 有一个黑匣子，黑匣子里有一个关于 x 的多项式 p(x) 。我们不知道它有多少项，但已知所有的系数都是正整数。每一次，你可以给黑匣子输入一个整数，黑匣子将返回把这个整数代入多项式后的值。那么，最少需要多少次， 我们可…
————————————————2015最后更新————————————————&br&&br&---------------------------------新书新方法(兼容之前的答案)---------------------------------&br&&br&
这是我第4次更新这个答案了。我觉得是最终版本了。因为被我忽悠的师弟师妹都学了下去。看来这个办法真的有效果。&i&&b&再次强调，只是入门。&/b&&/i&&br&&br&&br&&b&1. &我想学好基础的数据结构和算法! &&/b&&br&不多说，有这心就往下看。&br&&br&&b&2. &我应该准备些什么? &&/b&&br&a. 这本橙书: 《算法 第四版》&br&
--亚马逊中文版:
&a href=&//link.zhihu.com/?target=http%3A//www.amazon.cn/%25E5%259B%25BE%25E7%%25E7%25A8%258B%25E5%25BA%258F%25E8%25AE%25BE%25E8%25AE%25A1%25E4%25B8%259B%25E4%25B9%25A6-%25E7%25AE%%25B3%%25A1%259E%25E5%25A5%%25A8%%B/dp/B009OCFQ0O/ref%3Dsr_1_1%3Fie%3DUTF8%26qid%3D%26sr%3D8-1%26keywords%3D%25E7%25AE%%25B3%E7%25AC%25AC%25E5%259B%259B%25E7%& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&amazon.cn 的页面&i class=&icon-external&&&/i&&/a&&br&
--线上资源: &a href=&//link.zhihu.com/?target=http%3A//algs4.cs.princeton.edu/home/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne&i class=&icon-external&&&/i&&/a&&br&b. 注册Coursera, 依次加入这2门课:
&算法, 第一部分& &算法, 第二部分&&br&&i&Part 1: &/i&&a href=&//link.zhihu.com/?target=https%3A//www.coursera.org/course/algs4partI& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://www.&/span&&span class=&visible&&coursera.org/course/alg&/span&&span class=&invisible&&s4partI&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&&i&Part 2: &/i&&a href=&//link.zhihu.com/?target=https%3A//class.coursera.org/algs4partII-006& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://&/span&&span class=&visible&&class.coursera.org/algs&/span&&span class=&invisible&&4partII-006&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&如果没开课, 就先标记, 这样开课时会通过邮箱提示你.&br&&br&&b&3. &我应该做些什么? &&/b&&br&先熟读书内1.1和1.2, 最好把课后习题都做一做. 网站上开课后(即使已经开课几周了, 没关系),
跟住上课内容: 课本知识 + 视频内容 + 课件重点+ Exercises (&i&&b&独立完成且满分&/b&&/i&) + Programming Assignments (&b&&i&独立完成且尽量满分&/i&&/b&) + Job Interview Questions. &b&&u&从Part 1到Part 2, 跟住, 跟住, 跟住!&/u&&/b&&br&&br&&br&&u&&i&关于做书后练习题，参见：&/i&&br&&/u&&a href=&https://www.zhihu.com/question//answer/& class=&internal&&算法 第四版(algorithms 4th edition ) 这本书有配套的习题答案吗？ - 孟祥丰的回答&/a&&br&&br&&b&4. &我学完了呢!&&/b&&br&再去跟隔壁斯坦福的算法公开课, 他还给证书! 因为参考书籍基本上就是是《CLRS》, 所以也就是强迫自己去仔细研读算法导论. &br& ---课程名称: &br&
&算法设计与分析, 第一部分&&br&
&算法设计与分析, 第二部分&&br& ---课程地址&br&&i&
Part 1: &/i&&a href=&//link.zhihu.com/?target=https%3A//www.coursera.org/course/algo& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://www.&/span&&span class=&visible&&coursera.org/course/alg&/span&&span class=&invisible&&o&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&&i&
Part 2: &/i&&a href=&//link.zhihu.com/?target=https%3A//www.coursera.org/course/algo2& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://www.&/span&&span class=&visible&&coursera.org/course/alg&/span&&span class=&invisible&&o2&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&&br&&b&5. &又学完啦! &&/b&&br&可能今后在这个方面不需要看网络上不知名人士(没错, 就是我)的建议了. 拜拜.&br&&br&&b&&i&&u&PS: 就这些?? 对, 就这些. &/u&&/i&&/b&&br&&br&&br&&br&&br&——————————————— 补充———————————————&br&Coursera上6月19号开普林斯顿讲的算法课程了:&br&&a href=&//link.zhihu.com/?target=https%3A//www.coursera.org/courses%3Fcategories%3Dcs-theory& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Coursera - Free Online Courses From Top Universities&i class=&icon-external&&&/i&&/a&&br&教材就是橙宝书:&br&&a href=&//link.zhihu.com/?target=http%3A//algs4.cs.princeton.edu/home/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne&i class=&icon-external&&&/i&&/a&&br&&br&课程负担并不大。刚入门的同学可以跟一跟。当然学习算法还是要多做题。^_^&br&&br&—————————————————原答案—————————————————&br&&b&我要好好回答一下这个问题。&/b&&br&&br&从刚上大学在课堂上听老师讲解，到后来自学，反复学等种种失败经历给了我当头棒喝。我这样的小渣渣还真是难以捧本书看一看就能学懂。还真得特殊准备一套方法来学习它。借助知乎，网上大神，ACMer的经验分享，我自己总结了一个入门的学习方法，让我快乐且热情的坚持下来了对数据结构与算法的学习。（&u&仅针对初学者的入门级学习，大神们请绕过，拜拜么么哒&/u&）&br&&br&好，剩下来像我一样的阿渣们，让我们先来痛快的分（tu）析（cao）下为啥这东西难学：&br&1. 抽象，数学知识多，大多数书籍有很多数学证明，很枯燥，爱掉头发。&br&2. 反馈差。比如学完了“快速排序”也就学完了，没什么事做，也没觉得自己厉害多少。但是要是学习下cocos2d-x，过几天自己都能写小游戏了。学了难以分分钟高能还真就难以坚持了。没错，学习这事我就是这么投机这么功利。&br&3. 孤立的知识点都很难有什么作为，只有理解＋融汇＋贯通才能显威力。&br&4. 没有好“老师”。搜索下“如何学习雅思&托福”，各种高能大法学习小组培训机构怒刷一脸屏。&br&&br&&b&好了，吐槽完毕，以下是干货：&/b&&br&&b&&br&1.先来本入门级的好书&/b&&br&&figure&&img src=&https://pic1.zhimg.com/cefe0d6caa_b.jpg& data-rawwidth=&334& data-rawheight=&468& class=&content_image& width=&334&&&/figure&我把里面的代码全打了一遍，整不懂就一点点在草纸上演示，还整不懂的就死记硬背了下来，说不定哪天就想通了。学起来很慢，但是效果不错。谁让我笨呢。（现在没事抽风还要默写一下AVL树的c实现，也是病没好）&br&&br&&b&2. 可视化&/b&&br&刚开始我就按照1这么学，学一周就学不动了，太高估自己的能力，又冒充不下去学霸了。这知识尼玛这么抽象。之后发现了一个可视化工具（很多大神都推荐过啦）&div class=&highlight&&&pre&&code class=&language-text&&http://visualgo.net
&/code&&/pre&&/div& 什么冒泡插入快速排序一演示，小动画一播放分分钟我就都整明白了，一低头那些小代码也就都被我看穿看穿了。来一把倚天剑屠龙刀我也能混个山大王。&br&&figure&&img src=&https://pic3.zhimg.com/71b69c54bff755bb0e8aa93ce5da5f3e_b.jpg& data-rawwidth=&964& data-rawheight=&478& class=&origin_image zh-lightbox-thumb& width=&964& data-original=&https://pic3.zhimg.com/71b69c54bff755bb0e8aa93ce5da5f3e_r.jpg&&&/figure&（图是二叉堆的演示）&br&一可视化之后你会发现很多抽象的数据结构在脑海中有了样子。我也说不太明白那种感觉，就好像你在一个姑娘/小伙子身上看到了爱情的样子。&br&&br&&b&3.编程实践&/b&&br&其实学习算法可以分3个部分，&b&算法设计，算法分析，算法实践&/b&。我个人觉得更需要静下心花大块时间琢磨的是前两方面，但是算法实践更容易让大家产生“我确实进步了”的正反馈。如果你参考的是我的旧答案，也就是起手看的是《数据结构与算法分析 in C》。那么我建议用这两本书《C语言程序设计》和《C和指针》再去复习下C语言，之后去LeetCode上找相关题用C/C++去做。或者转头去看《算法第四版》，然后去独立完成上文提到的公开课的编程作业和书后习题。（受限于当时所学，这部分于16年删掉重写）&br&&br&好了，总结起来就是&b&对于每一个知识点&/b&，我们用&b&&u&学理论&/u&&/b&＋&b&&u&可视化&/u&&/b&＋&b&&u&编程实践&/u&&/b&相结合的方式&b&&u&一个知识点一步地踏实前进&/u&。&/b&&b&但是到这里我们真的就只是入门。&/b&所以我在这之后就愉快的重新认真地撸《算法导论》去了。可以参见我另外一个回答：&a href=&http://www.zhihu.com/question//answer/& class=&internal&&你是如何坚持读完《算法导论》这本书的？ - 孟祥丰的回答&/a&。撸完如果觉得不够可以继续撸其它一些算法书籍，详情参见大神文章：&a href=&//link.zhihu.com/?target=http%3A//www.cnblogs.com/figure9/archive//3708351.html& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&我的算法学习之路&i class=&icon-external&&&/i&&/a&&br&&br&虽然我还是觉得自己很渣很菜，但想想没有昨天那么渣了，就会很开心。
————————————————2015最后更新———————————————— ---------------------------------新书新方法(兼容之前的答案)--------------------------------- 这是我第4次更新这个答案了。我觉得是最终版本了。因为被我忽悠的师弟师…
×××××11月22日已更新×××××&br&&br&隐马尔可夫（HMM）好讲，简单易懂不好讲。我认为 &a data-hash=&cd5aebd240bfd& href=&//www.zhihu.com/people/cd5aebd240bfd& class=&member_mention& data-editable=&true& data-title=&@者也& data-tip=&p$b$cd5aebd240bfd& data-hovercard=&p$b$cd5aebd240bfd&&@者也&/a&的回答没什么错误，不过我想说个更通俗易懂的例子。我希望我的读者不是专家，而是对这个问题感兴趣的入门者，所以我会多阐述数学思想，少写公式。霍金曾经说过，你多写一个公式，就会少一半的读者。所以时间简史这本关于物理的书和麦当娜关于性的书卖的一样好。我会效仿这一做法，写最通俗易懂的答案。&br&&br&还是用最经典的例子，掷骰子。假设我手里有三个不同的骰子。第一个骰子是我们平常见的骰子（称这个骰子为D6），6个面，每个面（1，2，3，4，5，6）出现的概率是1/6。第二个骰子是个四面体（称这个骰子为D4），每个面（1，2，3，4）出现的概率是1/4。第三个骰子有八个面（称这个骰子为D8），每个面（1，2，3，4，5，6，7，8）出现的概率是1/8。&br&&br&&figure&&img src=&https://pic4.zhimg.com/435fb8d2d675dc0be95aedf27feb6b67_b.jpg& data-rawwidth=&1351& data-rawheight=&825& class=&origin_image zh-lightbox-thumb& width=&1351& data-original=&https://pic4.zhimg.com/435fb8d2d675dc0be95aedf27feb6b67_r.jpg&&&/figure&&br&假设我们开始掷骰子，我们先从三个骰子里挑一个，挑到每一个骰子的概率都是1/3。然后我们掷骰子，得到一个数字，1，2，3，4，5，6，7，8中的一个。不停的重复上述过程，我们会得到一串数字，每个数字都是1，2，3，4，5，6，7，8中的一个。例如我们可能得到这么一串数字（掷骰子10次）：1 6 3 5 2 7 3 5 2 4&br&&br&这串数字叫做可见状态链。但是在隐马尔可夫模型中，我们不仅仅有这么一串可见状态链，还有一串隐含状态链。在这个例子里，这串隐含状态链就是你用的骰子的序列。比如，隐含状态链有可能是：D6 D8 D8 D6 D4 D8 D6 D6 D4 D8&br&&br&一般来说，HMM中说到的马尔可夫链其实是指隐含状态链，因为隐含状态（骰子）之间存在转换概率（transition probability）。在我们这个例子里，D6的下一个状态是D4，D6，D8的概率都是1/3。D4，D8的下一个状态是D4，D6，D8的转换概率也都一样是1/3。这样设定是为了最开始容易说清楚，但是我们其实是可以随意设定转换概率的。比如，我们可以这样定义，D6后面不能接D4，D6后面是D6的概率是0.9，是D8的概率是0.1。这样就是一个新的HMM。&br&&br&同样的，尽管可见状态之间没有转换概率，但是隐含状态和可见状态之间有一个概率叫做输出概率（emission probability）。就我们的例子来说，六面骰（D6）产生1的输出概率是1/6。产生2，3，4，5，6的概率也都是1/6。我们同样可以对输出概率进行其他定义。比如，我有一个被赌场动过手脚的六面骰子，掷出来是1的概率更大，是1/2，掷出来是2，3，4，5，6的概率是1/10。&br&&br&&figure&&img src=&https://pic1.zhimg.com/95ba126e02e370c595000_b.jpg& data-rawwidth=&1508& data-rawheight=&781& class=&origin_image zh-lightbox-thumb& width=&1508& data-original=&https://pic1.zhimg.com/95ba126e02e370c595000_r.jpg&&&/figure&&br&&figure&&img src=&https://pic2.zhimg.com/ae8a9d756089_b.jpg& data-rawwidth=&1384& data-rawheight=&731& class=&origin_image zh-lightbox-thumb& width=&1384& data-original=&https://pic2.zhimg.com/ae8a9d756089_r.jpg&&&/figure&&br&其实对于HMM来说，如果提前知道所有隐含状态之间的转换概率和所有隐含状态到所有可见状态之间的输出概率，做模拟是相当容易的。但是应用HMM模型时候呢，往往是缺失了一部分信息的，有时候你知道骰子有几种，每种骰子是什么，但是不知道掷出来的骰子序列；有时候你只是看到了很多次掷骰子的结果，剩下的什么都不知道。如果应用算法去估计这些缺失的信息，就成了一个很重要的问题。这些算法我会在下面详细讲。&br&&br&×××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××&br&如果你只想看一个简单易懂的例子，就不需要往下看了。&br&×××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××&br&说两句废话，答主认为呢，要了解一个算法，要做到以下两点：会其意，知其形。答主回答的，其实主要是第一点。但是这一点呢，恰恰是最重要，而且很多书上不会讲的。正如你在追一个姑娘，姑娘对你说“你什么都没做错！”你要是只看姑娘的表达形式呢，认为自己什么都没做错，显然就理解错了。你要理会姑娘的意思，“你赶紧给我道歉！”这样当你看到对应的表达形式呢，赶紧认错，跪地求饶就对了。数学也是一样，你要是不理解意思，光看公式，往往一头雾水。不过呢，数学的表达顶多也就是晦涩了点，姑娘的表达呢，有的时候就完全和本意相反。所以答主一直认为理解姑娘比理解数学难多了。&br&&br&回到正题，和HMM模型相关的算法主要分为三类，分别解决三种问题：&br&&br&&b&1）知道骰子有几种（隐含状态数量），每种骰子是什么（转换概率），根据掷骰子掷出的结果（可见状态链），我想知道每次掷出来的都是哪种骰子（隐含状态链）。&/b&&br&这个问题呢，在语音识别领域呢，叫做解码问题。这个问题其实有两种解法，会给出两个不同的答案。每个答案都对，只不过这些答案的意义不一样。第一种解法求最大似然状态路径，说通俗点呢，就是我求一串骰子序列，这串骰子序列产生观测结果的概率最大。第二种解法呢，就不是求一组骰子序列了，而是求每次掷出的骰子分别是某种骰子的概率。比如说我看到结果后，我可以求得第一次掷骰子是D4的概率是0.5，D6的概率是0.3，D8的概率是0.2.第一种解法我会在下面说到，但是第二种解法我就不写在这里了，如果大家有兴趣，我们另开一个问题继续写吧。&br&&br&&b&2）还是知道骰子有几种&/b&&b&（隐含状态数量）&/b&&b&，每种骰子是什么&/b&&b&（转换概率）&/b&&b&，根据掷骰子掷出的结果&/b&&b&（可见状态链）&/b&&b&，我想知道掷出这个结果的概率。&/b&&br&看似这个问题意义不大，因为你掷出来的结果很多时候都对应了一个比较大的概率。问这个问题的目的呢，其实是检测观察到的结果和已知的模型是否吻合。如果很多次结果都对应了比较小的概率，那么就说明我们已知的模型很有可能是错的，有人偷偷把我们的骰子給换了。&br&&br&&b&3）知道骰子有几种&/b&&b&（隐含状态数量）&/b&&b&，不知道每种骰子是什么&/b&&b&（转换概率）&/b&&b&，观测到很多次掷骰子的结果&/b&&b&（可见状态链）&/b&&b&，我想反推出每种骰子是什么&/b&&b&（转换概率）&/b&&b&。&/b&&br&这个问题很重要，因为这是最常见的情况。很多时候我们只有可见结果，不知道HMM模型里的参数，我们需要从可见结果估计出这些参数，这是建模的一个必要步骤。&br&&br&问题阐述完了，下面就开始说解法。（0号问题在上面没有提，只是作为解决上述问题的一个辅助）&br&&br&0.一个简单问题&br&其实这个问题实用价值不高。由于对下面较难的问题有帮助，所以先在这里提一下。&br&&br&知道骰子有几种，每种骰子是什么，每次掷的都是什么骰子，根据掷骰子掷出的结果，求产生这个结果的概率。&br&&figure&&img src=&https://pic1.zhimg.com/2ca5e20b49d2ad91a9e0_b.jpg& data-rawwidth=&364& data-rawheight=&237& class=&content_image& width=&364&&&/figure&解法无非就是概率相乘：&br&&img src=&//www.zhihu.com/equation?tex=P%3DP%28D6%29%2AP%28D6%5Crightarrow+1%29%2AP%28D6%5Crightarrow+D8%29%2AP%28D8%5Crightarrow+6%29%2AP%28D8%5Crightarrow+D8%29%2AP%28D8%5Crightarrow+3%29& alt=&P=P(D6)*P(D6\rightarrow 1)*P(D6\rightarrow D8)*P(D8\rightarrow 6)*P(D8\rightarrow D8)*P(D8\rightarrow 3)& eeimg=&1&&&br&&img src=&//www.zhihu.com/equation?tex=%3D%5Cfrac%7B1%7D%7B3%7D+%2A%5Cfrac%7B1%7D%7B6%7D+%2A%5Cfrac%7B1%7D%7B3%7D+%2A%5Cfrac%7B1%7D%7B8%7D+%2A%5Cfrac%7B1%7D%7B3%7D+%2A%5Cfrac%7B1%7D%7B8%7D+& alt=&=\frac{1}{3} *\frac{1}{6} *\frac{1}{3} *\frac{1}{8} *\frac{1}{3} *\frac{1}{8} & eeimg=&1&&&br&&br&&b&1.看见不可见的，破解骰子序列&/b&&br&这里我说的是第一种解法，解最大似然路径问题。&br&举例来说，我知道我有三个骰子，六面骰，四面骰，八面骰。我也知道我掷了十次的结果（1 6 3 5 2 7 3 5 2 4），我不知道每次用了那种骰子，我想知道最有可能的骰子序列。&br&&br&其实最简单而暴力的方法就是穷举所有可能的骰子序列，然后依照第零个问题的解法把每个序列对应的概率算出来。然后我们从里面把对应最大概率的序列挑出来就行了。如果马尔可夫链不长，当然可行。如果长的话，穷举的数量太大，就很难完成了。&br&&br&另外一种很有名的算法叫做Viterbi algorithm. 要理解这个算法，我们先看几个简单的列子。&br&&br&首先，如果我们只掷一次骰子：&br&&figure&&img src=&https://pic4.zhimg.com/cd4edec33cd3921ac64bfeb_b.jpg& data-rawwidth=&1477& data-rawheight=&275& class=&origin_image zh-lightbox-thumb& width=&1477& data-original=&https://pic4.zhimg.com/cd4edec33cd3921ac64bfeb_r.jpg&&&/figure&&br&看到结果为1.对应的最大概率骰子序列就是D4，因为D4产生1的概率是1/4，高于1/6和1/8.&br&&br&把这个情况拓展，我们掷两次骰子：&br&&figure&&img src=&https://pic1.zhimg.com/549e1f2a8dae1abcde44_b.jpg& data-rawwidth=&1477& data-rawheight=&275& class=&origin_image zh-lightbox-thumb& width=&1477& data-original=&https://pic1.zhimg.com/549e1f2a8dae1abcde44_r.jpg&&&/figure&&br&结果为1，6.这时问题变得复杂起来，我们要计算三个值，分别是第二个骰子是D6，D4，D8的最大概率。显然，要取到最大概率，第一个骰子必须为D4。这时，第二个骰子取到D6的最大概率是&br&&img src=&//www.zhihu.com/equation?tex=P2%28D6%29%3DP%28D4%29%2AP%28D4%5Crightarrow+1%29%2AP%28D4%5Crightarrow+D6%29%2AP%28D6%5Crightarrow+6%29& alt=&P2(D6)=P(D4)*P(D4\rightarrow 1)*P(D4\rightarrow D6)*P(D6\rightarrow 6)& eeimg=&1&&&br&&img src=&//www.zhihu.com/equation?tex=%3D%5Cfrac%7B1%7D%7B3%7D+%2A%5Cfrac%7B1%7D%7B4%7D+%2A%5Cfrac%7B1%7D%7B3%7D+%2A%5Cfrac%7B1%7D%7B6%7D& alt=&=\frac{1}{3} *\frac{1}{4} *\frac{1}{3} *\frac{1}{6}& eeimg=&1&&&br&同样的，我们可以计算第二个骰子是D4或D8时的最大概率。我们发现，第二个骰子取到D6的概率最大。而使这个概率最大时，第一个骰子为D4。所以最大概率骰子序列就是D4 D6。&br&&br&继续拓展，我们掷三次骰子：&br&&figure&&img src=&https://pic4.zhimg.com/ebb5f0bbca544063_b.jpg& data-rawwidth=&1477& data-rawheight=&275& class=&origin_image zh-lightbox-thumb& width=&1477& data-original=&https://pic4.zhimg.com/ebb5f0bbca544063_r.jpg&&&/figure&&br&同样，我们计算第三个骰子分别是D6，D4，D8的最大概率。我们再次发现，要取到最大概率，第二个骰子必须为D6。这时，第三个骰子取到D4的最大概率是&img src=&//www.zhihu.com/equation?tex=P3%28D4%29%3DP2%28D6%29%2AP%28D6%5Crightarrow+D4%29%2AP%28D4%5Crightarrow+3%29& alt=&P3(D4)=P2(D6)*P(D6\rightarrow D4)*P(D4\rightarrow 3)& eeimg=&1&&&br&&img src=&//www.zhihu.com/equation?tex=%3D%5Cfrac%7B1%7D%7B216%7D+%2A%5Cfrac%7B1%7D%7B3%7D+%2A%5Cfrac%7B1%7D%7B4%7D& alt=&=\frac{1}{216} *\frac{1}{3} *\frac{1}{4}& eeimg=&1&&&br&同上，我们可以计算第三个骰子是D6或D8时的最大概率。我们发现，第三个骰子取到D4的概率最大。而使这个概率最大时，第二个骰子为D6，第一个骰子为D4。所以最大概率骰子序列就是D4 D6 D4。&br&&br&写到这里，大家应该看出点规律了。既然掷骰子一二三次可以算，掷多少次都可以以此类推。我们发现，我们要求最大概率骰子序列时要做这么几件事情。首先，不管序列多长，要从序列长度为1算起，算序列长度为1时取到每个骰子的最大概率。然后，逐渐增加长度，每增加一次长度，重新算一遍在这个长度下最后一个位置取到每个骰子的最大概率。因为上一个长度下的取到每个骰子的最大概率都算过了，重新计算的话其实不难。当我们算到最后一位时，就知道最后一位是哪个骰子的概率最大了。然后，我们要把对应这个最大概率的序列从后往前推出来。&br&&br&&b&2.谁动了我的骰子？&/b&&br&比如说你怀疑自己的六面骰被赌场动过手脚了，有可能被换成另一种六面骰，这种六面骰掷出来是1的概率更大，是1/2，掷出来是2，3，4，5，6的概率是1/10。你怎么办么？答案很简单，算一算正常的三个骰子掷出一段序列的概率，再算一算不正常的六面骰和另外两个正常骰子掷出这段序列的概率。如果前者比后者小，你就要小心了。&br&&br&比如说掷骰子的结果是：&br&&figure&&img src=&https://pic4.zhimg.com/ebb5f0bbca544063_b.jpg& data-rawwidth=&1477& data-rawheight=&275& class=&origin_image zh-lightbox-thumb& width=&1477& data-original=&https://pic4.zhimg.com/ebb5f0bbca544063_r.jpg&&&/figure&&br&要算用正常的三个骰子掷出这个结果的概率，其实就是将所有可能情况的概率进行加和计算。同样，简单而暴力的方法就是把穷举所有的骰子序列，还是计算每个骰子序列对应的概率，但是这回，我们不挑最大值了，而是把所有算出来的概率相加，得到的总概率就是我们要求的结果。这个方法依然不能应用于太长的骰子序列（马尔可夫链）。&br&&br&我们会应用一个和前一个问题类似的解法，只不过前一个问题关心的是概率最大值，这个问题关心的是概率之和。解决这个问题的算法叫做前向算法（forward algorithm）。&br&&br&首先，如果我们只掷一次骰子：&br&&figure&&img src=&https://pic4.zhimg.com/cd4edec33cd3921ac64bfeb_b.jpg& data-rawwidth=&1477& data-rawheight=&275& class=&origin_image zh-lightbox-thumb& width=&1477& data-original=&https://pic4.zhimg.com/cd4edec33cd3921ac64bfeb_r.jpg&&&/figure&&br&看到结果为1.产生这个结果的总概率可以按照如下计算，总概率为0.18：&br&&figure&&img src=&https://pic1.zhimg.com/9b76649fefc_b.jpg& data-rawwidth=&1496& data-rawheight=&440& class=&origin_image zh-lightbox-thumb& width=&1496& data-original=&https://pic1.zhimg.com/9b76649fefc_r.jpg&&&/figure&&br&把这个情况拓展，我们掷两次骰子：&br&&figure&&img src=&https://pic1.zhimg.com/549e1f2a8dae1abcde44_b.jpg& data-rawwidth=&1477& data-rawheight=&275& class=&origin_image zh-lightbox-thumb& width=&1477& data-original=&https://pic1.zhimg.com/549e1f2a8dae1abcde44_r.jpg&&&/figure&&br&看到结果为1，6.产生这个结果的总概率可以按照如下计算，总概率为0.05：&br&&figure&&img src=&https://pic2.zhimg.com/a6e932a53753acdf67085_b.jpg& data-rawwidth=&1496& data-rawheight=&440& class=&origin_image zh-lightbox-thumb& width=&1496& data-original=&https://pic2.zhimg.com/a6e932a53753acdf67085_r.jpg&&&/figure&&br&&br&继续拓展，我们掷三次骰子：&br&&figure&&img src=&https://pic4.zhimg.com/ebb5f0bbca544063_b.jpg& data-rawwidth=&1477& data-rawheight=&275& class=&origin_image zh-lightbox-thumb& width=&1477& data-original=&https://pic4.zhimg.com/ebb5f0bbca544063_r.jpg&&&/figure&&br&看到结果为1，6，3.产生这个结果的总概率可以按照如下计算，总概率为0.03：&br&&figure&&img src=&https://pic3.zhimg.com/ea53d42a8a_b.jpg& data-rawwidth=&1496& data-rawheight=&440& class=&origin_image zh-lightbox-thumb& width=&1496& data-original=&https://pic3.zhimg.com/ea53d42a8a_r.jpg&&&/figure&&br&&br&同样的，我们一步一步的算，有多长算多长，再长的马尔可夫链总能算出来的。用同样的方法，也可以算出不正常的六面骰和另外两个正常骰子掷出这段序列的概率，然后我们比较一下这两个概率大小，就能知道你的骰子是不是被人换了。&br&&br&&b&3.掷一串骰子出来，让我猜猜你是谁&/b&&br&&b&（答主很懒，还没写，会写一下EM这个号称算法的方法）&br&&/b&&br&上述算法呢，其实用到了递归，逆向推导，循环这些方法，我只不过用很直白的语言写出来了。如果你们去看专业书籍呢，会发现更加严谨和专业的描述。毕竟，我只做了会其意，要知其形，还是要看书的。
×××××11月22日已更新××××× 隐马尔可夫（HMM）好讲，简单易懂不好讲。我认为 的回答没什么错误，不过我想说个更通俗易懂的例子。我希望我的读者不是专家，而是对这个问题感兴趣的入门者，所以我会多阐述数学思想，少写公式。霍金曾经说过，你…
&p&这里我想给大家介绍另外一种推荐系统，这种算法叫做潜在因子（Latent
Factor）算法。这种算法是在NetFlix（没错，就是用大数据捧火《纸牌屋》的那家公司）的推荐算法竞赛中获奖的算法，最早被应用于电影推荐中。这种算法在实际应用中比现在排名第一的 &a data-hash=&ac7121dce72e2424edbd552& href=&//www.zhihu.com/people/ac7121dce72e2424edbd552& class=&member_mention& data-editable=&true& data-title=&@邰原朗& data-tip=&p$b$ac7121dce72e2424edbd552& data-hovercard=&p$b$ac7121dce72e2424edbd552&&@邰原朗&/a& 所介绍的算法误差（RMSE）会小不少，效率更高。我下面仅利用基础的矩阵知识来介绍下这种算法。&/p&&p&这种算法的思想是这样：每个用户（&b&user&/b&）都有自己的偏好，比如A喜欢带有&b&小清新的&/b&、&b&吉他伴奏的&/b&、&b&王菲&/b&等元素（&b&latent factor&/b&），如果一首歌（&b&item&/b&）带有这些元素，那么就将这首歌推荐给该用户，也就是用元素去连接用户和音乐。每个人对不同的元素偏好不同，而每首歌包含的元素也不一样。我们希望能找到这样两个矩阵：&/p&&p&一，&b&用户-潜在因子矩阵Q&/b&，表示不同的用户对于不用元素的偏好程度，1代表很喜欢，0代表不喜欢。比如下面这样：&/p&&figure&&img src=&https://pic3.zhimg.com/6be14fdab88e_b.jpg& data-rawwidth=&543& data-rawheight=&194& class=&origin_image zh-lightbox-thumb& width=&543& data-original=&https://pic3.zhimg.com/6be14fdab88e_r.jpg&&&/figure&&p&二，&b&潜在因子-音乐矩阵P&/b&，表示每种音乐含有各种元素的成分，比如下表中，音乐A是一个偏小清新的音乐，含有小清新这个Latent Factor的成分是0.9，重口味的成分是0.1，优雅的成分是0.2……&/p&&figure&&img src=&https://pic3.zhimg.com/b37d2aea4a35d3f45e8f25fd121c4e52_b.jpg& data-rawwidth=&543& data-rawheight=&231& class=&origin_image zh-lightbox-thumb& width=&543& data-original=&https://pic3.zhimg.com/b37d2aea4a35d3f45e8f25fd121c4e52_r.jpg&&&/figure&&p&利用这两个矩阵，我们能得出张三对音乐A的喜欢程度是：张三对&b&小清新&/b&的偏好*音乐A含有&b&小清新&/b&的成分+对&b&重口味&/b&的偏好*音乐A含有&b&重口味&/b&的成分+对&b&优雅&/b&的偏好*音乐A含有&b&优雅&/b&的成分+……&/p&&figure&&img src=&https://pic1.zhimg.com/7a37d920fff8d307c9e8_b.jpg& data-rawwidth=&543& data-rawheight=&116& class=&origin_image zh-lightbox-thumb& width=&543& data-original=&https://pic1.zhimg.com/7a37d920fff8d307c9e8_r.jpg&&&/figure&&figure&&img src=&https://pic4.zhimg.com/5cddc0bb594de2b8bd3e47_b.jpg& data-rawwidth=&543& data-rawheight=&116& class=&origin_image zh-lightbox-thumb& width=&543& data-original=&https://pic4.zhimg.com/5cddc0bb594de2b8bd3e47_r.jpg&&&/figure&&p&即：0.6*0.9+0.8*0.1+0.1*0.2+0.1*0.4+0.7*0=0.69&/p&&p&每个用户对每首歌都这样计算可以得到不同用户对不同歌曲的评分矩阵&img src=&//www.zhihu.com/equation?tex=%5Ctilde%7BR%7D+& alt=&\tilde{R} & eeimg=&1&&。（注，这里的破浪线表示的是估计的评分，接下来我们还会用到不带波浪线的R表示实际的评分）：&/p&&figure&&img src=&https://pic3.zhimg.com/a16ed64edfb9bc4e_b.jpg& data-rawwidth=&459& data-rawheight=&194& class=&origin_image zh-lightbox-thumb& width=&459& data-original=&https://pic3.zhimg.com/a16ed64edfb9bc4e_r.jpg&&&/figure&&p&因此我们队张三推荐四首歌中得分最高的B，对李四推荐得分最高的C，王五推荐B。&/p&&p&如果用矩阵表示即为：&/p&&img src=&//www.zhihu.com/equation?tex=%5Ctilde%7BR%7D+%3DQP%5E%7BT%7D+& alt=&\tilde{R} =QP^{T} & eeimg=&1&&&br&&br&&p&下面问题来了，&b&这个潜在因子（latent factor）&/b&&b&是怎么得到的呢？&/b&&/p&由于面对海量的让用户自己给音乐分类并告诉我们自己的偏好系数显然是不现实的，事实上我们能获得的数据只有用户行为数据。我们沿用 &a data-hash=&ac7121dce72e2424edbd552& href=&//www.zhihu.com/people/ac7121dce72e2424edbd552& class=&member_mention& data-editable=&true& data-title=&@邰原朗& data-tip=&p$b$ac7121dce72e2424edbd552& data-hovercard=&p$b$ac7121dce72e2424edbd552&&@邰原朗&/a&的量化标准：单曲循环=5, 分享=4, 收藏=3, 主动播放=2 , 听完=1, 跳过=-2 , 拉黑=-5，在分析时能获得的实际评分矩阵&b&R&/b&，也就是输入矩阵大概是这个样子：&br&&figure&&img src=&https://pic2.zhimg.com/1a783eefd2beaa432faf2e2_b.jpg& data-rawwidth=&1079& data-rawheight=&298& class=&origin_image zh-lightbox-thumb& width=&1079& data-original=&https://pic2.zhimg.com/1a783eefd2beaa432faf2e2_r.jpg&&&/figure&事实上这是个非常非常稀疏的矩阵，因为大部分用户只听过全部音乐中很少一部分。如何利用这个矩阵去找潜在因子呢？这里主要应用到的是矩阵的UV分解。也就是将上面的评分矩阵分解为两个低维度的矩阵，用Q和P两个矩阵的乘积去估计实际的评分矩阵，而且我们希望估计的评分矩阵&img src=&//www.zhihu.com/equation?tex=%5Ctilde%7BR%7D+& alt=&\tilde{R} & eeimg=&1&&&br&&figure&&img src=&https://pic1.zhimg.com/59b28d6c857ececb8a08a6c_b.jpg& data-rawwidth=&1082& data-rawheight=&259& class=&origin_image zh-lightbox-thumb& width=&1082& data-original=&https://pic1.zhimg.com/59b28d6c857ececb8a08a6c_r.jpg&&&/figure&&br&和实际的评分矩阵不要相差太多，也就是求解下面的目标函数：&br&&img src=&//www.zhihu.com/equation?tex=min_%7BP%2CQ%7D+%5CSigma+%28r_%7Bui%7D-q_%7Bi%7Dp_%7Bu%7D%5E%7BT%7D%29%5E2& alt=&min_{P,Q} \Sigma (r_{ui}-q_{i}p_{u}^{T})^2& eeimg=&1&&&br&这里涉及到最优化理论，在实际应用中，往往还要在后面加上2范数的罚项，然后利用梯度下降法就可以求得这&b&P,Q&/b&两个矩阵的估计值。这里我们就不展开说了。例如我们上面给出的那个例子可以分解成为这样两个矩阵：&br&&figure&&img src=&https://pic2.zhimg.com/56d1d16d5abe403cb9371_b.jpg& data-rawwidth=&1483& data-rawheight=&298& class=&origin_image zh-lightbox-thumb& width=&1483& data-original=&https://pic2.zhimg.com/56d1d16d5abe403cb9371_r.jpg&&&/figure&这两个矩阵相乘就可以得到估计的得分矩阵：&br&&figure&&img src=&https://pic2.zhimg.com/c3e70bdd45d67b49d81e4bd_b.jpg& data-rawwidth=&1177& data-rawheight=&298& class=&origin_image zh-lightbox-thumb& width=&1177& data-original=&https://pic2.zhimg.com/c3e70bdd45d67b49d81e4bd_r.jpg&&&/figure&将用户已经听过的音乐剔除后，选择分数最高音乐的推荐给用户即可（红体字）。&br&&br&在这个例子里面用户7和用户8有强的相似性：&br&&figure&&img src=&https://pic2.zhimg.com/78188eafd238feba2063d_b.jpg& data-rawwidth=&1079& data-rawheight=&67& class=&origin_image zh-lightbox-thumb& width=&1079& data-original=&https://pic2.zhimg.com/78188eafd238feba2063d_r.jpg&&&/figure&从推荐的结果来看，正好推荐的是对方评分较高的音乐：&br&&figure&&img src=&https://pic1.zhimg.com/ae603dd2cb19d4f01f42fc_b.jpg& data-rawwidth=&1079& data-rawheight=&67& class=&origin_image zh-lightbox-thumb& width=&1079& data-original=&https://pic1.zhimg.com/ae603dd2cb19d4f01f42fc_r.jpg&&&/figure&
这里我想给大家介绍另外一种推荐系统，这种算法叫做潜在因子（Latent
Factor）算法。这种算法是在NetFlix（没错，就是用大数据捧火《纸牌屋》的那家公司）的推荐算法竞赛中获奖的算法，最早被应用于电影推荐中。这种算法在实际应用中比现在排名第一的 …
&p&答案是&b&&a href=&tel:751&/a&天&/b& ，差不多是70年。&/p&&br&&p&&b&刚开始写答案时不够认真，没仔细检查，虽然结果是对的，但中间步骤有很多纰漏和笔误，给不少人造成了困扰，十分抱歉。幸而不断有知友帮忙指出错误，大家的帮助下，我应该是把错误都改正了。&/b&&/p&&br&&p&==================================================================&/p&&p&感谢评论区，有人指出这个问题叫做Coupon collector's problem(优惠券收集问题)。&/p&&br&&p&例如我想集齐小浣熊的108将人物卡，假设每张卡出现的概率是相同的（ &img src=&//www.zhihu.com/equation?tex=%5Cfrac%7B1%7D%7B108%7D& alt=&\frac{1}{108}& eeimg=&1&& ），则平均需要买多少袋干脆面。这实质上和本问题是一样的。&/p&&br&&p&在这个问题中，我们假设皇帝现在已经宠幸了 &img src=&//www.zhihu.com/equation?tex=n& alt=&n& eeimg=&1&& 位佳丽，也就是还没宠幸的佳丽是 &img src=&//www.zhihu.com/equation?tex=N-n& alt=&N-n& eeimg=&1&& 位。&/p&&br&&p&那么下次皇帝随机宠信佳丽时，遇到宠幸过的概率是 &img src=&//www.zhihu.com/equation?tex=%5Cfrac%7Bn%7D%7BN%7D& alt=&\frac{n}{N}& eeimg=&1&& ，遇到没宠幸过的概率是 &img src=&//www.zhihu.com/equation?tex=%5Cfrac%7BN-n%7D%7BN%7D& alt=&\frac{N-n}{N}& eeimg=&1&&&/p&&br&&figure&&img src=&https://pic1.zhimg.com/v2-ce6befd7f33cf7ff2d71174_b.jpg& data-rawwidth=&1210& data-rawheight=&873& class=&origin_image zh-lightbox-thumb& width=&1210& data-original=&https://pic1.zhimg.com/v2-ce6befd7f33cf7ff2d71174_r.jpg&&&/figure&&br&&p&现在皇帝已经宠幸过了 &img src=&//www.zhihu.com/equation?tex=n& alt=&n& eeimg=&1&& 位佳丽后，他再宠幸1位&b&之前没宠信&/b&的佳丽，使得宠信过的佳丽数达到 &img src=&//www.zhihu.com/equation?tex=n%2B1& alt=&n+1& eeimg=&1&&需要的天数为 &img src=&//www.zhihu.com/equation?tex=x_n& alt=&x_n& eeimg=&1&& ，其满足几何分布，因此 &img src=&//www.zhihu.com/equation?tex=x_n& alt=&x_n& eeimg=&1&& 的期望为：&/p&&br&&figure&&img src=&https://pic2.zhimg.com/v2-e1f7dcd4fdde63307c59_b.jpg& data-rawwidth=&204& data-rawheight=&86& class=&content_image& width=&204&&&/figure&&br&&p&而宠幸所有佳丽所需的总天数为&/p&&br&&figure&&img src=&https://pic2.zhimg.com/v2-54fa91c273b03e81dd61_b.jpg& data-rawwidth=&229& data-rawheight=&55& class=&content_image& width=&229&&&/figure&&br&&p&而且不同的 &img src=&//www.zhihu.com/equation?tex=x_n& alt=&x_n& eeimg=&1&& 之间相互独立，因此所需时间的期望为&/p&&br&&figure&&img src=&https://pic3.zhimg.com/v2-ed50be45eac1bb82200f2_b.jpg& data-rawwidth=&629& data-rawheight=&93& class=&origin_image zh-lightbox-thumb& width=&629& data-original=&https://pic3.zhimg.com/v2-ed50be45eac1bb82200f2_r.jpg&&&/figure&&br&&br&&p&&b&因为专业背景用排队论比较多，所以我最初把问题考虑成了一个马尔可夫链，虽然也能求出结果，但复杂了很多，也不是那么好理解，如果大家感兴趣也可以看一下。&/b&&/p&&br&&p&我最初的解题过程如下：&/p&&p&===================================================================&/p&&p&第 &img src=&//www.zhihu.com/equation?tex=n& alt=&n& eeimg=&1&& 天结束后，宠幸过妃子的数为 &img src=&//www.zhihu.com/equation?tex=X_n& alt=&X_n& eeimg=&1&& 。&/p&&br&&p&易发现随机序列 &img src=&//www.zhihu.com/equation?tex=%5C%7BX_n%2Cn%5Cge1%5C%7D& alt=&\{X_n,n\ge1\}& eeimg=&1&& 是一个马尔科夫链，状态转移图如下:&/p&&br&&figure&&img src=&https://pic2.zhimg.com/v2-a76bf1e18023b30afce4d_b.jpg& data-rawwidth=&1568& data-rawheight=&245& class=&origin_image zh-lightbox-thumb& width=&1568& data-original=&https://pic2.zhimg.com/v2-a76bf1e18023b30afce4d_r.jpg&&&/figure&&p&接下来让我们分析状态转移概率：&/p&&ul&&li&当 &img src=&//www.zhihu.com/equation?tex=X_n%3D0& alt=&X_n=0& eeimg=&1&& 时，说明任何佳丽都没有宠幸，则第二天宠幸过的妃子数量一定会加1，即 &img src=&//www.zhihu.com/equation?tex=%5CPr%5C%7BX_%7Bn%2B1%7D%3D1%7CX_n%3D0%5C%7D%3D1& alt=&\Pr\{X_{n+1}=1|X_n=0\}=1& eeimg=&1&& ;&/li&&li&当 &img src=&//www.zhihu.com/equation?tex=X_n%3DS%5Cin%5B1%2CN-1%5D& alt=&X_n=S\in[1,N-1]& eeimg=&1&&时，代表 &img src=&//www.zhihu.com/equation?tex=S& alt=&S& eeimg=&1&& 个佳丽已经被宠幸， &img src=&//www.zhihu.com/equation?tex=N-S& alt=&N-S& eeimg=&1&& 个佳丽未被宠幸，则晚上皇帝宠幸到新妃子的概率为 &img src=&//www.zhihu.com/equation?tex=%5Cfrac%7BN-S%7D%7BN%7D& alt=&\frac{N-S}{N}& eeimg=&1&&，即 &img src=&//www.zhihu.com/equation?tex=%5CPr%5C%7BX_%7Bn%2B1%7D%3DS%2B1%7CX_n%3DS%5C%7D%3D%5Cfrac%7BN-S%7D%7BN%7D& alt=&\Pr\{X_{n+1}=S+1|X_n=S\}=\frac{N-S}{N}& eeimg=&1&&&/li&&li&晚上皇帝宠未幸到新妃子的概率为 &img src=&//www.zhihu.com/equation?tex=%5CPr%5C%7BX_%7Bn%2B1%7D%3DS%7CX_n%3DS%5C%7D%3D%5Cfrac%7BS%7D%7BN%7D& alt=&\Pr\{X_{n+1}=S|X_n=S\}=\frac{S}{N}& eeimg=&1&& ；&/li&&/ul&&br&&p&令 &img src=&//www.zhihu.com/equation?tex=%5Clambda_%7Bij%7D& alt=&\lambda_{ij}& eeimg=&1&& 表示状态 &img src=&//www.zhihu.com/equation?tex=i& alt=&i& eeimg=&1&& 一步转换到 &img src=&//www.zhihu.com/equation?tex=j& alt=&j& eeimg=&1&& 的概率，有：&/p&&ul&&li&当 &img src=&//www.zhihu.com/equation?tex=i%3Cj& alt=&i&j& eeimg=&1&& 和 &img src=&//www.zhihu.com/equation?tex=j-i%3E1& alt=&j-i&1& eeimg=&1&& 时， &img src=&//www.zhihu.com/equation?tex=%5Clambda_%7Bij%7D%3D0& alt=&\lambda_{ij}=0& eeimg=&1&& ，代表皇帝宠幸过的佳丽数量是不会减少的，以及每晚增加的数量最多为1；&/li&&li&当 &img src=&//www.zhihu.com/equation?tex=i%3Dj& alt=&i=j& eeimg=&1&& 时， &img src=&//www.zhihu.com/equation?tex=%5Clambda_%7Bij%7D%3D%5Cfrac%7Bi%7D%7BN%7D& alt=&\lambda_{ij}=\frac{i}{N}& eeimg=&1&&&/li&&li&当 &img src=&//www.zhihu.com/equation?tex=j%3Di%2B1& alt=&j=i+1& eeimg=&1&& 时， &img src=&//www.zhihu.com/equation?tex=%5Clambda_%7Bij%7D%3D%5Cfrac%7BN-i%7D%7BN%7D& alt=&\lambda_{ij}=\frac{N-i}{N}& eeimg=&1&& ；&/li&&/ul&&br&&p&以 &img src=&//www.zhihu.com/equation?tex=N%3D5& alt=&N=5& eeimg=&1&& 情形举例，则状态转移方程为：&/p&&img src=&//www.zhihu.com/equation?tex=%5C%5BP+%3D+%5Cleft%5B+%7B%5Cbegin%7Barray%7D%7B%2A%7B20%7D%7Bc%7D%7D+%7B%7B%5Clambda+_%7B00%7D%7D%7D%26%7B%7B%5Clambda+_%7B01%7D%7D%7D%26%7B%7B%5Clambda+_%7B02%7D%7D%7D%26%7B%7B%5Clambda+_%7B03%7D%7D%7D%26%7B%7B%5Clambda+_%7B04%7D%7D%7D%26%7B%7B%5Clambda+_%7B05%7D%7D%7D%5C%5C+%7B%7B%5Clambda+_%7B10%7D%7D%7D%26%7B%7B%5Clambda+_%7B11%7D%7D%7D%26%7B%7B%5Clambda