OpenRaiser/Intern-Atlas huggingface dataset:
Managing Hybrid Main Memories with a Page-Utility Driven Performance Model
Venue: arXiv cs.AR 2015
Year: 2015

Hybrid memory systems comprised of dynamic random access memory (DRAM) and non-volatile memory (NVM) have been proposed to exploit both the capacity advantage of NVM and the latency and dynamic energy advantages of DRAM. An important problem for such systems is how to place data between DRAM and NVM to improve system performance. In this paper, we devise the first mechanism, called UBM (page Utility Based hybrid Memory management), that systematically estimates the system performance benefit of placing a page in DRAM versus NVM and uses this estimate to guide data placement. UBM's estimation method consists of two major components. First, it estimates how much an application's stall time can be reduced if the accessed page is placed in DRAM. To do this, UBM comprehensively considers access frequency, row buffer locality, and memory level parallelism (MLP) to estimate the application's stall time reduction. Second, UBM estimates how much each application's stall time reduction contributes to overall system performance. Based on this estimation method, UBM can determine and place the most critical data in DRAM to directly optimize system performance. Experimental results show that UBM improves system performance by 14% on average (and up to 39%) compared to the best of three state-of-the-art mechanisms for a large number of data-intensive workloads from the SPEC CPU2006 and Yahoo Cloud Serving Benchmark (YCSB) suites.
Polynomial Kernels for Weighted Problems
Venue: arXiv cs.CC 2015
Year: 2015

Kernelization is a formalization of efficient preprocessing for NP-hard problems using the framework of parameterized complexity. Among open problems in kernelization it has been asked many times whether there are deterministic polynomial kernelizations for Subset Sum and Knapsack when parameterized by the number $n$ of items. We answer both questions affirmatively by using an algorithm for compressing numbers due to Frank and Tardos (Combinatorica 1987). This result had been first used by Marx and Végh (ICALP 2013) in the context of kernelization. We further illustrate its applicability by giving polynomial kernels also for weighted versions of several well-studied parameterized problems. Furthermore, when parameterized by the different item sizes we obtain a polynomial kernelization for Subset Sum and an exponential kernelization for Knapsack. Finally, we also obtain kernelization results for polynomial integer programs.
Incremental LSTM-based Dialog State Tracker
Venue: arXiv cs.CL 2015
Year: 2015

A dialog state tracker is an important component in modern spoken dialog systems. We present an incremental dialog state tracker, based on LSTM networks. It directly uses automatic speech recognition hypotheses to track the state. We also present the key non-standard aspects of the model that bring its performance close to the state-of-the-art and experimentally analyze their contribution: including the ASR confidence scores, abstracting scarcely represented values, including transcriptions in the training data, and model averaging.
A Combinatorial Bound for Beacon-based Routing in Orthogonal Polygons
Venue: arXiv cs.CG 2015
Year: 2015

Beacon attraction is a movement system whereby a robot (modeled as a point in 2D) moves in a free space so as to always locally minimize its Euclidean distance to an activated beacon (which is also a point). This results in the robot moving directly towards the beacon when it can, and otherwise sliding along the edge of an obstacle. When a robot can reach the activated beacon by this method, we say that the beacon attracts the robot. A beacon routing from $p$ to $q$ is a sequence $b_1, b_2,$ ..., $b_{k}$ of beacons such that activating the beacons in order will attract a robot from $p$ to $b_1$ to $b_2$ ... to $b_{k}$ to $q$, where $q$ is considered to be a beacon. A routing set of beacons is a set $B$ of beacons such that any two points $p, q$ in the free space have a beacon routing with the intermediate beacons $b_1, b_2,$ ..., $b_{k}$ all chosen from $B$. Here we address the question of "how large must such a $B$ be?" in orthogonal polygons, and show that the answer is "sometimes as large as $[(n-4)/3]$, but never larger."
Predicting Scheduling Failures in the Cloud
Venue: arXiv cs.DC 2015
Year: 2015

