氧气

Posted on 2020-07-102020-07-10 by chiccs

Math, theory and observation.

只要我想，我可以试着用形而上学重写一遍信息检索的基础：从黑格尔和费尔巴哈的著作里面搜刮几个词语，把容易理解的概念和演算法则说成是“理性精神”，把那些我看不懂的东西推说是“客观精神”，模型和算法就叫做“精神运动”；再花上钱或者人情，找个“AI自媒体”的公众号放上一篇像模像样的通告，取上诸如《XX点赞，大佬力挺，最新超越blahblah！》的标题，一样把麻瓜耍得团团转（所以我从未订阅这些公众号，作为一个平凡人，希望每天早上一睁眼就吃点好的，而不是面对那么多莫名其妙的“疾风”。如果按照新闻从业人员的职业规范，这些家伙没有一个能够上岗）。

然而自我陶醉的理论最终要接受现实的考验，在这之间架设名为评估的桥梁。科学是求错不犯错而不是求对，否则就容易陷入重言式的陷阱。我见过几篇研究“可解释性”的文章，粗略扫描我就知道他们可能进入了一个无法自拔的循环：在自己设计的体系里面不管怎么说怎么测试最终都是自己的结论对。就好比如果对 SDM 穷举参数值进行优化，它必然胜过 LM——单从数学的形式上说后者是前者退化的情况。这样的比较是毫无意义的，而要验证它们对于现实不同的观察和理解，再反推出结论。顺带一说，有一家国内公司之前招聘过专门研究“可解释性”的研究员，一开始我很赞赏该公司领导的眼界和魄力，但转念一想我就担心起担任这个职位的人，因为“解释性”是真正苍白的深渊。除了少数几个得到验证的东西以外，大部分的模型都是不知正误的，又如何在此基础上“解释”呢。Yann Lecun 最近在 Twitter 上评论 “PULSE 风波”说，用白人的数据集训练出来的模型当然结果输出是白人，用黑人的数据集训练出来的模型当然结果输出是黑人。这是很实在的话，但会让人怀疑这些理论到底是“智能”还是别的东西。

最近有一位老师在推广自己在几何方面的成果，讲解比较深奥的数学知识，顺便提到一些和“深度学习”可能的联系。他老人家传授的数学正确而且精彩，晚辈瞎掰的一些东西可能也要学习借用类似的步骤自圆其说，但每个学科都有自己的见解，否则这个世界只需要数学这一种科学了。有些文章的标题，自己迫不及待地加上了不少激进的词汇，结果还是老样子。这让我想起武侠电视剧的主角在荒郊野岭捡到一本“武林秘籍”之后对着空气瞎比划几下盯着自己的爪子得意傻笑的场景。从这方面思考，解释不仅是解释，否则某个“正确的解释”只会产生一样的结果，某种意义上说等于没有解释。所以求的不是解释，而是理解上的前进或不同。

根(Dead City, Mad Man)

Posted on 2020-07-012020-07-01 by chiccs

野火烧不尽，春风吹又生，练武先修德。

我只想做平庸的人，但所感受到这个世界的一些真实的恶意，使我只能一边记叙黑暗的片段，一边做超越想象的事情。

大蛇薙

Posted on 2020-05-012020-05-01 by chiccs

“流形检索”提要。

最近，我写的一篇文章进了 SIGIR 2020 这个会。它很短，对我来说是一个“锚”，这样以后写作的时候起码有资料可以引用，不用像民科一样没有根据地长篇大论。

这篇文章只想讲一件事：在连续的集合上可以定义“语言”。如此，所谓的“神经排序”就是连续点集上的统计语言模型，因此所谓的“end-to-end” 就是内蕴的性质。“结构”(structure)与“测度”(measure)是“新语义检索”的基础，它们分别概括了“表示法”(representation)和“模型”(retrieval model)这两个传统的概念。它必须收敛，收敛性是模型正确性和性能的一种估计。有些公司的什么“技术博客”总喜欢吹嘘“数据决定模型性能”这类有机械唯物主义意味的观点，奉之为“指导思想”，把自己的命运完全交给收集用户偶然的行为（这些用户行得通，那些用户呢？当然可以说自己的模型都能奏效，但这就不只是数据的问题），还有对 learning-to-rank 望文生义的涂改，不想多说，专心做生意吧。

