Using interaction data for improving the offline and online evaluation of search engines

This thesis investigates how web search evaluation can be improved using historical interaction data. Modern search engines combine offline and online evaluation approaches in a sequence of steps that a tested change needs to pass through to be accepted as an improvement and subsequently deployed. We refer to such a sequence of steps as an evaluation pipeline. In this thesis, we consider the evaluation pipeline to contain three sequential steps: an offline evaluation step, an online evaluation scheduling step, and an online evaluation step. In this thesis we show that historical user interaction data can aid in improving the accuracy or efficiency of each of the steps of the web search evaluation pipeline. As a result of these improvements, the overall efficiency of the entire evaluation pipeline is increased. Firstly, we investigate how user interaction data can be used to build accurate offline evaluation methods for query auto-completion mechanisms. We propose a family of offline evaluation metrics for query auto-completion that represents the effort the user has to spend in order to submit their query. The parameters of our proposed metrics are trained against a set of user interactions recorded in the search engine’s query logs. From our experimental study, we observe that our proposed metrics are significantly more correlated with an online user satisfaction indicator than the metrics proposed in the existing literature. Hence, fewer changes will pass the offline evaluation step to be rejected after the online evaluation step. As a result, this would allow us to achieve a higher efficiency of the entire evaluation pipeline. Secondly, we state the problem of the optimised scheduling of online experiments. We tackle this problem by considering a greedy scheduler that prioritises the evaluation queue according to the predicted likelihood of success of a particular experiment. This predictor is trained on a set of online experiments, and uses a diverse set of features to represent an online experiment. Our study demonstrates that a higher number of successful experiments per unit of time can be achieved by deploying such a scheduler on the second step of the evaluation pipeline. Consequently, we argue that the efficiency of the evaluation pipeline can be increased. Next, to improve the efficiency of the online evaluation step, we propose the Generalised Team Draft interleaving framework. Generalised Team Draft considers both the interleaving policy (how often a particular combination of results is shown) and click scoring (how important each click is) as parameters in a data-driven optimisation of the interleaving sensitivity. Further, Generalised Team Draft is applicable beyond domains with a list-based representation of results, i.e. in domains with a grid-based representation, such as image search. Our study using datasets of interleaving experiments performed both in document and image search domains demonstrates that Generalised Team Draft achieves the highest sensitivity. A higher sensitivity indicates that the interleaving experiments can be deployed for a shorter period of time or use a smaller sample of users. Importantly, Generalised Team Draft optimises the interleaving parameters w.r.t. historical interaction data recorded in the interleaving experiments. Finally, we propose to apply the sequential testing methods to reduce the mean deployment time for the interleaving experiments. We adapt two sequential tests for the interleaving experimentation. We demonstrate that one can achieve a significant decrease in experiment duration by using such sequential testing methods. The highest efficiency is achieved by the sequential tests that adjust their stopping thresholds using historical interaction data recorded in diagnostic experiments. Our further experimental study demonstrates that cumulative gains in the online experimentation efficiency can be achieved by combining the interleaving sensitivity optimisation approaches, including Generalised Team Draft, and the sequential testing approaches. Overall, the central contributions of this thesis are the proposed approaches to improve the accuracy or efficiency of the steps of the evaluation pipeline: the offline evaluation frameworks for the query auto-completion, an approach for the optimised scheduling of online experiments, a general framework for the efficient online interleaving evaluation, and a sequential testing approach for the online search evaluation. The experiments in this thesis are based on massive real-life datasets obtained from Yandex, a leading commercial search engine. These experiments demonstrate the potential of the proposed approaches to improve the efficiency of the evaluation pipeline.

State-narco networks and the ‘War on Drugs’ in post-transition Bolivia, with special reference to 1989-1993

This thesis examines the development of state-narco networks in post-transition Bolivia. Mainstream discourses of drugs tend to undertheorise such relationships, holding illicit economies, weak states and violence as synergistic phenomena. Such assumptions fail to capture the nuanced relations that emerge between the state and the drug trade in different contexts, their underlying logics and diverse effects. As an understudied case, Bolivia offers novel insights into these dynamics. Bolivian military authoritarian governments (1964-1982), for example, integrated drug rents into clientelistic systems of governance, helping to establish factional coalitions and reinforce regime authority. Following democratic transition in 1982 and the escalation of US counterdrug efforts, these stable modes of exchange between the state and the coca-cocaine economy fragmented. Bolivia, though, continued to experience lower levels of drug-related violence than its Andean neighbours, and sustained democratisation despite being a major drug producer. Focusing on the introduction of the Andean Initiative (1989-1993), I explore state-narco interactions during this period of flux: from authoritarianism to (formal) democracy, and from Cold War to Drug War. As such, the thesis transcends the conventional analyses of the drugs literature and orthodox readings of Latin American narco-violence, providing insights into the relationship between illicit economies and democratic transition, the regional role of the US, and the (unintended) consequences of drug policy interventions. I utilise a mixed methods approach to offer discrete perspectives on the object of study. Drawing on documentary and secondary sources, I argue that state-narco networks were interwoven with Bolivia’s post-transition political settlement. Uneven democratisation ensured pockets of informalism, as clientelistic and authoritarian practices continued. This included police and military autonomy, and tolerance of drug corruption within both institutions. Non-enforcement of democratic norms of accountability and transparency was linked to the maintenance of fragile political equilibrium. Interviews with key US and Bolivian elite actors also revealed differing interpretations of state-narco interactions. These exposed competing agendas, and were folded into alternative paradigms and narratives of the ‘war on drugs’. The extension of US Drug War goals and the targeting of ‘corrupt’ local power structures, clashed with local ambivalence towards the drug trade, opposition to destabilising, ‘Colombianised’ policies and the claimed ‘democratising mission’ of the Bolivian government. In contrasting these US and Bolivian accounts, the thesis shows how real and perceived state-narco webs were understood and navigated by different actors in distinct ways. ‘Drug corruption’ held significance beyond simple economic transaction or institutional failure. Contestation around state-narco interactions was enmeshed in US-Bolivian relations of power and control.