Posts

每年春晚过后，央视又要吹嘘说今年春晚收视率创新高了，但是我们总感觉央视在骗我们，因为我是越长大越不看春晚了[笑cry]，所以收视率到底是怎么统计出来的，央视的说法是否靠谱呢？ 最近的美国大选真是热闹，很多机构都会发放一些调查问卷，然后统计出希拉里或者唐纳德的民众支持率是多少，但是我并没有收到调查问卷，凭什么就得出了民众支持率了，意思是把我排除在民众之外咯？所以引出这样一个问题，调查问卷是否可信，即调查问卷的有效性。 其实，央视统计收视率并不要问全中国14亿人口有多少人看了春晚，他只需要从14亿人口里面随机抽\(n\)个人，问一下这\(n\)个人里有多少人看了春晚，然后把看的人数除以总数就大概估计出全国的收视率了。同理调查民众支持率也是一样，只需要随机调查\(n\)个人的意向，把支持希拉里的人数除以总数就大概得到了希拉里的支持率。 但是你要问了，通过抽样调查出来的收视率和支持率靠谱吗，需要随机抽样多少人才能得到一个比较好的全局近似解呢？今天我们就来解决这个问题。 假设我们随机抽样了\(n\)个人，分别是\(x_1,x_2,…,x_n\)。如果第\(i\)个人看了春晚，则\(x_i=1\)，否则\(x_i=0\)。那么通过这\(n\)个人的收视情况，我们可以估计出一个收视率 $$\begin{equation}\hat{p}=\frac{x_1+x_2+…+x_n}{n}\end{equation}$$假设全国的真实收视率是\(p\)，那么平均到每一个人，他看了春晚的概率就是\(p\)，也即\(Pr(x_i=1)=p\)，所以有 $$\begin{equation}E(x_i)=p\quad E(x_i^2)=p\quad Var(x_i)=p(1-p)\end{equation}$$我们的目的就是希望通过\(n\)个人估计出来的\(\hat{p}\)和\(p\)越接近越好。换句话说，我们希望\(\hat{p}\)和\(p\)相差大于5%的概率要小于5%。再换句话说就是有至少95%的概率，\(\hat{p}\)和\(p\)相差在5%以内，即\(\hat{p}\)和\(p\)很接近。注意这里的两个5%都是可以换成任意你想要的精度。用数学语言表示就是，\(n\)至少为多少时，以下不等式可以被满足。 $$\begin{equation}Pr(|\hat{p}-p|\geq 5\%)\leq 5\%\end{equation}$$把(1)式代入(3)式，用\(\frac{1}{20}\)代替5%，得到等价形式： $$\begin{equation}Pr(|(\frac{x_1+x_2+…+x_n}{n})-p|\geq\frac{1}{20})\\ \Longleftrightarrow~Pr(|X-np|\geq\frac{n}{20})\end{equation}$$其中\(X=x_1+x_2+…+x_n\)。根据期望的线性可加性，有 $$\begin{equation}E(X)=E(x_1+x_2+…+x_n)=E(x_1)+E(x_2)+…+E(x_n)=np\end{equation}$$所以(4)又等价于 $$\begin{equation}Pr(|X-E(X)|\geq\frac{n}{20})\end{equation}$$我们需要利用著名的切比雪夫不等式来求解上式，切比雪夫不等式如下： $$\begin{equation}Pr(|X-E(X)|\geq~c)\leq\frac{Var(X)}{c^2}\end{equation}$$切比雪夫不等式可以直接由马尔可夫不等式得到，马尔可夫不等式的证明也不难，略过。 利用切比雪夫不等式求解(6)式 $$\begin{equation}Pr(|X-E(X)|\geq\frac{n}{20})\leq\frac{Var(X)}{n^2}*400\\ =\frac{n*Var(x_i)}{n^2}*400\\ =\frac{p(1-p)}{n}*400\\ \leq\frac{1/4}{n}*400=\frac{100}{n} \end{equation}$$第一个等号是因为\(n\)个变量是独立同分布的，所以方差也有类似于(5)式的线性性质。最后一个不等号是因为\(p(1-p)\)是一个开口向下的抛物线，在\(p=1/2\)时取到极值\(1/4\)。 回到最初的不等式(3)，则(8)式要满足\(\frac{100}{n}\leq 5\%\)，解得\(n\geq 2000\)。注意到求出的\(n\)和总体人数是无关的，也就是说，虽然全中国有十几亿人口，但是央视只要随机抽样调查2000个人的收视情况，就能以比较高的概率准确估计出全国的收视率。 这个结论还是很漂亮的，但是这种方法有两个限制条件： 采样满足独立同分布，即这\(n\)个人是独立同分布的，不能针对某一特定人群调查 (3)式的5%是一个绝对误差，当\(p\)本身很小的时候，容易被5%淹没 对于第1个问题，稍微好处理一点，抽样的时候尽量随机一点。对于第2个问题，比较好的解决办法是引入相对误差，即把(3)式转换为如下的不等式 $$\begin{equation}Pr(|\hat{p}-p|\geq\delta p)\leq\epsilon\end{equation}$$(9)式的求解就比较复杂了，得出的结论也没有上面那么简单，具体的求解方法请听下回分解。

