PhD Notes

Contents:

\[\gdef{\R}{\mathbb{R}} \gdef{\src}{\mathrm{src}} \gdef{\fle}{\preceq} \gdef{\flt}{\prec} \]

Notes on Monotonicity for USums TD operator

Preliminaries

Suppose there are \(k\) sources \(s_1,\ldots,s_k\) and \(l\) facts \(f_1,\ldots,f_l\). Let \(M\) be the \(k \times l\) source-claims matrix, with \(M_{ij} = 1\) if source \(s_i\) claims fact \(f_j\), and \(M_{ij} = 0\) otherwise.

Let \(w_n \in \R^l\) be the vector of belief scores for facts in the \(n\)-th iteration of USums. Then, writing \(B = M^\top M\), we have

\[\begin{aligned} w_1 &= M^\top \bm{e} \\ w_{n+1} &= Bw_n \quad (n \ge 1) \end{aligned}\]

We have already shown that there is some \(N \in \N\) (which depends on \(M\)) such that the ranking associated with \(w_n\) is the same for all \(n \ge N\); this ranking defines the USums operator.

Monotonicity

To start with, consider a simplest special case of Monotonicity: a source \(s_u\) does not make a claim for the object associated with some fact \(f_v\) (i.e. \(M_{uv} = 0\)), and we modify the network to add this claim. We need to show that the ranking of \(f_v\) improves, with ties broken in its favour. 1

The new source-claims matrix is \(M' = M + \bm{1}_{uv}\). Let \(B'\) and \(w'_n\) be defined as above, but with \(M'\) replacing \(M\). For ease of notation, write \(j_1 \fle j_2\) to mean \(f_{j_1}\) ranks below (or equal to) \(f_{j_2}\) in the network \(M\), and \(j_1 \fle' j_2\) for the same thing in the network \(M'\).

We need to show that \(j \fle v \implies j \flt' v\) for all \(j \ne v\).

A sufficient condition: Consider the difference \(d_n = w'_{n+1} - w_{n+1}\) between belief scores in \(M'\) and \(M\). If for sufficiently large \(n\) we have \([d_n]_j < [d_n]_v\) for all \(j \fle v\), then

\[\begin{aligned} [w'_{n+1}]_j &= \underbrace{[d_n]_j}_{< [d_n]_v} + \underbrace{[w_{n+1}]_j}_{\le [w_{n+1}]_v \text{ since } j \fle v} \\ &< [d_n]_v + [w_{n+1}]_v \\ &= [w'_{n+1}]_v \end{aligned}\]

which shows \(j \flt' v\) as required.

Experimentally, this condition does seem to hold (tested up to \(k = l = 4\)). To actually prove it, the following expression for \(d_n\) might prove useful.

Proposition 1

Define an \(l \times l\) matrix \(U\) by \(U_{jk} = M_{uj}\delta_{kv} + M_{uk}\delta_{jv} + \delta_{jv}\delta_{kv}\). 2 Then

\[d_n = (B+U)^n\bm{e}_v + \sum_{i=1}^{n}{(B+U)^{n-i}Uw_i} \tag{1}\]

where \(\bm{e}_v \in \R^l\) is the vector with a 1 in position \(v\) and zeros elsewhere.

Proof.

We proceed by induction. For case \(n = 0\), we have

\[\begin{aligned} d_0 &= w'_1 - w_1 \\ &= (M')^\top\bm{e} - M^\top\bm{e} \\ &= (M' - M)^\top\bm{e} \\ &= (\bm{1}_{uv})^\top\bm{e} \\ &= \bm{1}_{vu}\bm{e} \\ &= \bm{e}_v \end{aligned} \]

Plugging \(n=0\) into the RHS on \((1)\) also yields \(\bm{e}_v\), so we are done.

Now suppose \((1)\) holds for some \(n \ge 0\). It can be checked without too much trouble that \(B' = B + U\). We have

\[\begin{aligned} d_{n+1} &= w'_{n+2} - w_{n+2} \\ &= B'w'_{n+1} - Bw_{n+1} \\ &= (B + U)(w_{n+1} + d_n) - Bw_{n+1} \\ &= Uw_{n+1} + (B + U)d_n \\ &= Uw_{n+1} + (B+U)^{n+1}\bm{e}_v + \sum_{i=1}^{n}{(B+U)^{n + 1 - i}Uw_i} \end{aligned} \]

Note that \(Uw_{n+1} = (B + U)^0Uw_{n+1} = (B + U)^{n+1-(n+1)}Uw_{n+1}\), which is equal to the summand above taken at \(i = n+1\). We see that

\[d_{n+1} = (B+U)^{n+1}\bm{e}_v + \sum_{i=1}^{n+1}{(B+U)^{n + 1 - i}Uw_i} \]

as required.

1

To prove the full Monotonicity axiom, we also need to show that the ranking of \(f_v\) improves if we removed a claim \((s_u, f_{v'})\) for some \(f_{v'}\) associated with the same object as \(f_v\)…

2

\(\delta\) denotes the Kronecker delta symbol