流形上的概率论很早就有了，这与信息几何(information geometry)的发展有关，只是它们研究的大多都是参数空间的分布，本文反而考虑变量空间的事情。以前那些形如“xx learning/clustering on manifold”的文章，为了让梯度可以直接在曲面上更新，一定会用指数映射之类的方法。这些画蛇添足的内容我全都放弃了。从某种意义上说，直接更新梯度之后再把向量归一化再算测度，是一种“传输”，这暗示了那些 xx norm 之类的方法真正的含义。还有一些譬如 ngram 表示之类的问题，可以在复流形上解决，也可以用一些像向量一样的东西代替。

其实，这也和量子检索(quantum retrieval)有关，只是前面的人比较极端，试图用量子力学直接概括整个领域。

这篇论文的写作和发表可能得到了无法知晓的支持，在此顺带以真诚致谢。我从不打算靠做此类研究谋生。这个时代，智力正常的人都应该想出一百种赚钱的方式，在每个行业只要花足够多的时间和毅力，最后都能得到可观的财富，做到底就知道这其实是国家实力发展的结果。在一个动荡的社会里很难静下心来做事，这是我暂时离开香港的原因，无法一直在负面的情绪中工作和生活，这会扭曲人的心灵，神智将和社会一样撕裂。但我会认为，这篇论文是给香港社会的答谢，尽管它没有了不起的内容，我也只是很渺小的一个人，能够没有负担地走出去。

这是“拳皇”系列博文的结束，台湾知名格斗游戏选手“Nikolai 保力達”的视频给了我很多的乐趣，过段时间再写下个系列。

鬼烧

Posted on 2019-11-092019-11-09 by chiccs

所谓“策略随机检索” (Strategic Random Retrieval)

本来，在这个系列的最后，我准备放上几个 runs，进行期待已久的“清算”。可是有个小朋友给我分享了自己好友在父母长达十余年外遇、家暴的历史下艰难生活的故事，告诉我要“be kind to others”。所以那种“灭门”的事情以后再说。现在想写关于 diversity 的故事。

这个世界充满了优胜劣汰，所有设计模型的人都想着如何 do the best estimation given observations. 供给信息的人则想着如何 maximize the importance of their features. 所以系统忙着 learning to rank，供给者忙着做 SEO，而用户则忙着辨认真切的结果和“充值”的结果。这个三方系统的内部成本在这样的内耗中不断增加。正确性和相关性、以及任何试图学习这两者的性质，最后都失去意义。

一种没有排序的检索从随机返回任何结果中产生。为了满足愉悦和可靠的目标，在最开始它可以从向传统的检索施加有策略的扰动开始。这种扰动可以是一种约束，也可以是一种行为。

**（当然我说的不是“转化率”。敢把转化率当成吹嘘的资本写进每次署名七八个作者的的学术论文里面也就只有国内几个胆子大的公司才能成就如此伟业。）

七十五式改

Posted on 2019-09-142019-09-14 by chiccs

A toy retrieval model (H-RM0).

查询 $Q=q_1 q_2 .. q_n$ ，文档 $D=t_1 t_2 ... t_m$ 。假定 $S^{N-1}$ 上有 $n$ 个初始点各自符合分布 $\mathcal{N}(\mu_i , \sigma_i)$ ，还有 $m$ 个点表示文档词的位置。
选取 $S^{N-1}$ 上任意一个度规。对每个初始点和文档点，计算距离 $M_{ij}$ 。把 $M_{ij}$ 作为分布的变量，计算分数 $p_{ij}$ 。
对每个初始点 $i$ 使用“路径选择器” $M_{p}^{i}(p_{i1},p_{i2}, ... , p_{im})$
返回 $\sum {log M_{p}^{i}}$

这其实是什么呢，去掉了 learning to rank 层，并且相差一个输入线性变换的 K-NRM (Xiong et al., 2017)。K-NRM 对 “每一行” 都使用 $K$ 个核函数。如果设计得当， $K$ 也可以是内生变量。