你是否想过如下问题：怎样向色盲证明两只袜子的颜色是不一样的？怎样证明两个图是不同构的？怎样证明一个数是二次非剩余的？ 咋听起来觉得很有意思吧，色盲是区分不了颜色的，怎么能让他相信两只袜子的颜色不一样呢。图同构问题目前既没有被证明属于P，也没有被证明属于NP-Complete。二次非剩余问题也没有被证明属于NP。 这些听起来很“难”的问题，却可以通过交互式证明进行证明，下面先通过“向色盲证明两只袜子的颜色不同”这个有趣的例子一窥交互式证明的强大。 向色盲证明两只袜子的颜色不同 P有一只红袜子和黄袜子，她的一个色盲朋友V不相信P的袜子颜色不同，P如何才能让V相信这是真的呢？一个简单的办法如下： P把两只袜子给V，V每只手拿了一只袜子 P转过身背对V V抛一枚硬币，如果头面朝上，则保持两只袜子不动，否则交换左右手的袜子 P转过身，V问P是否交换过袜子 如果P回答错误，则V不相信；否则，重复100次实验，如果P都回答正确，则V相信这两只袜子是不同颜色的 如果两只袜子的颜色确实不一样，则P通过区分两只袜子的颜色能正确回答V有没有交换过袜子。但是如果两只袜子颜色一样，则不管V有没有交换过，P都无法分辨这两只袜子，所以只好猜V有没有交换，而猜对的概率只有1/2，重复100次，都猜对的概率只有\((1/2)^{100}\)，这是一个非常小的数，可以认为几乎不会发生，即出错的概率极低。 这就是交互式证明的一个例子，上述证明有三个特点：1）交互过程，整个证明需要P和V进行交互才能完成；2）具有随机性，即V需要抛一枚硬币，来决定是否交换袜子；3）零知识，虽然V最终相信了这两只袜子是不同颜色的，但V还是不知道这两只袜子是什么颜色的。 下面我们给出交互式证明的形式化定义。 交互式证明（Interactive Proofs, IP） 令\(k\)是\(N\rightarrow N\)的一个函数，我们称语言\(L\)属于\(IP[k]\)，如果存在一个\(k(|x|)\)多项式时间概率图灵机TM \(V\)，使得： $$ \begin{equation} \begin{cases} x\in L \Longrightarrow\exists P\quad Pr[V \text{ accepts }x, V(x)=1]\geq 2/3 \\ x\notin L \Longrightarrow\forall P\quad Pr[V \text{ accepts }x, V(x)=1]\leq 1/3 \end{cases} \end{equation} $$定义 $$IP=\underset{c}{\bigcup} IP[n^c]$$上述定义的第一条称为“完备性”（Completeness）：如果\(x\in L\)，则存在一个证明者P（prover），使得验证者V（verfier）能以多项式时间接受\(x\)，且接受的概率大于2/3；第二条称为“可靠性”（Soundness），如果\(x\notin L\)，则对于所有证明者P，V接受\(x\)的概率都不会超过1/3。 对应到上面的例子，完备性：当两只袜子的颜色确实不同时，V接受的概率为1>2/3；可靠性：当两只袜子的颜色相同时，重复100次实验，V接受的概率只有\((1/2)^{100}<1/3\)。 IP这个复杂性类就是所有IP[k]的并集。在IP中，P的能力是无穷的，但它不一定是诚实的；V能力较弱，只能进行多项式时间的计算。 下面我们给出另外两个交互式证明的协议。 图不同构（Graph Non-isomorphism, GNI）的交互式证明 如果图\(G_1\)和\(G_2\)可以通过对顶点进行恰当标记来将它们转换为同一个图，则称\(G_1\)和\(G_2\)同构，记为\(G_1\cong G_2\)。换句话说，如果\(G_1\)和\(G_2\)同构，则在\(G_1\)的所有顶点标签上存在一个置换\(\pi\)使得\(\pi (G_1)=G_2\)，其中\(\pi (G_1)\)是将\(\pi\)作用到\(G_1\)的各个顶点上之后得到的图。下图就是两个同构图，右边给出了置换\(\pi\)。 图同构的补集为图不同构（Graph Non-isomorphism, GNI），即判定给定的两个图是否不同构。下面是GNI的一个交互式证明过程。 给定两个图\(G_1\)和\(G_2\)，证明者P想要向验证者V证明\(G_1\ncong G_2\)。 V：随机选一个\(i\in \{1,2\}\)，对\(G_i\)做一个随机的置换，得到新图\(H\)，则有\(H\cong G_i\)，将\(H\)发送给P P：发送\(j\)给V V：如果\(i\neq j\)，则拒绝；否则重复100次实验，都有\(i==j\)，则相信\(G_1\ncong G_2\) 完备性：如果\(G_1\ncong G_2\)，则\(H\)只和\(G_1, G_2\)中的一个图同构，P因为能力无穷，一定能找出和\(H\)同构的图\(G_j\)，且满足\(j==i\)。 ...

