Publications related to Role of thesauri in a scientific organisation

Mapping for Multi-Source Visualization: Scientific Information Retrieval Service (SIRS)

This paper introduces SIRS and discusses the design process of a multi-index, multi-source information retrieval system. SIRS provides comprehensive visualization of different document types for the JRC working environment. The interface design is based on elastic window management and on the Focus+Context method to browse large amounts of information without losing its contextual relevance. Source integration was achieved by mapping techniques, on which we applied methods, degree-of-separation and closure, to provide advanced relational context for objects.

Springer Verlag2009

Rate allocation and optimized decoding in inter-session network coding

Eirina Bourtsoulatze

Recent advances in data processing and communication systems have led to a continuous increase in the amount of data communicated over today’s networks. These large volumes of data pose new challenges on the current networking infrastructure that only offers a best effort mechanism for data delivery. The emergence of new distributed network architectures, such as peer-to-peer networks and wireless mesh networks, and the need for efficient data delivery mechanisms have motivated researchers to reconsider the way that information is communicated and processed in the networks. This has given rise to a new research field called network coding. The network coding paradigm departs from the traditional routing principle where information is simply relayed by the network nodes towards the destination, and introduces some intelligence in the network through coding at the intermediate nodes. This in-network data processing has been proved to substantially improve the performance of data delivery systems in terms of throughput and error resilience in networks with high path diversity. Motivated by the promising results in the network coding research, we focus in this thesis on the design of network coding algorithms for simultaneous transmission of multiple data sources in overlay networks. We investigate several problems that arise in the context of inter-session network coding, namely (i) decoding delay minimization in inter-session network coding, (ii) distributed rate allocation for inter-session network coding and (iii) correlation-aware decoding of incomplete network coded data. We start by proposing a novel framework for data delivery from multiple sources to multiple clients in an overlay wireline network, where intermediate nodes employ randomized inter-session network coding. We consider networks with high resource diversity, which creates network coding opportunities with possibly large gains in terms of throughput, delay and error robustness. However, the coding operations in the intermediate nodes must be carefully designed in order to enable efficient data delivery. We look at the problem from the decoding delay perspective and design solutions that lead to a small decoding delay at clients through proper coding and rate allocation. We cast the optimization problem as a rate allocation problem, which seeks for the coding operations that minimize the average decoding delay in the client population. We demonstrate the validity of our algorithm through simulations in representative network topologies. The results show that an effective combination of intra- and inter-session network coding based on randomized linear coding permits to reach small decoding delays and to better exploit the available network resources even in challenging network settings. Next, we design a distributed rate allocation algorithm where the users decide locally how many intra- and inter-session network coded packets should be requested from the parent nodes in order to get minimal decoding delay. The capability to take coding decisions locally with only a partial knowledge of the network statistics is of crucial importance for applications where users are organized in dynamic overlay networks. We propose a receiver-driven communication protocol that operates in two rounds. First, the users request and obtain information regarding the network conditions and packet availability in their local neighborhood. Then, every user independently optimizes the rate allocation among different possible intra- and inter-session packet combinations to be requested from its parents. We also introduce the novel concept of equivalent flows, which permits to efficiently estimate the expected number of packets that are necessary for decoding and hence to simplify the rate allocation process. Experimental results indicate that our algorithm is capable of eliminating the bottlenecks and reducing the decoding delay of users with limited resources. We further investigate the application of the proposed distributed rate allocation algorithm to the transmission of video sequences and validate the performance of our system using the NS-3 simulator. The simulation results show that the proposed rate allocation algorithm is successful in improving the quality of the delivered video compared to intra-session network coding based solutions. Finally, we investigate the problem of decoding the source information from an incomplete set of network coded data with the help of source priors in a finite algebraic field. The inability to form a complete decoding system can be often caused by transmission losses or timing constraints imposed by the application. In this case, exact reconstruction of the source data by conventional algorithms such as Gaussian elimination is not feasible; however, partial recovery of the source data may still be possible, which can be useful in applications where approximate reconstruction is informative. We use the statistical characteristics of the source data in order to perform approximate decoding. We first analyze the performance of a hypothetical maximum a posteriori decoder, which recovers the source data from an incomplete set of network coded data given the joint statistics of the sources. We derive an upper bound on the probability of erroneous source sequence decoding as a function of the system parameters. We then propose a constructive solution to the approximate decoding problem and design an iterative decoding algorithm based on message passing, which jointly considers the network coding and the correlation constraints. We illustrate the performance of our decoding algorithm through extensive simulations on synthetic and real data sets. The results demonstrate that, even by using a simple correlation model expressed as a correlation noise between pairs of sources, the original source data can be partially decoded in practice from an incomplete set of network coded symbols. Overall, this thesis addresses several important issues related to the design of efficient data delivery methods with inter-session network coding. Our novel framework for decoding delay minimization can impact the development of practical inter-session network coding algorithms that are appropriate for applications with low delay requirements. Our rate allocation algorithms are able to exploit the high resource diversity of modern networking systems and represent an effective alternative in the development of distributed communication systems. Finally, our algorithm for data recovery from incomplete network coded data using correlation priors can contribute significantly to the improvement of the delivered data quality and provide new insights towards the design of joint source and network coding algorithms.