本系列 posts 只用一些简单的概念讨论检索的输入和表示，还有两篇结束。下个系列使用几何工具进行信号的变换，它们对应一部分“隐层”的行为。

轹铁

Posted on 2019-08-152019-08-16 by chiccs

LambdaRank，与星形集的上同调。

节选 <Learning to rank with Non-smooth cost functions> (CJC Burges et al., 2007)

给定查询 $Q$ 与文档集，排序模型对文档集的所有文档打分，并产生长度为 $n$ 的 top- $n$ 结果（如果使用 two-stage strategy）。任何对此的重排序都是施加在其上的置换，因此这些结果关于所有重排序函数形成一个置换群。

LambdaRank 假定有隐式损失函数 $C$ 满足 $\frac{\partial_C }{\partial_{s_j}}=-\lambda_{j}(s_1,l_1,...,s_{n_i},l_{n_i})$ 。 $s_j$ 是搜索结果中第 $j$ 位的文档的排序分数。

显然函数 $C$ 必须是在空间 $(s_1,l_1,...,s_{n_i},l_{n_i})$ 中良好定义的，应该满足： $C=\int \lambda_{j} d_{s_j}, \forall j \in {1..n_i}$

想象在 $(s_1,...,s_{n_i})$ 张成的空间中，任意 $\lambda$ 都是定义在此空间的函数，于是上式是指 $\lambda$ 函数沿此空间内给定两点间的任意路径积分都能“还原”到损失函数 $C$ 。满足这样性质的空间称为“星形集” (star-shaped set)，这样的集合中存在一点，使得集合内所有点与该点的线段都属于该集合。进一步又有，

(1) $\begin{equation*} \frac{\partial_{\lambda_j} }{\partial_{s_k}} =\partial \frac{\frac{\partial_C }{\partial_{s_j}}}{\partial_{s_k}}=\partial \frac{\frac{\partial_C }{\partial_{s_k}}}{\partial_{s_j}}=\frac{\partial_{\lambda_k} }{\partial_{s_j}} \end{equation*}$

中间的等号成立是因为交换微分顺序不改变结果。所以关于所有 $\lambda_j$ 函数的 Jacobian 矩阵是对称的。如果损失函数 $C$ 是凸的，那么 $C$ 关于 $(s_1,...,s_{n_i})$ 的 Hessian 矩阵就是对称正定阵，自动满足以上条件。希望损失函数是凸函数的原因是因为这样可以使用梯度下降法找到最优解（……………..）

现在用微分拓扑的角度，考虑在空间 $(s_1,...,s_{n_i})$ 中的向量 $(\lambda_1,...,\lambda_{n_i})$ ，定义 1-形式 $\lambda=\sum \lambda_j d_{s_j}$ 。 $d_{s_j}$ 可以看作是一个“有向的”微元。 LambdaRank 的假定可以写成 $\lambda=dC$ ， $d$ 是外微分。想要找到满足假定的一般的 $\lambda$ 不容易，但是庞加莱引理 (Poincare’s lemma) 给出一个结论：在星形集中， $d\lambda=0$ 当且仅当 $\lambda=dC$ （每个闭形式都是恰当形式）。因此现在只需要寻找满足 $d\lambda=0$ 的 $\lambda$ 函数，具体来说，就是寻找合适的每个分量 $\lambda_j$ 。而这个条件，就等价于上面的 “Jacobian 条件”。

月相

Posted on 2019-07-192019-07-20 by chiccs

考虑在 $\mathbb{R}^n$ 上的函数 $f$ ，现在定义一个在 $[0,2\pi]^n$ 上的对应映射 $p(\textbf{x})$ ，通过以下方式

$p(\textbf{x}) = \sum_{k_i=-\infty}^{\infty}f(\textbf{x}+2(k_1,k_2,...,k_n)\pi)$

这样就可以有所根据地考虑在 $S^{n-1}$ 的概率测度，经过推广，也可以适用于一些简单的流形。

$S^{n-1}$ 上最简单的概率测度当然是均匀分布 $p(\textbf{x})=\frac{1}{Area(S^{n-1})}$