\(\LaTeX\)的强大我就不赘述了，这里简单介绍一下怎样在Windows快速配置一个完美好用的\(\LaTeX\)环境。 我大学刚接触\(\LaTeX\)的时候，使用的是CTeX，CTeX是一个大礼包，整合了编译器编辑器等，但是由于久不更新，很多宏包和语法都变了，而且CTeX附带的WinEdt是商业软件，30天之后需要收费，我又不想用盗版，所以就打算自己配置\(\LaTeX\)环境。 目前使用的是MiKTeX+Texmaker的完美组合！MiKTeX是\(\LaTeX\)编译器，Texmaker是\(\LaTeX\)编辑器。两者都是开源软件。 MiKTeX非常棒的地方在于“MiKTeX has the ability to install needed packages automatically (on-the-fly)”，就是说，你用MiKTeX时，不需要担心某个宏包是否存在，你只管用就是了，MiKTeX会在你第一次用到某个宏包时，自动从网上下载，非常方便。正因为这样，MiKTeX的安装包很小，只有175MB。当然，因为是on-the-fly的，所以必须联网使用，而且MiKTeX只有Windows版本。 MiKTeX自带了一个TeXworks编辑器的，但是这软件用户体验并不好。我以前一直都用WinEdt，很好用，但是它是商业软件，我又不想盗版（说到底是没钱…），所以换了Texmaker。Texmaker可以媲美WinEdt，软件布局合理，各种快捷键用起来也很方便。不过在上手之前要简单配置一下。 如果是写英文文章，点击“快速构建”左边的箭头（或者F1快捷键），就能一键编译并刷新pdf视图。但是默认的快速构建使用的引擎是PdfLaTeX，如果你是中文用户，使用了xeCJK宏包，则必须使用XeLaTeX引擎编译，所以依次点击“选项->配置Texmaker->（左边）快速构建”，选择快速构建命令为”XeLaTeX + View PDF”。 构建好的PDF默认是以弹窗的形式展现的，我们可以设置让代码和PDF并排显示，这样方便在PDF和源代码之间切换，配置如下： Texmaker自带了一个PDF阅读器，当然你也可以使用外部阅读器，比如非常棒的Sumatra PDF，只需填入Sumatra PDF的路径跟上%.pdf，并选中External Viewer。 Texmaker还有一个很好用的功能是“正向/反向搜索”。反向搜索是点击PDF某个位置，会跳到tex源代码对应位置，快捷方式是ctrl+click。正向搜索是点击tex源代码某个位置，会跳到PDF对应的位置，默认快捷方式ctrl+space，但是这个快捷方式好像用不了，可以自行配置成其他快捷方式，比如ctrl+1，我当时是打开下图的快捷方式窗口才发现这个问题的。 正反向搜索都可以通过鼠标右键菜单实现，但是快捷键还是更方便的。最重要的一点是，源文件*.tex所在路径不能有中文！！！要不然正反向搜索不能用，这点很重要，我当时郁闷了好久。 另外还可以配置一下编辑器的字体，勾选”Backup documents every 10 min”之类的。 OK，大功告成，这种三段式的界面、F1快速构建以及正向/反向搜索，用起来真是太顺手了，Just Enjoy \(\LaTeX\)~ 下面是我常用的\(\LaTeX\)中文模板： LaTeXDemo.pdf LaTeXDemo.tex

