Growing a list

Abstract

It is easy to find expert knowledge on the Internet on almost any topic, but obtaining a complete overview of a given topic is not always easy: information can be scattered across many sources and must be aggregated to be useful. We introduce a method for intelligently growing a list of relevant items, starting from a small seed of examples. Our algorithm takes advantage of the wisdom of the crowd, in the sense that there are many experts who post lists of things on the Internet. We use a collection of simple machine learning components to find these experts and aggregate their lists to produce a single complete and meaningful list. We use experiments with gold standards and open-ended experiments without gold standards to show that our method significantly outperforms the state of the art. Our method uses the ranking algorithm Bayesian Sets even when its underlying independence assumption is violated, and we provide a theoretical generalization bound to motivate its use.

Appendix A implementation details

Source discovery: This step requires submitting the query “term1” “term2” to a search engine. In our experiments we used Google as the search engine, but any index would suffice. We retrieved the top 100 results.

List extraction: For each site found with the combinatorial search, we look for HTML tags around the seed items. We use the following lines of HTML to illustrate:

$<$ $\mathtt{h}2$ $>$ $<$ $\mathtt{b}$ $>$ $<$a href=“example1.com”$>$ Boston Harborfest $<$ $\mathtt{/a}$ $>$ $<$ $\mathtt{/b}$ $>$ $<$ $\mathtt{/h}2$ $>$

$<$ $\mathtt{b}$ $>$ $<$a href=“example2.com”$>$ Jimmy fund scooper bowl $<$ $\mathtt{/a}$ $>$ $<$ $\mathtt{/b}$ $>$

$<$ $\mathtt{b}$ $>$ $<$a href =“example3.com”$>$ the Boston Arts Festival 2012$<$ $\mathtt{/a}$ $>$ $<$ $\mathtt{/b}$ $>$

$<$ $\mathtt{h3}$ $>$ $<$ $\mathtt{b}$ $>$ $<$a href=“example4.com”$>$ Boston bacon takedown $<$ $\mathtt{/a}$ $>$ $<$ $\mathtt{/b}$ $>$ $<\mathtt{/h3}$ $>$

$<$a href=“example5.com”$>$ Just a url $<$ $\mathtt{/a}$ $>$

For each of the two seed items used to discover this source, we search the HTML for the pattern:

$$\begin{aligned} \mathrm{<\!largest\, set\, of\, tags\!>(up\, to\, 5\, words)\, seed\, item\, (up\, to\, 5 \,words)<\!matching\, end\, tags\!>}. \end{aligned}$$

In the above example, if the first seed item is “Boston arts festival,” then it matches the pattern with the HTML tags: $<$ $\mathtt{b}$ $>$ $<$ $\mathtt{a}$ $>$. If the second seed item is “Boston harborfest,” it matches the pattern with HTML tags: $<$ $\mathtt{h2}$ $>$ $<$ $\mathtt{b}$ $>$ $<$ $\mathtt{a}$ $>$. We then find the largest set of HTML tags that are common to both seed items, for this site. In this example, “Boston arts festival” does not have the $<$ $\mathtt{h2}$ $>$ tag, so the largest set of common tags is: $<$ $\mathtt{b}$ $>$ $<$ $\mathtt{a}$ $>$. If there are no HTML tags common to both seed items, we discard the site. Otherwise, we extract all items on the page that use the same HTML tags. In this example, we extract everything with both a $<$ $\mathtt{b}$ $>$ and an $<$ $\mathtt{a}$ $>$ tag, which means “Jimmy fund scooper bowl” and “Boston bacon takedown,” but not “Just a url.”

In our experiments, to avoid search spam sites with extremely long lists of unrelated keywords, we reject sources that return more than 300 items. We additionally applied a basic filter rejecting items of more than 60 characters or items consisting of only numbers and punctuation. No other processing was done.

Feature space: We do separate Google searches for each item we have extracted to find the set of webpages containing it. We use quotes around the query term, discard results when Google’s spelling correction system modifies the query, and retrieve the top 300 search results.

Ranking: In all of our experiments we took $\kappa _2=5$ and $\kappa _1=2$, similarly to that done in Heller and Ghahramani (2006).

Feedback: To avoid filling the seed with duplicate items like “Boston arts festival” and “The boston arts festival 2012,” in our implicit feedback we do not add items to the seed if they are a sub- or super-string of a current seed item.

Access of online tools: The results for Boo!Wa! and Google Sets used in Sect.4.1 were retrieved from their respective online tools on November 14, 2012, and those used in Sect. 4.3 were retrieved on December 13, 2012. Results for our algorithm, which depend on Google search results and the content of the source webpages, were obtained in the period March 14–21, 2013 for the Wikipedia gold-standard experiments in Sects. 4.1 and 4.2, and in the period May 28–30, 2012 for the open-ended experiments in Sect. 4.3.