奈落落

Posted on 2019-05-312019-06-01 by chiccs

这一篇不讲武功，只讲想法。

前几天看了一篇 NIPS 2017 的文章<Deep Hyperspherical Learning>。很显然，作者也想到了 $S^{n-1}$ 上的内积和测地线的性质。看到这篇文章的第二节的前两段的时候，我觉得自己不用再写这些东西，直接抱大腿、用现成的模型就行。但作者紧接着只是介绍自己提出的 SphereConv 这个卷积层。

（这个作者在 NIPS 2018 又有一篇文章 <Learning towards Minimum Hyperspherical Energy>。作者又想了一个电子分布能量的概念，其实就是类比电场的多体问题的稳态解。然而这种东西只是一种根据问题的语义自定义的场而不是空间本身的性质。）

很多从无到有的事情还是要自己做。

很多 word embedding 模型在训练的时候都做这样的事情：首先给每个词指定一个随机向量，然后根据总体损失函数的向量场更新词向量。如果用 word as point 的观点，这就是说词代表的点在一个 n 维流形做有限次的跃迁。

另一方面，假定这些 word embedding 模型是收敛的。原则上说，对于任意的初始值，词向量在训练后都能保持内积，也就是说对于任意的两个词向量它们的内积是不变的。其次，对于不同的初值，词的向量表示很有可能也是不同的。这是由于词汇空间和流形不等势造成的稀疏性。对一个给定的初值向量的某些分量施加一个无穷小的微扰，得到的结果应该是相同的。因此这暗示：

n 维流形上的每个点都对应一个词汇空间的元素。

紧接着做出连续性假设：

每个词汇空间的元素在 n 维流形上对应的点集都是连续的，或是不相交连续点集的并。

这就是说：

每个词在 n 维流形上都具有非零 (Lebesgue) 测度。

超重当

Posted on 2019-05-222019-05-23 by chiccs

有了“测地线”的概念，就可以在 $S^{n-1}$ 上解释一些模型的行为，比如位置语言模型 (Positional Language Model)。

现在，PLM 的假设 “a term at each position can propagate its occurrence at that position to other positions within the same document through a proximity-based density function” (Lv and Zhai, 2009) 是内蕴的。一个词对应 $S^{n-1}$ 上的一个点，沿着测地线到达另一个点，产生语素变换的损失。所谓的 “virtual document” 就是在指定距离处的有限点集。用“word as a point”这个强假设，代替原文中有点勉强的假设，还是比较划算的，因为可以定义内积和距离。
proximity-based kernel function for propagation 是关于路径的损失密度函数。也许可以写成路径积分，也许不是测地线。反正就是类似的意思。

一些查询扩展(query expansion)的方法也可以用这个套路解释，但意义不大。PLM 还是基于词的多项分布，用的是计数测度，所以当时来看，结果没有提高很多，很正常。

所以接下来，就是利用 $S^{n-1}$ 的性质得到更好的估计。过段时间再写。

白山桃

Posted on 2019-05-192019-05-19 by chiccs

$U,V \in S^{n-1}$ ，求连接 $U$ 和 $V$ 的测地线(geodesic)的长度。

这其实很简单，只需要一个结论： $S^{n-1}$ 上两点间测地线一定被过圆心的大圆覆盖。然后使用 $g=r\theta$ 计算小于等于 $\pi$ 的那部分弧长。通过 $U$ 和 $V$ 的内积可以得到角度。

不过关心的是另外一件事情：假使两个语素被映射到某个流形上，度量它们接近程度的应该是测地线而不是余弦相似度，cosine similarity 只是在映射到 $S^{n-1}$ 时的特殊情况。因为测地线可以有另一种定义：其上每一点都指向局部变换代价最小的方向。

想要推动一件事情的发展，不需要很多勉强的创新，而是观念上的改变，还有一些传播的技巧。不管这样的改变是正确的，还是有争议的。坦白说最近这些东西都是用写作治疗自己，我不是很在意内容的对错（但为了对同行负责还是把个人主页上 blog 的链接删掉了）。不过我想还要写一段时间，因为一些重要的内容还没出现。

扇沟流

Posted on 2019-05-142019-05-16 by chiccs

有很多的检索模型，都使用这样的策略：首先使用一种简单的检索模型（比如 LM, BM25 和 TF-IDF）找出最接近 query 的前 N 个结果（比如 top 100/500/1000），然后再使用自己的模型重新对这些结果打分并排序(rerank)。

这些模型可以分成两类：对 N 不敏感的和对 N 敏感的。

随着 N 的增大，对 N 不敏感的模型的性能整体上只会在一个很小的区间内波动，这称为它们具有“收敛性”。对 N 敏感的模型的性能一般和 N 的取值是负相关的，也许 N=100 的时候性能很好，但是当 N 增大数倍之后结果就变得惨不忍睹。