Cloud Computing has emerged as a key technology to deliver and manage computing, platform, and software services over the Internet. Task scheduling algorithms play an important role in the efficiency of cloud computing services as they aim to reduce the turnaround time of tasks and improve resource utilization. Several task scheduling algorithms have been proposed in the literature for cloud computing systems, the majority relying on the computational complexity of tasks and the distribution of resources. However, several tasks scheduled following these algorithms still fail because of unforeseen changes in the cloud environments. In this paper, using tasks execution and resource utilization data extracted from the execution traces of real world applications at Google, we explore the possibility of predicting the scheduling outcome of a task using statistical models. If we can successfully predict tasks failures, we may be able to reduce the execution time of jobs by rescheduling failed tasks earlier (i.e., before their actual failing time). Our results show that statistical models can predict task failures with a precision up to 97.4%, and a recall up to 96.2%. We simulate the potential benefits of such predictions using the tool kit GloudSim and found that they can improve the number of finished tasks by up to 40%. We also perform a case study using the Hadoop framework of Amazon Elastic MapReduce (EMR) and the jobs of a gene expression correlations analysis study from breast cancer research. We find that when extending the scheduler of Hadoop with our predictive models, the percentage of failed jobs can be reduced by up to 45%, with an overhead of less than 5 minutes.
A pilot study of the use of LogEx, lessons learned
Venue: arXiv cs.CY 2015
Year: 2015

LogEx is a learning environment that supports students in rewriting propositional logical formulae, using standard equivalences. We organized a pilot study to prepare a large scale evaluation of the learning environment. In this paper we describe this study, together with the outcomes, which teach us valuable lessons for the large scale evaluation.
Easyprove: a tool for teaching precise reasoning
Venue: arXiv cs.CY 2015
Year: 2015

Teaching precise mathematical reasoning can be very hard. It is very easy for a student to make a subtle mistake in a proof which invalidates it, but it is often hard for the teacher to pinpoint and explain the problem in the (often chaotically written) student's proof. We present Easyprove, an interactive proof assistant aimed at first year computer science students and high school students, intended as a supplementary tool for teaching logical reasoning. The system is a Web application with a natural, mouse-oriented user interface.
Logic considered fun
Venue: arXiv cs.CY 2015
Year: 2015