SVM回顾 支持向量机（SVM）的一大特点是最大化间距（max margin）。对于如上图的二分类问题，虽然有很多线可以将左右两部分分开，但是只有中间的红线效果是最好的，因为它的可活动范围（margin）是最大的，从直观上来说很好理解。 对于线性二分类问题，假设分类面为 $$\begin{equation} u=\vec w \cdot \vec x-b \end{equation}$$则margin为 $$\begin{equation} m=\frac{1}{||w||_2} \end{equation}$$根据max margin规则和约束条件，得到如下优化问题，我们要求的就是参数\(\vec w\)和\(b\)： $$\begin{equation} \min\limits_{\vec w,b}\frac{1}{2}||\vec w||^2 \quad\text{subject to}\quad y_i(\vec w\cdot \vec x_i-b) \geq 1, \forall i,\end{equation}$$对于正样本，类标号\(y_i\)为+1，反之则为-1。根据拉格朗日对偶，(3)可以转换为如下的二次规划（QP）问题，其中\(\alpha_i\)为拉格朗日乘子。 $$\begin{equation} \min\limits_{\vec \alpha}\Psi(\vec\alpha)=\min\limits_{\vec \alpha}\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^Ny_iy_j(\vec x_i\cdot\vec x_j)\alpha_i\alpha_j-\sum_{i=1}^N\alpha_i,\end{equation}$$其中N为样本数量。上式还需满足如下两个约束条件： $$\begin{equation} \alpha_i\geq 0, \forall i,\end{equation}$$$$\begin{equation} \sum_{i=1}^Ny_i\alpha_i=0.\end{equation}$$一旦求解出所有的拉格朗日乘子，则我们可以通过如下的公式得到分类面参数\(\vec w\)和\(b\)。 $$\begin{equation}\vec w=\sum_{i=1}^Ny_i\alpha_i\vec x_i,\quad b=\vec w\cdot\vec x_k-y_k\quad\text{for some}\quad\alpha_k>0.\end{equation}$$当然并不是所有的数据都可以完美的线性划分，可能有少量数据就是混在对方阵营，这时可以通过引入松弛变量\(\xi_i\)得到软间隔形式的SVM： $$\begin{equation} \min\limits_{\vec w,b,\vec\xi}\frac{1}{2}||\vec w||^2+C\sum_{i=1}^N\xi_i \quad\text{subject to}\quad y_i(\vec w\cdot \vec x_i-b) \geq 1-\xi_i, \forall i,\end{equation}$$其中的\(\xi_i\)为松弛变量，能假装把错的样本分对，\(C\)对max margin和margin failures的trades off。对于这个新的优化问题，约束变成了一个box constraint： $$\begin{equation}0\leq\alpha_i \leq C,\forall i.\end{equation}$$而松弛变量\(\xi_i\)不再出现在对偶公式中了。 ...

yn说最近在备考GMAT和托福，把手机都清理了只为专心学习。xx说TCP/IP大作业要用Qt做一个网络监控的软件，问我Qt好不好学。 GRE遇见Qt，会擦出怎样的火花呢~没错，我用Qt写了一个强化背诵GRE单词的软件——Cracking 3000 当时的一本GRE单词书有3000个单词，用杨鹏17天刷过之后，很多都记不住，于是想有没有办法把记不住的单词筛选出来，集中力量强化记忆。网上已经有3000的Excel表，所以我很自然的想到了把表格导入软件，用软件快速测试，并把不认识的单词筛选到新的Excel表格中。这样就可以把不认识的单词表打印出来，记完之后再导入软件进行新一轮的测试筛选，直到不认识的单词数为零。 有了软件需求，代码实现起来就很快了。由于当时用Qt库比较多，所以直接拿来用了。软件实现这一块，主要是Excel表格的导入和导出，需要查一些文档，其他的就很简单了。 虽然和GRE纠缠了一个多月，最终却没有考，但是想起当初早上6点爬起来背单词，晚上回宿舍抹黑写代码的情景，心情还是有一点小小的激动！以后类似的体验估计不会太多吧。 最后祝yn GT考试顺利，xx大作业圆满完成！ Cracking_3000软件安装包及说明

