Articles tagged as

  1. Probabilistic latent semantic analysis (pLSA)

    Probabilistic latent semantic analysis (概率潜在语义分析,pLSA) 是一种 Topic model,在99年被 Thomas Hofmann 提出。它和随后提出的 LDA 使得 Topic Model 成为了研究热点,其后的模型大都是建立在二者的基础上的。

    我们有时会希望在数量庞大的文档库中自动地发现某些结构。比如我们希望在文档库发现若干个“主题”,并将每个主题用关键词的形式表现出来。 我们还希望知道每篇文章中各个主题占得比重如何,并据此判断两篇文章的相关程度。而 pLSA 就能完成这样的任务。

    我之前取了 Wikinews 中的 1000 篇新闻,试着用 pLSA 在其中发现 K=15 个主题。比如一篇关于 Wikileaks 的阿萨奇被保释消息的新闻,算法以 100% 的概率把它分给了主题 9,其关键词为:

    media phone hacking wikileaks assange australian stated information investigation murdoch

    可以看到这个主题的发现还是非常靠谱的。又比如这条中国人民的老朋友威胁要大打打核战争 的新闻。 算法把它以 97.7% 的概率分给了主题 3,2.3% 的概率分给了主题 7。主题 3 的关键词是:

    south north court china military death tornado service million storm

    主题 7 的关键词是:

    nuclear plant power japan million carbon radiation china water minister

    可以看到这条新闻和主题 3 中的“南北”、“军事”、“中国”、“死亡”这些信息联系在一起,和主题 7 中的“核”、“中国”联系在一起。 应该是因为我的数据集中与北朝鲜核问题相关的新闻只有不到 10 条,而 10 个主题的划分并不够细致,所以关于“朝核问题”或者“核武器”的这样的主题并没能被分离出来。但可以看到即使是这样结果也是很 make sense 的。

    那我们就来看看 pLSA 模型是怎么回事吧。和很多模型一样,pLSA 遵从 bag-of-words 假设, 即只考虑一篇文档中单词出现的次数,忽略单词的先后次序关系,且每个单词的出现都是彼此独立的。 这样一来,我们观察到的其实就是每个单词 \(w \in W\) 在每篇文档 \(d \in D\) 中出现的次数 \(n(w,d)\)。 pLSA 还假设对于每对出现的 \((d,w)\) 都对应着一个表示“主题”的隐藏变量 \(z \in Z\)。 pLSA 是一个生成模型,它假设 \(d\)\(w\)\(z\) 之间的关系用贝叶斯网络表示是这样的(从 [Blei03] 偷的图):

    image0

    实心的节点 \(d\)\(w\) 表示我们能观察到的文档和单词,空心的 \(z\) 表示我们观察不到的隐藏变量,用来表示隐含的主题。图中用了所谓的“盘子记法”, 即用方框表示随机变量的重复。这里方框右下角的字母 \(M\)\(N\) 分别表示有 \(M\) 篇文档,第 \(j\) 篇文档有 \(N_j\) 个单词。每条有向边表示随机变量间的依赖关系 ...

  2. Expectation-Maximization(EM) 算法

    Expectation-Maximization 算法是统计学中用来给带隐含变量的模型做最大似然(和最大后验概率)的一种方法。EM 的应用特别广泛,经典的比如做概率密度估计用的 Gaussian Mixture Model。这两天我或许还会写 p 的笔记放上来,也是 EM 应用的例子。

    下面我会先解释 EM 算法要解决的问题,然后直接给出算法的过程,最后再说明算法的正确性。

    问题

    首先我们定义要解决的问题。给定一个训练集 \(X=\{x^{(1)},…,x^{(m)}\}\),我们希望拟合包含隐含变量 \(z\) 的模型 \(P(x,z;\theta)\) 中的参数 \(\theta\)。根据模型的假设,每个我们观察到的 \(x^{(i)}\) 还对应着一个我们观察不到的隐含变量 \(z^{(i)}\),我们记 \(Z=\{z^{(1)},…,z^{(m)}\}\)。做最大对数似然就是要求 \(\theta\) 的“最优值”:

    \begin{equation*} \theta=\arg\max_\theta{L(\theta;X)} \end{equation*}

    其中

    \begin{equation*} L(\theta;X)=log{P(X;\theta)}=\log{\sum_Z P(X,Z;\theta)} \end{equation*}

    想用这个 \(\log\)\(\sum\) 的形式直接求解 \(\theta\) 往往非常困难。而如果能观察到隐含变量 \(z\) ,求下面的似然函数的极大值会容易许多:

    \begin{equation*} L(\theta;X,Z)=\log{P(X, Z;\theta)} \end{equation*}

    问题是实际上我们没法观察到 \(z\) 的值,只能在给定 \(\theta\) 时求 \(z\) 的后验概率 \(P(z|x;\theta)\)[1] EM 算法就可以帮我们打破这样的困境。

    算法

    下面给出 EM 算法的过程。其中 \(\theta_t\) 是第 t-1 次迭代时算出的 \(\theta\) 值;\(\theta_0\) 为任意初值。

    Repeat until converge {

    1. (E-step) 计算 \(P(Z|X;\theta_t)\) 以得到

      \begin{align*} E_{Z|X;\theta_t}[L(\theta;X,Z)] &:= E_{Z|X;\theta_t}[\log{P(X,Z;\theta)}] \\ &= \sum_Z P(Z|X;\theta_t) \log{P(X,Z;\theta)} \end{align*}
    2. (M-step)

      \begin{equation*} \theta_{t+1} := \arg\max_\theta E_{Z|X;\theta_t}[\log{P(X,Z;\theta)}] \end{equation*}

    }

    对,就这么短 ...

  3. [POJ1771] Elevator Stopping Plan

    Description

    ZSoft Corp. is a software company in GaoKe Hall. And the workers in the hall are very hard-working. But the elevator in that hall always drives them crazy. Why? Because there is only one elevator in GaoKe Hall, while there are hundreds of companies in it. Every morning, people must waste a lot of time waiting for the elevator.

    Hal, a smart guy in ZSoft, wants to change this situation. He wants to find a way to make the elevator work more effectively. But it’s not an easy job.

    There are 31 floors in GaoKe Hall. It takes 4 seconds for the elevator to raise one floor. It means:

    It costs (31-1)*4=120 seconds if the elevator goes from the 1st floor to the 31st floor without stop. And the elevator stops 10 second once. So, if the elevator stops at each floor, it will cost 30*4+29*10 = 410 seconds (It is not necessary to calculate the stopping time at 31st floor). In another way, it takes 20 seconds for the workers to go up or down one floor. It takes 30*20 = 600 seconds for them to walk from the 1st floor to the ...

  4. [BHOJ10235] 窗口取数

    时间限制:5000 ms
    内存限制:65535 KB

    描述

    有一串整数在排队……

    有N个整数,你有一个可以框住M个连续段整数的木框,现在你想知道,对于这个队列中任意的连续M个整数,最大和最小的整数是哪个?

    例:(M大小的窗口向右滑动)

    1 2 3 2 1   M=2
    1 2    MAX 2  MIN 1
    2 3    MAX 3  MIN 2
    3 2    MAX 3  MIN 2
    2 1    MAX 2  MIN 1
    

    最后需要输出的是两行:

    1 2 2 1
    2 3 3 2
    

    输入格式

    第一行包含一个整数T,表示有T组测试数据; 以下每组测试数据格式: 第一行包含2个整数N,M表示有N个整数在排队,取连续M个整数。 第二行包含N个整数。 其中N不大于1,000,000,M不大于N。

    输出格式

    按照题目描述格式输出结果,第一行为MIN,第二行为MAX

    问题来源

    软件学院07级数据结构第二次测试

    题解

    很久不考虑算法问题了的说……当然也好久不写解题报告了。上面这题让我体会到久违了的思考的乐趣(i.e.我废掉好久了>_<)

    最显然的解法是利用平衡树始终保持木框内M个数的有序状态,大体是O(NlogM)的复杂度。这个不用多说。

    问题是:能否找到O(N)的解法?在读下去之前你可以好好想想。

    我纠结了好久,终于……也没想出来- – 尽管想出很多优化,终究还是不能达到要求。网上搜了下,看到 CS大牛csdn 上有人给出了一个解法(你也可以在读完全文后再回头看这一段):

    是可以到o(n);

    编程之美上有一个类似的问题:”队列中取最大值操作问题”;
    实际上窗口移动就相当于对队列做了一次出队与入队操作,所以lz这道题可以套用该解法;

    书上是使用两个栈来模拟队列,假设为分别 A,B;

    1) 当入队的时候,push A; 2)

    当出队的时候

    1. 若B非空, pop B,
    2. 若B为空,则先将A中的元素依次 pop 并 push 到 B,再 pop B;

    这样,就使用两个栈达到了队列的功能;

    同时,对于单个栈,由于 pop, push 都是在栈顶进行的,所以每个栈都可以方便地维护自己的最大值与最小值在栈内的索引;
    以最大值为例;
    max_idx 保存栈内最大值的索引;
    另使用一个跟栈的最大长度一样的数组 idx , idx[i] 表示栈的索引范围在0到i-1的元素中的最大值的索引为 idx[i] ;
    1. 当push的时候,比较栈顶元素与栈的已保存的最大值,
    2. 若栈顶元素大于已保存的最大值,那么 idx[top]=max_idx,max_idx=top;
    3. 若栈顶元素不大于已保存的最大值,那么 idx[top]=max_idx (书上是 idx[top]=-1);
    4. 当pop的时候, max_idx=idx[top] (书上是先比较 topmax_idx ,若 top==max_idx ,则 max_idx=idx[top] );

    具体到这个题目; 可以使用两个长度为m的栈来模拟窗口;

    1. 将前m个元素依次push到栈A;
    2. 移动窗口就相当于分别进行 pop B 与 push A 操作;
    3. 窗口的最大值 == max[A.items ...
  5. [NOIP05] 篝火晚会

    描述

    佳佳刚进高中,在军训的时候,由于佳佳吃苦耐劳,很快得到了教官的赏识,成为了“小教官”。在军训结束的那天晚上,佳佳被命令组织同学们进行篝火晚会。一共有n个同学,编号从1到n。一开始,同学们按照1,2,……,n的顺序坐成一圈,而实际上每个人都有两个最希望相邻的同学。如何下命令调整同学的次序,形成新的一个圈,使之符合同学们的意愿,成为摆在佳佳面前的一大难题。

    佳佳可向同学们下达命令,每一个命令的形式如下:

    (b1, b2,… bm -1, bm)

    这里m的值是由佳佳决定的,每次命令m的值都可以不同。这个命令的作用是移动编号是b1,b2,…… bm –1,bm的这m个同学的位置。要求b1换到b2的位置上,b2换到b3的位置上,……,要求bm换到b1的位置上。

    执行每个命令都需要一些代价。我们假定如果一个命令要移动m个人的位置,那么这个命令的代价就是m。我们需要佳佳用最少的总代价实现同学们的意愿,你能帮助佳佳吗?

    输入格式

    输入文件fire.in的第一行是一个整数n(3 <= n <= 50000),表示一共有n个同学。其后n行每行包括两个不同的正整数,以一个空格隔开,分别表示编号是1的同学最希望相邻的两个同学的编号,编号是2的同学最希望相邻的两个同学的编号,……,编号是n的同学最希望相邻的两个同学的编号。

    输出格式

    输出文件fire.out包括一行,这一行只包含一个整数,为最小的总代价。如果无论怎么调整都不能符合每个同学的愿望,则输出-1。

    数据规模

    对于30%的数据,n <= 1000;

    对于全部的数据,n <= 50000。

    题解

    至此我就算做完了NOIP05提高组的全部四道题,发现除了第一题外其它题都不水,对于我这样的水平来说很值得一做。过河的状态压缩我想了好久;本题优化方法较过河简单,但也需要动动脑子;至于那个等价表达式则是典型的ws题:思想简单(特值法+用栈求表达式的值),但实现起来却比较繁琐,细节硕多,稍不留神就会出错,我前后一共提交了5次才AC(得到的分数分别是20、30、40、90、100)。还好这些题都是自己独立搞出来的。顺带一提,等价表达式取特值时并不像很多人说的要多个,一个足矣,当然不要取太特殊的,比如取a=1,-2,-3,0这样的就很容易被强数据阴掉,但要是取个a=-5.65742它不就没治了;同时B4数据中括号不匹配的情况。

    当然这都是题外话,下面言归正传。

    首先需要看到的是,虽然佳佳下达的命令形式很ws,但是在求总代价的时候却完全不需要管它。显然,在佳佳下达完一系列诡异的命令后,最后有几个人离开了原来的位置,这种情况下最小代价就是几(为什么?)。看清了这一点,问题就转化为:要使得所有人满意,最少需要让几个人离开原来的位置?

    我们先考虑无解的情况。把每个人看成无向图中的节点,两人相邻则连一条边。当n个人以某种次序围坐成一个圈的时候,每个节点的度一定都是2。而这种状态一定是初始状态通过若干次次序调整能达到的,即一定有解。那么无解的情况就一定是,根据同学们的希望构图后有同学的度不为2。这样,我们只需要构图,然后看是否所有节点的度都为2就可以判断是否有解了。

    如果有解,下面就需要计算最小代价了。对于我们构得的图,DFS(1)后一定得到唯一的一个序列。例如1,5,3,2,4。我们现在就需要比较它和初始状态1,2,3,4,5,看有几个人离开了原来的位置。但这个序列实际代表的是一个环,而且方向正反有两种(即1,3,5,2,4和4,2,5,3,1应该是等价的),我们就需要把初始序列正反分别“转”N次(即1,2,3,4,5; 5,1,2,3,4; 4,5,1,2,3; 3,4,5,1,2; 2,3,4,5,1 以及 5,4,3,2,1; 1,5,4,3,2; 2 ...

Page 1 / 5