为什么会有这种区别呢？这只取决于这些模型是否是词汇空间上良好定义的测度。正确的测度会因为大数定律的限制而变得稳定，不标准的度量会因为有偏的估计而失常。Batch normalization 为什么有用呢？也许其实和什么“独立同分布假设”之类关系不大，只是为一堆杂乱无章的东西(batch)强行定义了一个良好的概率测度(normalization)。

所以想要检验没有理论基础的模型，最好不要用 two-stage strategy，而要浪费大把时间直接 rank the whole collection。不然文章发出来，最多也只是有人引用、没人敢用。

琴月

Posted on 2019-05-082019-05-08 by chiccs

$V$ 在 $S^{n-1}$ 均匀分布， $U$ 是其上的固定点， $U \cdot V \sim ?$

定义累积分布 $F(X)=Pr(U \cdot V < x)$
以 $U$ 的正方向为轴，想象用一个垂直于 $U$ 并与其它 $n-1$ 个坐标轴平行的超平面，将 $S^{n-1}$ 截成两个部分
满足条件的点集构成 $S^{n-1}$ 上非球缺的部分

$F(x)=1-\frac{\frac{n\pi^{\frac{n}{2}}}{\Gamma(\frac{n}{2})}I_{1-x^2}(\frac{n-1}{2},\frac{1}{2})}{\frac{n\pi^{\frac{n}{2}}}{\Gamma(\frac{n}{2}+1)}}$

$I$ 是正则化不完全 Beta 函数

$I_{1-x^2}(\frac{n-1}{2},\frac{1}{2})=\frac{\int_{0}^{1-x^2}t^{\frac{n-3}{2}}(1-t)^{-0.5}}{\int_{0}^{1}t^{\frac{n-3}{2}}(1-t)^{-0.5}}$

$f(x)\propto (1-x^2)^{\frac{n-3}{2}}$

简单修改 $V$ 的分布条件，结论对 $S^{n-1}$ 上的任意分布几乎成立。从某种意义上说，所有使用 word embedding 而不考虑维度影响的 NLP/IR 模型都是有问题的。

开始名为新·语义检索的转向。

九伤

Posted on 2019-05-072019-05-07 by chiccs

$V$ 在 $S^{2}$ 均匀分布， $U$ 是其上的固定点， $U \cdot V \sim ?$
定义累积分布 $F(X)=Pr(U \cdot V < x)$
只考虑 $x \in [0,1]$ 的情形，其它区间置零截断。
满足条件的点集构成 $S^{2}$ 上的非球缺，计算它们的测度
$F(x)=\frac{2\pi x}{2\pi}$
$f(x)=\frac{dF(x)}{dx}=1$

荒咬

Posted on 2019-05-052019-05-05 by chiccs

$V$ 在 $S^{1}$ 均匀分布， $U$ 是其上的固定点， $U \cdot V \sim ?$
定义累积分布 $F(X)=Pr(U \cdot V < x)$
考虑 $x \in [0,1]$ 的情形，其他类似
满足条件的点集构成 $S^{1}$ 上的弧，取它们的测度为 $S^{1}$ 的弧长
$F(x)=\frac{2arcsin(x)}{2\frac{\pi}{2}}$
$f(x)=\frac{dF(x)}{dx}=\frac{2}{\pi \sqrt{1-x^2}}$

TREC CAR 2018 随想

Posted on 2018-12-042018-12-04 by chiccs

结果如何？直接看图吧。

今年春节的时候就想开发一个比去年更好的方法。一直被阻拦，只能断断续续地做实验。在 cikm 交稿之后，离 trec 的 deadline 只剩一两周的时候匆忙继续。发现了 Wikipedia article information 可以增强性能。总算有东西可以提交。

这个 task 有几个比较奇特的地方：

一是输入输出格式比较复杂，要自己用 trec-car-tools 从 cbor 里面读取每个 query path。这两年还有区分 query 的类型，比如 outlines（文章标题）, hierarchical（最具体的章节路径）。输出的时候要加上 “enwiki:” 或者 “tqa”这样的前缀。说实话不能理解为什么要这么折腾。

二是这个任务的 evaluation 其实是有偏差的 (biased)。评估方式分三种 Automatic, manual 和 lenient。Automatic 就是用维基百科的章节路径当作 query，然后章节里面包含的段落当作 ground truth。 manual 和 lenient 是按照 trec 标准的人工评测。个人发现 SDM 类的模型经过充分的调参以后可以在 automatic 上取得 state-of-the-art 的结果，但是 manual 和 lenient 的评测结果和其他方法比就还有差距。这其实反映了统计语言模型和 neural ranking model 对 concept salience 的假设是不一样的。

三是我这次用 Wikipedia article 的信息作为一个特征输入，由于程序的一个 bug，这个部分全部输出为0，结果竟然还比没有集成这个特征的原始模型提升了至少 15%。这起码说明能找到对应 Wikipedia article 的段落更有可能成为答案。我感觉 Laura 可能已经发现了这个问题，后续的数据集应该会变得更加 Wikipedia-free。