刚坐上去北京的列车，就收到了妈妈的微信语音：霖，早上收拾东西怎么忘了带上我给你洗好的鞋呀。我这才想起早上妈妈把洗好的鞋和叠好的衣服放在我房间，我却忘了带鞋。 后来和爸妈在群里聊了起来。当我问爸爸什么时候返回学校时，他却说前天突然请假回家惹老板不高兴了，可能要被炒鱿鱼。是，老爸在那个学校当老师十几年了，我平时老数落他当老师工资那么低，为什么不改行，可突然听到这个消息，心里却不是滋味。 其实老爸没必要请假回来的。前几天我发脾气，老爸好像真的决定转行搞种植业了，托我在淘宝买了好多枸杞树，自己带回了五十棵脐橙树苗，还准备去某个地方考察什么药材。 离家前一天，妈妈特地跑到县城买了好多排骨回来，还煮了十个土鸡蛋要我带着路上吃。老爸买了好多苹果、香蕉、猕猴桃要我带着路上吃。今天早上收拾行李的时候，从来不动手的爸爸，也抢着往我包里塞各种牛奶和水果。 二十多年了，经历了多少次的离家，从来没有像今天这样的不舍。二十多年了，我突然发现爸爸妈妈变矮了，爸爸的额头黑得发亮，妈妈的眼角也长出了好多鱼尾纹。 今年难得有一个月的寒假，但我整天忙着看论文、书和电视剧，和爸妈的交流反而少了。有天吃过晚饭，发现妈妈独自坐在客厅戳着她的手机。我问过才发现原来妈妈想看哥哥和他女朋友的照片，但是怎么都弄不出来，我帮妈妈找出来之后，还教她怎么用微信和qq，妈妈说wifi图标像降落伞，我说你什么时候想上网就把降落伞打开，我说你如果想和哥哥聊天，就按住底部的按钮，等到出现小喇叭之后就可以说话了，说完放开手，听到“嗖“”的一声，说的话就发过去了，但是妈妈经常忘记打开降落伞，经常忘记按小喇叭。。。 刚刷QQ空间的时候，看到一个同学的说说“马上又要去坐火车回武汉了，在家的时间越来越少了，没能好好陪陪父母，我不是称职的儿子。” 坐在火车上，看着窗外闪过的霓虹灯，突然觉得这个世界好陌生好无情，每个人在时间面前是多么的渺小。 2016年2月26日于z68列车上。