接着就是模仿正态分布的 $p(\textbf{x})=\frac{1}{Z}e^{-\frac{1}{2} \lVert \mathbf{x}-\mathbf{\mu } \rVert ^2}$ 。以及使用上述映射变换正态分布的结果。利用 L2 范数就会放弃一些弯曲空间的特征，可以想象这类分布的实用性一般。用测地线长度代替也许会好一些，但仍然过于平凡。还有一些可靠的分布，需要更深入的探索。

在流形上，滤波、平滑和贝叶斯推断可以有很强的联系，许多定义在离散空间的模型会有更舒展的表达。

罪咏

Posted on 2019-07-152019-07-15 by chiccs

最近信息检索社群的研究动向之一是所谓交互式检索的方法论（interactive/conversational/online + retrieval/learning to rank/blahblahblah.. ）。简单来说，就是从用户的角度来考虑检索问题，因此系统的设计和评价方式需要从用户的实际行为和反馈出发，而不是通过假设单方面推进检索的过程。

以唯物史观看待（强调这点是因为，也可以有不同的角度认为这是某几个“大佬”以个人意志带动的潮流。），这种研究兴趣的迁移是对当前自然语言处理研究的被动回应和规避：传统的信息检索研究大多和 NLP 研究一样，是在离线的数据集上评价模型。由于神经网络强大的学习能力，以及信息检索和自然语言处理的相关性，现在信息检索确实有被自然语言处理的研究狂潮淹没的隐忧或危机。IR 社群亟需重新发掘信息检索的特异性，以示区别。因此交互性作为搜索引擎最显著的特征之一便被提上日程。
交互性检索是对多个已有方向的自然扩展。以信息供给（information supply）的角度，离线数据集的标注成本实在惊人并且存在道德风险，而用户行为数据丰富而有趣。通过学习用户行为再服务用户再收集数据，产生的“乘数效应”显然是比通过学习少数标注数据再服务用户的方法要大得多。另外，这也是 “searching as learning” 观点的延伸，只是强监督信号变成了弱监督信号。
现在的信息检索研究缺乏强有力的数学基础：许多最近的研究的表述方式，除了用结果说话的“炼金术”以外，就是一些高中级别的概率统计知识加上一点微积分，再加上作者自己想象的故事，最后再添上用海量实验结果堆砌的所谓“实验分析”。如果这一点不被解决，我不觉得能有什么很重要的进展。

毒咬

Posted on 2019-06-252019-06-25 by chiccs

所谓“路径选择”。

考虑函数 $M_{p}(x_1,x_2,...,x_n)=(\frac{1}{n}\sum_{1}^{n}x_{i}^{p})^{\frac{1}{p}}$

假定 $x_i$ 是第 $i$ 条路径的分数

$M_{\infty}=max(x_1,x_2,...,x_n)$ ，这是之前使用“两个 max”的 type taxonomy aware smoothing.

$p$ 控制路径间不同的组合方式。不用多说，懂的人自然明白该怎么使用，这是一个滤波器。

最近在栖霞岭和灵隐间行走，恶雨频频。途中有人告诉我四字偈语：峰回路转。正是意兴阑珊的时候，疯人疯语，不知所谓。

轰斧

Posted on 2019-06-092019-06-09 by chiccs

Some cliches.

从 Zhai and Lafferty (2004) 开始。给定文档 $D$ 和查询 $Q=q_1 q_2 q_3 ... q_n$ ，使用 bag-of-words 表示法，首先考虑所谓的文档语言模型 (document language model)：

$P_{ml}(Q|D)=\prod_{q_i} \frac{tf}{|D|}$

接着考虑所谓的全局语言模型 (collection language model)：

$P(Q|C)=\prod_{q_i} \frac{cf}{|C|}$

平滑 (smoothing) 是说，查询 $Q$ 在 $D$ 的观测概率分布为：

$P(Q|D)=\prod_{q_i} ( (1- \lambda) P_{ml}(Q|D) + \lambda P(Q|C) )$

$P_{ml}(Q|D)$ 是所谓的局部信息， $P(Q|C)$ 代表所谓的全局信息，两者通过一个参数 $\lambda$ 加权平均。取 $\lambda = \frac{\mu}{|D|+\mu}$ 就是 Dirichlet smoothing。

