2
$\begingroup$

I have a data set with keywords describing paragraphs in a car manual and the actual paragraphs. I want to rank those paragraphs by that keyword using PageRank algorithm.

How would I rank these paragraphs in relevance to the keywords?

The keywords are given an ID number while the paragraphs in the manual are texts. Let's say there is a keyword with ID number 89 and I have about 15 paragraphs that the keyword describes. How would the paragraphs be ranked in relevance to the keyword? Can I even use PageRank for this problem?

I understand for ranking websites, backlinks are used to sort the websites into ranks but for paragraphs of texts, how would I link and rank them?

$\endgroup$
  • $\begingroup$ "How to implement PageRank" is pretty broad, since you could want help at many levels. Narrow it down? $\endgroup$ – Sean Owen Sep 29 '15 at 10:17
1
$\begingroup$

If I understand, you have a set of paragraphs, and each paragraph is tagged with keywords. This defines a mapping from paragraph to keyword and vice-versa (an index and a reverse index). You can create a graph of paragraphs and keywords, but all of the edges are undirected (or they all have the same direction). Paragraphs only connect with keywords, and keywords only connect with paragraphs.

To establish relationships between paragraphs, you could define a transitive equivalence relation such as "all paragraphs that connect to the same keyword are now connected to each other". This would allow you to rank the paragraphs that contain a given keyword by their number of connections to other paragraphs, but it may not be an appropriate measure of relevance.

For PageRank to be most helpful, I think you need directional relationships (e.g. if "see page 123" was mentioned in a paragraph). To better represent the complexity of your data, creating additional relationships between keywords (e.g. semantic meaning, lexical relationships) and creating additional relationships between paragraphs (e.g. document classification) may help. Natural Language Processing with Python discusses these topics.

| improve this answer | |
$\endgroup$
1
$\begingroup$

Short version: I would not expect PageRank to be the right algorithm to use for this problem, because the thing you're interested in (relevance) is a feature of the content, not the context (i.e. the graph structure of the links). PageRank works on the web because the context is so closely related to the content.

Long version: PageRank is a way for weight to flow along directional links. Eventually, a stable distribution is reached where weight flows in and out in equal measure. (Generally, people talk about PageRank measuring "importance" or "popularity" because both of those have natural internal definitions--one item is popular because other popular items like it.)

You can create something like PageRank with a graph with multiple classes of objects--no 'paragraph' links to other paragraphs, but it links to 'keyword's, and no keyword links to other keywords, but it links to other paragraphs. This gives you a minor constraint on the graph structure, which should probably be reflected in the randomized restart probability used by PageRank. Initiate the algorithm with half the weight on paragraphs and half the weight on keywords, and it'll iterate until it converges. (This is very similar to Samuel Harrold's solution, except the weighting of the links between paragraphs depends on the number of keywords they have in common.)

But what problem will that actually solve? Which paragraphs and keywords will be the most popular? The useful work of PageRank is mostly being done by asymmetric links (knowing that Alice links to Bob but Bob does not link to Alice is evidence that Bob is more popular than Alice), and we only have symmetric links (unless we use different mechanisms to determine what keywords link to paragraphs than what paragraphs link to keywords).

The remaining work is being done by link scarcity--since a page's popularity is shared among all its links, a page that links to fewer pages transmits more popularity to them than a page that links to more pages. But this means that paragraphs that only match a few keywords make those keywords more popular, and keywords that only link to a few paragraphs make those paragraphs more popular. It's not obvious to me that this will have the effect that we want--a paragraph that receives weight from both "spark plug" and "wheel" is going to show up higher in the rankings than a paragraph that receives weight from just "spark plug," which is probably the opposite of what the user will want.

But you might want to show paragraphs to the user ranked by their weight percentage from a given keyword--if paragraph A gets 100% of its weight from spark plug, paragraph B gets 30% of its weight from spark plug, and C gets 0% of its weight from spark plug, then maybe A is the best result to show for spark plug, followed by B. But is this going to be any different in practice from just ranking pages by what fraction of their total keywords are any particular keyword? It doesn't seem like it'll be by much.

| improve this answer | |
$\endgroup$

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.