EPFL2013

Clusters of science and health related Twitter users become more isolated during the COVID-19 pandemic

Marcel Salathé

COVID-19 represents the most severe global crisis to date whose public conversation can be studied in real time. To do so, we use a data set of over 350 million tweets and retweets posted by over 26 million English speaking Twitter users from January 13 to June 7, 2020. We characterize the retweet network to identify spontaneous clustering of users and the evolution of their interaction over time in relation to the pandemic's emergence. We identify several stable clusters (super-communities), and are able to link them to international groups mainly involved in science and health topics, national elites, and political actors. The science- and health-related super-community received disproportionate attention early on during the pandemic, and was leading the discussion at the time. However, as the pandemic unfolded, the attention shifted towards both national elites and political actors, paralleled by the introduction of country-specific containment measures and the growing politicization of the debate. Scientific super-community remained present in the discussion, but experienced less reach and became more isolated within the network. Overall, the emerging network communities are characterized by an increased self-amplification and polarization. This makes it generally harder for information from international health organizations or scientific authorities to directly reach a broad audience through Twitter for prolonged time. These results may have implications for information dissemination along the unfolding of long-term events like epidemic diseases on a world-wide scale.

NATURE PORTFOLIO2021

This thesis is devoted to information-theoretic aspects of community detection. The importance of community detection is due to the massive amount of scientific data today that describes relationships between items from a network, e.g., a social network. Items from this network can be inherently partitioned into a known number of communities, but the partition can only be inferred from the data. To estimate the underlying partition, data scientists can apply any type of advanced statistical techniques; but the data could be very noisy, or the number of data is inadequate. A fundamental question here is about the possibility of weak recovery: does the data contain a sufficient amount of information that enables us to produce a non-trivial estimate of the partition? For the purpose of mathematical analysis, the above problem can be formulated as Bayesian inference on generative models. These models, including the stochastic block model (SBM) and censored block model (CBM), consider a random graph generated based on a hidden partition that divides the nodes in the graph into labelled groups. In the SBM, nodes are connected with a probability depending on the labels of the endpoints. Whereas, in the CBM, hidden variables are measured through a noisy channel, and the measurement outcomes form a weighted graph. In both models, inference is the task of recovering the hidden partition from the observed graph. The criteria for weak recovery can be studied via an information-theoretic quantity called mutual information. Once the asymptotic mutual information is computed, phase transitions for the weak recovery can be located. This thesis pertains to rigorous derivations of single-letter variational expressions for the asymptotic mutual information for models in community detection. These variational expressions, known as the replica predictions, come from heuristic methods of statistical physics. We present our development of new rigorous methods for confirming the replica predictions. These methods are based on extending the recently introduced adaptive interpolation method. We prove the replica prediction for the SBM in the dense-graph regime with two groups of asymmetric size. The existing proofs in the literature are indirect, as they involve mapping the model to an external problem whose mutual information is determined by a combination of methods. Here, on the contrary, we provide a self-contained and direct proof. Next, we extend this method to sparse models. Before this thesis, adaptive interpolation was known for providing a conceptually simple proof for replica predictions for dense graphs. Whereas, for a sparse graph, the replica prediction involves a more complicated variational expression, and rigorous confirmations are often lacking or obtained by rather complicated methods. Therefore, we focus on a simple version of CBM on sparse graphs, where hidden variables are measured through a binary erasure channel, for which we fully prove the replica prediction by the adaptive interpolation. The key for extending the adaptive interpolation to a broader class of sparse models is a concentration result for the so-called "multi-overlaps". This concentration forms the basis of the replica "symmetric" prediction. We prove this concentration result for a related sparse model in the context of physics. This provides inspiration for further development of the adaptive interpolation.