十五年以后再来看这个经典的方法，至少有以下问题需要解决：

使用的语言模型比较 straight-forward
全局信息的估计比较 straight-forward
结合局部和全局信息的方式比较 straight-forward

我曾经问某位同行，为什么他们的 neural ranking model 不使用“全局信息”，对方说因为这样做没有带来什么改进。很正常，这种模型一般都有成千上万个参数去拟合结果，所谓的“全局信息” 都体现在训练过程中参数值的变化上。这和 Bayesian 需要先验知识、无视训练集的想法完全不同。

按照这个方向，想要改进一个 entity retrieval model 就等价于改进一个 document retrieval model。没几个人会做这种吃力不讨好的事情。

所以接下来，对全局集合 $C$ 做分解：

$C=C_1 \cup C_2 \cup C_3 \cup ... C_m$ 。

假定这些集合具有偏序关系 (paritial order)，画出它们的哈斯图 $H$ (Hasse diagram)。于是 $H$ 就可分解为不同的路径 (path) 组成的集合。 $H=p_1 \cup p_2 \cup p_3 \cup ... p_l$ 。对任意一条路径 $p = c_1 c_2 c_3 ... c_k$ ，重写 $P(Q|D)$ 为如下形式：

$P(Q|D)=\prod_{q_i} \left[ \lambda_0 P(q_i|D) + \lambda_1 P(q_i|C) ) + \sum_{i=1..k}\lambda_i P(q_i|c_i) \right]$

定义：

$\lambda_0 = \frac{1}{|D|+\mu + \frac{\mu_i \alpha^{i}}{n(\alpha , p)} }$

$\lambda_1 = \frac{\mu}{|D|+\mu + \frac{\mu_i \alpha^{i} }{n(\alpha , p)} }$

$\lambda_i = \frac{\frac{\mu_i \alpha^{i} }{n(\alpha , p)}}{|D|+\mu+ \frac{\mu_i \alpha^{i} }{n(\alpha , p)}}$

这就是一般化的 path-aware smoothing (PAS)。注意这里完全仅依靠对 collection 的偏序假设，没有利用到任何 knowledge graph 的信息，比如 type taxonomy 的结构。从表面的无序中寻找内在的结构，这是一个结构主义者 (structuralist) 的追求，也是结构平滑 (structure-aware smoothing) 的方法论。

FAQ:

A：为什么你的文章的结果和 DBpedia-entity v2 上面的正式结果不一样？

Q：1. 使用的 index 不同，预处理的方法不同，还有检索实现的方式不同。2. FSDM-CA 的参数取值覆盖了 SDM, MLM 和 LM 的情况，所以结果永远都是 FSDM-CA > MLM-CA > LM-CA，而我的模型的参数估计用的是 mapping-based probabilities (Hasibi et al. (2017))，所以它们的结果会好看一些。

A：FSDM-CA 和 FSDM + type (TAS/PAS) 哪个性能强？

Q：如果你愿意花费大量时间训练的话 (真的是”大量”… 反正我花了好几天都没有达到 DBpedia-entity v2 上面报告的结果) ，当然是 FSDM-CA 的结果比较好。然而，我写文章的目的是要说明 结构即先验 ，因此文章被组织成比较现有模型的性能，和它们加上这些先验知识以后的性能。事实上我的模型运行得相当快，而且性能理想。想看我打擂台的人请参考去年 EYRE 的结果。

A：你的结果有没有做过 evaluation？

Q：信则有，不信则永远无。事实上大部分对比数据的 P 值约等于 0，置信度 0.95，配对 t 检验。最难的是 FSDM 和 FSDM+type，因为使用 mapping-based probabilities 作为域的权重，这个模型不能像 FSDM-CA 那样靠覆盖特殊情况来轻松提高性能，需要花点时间调参数，这一组的 P 值在 0.02 左右。

A：这篇 blog post 怎么没用到 $S^{n-1}$ ？

Q：因为这几天我想怀旧一下。。。

chiccs's Blog

Time is Scarce, Life is Short

Category: Research

氧气

根(Dead City, Mad Man)

大蛇薙

鬼烧

七十五式改

轹铁

月相

罪咏

毒咬

轰斧