反正结果就是这样，这次其他的队伍用了很多成熟的 learning to rank 的方法，再加上一些 hand-crafted feature 和 query expansion mechnism（比如 RM3。。。）。取得好的结果是意料之中。恭喜。

我十月份申请的美签居然还在 administrative processing! 最后没去参加 trec。只好给 Laura 发邮件解释原因，给 hilton 发邮件取消房间，交 no-show charge，取消机票。我很讨厌处理这种琐事，这次耗尽了所有精力。 us visa office seems to believe that the higher education a Chinese get, the more dangerous is he or she to the United States. This is truly ridiculous and racist. 另外美国香港领事馆是我见过的服务态度最恶劣的领事馆，只能说人在做天在看。非常失望，这辈子都不考虑去美国。

总的来说今年的这件事算是彻底的失败了。但这不是我的失败，也不是我的耻辱。我只是在有限的时间里做了自己能做的所有事情。有些阻碍不是我能跨越的，有些装睡的人不是我能叫醒的。如果一百年以后的哪天我死了，我的墓碑上也许会有一句话：此人此生光明磊落。

Comment on EYRE’18

Posted on 2018-11-062019-03-17 by chiccs

EYRE’18 就是 “1st International Workshop on EntitY REtrieval (EYRE ’18)”

因为我那天在都灵睡过头了，错过了一些 presentation，所以只谈几个我感兴趣的。

1. Graph Analytical Re-ranking for Entity Search. Takahiro Komamizu

文章和之前评论的内容差不多，我甚至有点怀疑作者是看了我的评论才把这个方法叫做 “Personalized Pagerank based score distribution”。这个方法是否本质有效，不想说了，最近心情不好。

（说点不好听的吧，~~这其实是我三年前玩过的东西~~，研究我的 github 项目的人会发现，我的框架里面总有一个 createGraph 模块，就是给这个东西用的。为什么我没写文章讲这件事呢？自己想想吧）

Anyway, consider entities together 是有价值的想法。

2.Annotating Domain-Specific Texts with Babelfy: A Case Study. Michael Färber, Kristian Noullet and Boulos El Asmar

对文章内容不评价。讲一些趣闻：年初我参加 ECIR2018 找 Adam Jatowt 尬聊 NTCIR AKG 的时候看到 Michael 也在旁边，当时还以为他是 Adam 的学生，抢占了他几分钟时间，真是抱歉。。。个人看好这个小帅哥，感觉他是个比较踏实的人。

3.Graph-based Reranking Approach for DBpedia Entity Search. Bo Ma, Yating Yang, Tonghai Jiang, Xi Zhou and Lei Wang

我个人认为，作者提出来的方法本质是借鉴 Discounted Cumulative Gain 的思想来 rerank 所有结果。当然，他在 slides 里面说 “more links, more important”这种解释也还算说得过去，其实和 DCG 的思想是一样的。不过比较讽刺的是这个模型在 QALD2 和 SemSearch 上的结果很差，有点违背了他的解释。

为什么大部分模型都会有 “results are dataset specific” 的情况呢？不想说了，最近心情不好。

update 2019/03. 最近考虑了一下，感觉更像是从 pagerank 这类基于重要性的模型中得到灵感。NDCG 作为一种评价方式和 pagerank 有一些形式上的相同，这反而让我觉得有些意思。

4.Exploring Summary-Expanded Entity Embeddings for Entity Retrieval. Shahrzad Naseri, John Foley, James Allan and Brendan T. O’Connor

训练了一个 word-entity 的 embedding，embedding 的分数和 FSDM 的分数加权平均。不想说什么。

我觉得最不高兴的点就是这些人好像根本没有注意到 term-based retrieval model 的地位。另外好像也没读我的 ECIR 和 ICTIR 的文章，更别说引用了。（这并不是说我的文章有多么好或多么重要，而是在你准备做相关的研究的时候至少应该看看最近这个领域的人在谈论什么。）

总的来说这次研讨会的 entity search 部分就像一个大型民科自嗨现场，没有特别有效的进展。不过 Prof. Gong Cheng 花了很多时间尽力让这个会议变得正式和专业，作为开拓者劳苦功高，什么都干不了的小弟在此表示衷心感谢和敬意。期待下次变得更好。

Information need & supply

Posted on 2018-09-092019-03-16 by chiccs

For a fixed retrieval model that satisfies users’ information need to some extent

Margin: a unit of incremental data size may increase the “dimension” of the data, which makes it more difficult for the model to handle. Thus non-positive margin.

For a fixed data producing model that provides “information supply”.

Margin: a unit of incremental data size may increase the “dimension” of the data. In this situation, a new “basis” can be used to generate more “new deep” data. Thus non-negative margin.

Intersection: the best performance(utility) bound for a fixed retrieval model and data generator.

chiccs's Blog

Time is Scarce, Life is Short

Category: Research

奈落落

超重当

白山桃

扇沟流

琴月

九伤

荒咬

TREC CAR 2018 随想

Comment on EYRE’18

Information need & supply