OpenRaiser/Intern-Atlas huggingface dataset:
Randomized Composable Coresets for Matching and Vertex Cover
Venue: arXiv cs.DS 2017
Year: 2017

A common approach for designing scalable algorithms for massive data sets is to distribute the computation across, say $k$, machines and process the data using limited communication between them. A particularly appealing framework here is the simultaneous communication model whereby each machine constructs a small representative summary of its own data and one obtains an approximate/exact solution from the union of the representative summaries. If the representative summaries needed for a problem are small, then this results in a communication-efficient and round-optimal protocol. While many fundamental graph problems admit efficient solutions in this model, two prominent problems are notably absent from the list of successes, namely, the maximum matching problem and the minimum vertex cover problem. Indeed, it was shown recently that for both these problems, even achieving a polylog$(n)$ approximation requires essentially sending the entire input graph from each machine. The main insight of our work is that the intractability of matching and vertex cover in the simultaneous communication model is inherently connected to an adversarial partitioning of the underlying graph across machines. We show that when the underlying graph is randomly partitioned across machines, both these problems admit randomized composable coresets of size $\widetilde{O}(n)$ that yield an $\widetilde{O}(1)$-approximate solution. This results in an $\widetilde{O}(1)$-approximation simultaneous protocol for these problems with $\widetilde{O}(nk)$ total communication when the input is randomly partitioned across $k$ machines. We further prove the optimality of our results. Finally, by a standard application of composable coresets, our results also imply MapReduce algorithms with the same approximation guarantee in one or two rounds of communication
Distributed Algorithms for Feature Extraction Off-loading in Multi-Camera Visual Sensor Networks
Venue: arXiv cs.CV 2017
Year: 2017

Real-time visual analysis tasks, like tracking and recognition, require swift execution of computationally intensive algorithms. Visual sensor networks can be enabled to perform such tasks by augmenting the sensor network with processing nodes and distributing the computational burden in a way that the cameras contend for the processing nodes while trying to minimize their task completion times. In this paper, we formulate the problem of minimizing the completion time of all camera sensors as an optimization problem. We propose algorithms for fully distributed optimization, analyze the existence of equilibrium allocations, evaluate the effect of the network topology and of the video characteristics, and the benefits of central coordination. Our results demonstrate that with sufficient information available, distributed optimization can provide low completion times, moreover predictable and stable performance can be achieved with additional, sparse central coordination.
Microphone Subset Selection for MVDR Beamformer Based Noise Reduction
Venue: arXiv cs.SD 2017
Year: 2017

In large-scale wireless acoustic sensor networks (WASNs), many of the sensors will only have a marginal contribution to a certain estimation task. Involving all sensors increases the energy budget unnecessarily and decreases the lifetime of the WASN. Using microphone subset selection, also termed as sensor selection, the most informative sensors can be chosen from a set of candidate sensors to achieve a prescribed inference performance. In this paper, we consider microphone subset selection for minimum variance distortionless response (MVDR) beamformer based noise reduction. The best subset of sensors is determined by minimizing the transmission cost while constraining the output noise power (or signal-to-noise ratio). Assuming the statistical information on correlation matrices of the sensor measurements is available, the sensor selection problem for this model-driven scheme is first solved by utilizing convex optimization techniques. In addition, to avoid estimating the statistics related to all the candidate sensors beforehand, we also propose a data-driven approach to select the best subset using a greedy strategy. The performance of the greedy algorithm converges to that of the model-driven method, while it displays advantages in dynamic scenarios as well as on computational complexity. Compared to a sparse MVDR or radius-based beamformer, experiments show that the proposed methods can guarantee the desired performance with significantly less transmission costs.
Calidad en repositorios digitales en Argentina, estudio comparativo y cualitativo
Venue: arXiv cs.DL 2017
Year: 2017

Numerous institutions and organizations need not only to preserve the material and publications they produce, but also have as their task (although it would be desirable it was an obligation) to publish, disseminate and make publicly available all the results of the research and any other scientific/academic material. The Open Archives Initiative (OAI) and the introduction of Open Archives Initiative Protocol for Metadata Harvesting (OAI-PMH), make this task much easier. The main objective of this work is to make a comparative and qualitative study of the data -metadata specifically- contained in the whole set of Argentine repositories listed in the ROAR portal, focusing on the functional perspective of the quality of this metadata. Another objective is to offer an overview of the status of these repositories, in an attempt to detect common failures and errors institutions incur when storing the metadata of the resources contained in these repositories, and thus be able to suggest measures to be able to improve the load and further retrieval processes. It was found that the eight most used Dublin Core fields are: identifier, type, title, date, subject, creator, language and description. Not all repositories fill all the fields, and the lack of normalization, or the excessive use of fields like language, type, format and subject is somewhat striking, and in some cases even alarming
Music Playlist Continuation by Learning from Hand-Curated Examples and Song Features: Alleviating the Cold-Start Problem for Rare and Out-of-Set Songs
Venue: arXiv cs.IR 2017
Year: 2017

