3
$\begingroup$

I am reading a paper about the TextRank algorithm in keyword extraction and they mention the recursive formula: $$ \displaystyle S(V_{i}) = (1 - d) + d \ast \sum_{j \in In(V_{i})} \frac{1}{|Out(V_{j})|} \; S(V_{j}) $$

where $ In(V_{i}) $ are the vertices that point to $ V_{i} $ and $ Out(V_{i}) $ are the vertices that $ V_{i} $ points to.

The paper claimed that this algorithm will converge for any arbitrarily small positive threshold and any arbitrary initial values by testing with experiments. However, I am attempting to prove it mathematically that this algorithm will always converge regardless of the choice of the threshold as well as the initial values, but haven't succeeded at this point. My approach is to prove that if $ E_{ij} $ is the error at vertex $ i $ at the $ j $ iteration, then the sequence $ E_{i1}, E_{i2}, \dots, E_{in} $ is a decreasing sequence. Intuitively, it means that the error rate approaches $ 0. $

Any hint or suggestion is appreciated.

$\endgroup$
  • $\begingroup$ This is an interesting question but I think it's beyond the scope of a Stack Exchange site. Essentially, you're asking for original research and, if the proof you're looking for would fit reasonably in a Stack Exchange answer, one would imagine that the authors of the paper you're reading would have found it and published that, instead of empirical claims. $\endgroup$ – David Richerby Jun 17 '16 at 21:00
  • $\begingroup$ Can you edit your question to make it self-contained? You mention "arbitrarily small positive threshold": what's the threshold? What's $d$? Is it a constant in the range $0<d<1$? What is the definition of "converge"? What is the precise claim? Is the claim that this algorithm will converge for all $d$, all graphs, and all initial values of $S$? Are there some limits on the graph, such as that it is strongly connected? Have you tried looking at Markov random processes and random walks? $\endgroup$ – D.W. Jun 17 '16 at 22:20
2
$\begingroup$

Your process is a Markov chain, so I suggest you try applying the theory of Markov chains. There's a rich and powerful theory that has been built up over time, which might be applicable here.

In particular, if we let $S$ denote the column vector $S = (S(V_1),S(V_2),\dots,S(V_n))$, then there is a matrix $n\times n$ $M$ such that each iteration maps $S$ to $MS$. If the underlying graph is strongly connected, it looks like this Markov chain is irreducible, ergodic, aperiodic, and all its states are recurrent. From this you should be able to deduce that it has a stationary distribution $\pi$ and that the stationary distribution is the unique limiting distribution of the chain, hence the algorithm eventually converges. You should check all of this yourself carefully; I haven't checked any of this.

The rate of convergence will be dependent on the magnitude of the second-largest eigenvalue of the Markov chain.

Look at the analysis of PageRank for a detailed, worked example applying these concepts to a similar algorithm. This analysis can be found in many textbooks and algorithms courses.

$\endgroup$
1
$\begingroup$

I have read the article and I will address some concerns to keep you on the right track.

Since the smaller window behaves better, the convergence rate also decreases with longer window - very bad indicator. The F-measure has serious issues as statistic, but the $E$ indicator is not even a metric, this mere fact alarms in very nasty way, the convergence to arbitrary threshold might be possible, but the outcome is not conservative. In simple English even when it converges with error as small as $0$, this does not imply working solution yet.

As authors stated the maximum recall is strictly below $100%$, so this implies the $F-measure$ cannot be arbitrary good, hence the threshold is limited and when you go below critical level, it must diverge - so this is not arbitrary good but limited.

The score is not known in advance, but statistic used assumes real and , also you cannot set damping factor $d$ in range [0,1]. The error is calculated from consecutive iterations, so putting equiscore result in two iterations (let me say ambigous, or identical) it stops algorithm from scoring.

Another assumption comes from N-grams, it gives satisfactory bigrams after analysing over $10^9$ words 1 (sorry, non-english reference).

So summimg it up, you cannot prove it since some statements are false. You can put constraints from elements constituting the model, make assumption that you can squeeze all subproblems to the maximum, and this gives you bound how good is the model at best - since this is not arbitrary good as paper claims, this contradicts the statement, because it cannot converge when constants given aim at result better than calculated bound.

$\endgroup$
  • $\begingroup$ I agree with D.W.'s Markov chain model, and as such it will converge, but I have my own part on the paper - not every used part is good enough. Also avoiding to show everything in the paper by stating that some filters were used (but not shown) is a kind of hidding some problems in the way that nobody can really undermine the paper (if nobody can test it, how would one show it does not work as described?). $\endgroup$ – Evil Jun 19 '16 at 16:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.