现在是2016年2月4日，距离农历新年不到4天，结束了半年的国科大研一生活，躺在被窝里，松了一口气…… 来国科大之前，在贴吧上了解到国科大雁栖湖校区地处偏远农村，周边几乎没有娱乐场所；但同时学校的软硬件设施非常的棒：豪华单人间，研究员甚至院士亲自授课等等。所以对国科大雁栖湖校区满是憧憬。至今还清楚的记得坐校车从玉泉路过来时，沿途看到APEC主会场的鸟蛋、国科大桥、钟楼以及国科大正门几个大字时的激动心情~ 入住国科大，着实被UCAS的蓝天白云、青山绿水给迷住了。 当然，凡事有利必有弊，因为这里远离市区，环境好，但正因为远离市区，几乎没有年轻人的娱乐活动，想要看个电影唱个歌少说也得跑城里，再要想感受下帝都奢靡的生活，必须各种倒车近2个小时到市里。 研一这上学期，半年只进市里两次，一次是买山地车，一次是回所里开会。购物主要靠天猫超市。 九十月份，大家都和大一新生似的，各种疯玩，野长城、雁栖湖、慕田峪、青龙峡、密云水库。进入十一月，新鲜劲过去了，又开始各种赶大小作业，复习考试。 这是我这学期的课表，看着课好像不多，每天都有半天休息，但是真的感觉回到了大三呀！尤其数据挖掘、信息检索、矩阵论一周上两次课，当天上完的课如果没有及时复习，隔一天再学新内容完全跟不上啊，而且矩阵论每次课都有好多作业啊，这数学课不做练习完全消化不了呀。更神的课还要数周五的卜神算法，君不见，每到周四晚上，西A、西B两栋宿舍，灯火通明，大家都在熬夜赶算法作业啊，不熬个两三点都不好意思和别人说你熬夜了呀。大家可以感受一下我整理的卜神算法作业~~ 正是因为这奇葩的课程安排，这半年几乎没有12点前睡过觉，估计平均是1:30才睡觉，早上8点多才起，中午也没午休。想想大学的时候按时作息，真是惭愧。期间有一次听说搜狐一同届华科毕业生猝死，朋友圈传得沸沸扬扬，大伙都吓得要命，纷纷表示绝不熬夜，早睡早起，我那天也是吓坏了，决定早睡，11:30就爬床上了，但是不知道是因为紧张还是熬夜习惯了，辗转反侧，到12点多才睡着的。 我们研一在国科大上课是有补助的，但是在帝都完全不够用啊，而且CS相关的几个所补助都比ICT高，so当时还公车上书，各种写联名信、起义，经过半年之久的持久战，所里终于答应从2016年开始给我们涨500块钱的工资。涨了之后差不多够吃饭了。 虽然这半年课业繁重，但是也抽空锻炼了身体，天气不是很冷的时候，隔一天就会去夜跑；而且选了乒乓球课，从直拍转为了横拍，并且在课上结识了路路，打球好厉害的一个女生，每次老师来指导的时候，都叫路路温柔点 O__O “… 另外花了一千多块钱买了一辆二手山地车，骑着到处转悠了一下。很有缘的是，认识了一位才女。本来我们骑行社一块去美利达准备买车，但是由于种种原因我和小欣都没买，然后我们一块坐小黑车回村，在车上聊着聊着就认识，没想到后来还成为了好朋友，小欣的台球和乒乓球都打得不错，琴棋书画样样精通。突然发现身边的学霸才子佳人好多，更加深刻感受到有些东西不是你努力就能够弥补的，天赋、眼界、才艺、品味、性格…… 来国科大的这半年，自我感觉变化最大的是自己变得爱说话了，而且带着一种zhuang bi气息，不知道是不是受某几个我一直崇拜的人的影响。有时候静下心来想想都不敢相信之前的话是我说的，和大学时的我完全判若两人。当然这种事情有利也有弊，还在慢慢找平衡点，可能正如CL说的“话怎么说是一回事，内心要知道自己想要的”。 这半年突然害怕一个人上学，一个人吃饭，一个人自习了，更喜欢face-to-face的交谈，少了对网络的依赖，不知道是不是因为性格的变化、环境的变化、抑或是认识的人多了，有了念想。 半年时光，认识了不多不少几个好朋友：良辰、发文章、牛牛、欣儿、路路，有你们真好，谢谢你们~ 2016猴赛雷，即将从研一的上课转入课题组工作，很关键的一年，加油！

这学期选修了卜老师的算法课，都说这课是神课，上过之后果然是神课。同样是算法课，别人12月底就考完了，我们要1月底才考试。 本课程主要讲了以下几个专题： Divide-and-conquer Dynamic programming Greedy Linear programming Linear programming: duality Network flow Problem hardness: Polynomial-time reduction NP-Completeness Approximation algorithm 前三个专题的算法大多数本科时学过的，但是经卜老师讲一遍还会有新的收获。后六个专题接触较少，学到了很多新算法。 下图是卜老师每节课必讲的问题求解思路图： （待我回家把图画出来…） 本课程最神的要数课后作业了，一般deadline是周五，每到周四晚上，大家都做好熬通宵赶作业的准备，没熬到两三点都不好意思睡觉，我同学有一次甚至熬到了第二天六点！ 每次作业大概有10题，前7题是算法设计，后3题是算法实现，每题都不是省油的灯，不过如果把每道题都理解消化，算法及编程能力会有很大的提高。 下面是我整理出来的算法题目和个人解答，大家感受一下。（仅供完成作业之后交流使用，拒绝抄袭！） Assignment1_DandC.zip A1sol.pdf | A1sol.tex A1sol_supplement.pdf | A1sol_supplement.tex_.zip Assignment2_DP.zip A2sol.pdf | A2sol.tex_.zip A2sol_supplement.pdf | A2sol_supplement.tex Assignment3_Greedy.zip A3sol.pdf | A3sol.tex_.zip A3sol_supplement.pdf | A3sol_supplement.tex Assignment4_LP.zip A4sol.pdf | A4sol.tex A4sol_supplement.pdf | A4sol_supplement.tex Assignment5_NF.zip A5sol.pdf | A5sol.tex A5sol_supplement.pdf | A5sol_supplement.tex Assignment6_NP.pdf A6sol.pdf | A6sol.tex Assignment7_App.pdf A7sol.pdf | A7sol.tex