EPFL2019

Today's Internet is not transparent: when packets get lost or delayed, there is typically no information about where the problem occurred, hence no information about who is responsible. This results in Internet service providers (ISPs) offering service level agreements (SLAs) that cannot be verified, and governments enacting neutrality regulations that cannot be enforced. To remedy this, we propose a "transparency system," where each participating network emits receipts for traffic it receives and delivers; an independent monitor collects these receipts and makes decisions regarding the network's performance and neutrality (or lack thereof). The main challenge we face is misbehavior: On the one hand, a network that participates in such a system has a clear incentive to game the system and influence the monitor's decisions to its advantage, by manipulating either the receipts it emits or the corresponding traffic. On the other hand, the monitor (or, more precisely, an adversary who has access to the same information as the monitor, e.g., a government that has subpoenaed the monitor's records) may have an incentive to use the receipts emitted by a network in order to infer information that is otherwise private to the network, in particular, its internal topology. We make three contributions, each one to prevent a different type of misbehavior: (1) Incentive-compatible reporting, which ensures that networks have no incentive to manipulate the receipts they emit in order to claim better performance or fake neutrality. The key to our solution is a trade-off that we discover between network performance and neutrality: we design our system such that the more a network tries to exaggerate its estimated performance the more likely it is to be perceived to violate neutrality (and vice versa). (2) Unbiased reporting, which ensures that networks cannot manipulate the traffic for which they emit receipts in order to claim better performance. The key to our solution is delayed disclosure: we design receipt generation such that, by the time a network has all the information it needs to emit a correct receipt, the network has already forwarded the traffic that this receipt concerns, hence cannot manipulate it. (3) Topology-obfuscation reporting, which enables networks to emit the information that is necessary for the monitor to make correct decisions without leaking any information about internal network topology. The key to our solution is the observation that topology inference exploits the diversity of pairwise similarities between the delay vectors of different network paths; hence, we design receipt generation such that any delay vectors that the monitor might compute have almost 0 pairwise similarities. We conclude that it is possible to design a transparency system that enables networks to report on their own performance such that networks have no incentive to game the system and no fear of leaking information about their private topology.

EPFL2018

Mapping affinities: visualizing academic practice through collaboration

Dario Rodighiero

Academic affinities are one of the most fundamental hidden dynamics that drive scientific development. Some affinities are actual, and consequently can be measured through classical academic metrics such as co-authoring. Other affinities are potential, and therefore do not have visible traces in information systems; for instance, some peers may share scientific interests without actually knowing it. This thesis illustrates the development of a map of affinities for scientific collectives, which is intended to be relevant to three audiences: the management, the scholars themselves, and the external public. Our case study involves the School of Architecture, Civil and Environmental Engineering of EPFL, which consists of three institutes, seventy laboratories, and around one thousand employees. The actual affinities are modeled using the data available from the academic systems reporting publications, teaching, and advising, whereas the potential affinities are addressed through text mining of the documents registered in the information system. The major challenge for designing such a map is to represent the multi-dimensionality and multi-scale nature of the information. The affinities are not limited to the computation of heterogeneous sources of information, they also apply at different scales. Therefore, the map shows local affinities inside a given laboratory, as well as global affinities among laboratories. The thesis presents a graphical grammar to represent affinities. This graphical system is actualized in several embodiments, among which a large-scale carpet of 250 square meters and an interactive online system in which the map can be parameterized. In both cases, we discuss how the actualization influences the representation of data, in particular the way key questions could be appropriately addressed considering the three target audiences: the insights gained by the management and the relative decisions, the understanding of the researchersâ own positioning in the academic collective that might reveal opportunities for new synergies, and eventually the interpretation of the structure from an external standpoint that suggesting the relevance of the tool for communication.

EPFL2018

ReCache: Reactive Caching for Fast Analytics over Heterogeneous Data

Anastasia Ailamaki, Tahir Azim, Manolis Karpathiotakis