Automated music playlist generation is a specific form of music recommendation. Generally stated, the user receives a set of song suggestions defining a coherent listening session. We hypothesize that the best way to convey such playlist coherence to new recommendations is by learning it from actual curated examples, in contrast to imposing ad hoc constraints. Collaborative filtering methods can be used to capture underlying patterns in hand-curated playlists. However, the scarcity of thoroughly curated playlists and the bias towards popular songs result in the vast majority of songs occurring in very few playlists and thus being poorly recommended. To overcome this issue, we propose an alternative model based on a song-to-playlist classifier, which learns the underlying structure from actual playlists while leveraging song features derived from audio, social tags and independent listening logs. Experiments on two datasets of hand-curated playlists show competitive performance compared to collaborative filtering when sufficient training data is available and more robust performance when recommending rare and out-of-set songs. For example, both approaches achieve a recall@100 of roughly 35% for songs occurring in 5 or more training playists, whereas the proposed model achieves a recall@100 of roughly 15% for songs occurring in 4 or less training playlists, compared to the 3% achieved by collaborative filtering.
Her2 Challenge Contest: A Detailed Assessment of Automated Her2 Scoring Algorithms in Whole Slide Images of Breast Cancer Tissues
Venue: arXiv cs.CV 2017
Year: 2017

Evaluating expression of the Human epidermal growth factor receptor 2 (Her2) by visual examination of immunohistochemistry (IHC) on invasive breast cancer (BCa) is a key part of the diagnostic assessment of BCa due to its recognised importance as a predictive and prognostic marker in clinical practice. However, visual scoring of Her2 is subjective and consequently prone to inter-observer variability. Given the prognostic and therapeutic implications of Her2 scoring, a more objective method is required. In this paper, we report on a recent automated Her2 scoring contest, held in conjunction with the annual PathSoc meeting held in Nottingham in June 2016, aimed at systematically comparing and advancing the state-of-the-art Artificial Intelligence (AI) based automated methods for Her2 scoring. The contest dataset comprised of digitised whole slide images (WSI) of sections from 86 cases of invasive breast carcinoma stained with both Haematoxylin & Eosin (H&E) and IHC for Her2. The contesting algorithms automatically predicted scores of the IHC slides for an unseen subset of the dataset and the predicted scores were compared with the 'ground truth' (a consensus score from at least two experts). We also report on a simple Man vs Machine contest for the scoring of Her2 and show that the automated methods could beat the pathology experts on this contest dataset. This paper presents a benchmark for comparing the performance of automated algorithms for scoring of Her2. It also demonstrates the enormous potential of automated algorithms in assisting the pathologist with objective IHC scoring.
Question-Answering with Grammatically-Interpretable Representations
Venue: arXiv cs.CL 2017
Year: 2017

We introduce an architecture, the Tensor Product Recurrent Network (TPRN). In our application of TPRN, internal representations learned by end-to-end optimization in a deep neural network performing a textual question-answering (QA) task can be interpreted using basic concepts from linguistic theory. No performance penalty need be paid for this increased interpretability: the proposed model performs comparably to a state-of-the-art system on the SQuAD QA task. The internal representation which is interpreted is a Tensor Product Representation: for each input word, the model selects a symbol to encode the word, and a role in which to place the symbol, and binds the two together. The selection is via soft attention. The overall interpretation is built from interpretations of the symbols, as recruited by the trained model, and interpretations of the roles as used by the model. We find support for our initial hypothesis that symbols can be interpreted as lexical-semantic word meanings, while roles can be interpreted as approximations of grammatical roles (or categories) such as subject, wh-word, determiner, etc. Fine-grained analysis reveals specific correspondences between the learned roles and parts of speech as assigned by a standard tagger (Toutanova et al. 2003), and finds several discrepancies in the model's favor. In this sense, the model learns significant aspects of grammar, after having been exposed solely to linguistically unannotated text, questions, and answers: no prior linguistic knowledge is given to the model. What is given is the means to build representations using symbols and roles, with an inductive bias favoring use of these in an approximately discrete manner.
Cybernetic Health
Venue: arXiv cs.CY 2017
Year: 2017