至此，整个新闻搜索引擎构建完毕，总体效果令人满意，不过还是有很多可以改进的地方。下面总结一下本系统的优点和不足。 优点 倒排索引存储方式。因为不同词项的倒排记录表长度一般不同，所以没办法以常规的方式存入关系型数据库。通过将一个词项的倒排记录表序列化成一个字符串再存入数据库，读取的时候通过反序列化获得相关数据，整个结构类似于邻接表的形式。 推荐阅读实现方式。利用特征提取的方法，用25个关键词表示一篇新闻，大大减小了文档词项矩阵规模，提高计算效率的同时不影响推荐新闻相关性。 借用了Reddit的热度公式，融合了时间因素。 不足 构建索引时，为了降低索引规模，提高算法速度，我们将纯数字词项过滤了，同时忽略了词项大小写。虽然索引规模下降了，但是牺牲了搜索引擎的正确率。 构建索引时，采用了jieba的精确分词模式，比如句子“我来到北京清华大学”的分词结果为“我/ 来到/ 北京/ 清华大学”，“清华大学”作为一个整体被当作一个词项，如果搜索关键词是“清华”，则该句子不能匹配，但显然这个句子和“清华”相关。所以后续可以采用结巴的搜索引擎分词模式，虽然索引规模增加了，但能提升搜索引擎的召回率。 在推荐阅读模块，虽然进行了维度约减，但是当数据量较大时（数十万条新闻），得到的文档词项矩阵也是巨大的，会远远超过现有PC的内存大小。所以可以先对新闻进行粗略的聚类，再在类内计算两两cosine相似度，得到值得推荐的新闻。 在热度公式中，虽然借用了Reddit的公式，大的方向是正确的，但是引入了参数\(k_1\)和\(k_2\)，而且将其简单的设置为1。如果能够由专家给出或者经过机器学习训练得到，则热度公式的效果会更好。 完整可运行的新闻搜索引擎Demo请看我的Github项目news_search_engine。 以下是系列博客： 和我一起构建搜索引擎（一）简介 和我一起构建搜索引擎（二）网络爬虫 和我一起构建搜索引擎（三）构建索引 和我一起构建搜索引擎（四）检索模型 和我一起构建搜索引擎（五）推荐阅读 和我一起构建搜索引擎（六）系统展示 和我一起构建搜索引擎（七）总结展望

前几个博客已经介绍完搜索引擎的所有功能，为了实现更好的用户体验，需要一个web界面。这一部分是另一个队员做的，我这里借用他的代码。 我们利用开源的Flask Web框架搭建了展示系统，搜索引擎只需要两个界面，一个是搜索界面，另一个是展示详细新闻的页面（实际搜索引擎没有这个页面）。编写好这两个模板页面并调用前面给出的接口，得到数据，展示出来就可以。 这一部分没有太多需要讲解的算法，直接上效果图（点击图片可以查看大图）。 图1. 搜索页面 图2. 新闻详情页面 由于数据量不大，只有1000条新闻，所以第一页中后面几个结果相关度就不是很高了。但是经过测试，在大数据量的情况下，不论是搜索的速度、准确率、召回率以及推荐阅读的相关度，都达到了不错的效果。 完整可运行的新闻搜索引擎Demo请看我的Github项目news_search_engine。 以下是系列博客： 和我一起构建搜索引擎（一）简介 和我一起构建搜索引擎（二）网络爬虫 和我一起构建搜索引擎（三）构建索引 和我一起构建搜索引擎（四）检索模型 和我一起构建搜索引擎（五）推荐阅读 和我一起构建搜索引擎（六）系统展示 和我一起构建搜索引擎（七）总结展望