As data continues to be generated at exponentially growing rates in heterogeneous formats, fast analytics to extract meaningful information is becoming increasingly important. Systems widely use in-memory caching as one of their primary techniques to speed up data analytics. However, caches in data analytics systems cannot rely on simple caching policies and a fixed data layout to achieve good performance. Different datasets and workloads require different layouts and policies to achieve optimal performance. This paper presents ReCache, a cache-based performance accelerator that is reactive to the cost and heterogeneity of diverse raw data formats. Using timing measurements of caching operations and selection operators in a query plan, ReCache accounts for the widely varying costs of reading, parsing, and caching data in nested and tabular formats. Combining these measurements with information about frequently accessed data fields in the workload, ReCache automatically decides whether a nested or relational column-oriented layout would lead to better query performance. Furthermore, ReCache keeps track of commonly utilized operators to make informed cache admission and eviction decisions. Experiments on synthetic and real-world datasets show that our caching techniques decrease caching overhead for individual queries by an average of 59%. Furthermore, over the entire workload, ReCache reduces execution time by 19-75% compared to existing techniques.

2017

Speaker diarization of spontaneous meeting room conversations

Sree Harsha Yella

Speaker diarization is the task of identifying “who spoke when” in an audio stream containing multiple speakers. This is an unsupervised task as there is no a priori information about the speakers. Diagnostical studies on state-of-the-art diarization systems have isolated three main issues with the systems; overlapping speech, effects of background noise and speech/non- speech detection errors on clustering, and signficant performance variance between different systems. In this thesis we focuss on addressing these issues in diarization. We propose new features based on structure of a conversation such as silence and speaker change statistics for overlap detection. The features are estimated from a long-term context (3-4 seconds) and are used to estimate the probability of overlap at a given instant. These probabilities are later incorporated into acoustic feature based overlap detector as prior prob- abilities. Experiments on several meeting corpora reveal that overlap detection is improved significantly by the proposed method and this consequently reduces the diarization error. To address the issues arising from background noise, errors in speech/non-speech detection and capture speaker discriminative information in the signal, we propose two methods. In the first method, we propose Information Bottleneck with Side Information (IBSI) based diarization to supress artefacts of background noise and non-speech segments introduced into clustering. In the second method, we show that the phoneme transcript of a given recording carries useful information for speaker diarization. This obervation was used in estimation of phoneme background model which is used for diarization in Information Bottleneck (IB) framework. Both the methods achieve significant reduction in error on various meeting corpora. We train different artificial neural network (ANN) architectures to extract speaker discriminant features and use these features as input to speaker diarization systems. The ANNs are trained to perform related tasks such as speaker comparison, speaker classification and auto encod- ing. The bottleneck layer activations from these networks are used as features for speaker diarization. Experiments on different meeting corpora revealed that combination of MFCCs and ANN features reduces the diarization error. To address the issue of performance variations across different sytems, we propose feature level combination of HMM/GMM and IB diarization systems. The combination does not require any changes to the original systems. The output of IB system is used to generate features which when combined with MFCCs in a HMM/GMM system reduce diarization error.

EPFL2015

Speaker diarization of spontaneous meeting room conversations

Sree Harsha Yella

Speaker diarization is the task of identifying ``who spoke when'' in an audio stream containing multiple speakers. This is an unsupervised task as there is no a priori information about the speakers. Diagnostical studies on state-of-the-art diarization systems have isolated three main issues with the systems; overlapping speech, effects of background noise and speech/nonspeech detection errors on clustering, and signficant performance variance between different systems. In this thesis we focuss on addressing these issues in diarization. We propose new features based on structure of a conversation such as silence and speaker change statistics for overlap detection. The features are estimated from a long-term context (3-4 seconds) and are used to estimate the probability of overlap at a given instant. These probabilities are later incorporated into acoustic feature based overlap detector as prior probabilities. Experiments on several meeting corpora reveal that overlap detection is improved significantly by the proposed method and this consequently reduces the diarization error. To address the issues arising from background noise, errors in speech/non-speech detection and capture speaker discriminative information in the signal, we propose two methods. In the first method, we propose Information Bottleneck with Side Information (IBSI) based diarization to supress artefacts of background noise and non-speech segments introduced into clustering. In the second method, we show that the phoneme transcript of a given recording carries useful information for speaker diarization. This obervation was used in estimation of phoneme background model which is used for diarization in Information Bottleneck (IB) framework. Both the methods achieve significant reduction in error on various meeting corpora. We train different artificial neural network (ANN) architectures to extract speaker discriminant features and use these features as input to speaker diarization systems. The ANNs are trained to perform related tasks such as speaker comparison, speaker classification and auto encoding. The bottleneck layer activations from these networks are used as features for speaker diarization. Experiments on different meeting corpora revealed that combination of MFCCs and ANN features reduces the diarization error. To address the issue of performance variations across different sytems, we propose feature level combination of HMM/GMM and IB diarization systems. The combination does not require any changes to the original systems. The output of IB system is used to generate features which when combined with MFCCs in a HMM/GMM system reduce diarization error.

