This paper presents findings from an empirical study of multileaved comparisons, an efficient online evaluation methodology, in a commercial Web service. The most important difference from the previous studies is the number of rankers involved in the online evaluation: we compared 30 rankers for around 90 days by multileaved comparisons. A relatively large number of rankers answered several questions that could not be addressed in the previous work due to a small number of rankers: How much ranking difference is required for rankers to be statistically distinguished? How many impressions are necessary for finding statistically significant differences for correlated rankers? How large difference in offline evaluation can predict significant differences in a multileaved comparison? We answer these questions with the results of the multileaved comparisons, and generalized some of the findings by simulation-based experiments.

This paper discusses challenges of an online evaluation technique, multileaved comparison, based on the analysis of evaluation results in a community question-answering (cQA) search service. NTCIR-13 OpenLiveQ task offered a shared task in which participants addressed an ad-hoc retrieval task in a cQA service, and evaluated their rankers by multileaved comparison, which combines multiple rankings to generate a single search result page, and simultaneously evaluates the different rankings based on users' clicks on the search result page. Since the number of search result impressions during the evaluation period might not suffice to evaluate a hundred of rankers, we conducted the online evaluation only for rankers that achieved high performance in offline evaluation. The analysis of evaluation results showed that offline and online evaluation results did not fully agree, and a large number of users' clicks were necessary to find a statistically significant difference for every ranker pair. To cope with these problems in large-scale multileaved comparison, we propose a new experimental design that evaluates all the rankers online but intensively tests only the top-k rankers. Simulation-based experiments demonstrated that Copeland counting algorithm could achieve high top-k recall in the top-k identification problem for multileaved comparison.

We present one of the world's first attempts to examine the feasibility of multileaving evaluation of document rankings on a large scale commercial community Question Answering (cQA) service. As a natural enhancement of interleaving evaluation, multileaving merges more than two input rankings into one and measures the search user satisfaction of each input ranking on the basis of user clicks on the multileaved ranking. We evaluated the adequateness of two major multileaving methods, team draft multileaving (TDM) and optimized multileaving (OM), proposing their practical implementation for live services. Our experimental results demonstrated that multileaving methods could precisely evaluate the effectiveness of five rankings with different quality by using clicks from real users. Moreover, we concluded that OM is more efficient than TDM by observing that most of the evaluation results with OM converged after showing multileaved rankings around 40,000 times and an in-depth analysis of their characteristics.

We propose a method for extracting logical hierarchical structure of HTML documents. Because mark-up structure in HTML documents does not necessarily coincide with logical hierarchical structure, it is not trivial how to extract logical structure of HTML documents. Human readers, however, easily understand their logical structure. The key information used by them is headings in the documents. Human readers exploit the following properties of headings: (1) headings appear at the beginning of the corresponding blocks, (2) headings are given prominent visual styles, (3) headings of the same level share the same visual style, and (4) headings of higher levels are given more prominent visual styles. Our method also exploits these properties for extracting hierarchical headings and their associated blocks. Our experiment shows that our method outperforms existing methods. In addition, our method extracts not only hierarchical blocks but also their associated headings.