Future health ecosystems demand the integration of emerging data technology with an increased focus on preventive medicine. Cybernetics extracts the full potential of data to serve the spectrum of health care, from acute to chronic problems. Building actionable cybernetic navigation tools can greatly empower optimal health decisions, especially by quantifying lifestyle and environmental data. This data to decisions transformation is powered by intuitive event analysis to offer the best semantic abstraction of dynamic living systems. Achieving the goal of preventive health systems in the cybernetic model occurs through the flow of several components. From personalized models we can predict health status using perpetual sensing and data streams. Given these predictions, we give precise recommendations to best suit the prediction for that individual. To enact these recommendations we use persuasive technology in order to deliver and execute targeted interventions.
An effective algorithm for hyperparameter optimization of neural networks
Venue: arXiv cs.AI 2017
Year: 2017

A major challenge in designing neural network (NN) systems is to determine the best structure and parameters for the network given the data for the machine learning problem at hand. Examples of parameters are the number of layers and nodes, the learning rates, and the dropout rates. Typically, these parameters are chosen based on heuristic rules and manually fine-tuned, which may be very time-consuming, because evaluating the performance of a single parametrization of the NN may require several hours. This paper addresses the problem of choosing appropriate parameters for the NN by formulating it as a box-constrained mathematical optimization problem, and applying a derivative-free optimization tool that automatically and effectively searches the parameter space. The optimization tool employs a radial basis function model of the objective function (the prediction accuracy of the NN) to accelerate the discovery of configurations yielding high accuracy. Candidate configurations explored by the algorithm are trained to a small number of epochs, and only the most promising candidates receive full training. The performance of the proposed methodology is assessed on benchmark sets and in the context of predicting drug-drug interactions, showing promising results. The optimization tool used in this paper is open-source.
Simple Pricing Schemes for the Cloud
Venue: arXiv cs.GT 2017
Year: 2017

The problem of pricing the cloud has attracted much recent attention due to the widespread use of cloud computing and cloud services. From a theoretical perspective, several mechanisms that provide strong efficiency or fairness guarantees and desirable incentive properties have been designed. However, these mechanisms often rely on a rigid model, with several parameters needing to be precisely known in order for the guarantees to hold. In this paper, we consider a stochastic model and show that it is possible to obtain good welfare and revenue guarantees with simple mechanisms that do not make use of the information on some of these parameters. In particular, we prove that a mechanism that sets the same price per time step for jobs of any length achieves at least 50% of the welfare and revenue obtained by a mechanism that can set different prices for jobs of different lengths, and the ratio can be improved if we have more specific knowledge of some parameters. Similarly, a mechanism that sets the same price for all servers even though the servers may receive different kinds of jobs can provide a reasonable welfare and revenue approximation compared to a mechanism that is allowed to set different prices for different servers.
The Future of Ad Blocking: An Analytical Framework and New Techniques
Venue: arXiv cs.CR 2017
Year: 2017

We present a systematic study of ad blocking - and the associated "arms race" - as a security problem. We model ad blocking as a state space with four states and six state transitions, which correspond to techniques that can be deployed by either publishers or ad blockers. We argue that this is a complete model of the system. We propose several new ad blocking techniques, including ones that borrow ideas from rootkits to prevent detection by anti-ad blocking scripts. Another technique uses the insight that ads must be recognizable by humans to comply with laws and industry self-regulation. We have built prototype implementations of three of these techniques, successfully blocking ads and evading detection. We systematically evaluate our proposed techniques, along with existing ones, in terms of security, practicality, and legality. We characterize the order of growth of the development effort required to create/maintain ad blockers as a function of the growth of the web. Based on our state-space model, our new techniques, and this systematization, we offer insights into the likely "end game" of the arms race. We challenge the widespread assumption that the arms race will escalate indefinitely, and instead identify a combination of evolving technical and legal factors that will determine the outcome.
Flexible Cache-Aided Networks with Backhauling
Venue: arXiv cs.IT 2017
Year: 2017

Caching at the edge is a promising technique to cope with the increasing data demand in wireless networks. This paper analyzes the performance of cellular networks consisting of a tier macro-cell wireless backhaul nodes overlaid with a tier of cache-aided small cells. We consider both static and dynamic association policies for content delivery to the user terminals and analyze their performance. In particular, we derive closed-form expressions for the area spectral efficiency and the energy efficiency, which are used to optimize relevant design parameters such as the density of cache-aided small cells and the storage size. By means of this approach, we are able to draw useful design insights for the deployment of highly performing cache-aided tiered networks.
Robust Data Geometric Structure Aligned Close yet Discriminative Domain Adaptation
Venue: arXiv cs.CV 2017
Year: 2017