EPFL2015

Selection and Aggregation of Ranking Criteria for Retrieval from Scientific Publication Databases

Martin Veselý

Selection and aggregation of ranking criteria became an important topic in information retrieval as search is getting more specialized and as volume of electronically available information grows. In this context, document ranking has undergone a shift from purely content-based ranking criteria to combined ranking schemes, integrating additional fea- tures, such as document popularity or impact, or link-based techniques that were widely applied after the success of the PageRank algorithm. In this thesis we experiment with selection and aggregation of ranking criteria, aiming at increasing performance of a specialized scientific search engine. Based on theoretical foundations across several research fields including social choice theory, information re- trieval and digital libraries, we focus on ranking in databases of scientific publications in the field of High Energy Physics, identifying criteria that are pertinent for ranking scientific publications and selecting and aggregating them within a unified framework. The first issue that we address is thus identification and selection of ranking criteria for scientific documents in High Energy Physics. The criteria include the traditional information retrieval relevance that is based on the word similarity, but also the document usage, citation counts and links. In this context we present a novel ranking criterion combining the Hirsch index and the download counts, that we call the d-Hirsch index, taking into account counts of document downloads and assigning the corresponding Hirsch index directly to a document. Criteria selection is then based on correlation analysis between ranked lists of documents. We propose that correlations of entire document listings should be replaced by measuring an overlap on the top-k of the resulting list that should better reflect the independence in terms of ranking. To this end we proposed a new measure for the overlap, the Mean Average Overlap (MeanO). The second issue that we address is the aggregation framework for ranked lists of documents, where we focus on applying linear combination and models trained with ma- chine learning techniques based on logistic regression. As individual scores that are used for ranking are not necessarily comparable to each other, we describe a unified model for normalizing ranking scores before their aggregation, based on statistical properties of the underlying ranking criteria. Another contribution of our work is related to creation of a referential of relevance judgments for information retrieval experimentation in databases of scientific publications in the domain of High Energy Physics. Until now there has been no such resource avail- able that would allow to carry out evaluation of specialized information retrieval in this domain. We propose a method for automated generation of referentials, assuming that document relevance is determined by the document usage. Our approach corresponds to a modification of the pooling method, where validating of relevance judgments is not done by experts in the domain, but is inferred from previous document usage as observed in past user behaviors. The developed ranking models, methods and algorithms were validated in the frame- work of the d-Rank prototype developed in collaboration between EPFL and CERN, aiming at the design of document retrieval mechanisms and interfaces combining a multi- tude of individual specialized ranking criteria. This prototype has been integrated within the CERN institutional repository of scientific publications. We carried out several experiments to support the thesis that rank aggregation pro- vides a superior performance for specialized information retrieval than ranking with single criteria. We experimented with the CERN document server document repository, as well as with artificially generated data showing that rank aggregation can contribute to increased performance of a specialized information retrieval system, as compared to a baseline of the best individually performing ranking criteria. We showed on an experiment done with artificially generated data that if scores of individual ranking criteria follow a comparable distribution skewed to the right, then ag- gregating such ranking criteria can lead to an improvement of the ranking performance in terms of the Mean Average Precision. We reproduced this result on an experiment carried out on a real-world data set created from the CERN database of scientific publications showing that aggregating freshness and the download frequency yielded better ranking results as compared to rankings done with the download frequency and freshness sepa- rately, based on the Mean Reciprocal Rank and S@10 evaluation measures. We observed that local aggregates obtained from documents that were part of the result set performed significantly better than global aggregates, obtained through involving all documents in a collection. These results were confirmed by a 10-fold randomized cross-validation test for both the Mean Reciprocal Rank and the S@10 evaluation measure. We compared performance of the d-Hirsch index with existing ranking criteria at the CERN document server and with aggregates obtained through linear combination of individual scores and through logistic regression. We did not observe significantly better ranking results when ranking documents with the d-Hirsch index or its aggregates as compared to other ranking criteria in the test set. We suggested that selecting ranking criteria based on a novel selection criterion, the mean average overlaps between ranked lists, provides a justified basis for criteria selection.

EPFL2012