This report describes the development and use of an online teaching tool giving students exercises in logical modelling, or \emph{formalisation} as it is called in the older literature. The original version of the site, `Logic for Fun', dates from 2001, though it was little used except by small groups of students at the Australian National University. It is currently in the process of being replaced by a new version, free to all Internet users, intended to be promoted widely as a useful addition to both online and traditional logic courses.
Simple Priced Timed Games Are Not That Simple
Venue: arXiv cs.GT 2015
Year: 2015

Priced timed games are two-player zero-sum games played on priced timed automata (whose locations and transitions are labeled by weights modeling the costs of spending time in a state and executing an action, respectively). The goals of the players are to minimise and maximise the cost to reach a target location, respectively. We consider priced timed games with one clock and arbitrary (positive and negative) weights and show that, for an important subclass of theirs (the so-called simple priced timed games), one can compute, in exponential time, the optimal values that the players can achieve, with their associated optimal strategies. As side results, we also show that one-clock priced timed games are determined and that we can use our result on simple priced timed games to solve the more general class of so-called reset-acyclic priced timed games (with arbitrary weights and one-clock).
Towards Green and Infinite Capacity in Wireless Communication Networks: Beyond The Shannon Theorem
Venue: arXiv cs.IT 2015
Year: 2015

New and novel way for resources allocation in wireless communication has been proposed in this paper. Under this new method, it has been shown that the required power budget becomes independent of the number of served terminals in the downlink. However, the required power depends only of the coverage area, i.e. the channel losses at the cell boarder. Therefore, huge number (theoretically any number) of terminals could be supported concurrently at finite and small downlink power budget. This could be very useful to support the downlink signalling channels in HSPA+, LTE, and 5G. It can be very useful also to support huge D2D communication downlinks. Moreover, and based on the same concept, a new system configuration for a single link point-to-point communication has been presented. With this new configuration, the achieved data rate becomes independent of the required transmit power. This means that any data rate can be achieved at the target BER and with small and finite transmit power. This seems violating with some major results of the Shannon theorem. This issue will be discussed in details in this article.
Rich Component Analysis
Venue: arXiv cs.LG 2015
Year: 2015

In many settings, we have multiple data sets (also called views) that capture different and overlapping aspects of the same phenomenon. We are often interested in finding patterns that are unique to one or to a subset of the views. For example, we might have one set of molecular observations and one set of physiological observations on the same group of individuals, and we want to quantify molecular patterns that are uncorrelated with physiology. Despite being a common problem, this is highly challenging when the correlations come from complex distributions. In this paper, we develop the general framework of Rich Component Analysis (RCA) to model settings where the observations from different views are driven by different sets of latent components, and each component can be a complex, high-dimensional distribution. We introduce algorithms based on cumulant extraction that provably learn each of the components without having to model the other components. We show how to integrate RCA with stochastic gradient descent into a meta-algorithm for learning general models, and demonstrate substantial improvement in accuracy on several synthetic and real datasets in both supervised and unsupervised tasks. Our method makes it possible to learn latent variable models when we don't have samples from the true model but only samples after complex perturbations.
Fuzzy Answer Set Computation via Satisfiability Modulo Theories
Venue: arXiv cs.AI 2015
Year: 2015

Fuzzy answer set programming (FASP) combines two declarative frameworks, answer set programming and fuzzy logic, in order to model reasoning by default over imprecise information. Several connectives are available to combine different expressions; in particular the \Godel and \Luka fuzzy connectives are usually considered, due to their properties. Although the \Godel conjunction can be easily eliminated from rule heads, we show through complexity arguments that such a simplification is infeasible in general for all other connectives. %, even if bodies are restricted to \Luka or \Godel conjunctions. The paper analyzes a translation of FASP programs into satisfiability modulo theories~(SMT), which in general produces quantified formulas because of the minimality of the semantics. Structural properties of many FASP programs allow to eliminate the quantification, or to sensibly reduce the number of quantified variables. Indeed, integrality constraints can replace recursive rules commonly used to force Boolean interpretations, and completion subformulas can guarantee minimality for acyclic programs with atomic heads. Moreover, head cycle free rules can be replaced by shifted subprograms, whose structure depends on the eliminated head connective, so that ordered completion may replace the minimality check if also \Luka disjunction in rule bodies is acyclic. The paper also presents and evaluates a prototype system implementing these translations. To appear in Theory and Practice of Logic Programming (TPLP), Proceedings of ICLP 2015.
Simultaneous state and exogenous input estimation for nonlinear systems using boundary-layer sliding mode observers
Venue: arXiv cs.SY 2015
Year: 2015

While sliding mode observers (SMOs) using discontinuous relays are widely analyzed, most SMOs are implemented computationally using a continuous approximation of the discontinuous relays. This approximation results in the formation of a boundary layer in a neighborhood of the sliding manifold in the observer error space. Therefore, it becomes necessary to develop methods for attenuating the effect of the boundary layer and guaranteeing performance bounds on the resulting state estimation error. In this paper, a method is proposed for constructing boundary-layer SMOs (BL-SMOs) with prescribed state estimation error bounds. The BL-SMO formulation is then extended to simultaneously estimate exogenous inputs (disturbance signals in the state and output vector fields), along with the system state. Two numerical examples are presented to illustrate the effectiveness of the proposed approach.
Recurrent Polynomial Network for Dialogue State Tracking
Venue: arXiv cs.CL 2015
Year: 2015

Dialogue state tracking (DST) is a process to estimate the distribution of the dialogue states as a dialogue progresses. Recent studies on constrained Markov Bayesian polynomial (CMBP) framework take the first step towards bridging the gap between rule-based and statistical approaches for DST. In this paper, the gap is further bridged by a novel framework -- recurrent polynomial network (RPN). RPN's unique structure enables the framework to have all the advantages of CMBP including efficiency, portability and interpretability. Additionally, RPN achieves more properties of statistical approaches than CMBP. RPN was evaluated on the data corpora of the second and the third Dialog State Tracking Challenge (DSTC-2/3). Experiments showed that RPN can significantly outperform both traditional rule-based approaches and statistical approaches with similar feature set. Compared with the state-of-the-art statistical DST approaches with a lot richer features, RPN is also competitive.
Case Management: a data set of definitions
Venue: arXiv cs.SE 2015
Year: 2015

Knowledge-intensive processes (KiPs) are becoming increasingly important for organizations with the rise of the knowledge society. Due to their unpredictable and emergent characteristic worklfow management solutions are not suitable to support KiPs. Various case management related approaches have been proposed by researchers and practitioners to support characteristics of KiPs. In this paper we provide a comprehensive list of definitions available on case management, e.g. case handling, adaptive case management, dynamic case management, production case management. For every definition we present the explicit definition, paragraphs that better describe and summarize the case management approach, or extracted sequences that define the term in the referenced publication. All of these definitions are compared against characteristics of KiPs in order to get about understanding of the domain.
Feature Normalisation for Robust Speech Recognition
Venue: arXiv cs.CL 2015
Year: 2015

Speech recognition system performance degrades in noisy environments. If the acoustic models are built using features of clean utterances, the features of a noisy test utterance would be acoustically mismatched with the trained model. This gives poor likelihoods and poor recognition accuracy. Model adaptation and feature normalisation are two broad areas that address this problem. While the former often gives better performance, the latter involves estimation of lesser number of parameters, making the system feasible for practical implementations. This research focuses on the efficacies of various subspace, statistical and stereo based feature normalisation techniques. A subspace projection based method has been investigated as a standalone and adjunct technique involving reconstruction of noisy speech features from a precomputed set of clean speech building-blocks. The building blocks are learned using non-negative matrix factorisation (NMF) on log-Mel filter bank coefficients, which form a basis for the clean speech subspace. The work provides a detailed study on how the method can be incorporated into the extraction process of Mel-frequency cepstral coefficients. Experimental results show that the new features are robust to noise, and achieve better results when combined with the existing techniques. The work also proposes a modification to the training process of SPLICE algorithm for noise robust speech recognition. It is based on feature correlations, and enables this stereo-based algorithm to improve the performance in all noise conditions, especially in unseen cases. Further, the modified framework is extended to work for non-stereo datasets where clean and noisy training utterances, but not stereo counterparts, are required. An MLLR-based computationally efficient run-time noise adaptation method in SPLICE framework has been proposed.
Spectral Detection on Sparse Hypergraphs
Venue: arXiv cs.SI 2015
Year: 2015

We consider the problem of the assignment of nodes into communities from a set of hyperedges, where every hyperedge is a noisy observation of the community assignment of the adjacent nodes. We focus in particular on the sparse regime where the number of edges is of the same order as the number of vertices. We propose a spectral method based on a generalization of the non-backtracking Hashimoto matrix into hypergraphs. We analyze its performance on a planted generative model and compare it with other spectral methods and with Bayesian belief propagation (which was conjectured to be asymptotically optimal for this model). We conclude that the proposed spectral method detects communities whenever belief propagation does, while having the important advantages to be simpler, entirely nonparametric, and to be able to learn the rule according to which the hyperedges were generated without prior information.
Solomonoff Induction Violates Nicod's Criterion
Venue: arXiv cs.LG 2015
Year: 2015

Nicod's criterion states that observing a black raven is evidence for the hypothesis H that all ravens are black. We show that Solomonoff induction does not satisfy Nicod's criterion: there are time steps in which observing black ravens decreases the belief in H. Moreover, while observing any computable infinite string compatible with H, the belief in H decreases infinitely often when using the unnormalized Solomonoff prior, but only finitely often when using the normalized Solomonoff prior. We argue that the fault is not with Solomonoff induction; instead we should reject Nicod's criterion.
Beyond Contagion: Reality Mining Reveals Complex Patterns of Social Influence
Venue: arXiv cs.SI 2015
Year: 2015

Contagion, a concept from epidemiology, has long been used to characterize social influence on people's behavior and affective (emotional) states. While it has revealed many useful insights, it is not clear whether the contagion metaphor is sufficient to fully characterize the complex dynamics of psychological states in a social context. Using wearable sensors that capture daily face-to-face interaction, combined with three daily experience sampling surveys, we collected the most comprehensive data set of personality and emotion dynamics of an entire community of work. From this high-resolution data about actual (rather than self-reported) face-to-face interaction, a complex picture emerges where contagion (that can be seen as adaptation of behavioral responses to the behavior of other people) cannot fully capture the dynamics of transitory states. We found that social influence has two opposing effects on states: \emph{adaptation} effects that go beyond mere contagion, and \emph{complementarity} effects whereby individuals' behaviors tend to complement the behaviors of others. Surprisingly, these effects can exhibit completely different directions depending on the stable personality or emotional dispositions (stable traits) of target individuals. Our findings provide a foundation for richer models of social dynamics, and have implications on organizational engineering and workplace well-being.
Soft Pilot Reuse and Multi-Cell Block Diagonalization Precoding for Massive MIMO Systems
Venue: arXiv cs.IT 2015
Year: 2015

The users at cell edge of a massive multiple-input multiple-output (MIMO) system suffer from severe pilot contamination, which leads to poor quality of service (QoS). In order to enhance the QoS for these edge users, soft pilot reuse (SPR) combined with multi-cell block diagonalization (MBD) precoding are proposed. Specifically, the users are divided into two groups according to their large-scale fading coefficients, referred to as the center users, who only suffer from modest pilot contamination and the edge users, who suffer from severe pilot contamination. Based on this distinction, the SPR scheme is proposed for improving the QoS for the edge users, whereby a cell-center pilot group is reused for all cell-center users in all cells, while a cell-edge pilot group is applied for the edge users in the adjacent cells. By extending the classical block diagonalization precoding to a multi-cell scenario, the MBD precoding scheme projects the downlink transmit signal onto the null space of the subspace spanned by the inter-cell channels of the edge users in adjacent cells. Thus, the inter-cell interference contaminating the edge users' signals in the adjacent cells can be efficiently mitigated and hence the QoS of these edge users can be further enhanced. Our theoretical analysis and simulation results demonstrate that both the uplink and downlink rates of the edge users are significantly improved, albeit at the cost of the slightly decreased rate of center users.
Multicast Network Design Game on a Ring
Venue: arXiv cs.GT 2015
Year: 2015

In this paper we study quality measures of different solution concepts for the multicast network design game on a ring topology. We recall from the literature a lower bound of 4/3 and prove a matching upper bound for the price of stability, which is the ratio of the social costs of a best Nash equilibrium and of a general optimum. Therefore, we answer an open question posed by Fanelli et al. in [12]. We prove an upper bound of 2 for the ratio of the costs of a potential optimizer and of an optimum, provide a construction of a lower bound, and give a computer-assisted argument that it reaches $2$ for any precision. We then turn our attention to players arriving one by one and playing myopically their best response. We provide matching lower and upper bounds of 2 for the myopic sequential price of anarchy (achieved for a worst-case order of the arrival of the players). We then initiate the study of myopic sequential price of stability and for the multicast game on the ring we construct a lower bound of 4/3, and provide an upper bound of 26/19. To the end, we conjecture and argue that the right answer is 4/3.