Domain adaptation (DA) is transfer learning which aims to leverage labeled data in a related source domain to achieve informed knowledge transfer and help the classification of unlabeled data in a target domain. In this paper, we propose a novel DA method, namely Robust Data Geometric Structure Aligned, Close yet Discriminative Domain Adaptation (RSA-CDDA), which brings closer, in a latent joint subspace, both source and target data distributions, and aligns inherent hidden source and target data geometric structures while performing discriminative DA in repulsing both interclass source and target data. The proposed method performs domain adaptation between source and target in solving a unified model, which incorporates data distribution constraints, in particular via a nonparametric distance, i.e., Maximum Mean Discrepancy (MMD), as well as constraints on inherent hidden data geometric structure segmentation and alignment between source and target, through low rank and sparse representation. RSA-CDDA achieves the search of a joint subspace in solving the proposed unified model through iterative optimization, alternating Rayleigh quotient algorithm and inexact augmented Lagrange multiplier algorithm. Extensive experiments carried out on standard DA benchmarks, i.e., 16 cross-domain image classification tasks, verify the effectiveness of the proposed method, which consistently outperforms the state-of-the-art methods.
On Using Time Without Clocks via Zigzag Causality
Venue: arXiv cs.DC 2017
Year: 2017

Even in the absence of clocks, time bounds on the duration of actions enable the use of time for distributed coordination. This paper initiates an investigation of coordination in such a setting. A new communication structure called a zigzag pattern is introduced, and shown to guarantee bounds on the relative timing of events in this clockless model. Indeed, zigzag patterns are shown to be necessary and sufficient for establishing that events occur in a manner that satisfies prescribed bounds. We capture when a process can know that an appropriate zigzag pattern exists, and use this to provide necessary and sufficient conditions for timed coordination of events using a full-information protocol in the clockless model.
Representing the suffix tree with the CDAWG
Venue: arXiv cs.DS 2017
Year: 2017

Given a string $T$, it is known that its suffix tree can be represented using the compact directed acyclic word graph (CDAWG) with $e_T$ arcs, taking overall $O(e_T+e_{\overline{T}})$ words of space, where ${\overline{T}}$ is the reverse of $T$, and supporting some key operations in time between $O(1)$ and $O(\log{\log{n}})$ in the worst case. This representation is especially appealing for highly repetitive strings, like collections of similar genomes or of version-controlled documents, in which $e_T$ grows sublinearly in the length of $T$ in practice. In this paper we augment such representation, supporting a number of additional queries in worst-case time between $O(1)$ and $O(\log{n})$ in the RAM model, without increasing space complexity asymptotically. Our technique, based on a heavy path decomposition of the suffix tree, enables also a representation of the suffix array, of the inverse suffix array, and of $T$ itself, that takes $O(e_T)$ words of space, and that supports random access in $O(\log{n})$ time. Furthermore, we establish a connection between the reversed CDAWG of $T$ and a context-free grammar that produces $T$ and only $T$, which might have independent interest.
On the Success Probability of Decoding (Partial) Unit Memory Codes
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we derive analytic expressions for the success probability of decoding (Partial) Unit Memory codes in memoryless channels. An applications of this result is that these codes outperform individual block codes in certain channels.
MmWave System for Future ITS: A MAC-layer Approach for V2X Beam Steering
Venue: arXiv cs.NI 2017
Year: 2017

Millimeter Waves (mmWave) systems have the potential of enabling multi-gigabit-per-second communications in future Intelligent Transportation Systems (ITSs). Unfortunately, because of the increased vehicular mobility, they require frequent antenna beam realignments - thus significantly increasing the in-band Beamforming (BF) overhead. In this paper, we propose Smart Motion-prediction Beam Alignment (SAMBA), a MAC-layer algorithm that exploits the information broadcast via DSRC beacons by all vehicles. Based on this information, overhead-free BF is achieved by estimating the position of the vehicle and predicting its motion. Moreover, adapting the beamwidth with respect to the estimated position can further enhance the performance. Our investigation shows that SAMBA outperforms the IEEE 802.11ad BF strategy, increasing the data rate by more than twice for sparse vehicle density while enhancing the network throughput proportionally to the number of vehicles. Furthermore, SAMBA was proven to be more efficient compared to legacy BF algorithm under highly dynamic vehicular environments and hence, a viable solution for future ITS services.
On Patterns and Re-Use in Bioinformatics Databases
Venue: arXiv cs.DL 2017
Year: 2017

As the quantity of data being depositing into biological databases continues to increase, it becomes ever more vital to develop methods that enable us to understand this data and ensure that the knowledge is correct. It is widely-held that data percolates between different databases, which causes particular concerns for data correctness; if this percolation occurs, incorrect data in one database may eventually affect many others while, conversely, corrections in one database may fail to percolate to others. In this paper, we test this widely-held belief by directly looking for sentence reuse both within and between databases. Further, we investigate patterns of how sentences are reused over time. Finally, we consider the limitations of this form of analysis and the implications that this may have for bioinformatics database design. We show that reuse of annotation is common within many different databases, and that also there is a detectable level of reuse between databases. In addition, we show that there are patterns of reuse that have previously been shown to be associated with percolation errors.