Bradley-Terry Model
Bradley-Terry Model#
Setting#
Bradley-Terry是用于成对比较的一类概率模型，核心任务是：给定一组对象，根据两两对比的结果，估计每个对象的强度。
设每个对象 $i$ 有一个正实数参数 $\pi_i>0$标识其强度，模型假设：
$$P(i> j)=\frac{\pi_i}{\pi_i+\pi_j}$$
形式等价于：
令$\theta_i=\log \pi_i$，有
$$P(i> j)=\frac{e^{\theta_i}}{e^{\theta_i}+e^{\theta_j}}=\sigma(\theta_i-\theta_j)$$，
式中, $\sigma(\cdot)$ 是logistic函数。由此，BT模型本质上是一个logistic reg. on differences.
Likelihood#
对于任意一对 $(i,j)$，每一次比较是一个Bernoulli实验，即：
$$P(i>j)=\frac{\pi_i}{\pi_i+\pi_j},P(j>i)=\frac{\pi_j}{\pi_i+\pi_j}$$
如果仅观察一次，会得到如下的结果：
若$i$获胜，其概率为：
$$P(obs)=\frac{\pi_i}{\pi_i+\pi_j}$$
若$j$获胜，其概率为：
$$P(obs)=\frac{\pi_j}{\pi_i+\pi_j}$$
实际数据通常是聚合的，即是多次观察的结果。设 $w_{ij}$ 是 $i$ 战胜 $j$ 的次数，有似然函数可以被写作：
$$L(\pi)=\prod_{i<j}(\frac{\pi_i}{\pi_i+\pi_j})^{w_{ij}}(\frac{\pi_j}{\pi_i+\pi_j})^{w_{ji}}$$
对其取对数，有：
$$l(\pi)=\sum_{i<j} [w_{ij}\log \frac{\pi_i}{\pi_i+\pi_j}+w_{ji}\frac{\pi_j}{\pi_i+\pi_j}]$$
展开：
$$=\sum_{i<j} [w_{ij}(\log \pi_i-\log (\pi_i+\pi_j))+w_{ji}(\log \pi_j-\log (\pi_i+\pi_j))]$$
整理：
$$=\sum_{i<j} [w_{ij}\log \pi_i+w_{ji}\log \pi_j-(w_{ij}+w_{ji})\log(\pi_i+\pi_j)]$$
换base，使用 $\theta_i=\log \pi_i$ 进行参数化，似然函数可以被改写为：
$$l(\theta)=\sum_{i<j}[w_{ij}\theta_i+w_{ji}\theta_j-(w_{ij}+w_{ji})\log(e^{\theta_i}+e^{\theta_j})]$$
上述似然函数可以进行如下解释：
对于每一对 $(i,j)$，对数似然的每个项：
- ${w_{ij}\theta_i+w_{ji}\theta_j}$ 是线性项，代表empirical reward，谁赢的多，对应参数就被拉高
- $(w_{ij}+w_{ji})\log(e^{\theta_i}+e^{\theta_j})$ 是归一化惩罚项
Gradient#
对于$\theta_i$求导：
$$\frac{\partial L}{\partial \theta_i}=\sum_j[w_{ij}-(w_{ij}+w_{ji})P(i>j)]$$
这可以被看作“实际胜场-期望胜场”。
图视角#
Graph Modeling#
构造一个有向加权图 $G=(V,E)$，其中：
- 节点 $V$：每个对象 $i$
- 有向边 $i\rightarrow j$ ：表示i曾经战胜过j
- 边权重 $w_{ij}$
强连通图定义：对任意 $i,j$，都存在一条有向路径 $i\rightarrow j$且$j\rightarrow i$。BT模型要求如果比较图是强连通的，MLE才存在且唯一，否则会存在dominant的$\pi$，即$\pi\rightarrow \infty$，产生完全压制。
[证明]在BT模型中，MLE存在且有限，当且仅当比较图是强连通的#
性质#
[性质1] 平移不变性
$$l(\theta+c1)=l(\theta)$$
[证明]
把所有参数同时加上一个常数
$$\theta_i\rightarrow \theta_i+c$$
不会改变任何概率
(tobeadded)
因此只能在商空间 $\mathbb{R}^n/span{1}$ 讨论唯一性。即，将所有仅相差一个常数的向量当成同一个点。当没有约束时，解是无穷多个；而加约束后，解唯一。
[性质2] 凹性
函数 $-\log (e^a+e^b)$ 是凹函数，那么 $l(\theta)$ 是凹函数。
[性质3] 梯度
$$\frac{\partial l}{\partial \theta_i}=\sum_j[w_{ij}-n_{ij}\frac{e^{\theta_i}}{e^{\theta_i}+e^{\theta_j}}]$$
必要性：非强连通=>MLE不存在#
若图不是强连通图，那么存在划分，
$$V = A \cup B,\ A \cap B = \emptyset$$
满足：
- 存在 $i\in A,j\in B$，使 $w_{ij}>0$
- 但不存在 $j\rightarrow i$路径
此时，可以构造发散方向（recession dir.），即定义方向向量
$$d_i = \begin{cases} 1 & i \in A \ 0 & i \in B \end{cases}$$
(tobeadded)
考虑$\theta(t)=\theta+td$
对任意 $i\in A,j\in B$，有
$$\log \frac{e^{\theta_i+t}}{e^{\theta_i+t}+e^{\theta_j}}=-\log(1+e^{\theta_j-\theta_i-t})\rightarrow 0$$
当 $t\rightarrow 0$。即有 $\log P(i \succ j) \uparrow 0$。
对于这些项，
$$\frac{d}{dt}l(\theta+td)\ge 0$$
且严格增加。
[证明]
把对数似然拆开，有
$$l=\sum_{i<j} l_{ij}$$
式中
$$l_{ij}=w_{ij}\theta_i+w_{ji}\theta_j-n_{ij}\log (e^{\theta_i}+e^{\theta_j})$$
可以分三种情况来看：
[情况1] $i,j\in A$
改变 $\theta_i$和$\theta_j$，有
$$e^{\theta_i+t}+e^{\theta_j+t}=e^t(e^{\theta_i}+e^{\theta_j})$$
代入：
$$\log(e^{\theta_i+t}+e^{\theta_j+t})=t+\log(e^{\theta_i}+e^{\theta_j})$$
代回似然函数：
$$\ell_{ij}(t) = w_{ij}(\theta_i + t) + w_{ji}(\theta_j + t) - n_{ij}(t + \log(\cdots))$$
展开：
$$= \left(w_{ij}\theta_i + w_{ji}\theta_j - n_{ij}\log(\cdots)\right) + \left(w_{ij} + w_{ji} - n_{ij}\right)t$$
由于 $n_{ij} = w_{ij} + w_{ji}$，所以：
$$\ell_{ij}(t) = \ell_{ij}(0)$$
[情况2] $i,j\in B$
同理。
[情况3] 跨集合 $i\in A,j\in B$
根据d的定义，可以写出该情况下的似然函数：
$$\ell_{ij}(t) = w_{ij}(\theta_i + t) + w_{ji}\theta_j - n_{ij}\log\left(e^{\theta_i + t} + e^{\theta_j}\right)$$
对于t求导，有：
$$\frac{d}{dt} \ell_{ij}(t) = w_{ij} - n_{ij} \cdot \frac{e^{\theta_i + t}}{e^{\theta_i + t} + e^{\theta_j}}$$
在构造中，由于不存在j->i的边，所以 $n_{ij}=w_{ij}$
代入有
$$\frac{d}{dt}l_{ij}(t)=w_{ij}\frac{e^{\theta_j}}{e^{\theta_i+t}+e^{\theta_j}}\ge 0$$。
将所有项加起来，有：
$$\frac{d}{dt} \ell(\theta + t d) = \sum_{\substack{i \in A, j \in B}} w_{ij} \cdot \frac{e^{\theta_j}}{e^{\theta_i + t} + e^{\theta_j}} \geq 0$$
只要存在一条边 $w_{ij}>0$，就有正贡献。证毕。
取极限： $$\sup_\theta l(\theta)=0$$
对任何有限 $\theta$，都有 $l(\theta)<0$，极值只在 $t\rightarrow \infty$处到达。
充分性：强连通=>存在唯一解#
[命题]
若比较图是强连通图，则BT model对数似然在约束空间上存在唯一极大点。
即证明强制性条件coercivity：
$$|\theta| \to \infty,\ \theta \in \Theta \implies \ell(\theta) \to -\infty$$
[证明]
由于平移不变形，故限定在 $\Theta={\theta\in R^n:\sum_{i=1}^{n} \theta_i=0}$ 空间中进行优化。
[证明1:严格凹性]
[命题]
函数
$$f(a,b)=-\log(e^a+e^b)$$
是严格凹函数。
[证明]
Zermelo更新#
考虑公式：
$$P(W|\pi)=\prod_{i,j}(\frac{\pi_i}{\pi_i+\pi_j})^{w_{ij}}$$
使用对数似然函数：
$$l(\pi)=\sum_{i,j} w_{ij}\log \frac{\pi_i}{\pi_i+\pi_j}=\sum_{i,j} w_{ij}(\log \pi_i-\log (\pi_i+\pi_j))$$
使用极大似然估计：
$$\frac{\partial}{\partial \pi_i} l(w|\pi)=\frac{\sum_{i,j}w_{ij}}{\pi_i}-\sum_{i,j}\frac{w_{ij}+w_{ji}}{\pi_i+\pi_j}$$
令其=0，有：
$$\frac{\sum_{i,j}w_{ij}}{\pi_i}=\sum_{i,j}\frac{w_{ij}+w_{ji}}{\pi_i+\pi_j}$$
整理得自洽方程：
$$\pi_i=\frac{\sum_{i,j}w_{ij}}{\sum_{i,j}\frac{w_{ij}+w_{ji}}{\pi_i+\pi_j}}$$
使用迭代更新求解：
$$\pi_i^{(t+1)}=\frac{\sum_{i,j}w_{ij}}{\sum_{i,j}\frac{w_{ij}+w_{ji}}{\pi_i^{(t)}+\pi_j^{(t)}}}$$
上式即Zermelo算法，仅在比较网络强连通时收敛。