OpenRaiser/Intern-Atlas huggingface dataset:
Direct Load Control of Thermostatically Controlled Loads Based on Sparse Observations Using Deep Reinforcement Learning
Venue: arXiv cs.LG 2017
Year: 2017

This paper considers a demand response agent that must find a near-optimal sequence of decisions based on sparse observations of its environment. Extracting a relevant set of features from these observations is a challenging task and may require substantial domain knowledge. One way to tackle this problem is to store sequences of past observations and actions in the state vector, making it high dimensional, and apply techniques from deep learning. This paper investigates the capabilities of different deep learning techniques, such as convolutional neural networks and recurrent neural networks, to extract relevant features for finding near-optimal policies for a residential heating system and electric water heater that are hindered by sparse observations. Our simulation results indicate that in this specific scenario, feeding sequences of time-series to an LSTM network, which is a specific type of recurrent neural network, achieved a higher performance than stacking these time-series in the input of a convolutional neural network or deep neural network.
Cognitive Hierarchy and Voting Manipulation
Venue: arXiv cs.GT 2017
Year: 2017

By the Gibbard--Satterthwaite theorem, every reasonable voting rule for three or more alternatives is susceptible to manipulation: there exist elections where one or more voters can change the election outcome in their favour by unilaterally modifying their vote. When a given election admits several such voters, strategic voting becomes a game among potential manipulators: a manipulative vote that leads to a better outcome when other voters are truthful may lead to disastrous results when other voters choose to manipulate as well. We consider this situation from the perspective of a boundedly rational voter, and use the cognitive hierarchy framework to identify good strategies. We then investigate the associated algorithmic questions under the k-approval voting rule. We obtain positive algorithmic results for k=1 and 2, and NP- and coNP-hardness results for k>3.
Process Description, Behavior, and Control
Venue: arXiv cs.SE 2017
Year: 2017

Modeling processes are the activities of capturing and representing processes and control of their dynamic behavior. Desired features of the model include capture of relevant aspects of a real phenomenon, understandability, and completeness of static and dynamic specifications. This paper proposes a diagrammatic language for engineering process modeling that provides an integration tool for capturing the static description of processes, framing their behaviors in terms of events, and utilizing the resultant model for controlling processes. Without loss of generality, the focus of the paper is on process modeling in the area of computer engineering, and specifically, on modeling of computer services. To demonstrate the viability of the method, the proposed model is applied to depicting flow of services in the Information Technology department of a government ministry.
Communication versus Computation: Duality for multiple access channels and source coding
Venue: arXiv cs.IT 2017
Year: 2017

Computation codes in network information theory are designed for the scenarios where the decoder is not interested in recovering the information sources themselves, but only a function thereof. Körner and Marton showed for distributed source coding that such function decoding can be achieved more efficiently than decoding the full information sources. Compute-and-forward has shown that function decoding, in combination with network coding ideas, is a useful building block for end-to-end communication. In both cases, good computation codes are the key component in the coding schemes. In this work, we expose the fact that good computation codes could undermine the capability of the codes for recovering the information sources individually, e.g., for the purpose of multiple access and distributed source coding. Particularly, we establish duality results between the codes which are good for computation and the codes which are good for multiple access or distributed compression.
A Naive Algorithm for Feedback Vertex Set
Venue: arXiv cs.DS 2017
Year: 2017

Given a graph on $n$ vertices and an integer $k$, the feedback vertex set problem asks for the deletion of at most $k$ vertices to make the graph acyclic. We show that a greedy branching algorithm, which always branches on an undecided vertex with the largest degree, runs in single-exponential time, i.e., $O(c^k\cdot n^2)$ for some constant $c$.
Vertex Deletion Problems on Chordal Graphs
Venue: arXiv cs.DS 2017
Year: 2017

Containing many classic optimization problems, the family of vertex deletion problems has an important position in algorithm and complexity study. The celebrated result of Lewis and Yannakakis gives a complete dichotomy of their complexity. It however has nothing to say about the case when the input graph is also special. This paper initiates a systematic study of vertex deletion problems from one subclass of chordal graphs to another. We give polynomial-time algorithms or proofs of NP-completeness for most of the problems. In particular, we show that the vertex deletion problem from chordal graphs to interval graphs is NP-complete.
A New Game Equivalence and its Modal Logic
Venue: arXiv cs.GT 2017
Year: 2017

We revisit the crucial issue of natural game equivalences, and semantics of game logics based on these. We present reasons for investigating finer concepts of game equivalence than equality of standard powers, though staying short of modal bisimulation. Concretely, we propose a more finegrained notion of equality of "basic powers" which record what players can force plus what they leave to others to do, a crucial feature of interaction. This notion is closer to game-theoretic strategic form, as we explain in detail, while remaining amenable to logical analysis. We determine the properties of basic powers via a new representation theorem, find a matching "instantial neighborhood game logic", and show how our analysis can be extended to a new game algebra and dynamic game logic.
Bisimulation in Inquisitive Modal Logic
Venue: arXiv cs.LO 2017
Year: 2017

Inquisitive modal logic, InqML, is a generalisation of standard Kripke-style modal logic. In its epistemic incarnation, it extends standard epistemic logic to capture not just the information that agents have, but also the questions that they are interested in. Technically, InqML fits within the family of logics based on team semantics. From a model-theoretic perspective, it takes us a step in the direction of monadic second-order logic, as inquisitive modal operators involve quantification over sets of worlds. We introduce and investigate the natural notion of bisimulation equivalence in the setting of InqML. We compare the expressiveness of InqML and first-order logic, and characterise inquisitive modal logic as the bisimulation invariant fragments of first-order logic over various classes of two-sorted relational structures. These results crucially require non-classical methods in studying bisimulations and first-order expressiveness over non-elementary classes.
Games With Tolerant Players
Venue: arXiv cs.GT 2017
Year: 2017

A notion of pi-tolerant equilibrium is defined that takes into account that players have some tolerance regarding payoffs in a game. This solution concept generalizes Nash and refines epsilon-Nash equilibrium in a natural way. We show that pi-tolerant equilibrium can explain cooperation in social dilemmas such as Prisoner's Dilemma and the Public Good game. We then examine the structure of particularly cooperative pi-tolerant equilibria, where players are as cooperative as they can be, subject to their tolerances, in Prisoner's Dilemma. To the extent that cooperation is due to tolerance, these results provide guidance to a mechanism designer who has some control over the payoffs in a game, and suggest ways in which cooperation can be increased.
Arbitrary Arrow Update Logic with Common Knowledge is neither RE nor co-RE
Venue: arXiv cs.LO 2017
Year: 2017

Arbitrary Arrow Update Logic with Common Knowledge (AAULC) is a dynamic epistemic logic with (i) an arrow update operator, which represents a particular type of information change and (ii) an arbitrary arrow update operator, which quantifies over arrow updates. By encoding the execution of a Turing machine in AAULC, we show that neither the valid formulas nor the satisfiable formulas of AAULC are recursively enumerable. In particular, it follows that AAULC does not have a recursive axiomatization.
Optimizing Epistemic Model Checking Using Conditional Independence (Extended Abstract)
Venue: arXiv cs.LO 2017
Year: 2017

This paper shows that conditional independence reasoning can be applied to optimize epistemic model checking, in which one verifies that a model for a number of agents operating with imperfect information satisfies a formula expressed in a modal multi-agent logic of knowledge. The optimization has been implemented in the epistemic model checker MCK. The paper reports experimental results demonstrating that it can yield multiple orders of magnitude performance improvements.
Bayesian Decision Theory and Stochastic Independence
Venue: arXiv cs.GT 2017
Year: 2017

Stochastic independence has a complex status in probability theory. It is not part of the definition of a probability measure, but it is nonetheless an essential property for the mathematical development of this theory. Bayesian decision theorists such as Savage can be criticized for being silent about stochastic independence. From their current preference axioms, they can derive no more than the definitional properties of a probability measure. In a new framework of twofold uncertainty, we introduce preference axioms that entail not only these definitional properties, but also the stochastic independence of the two sources of uncertainty. This goes some way towards filling a curious lacuna in Bayesian decision theory.
Together We Know How to Achieve: An Epistemic Logic of Know-How (Extended Abstract)
Venue: arXiv cs.AI 2017
Year: 2017

The existence of a coalition strategy to achieve a goal does not necessarily mean that the coalition has enough information to know how to follow the strategy. Neither does it mean that the coalition knows that such a strategy exists. The paper studies an interplay between the distributed knowledge, coalition strategies, and coalition "know-how" strategies. The main technical result is a sound and complete trimodal logical system that describes the properties of this interplay.
Detection of Trending Topic Communities: Bridging Content Creators and Distributors
Venue: arXiv cs.SI 2017
Year: 2017

The rise of a trending topic on Twitter or Facebook leads to the temporal emergence of a set of users currently interested in that topic. Given the temporary nature of the links between these users, being able to dynamically identify communities of users related to this trending topic would allow for a rapid spread of information. Indeed, individual users inside a community might receive recommendations of content generated by the other users, or the community as a whole could receive group recommendations, with new content related to that trending topic. In this paper, we tackle this challenge, by identifying coherent topic-dependent user groups, linking those who generate the content (creators) and those who spread this content, e.g., by retweeting/reposting it (distributors). This is a novel problem on group-to-group interactions in the context of recommender systems. Analysis on real-world Twitter data compare our proposal with a baseline approach that considers the retweeting activity, and validate it with standard metrics. Results show the effectiveness of our approach to identify communities interested in a topic where each includes content creators and content distributors, facilitating users' interactions and the spread of new information.
Representation-Aggregation Networks for Segmentation of Multi-Gigapixel Histology Images
Venue: arXiv cs.CV 2017
Year: 2017

Convolutional Neural Network (CNN) models have become the state-of-the-art for most computer vision tasks with natural images. However, these are not best suited for multi-gigapixel resolution Whole Slide Images (WSIs) of histology slides due to large size of these images. Current approaches construct smaller patches from WSIs which results in the loss of contextual information. We propose to capture the spatial context using novel Representation-Aggregation Network (RAN) for segmentation purposes, wherein the first network learns patch-level representation and the second network aggregates context from a grid of neighbouring patches. We can use any CNN for representation learning, and can utilize CNN or 2D-Long Short Term Memory (2D-LSTM) for context-aggregation. Our method significantly outperformed conventional patch-based CNN approaches on segmentation of tumour in WSIs of breast cancer tissue sections.
LCD codes over ${\mathbb F}_q $ are as good as linear codes for q at least four
Venue: arXiv cs.IT 2017
Year: 2017

The hull $H(C)$ of a linear code $C$ is defined by $H(C)=C \cap C^\perp$. A linear code with a complementary dual (LCD) is a linear code with $H(C)=\{0\}$. The dimension of the hull of a code is an invariant under permutation equivalence. For binary and ternary codes the dimension of the hull is also invariant under monomial equivalence and we show that this invariant is determined by the extended weight enumerator of the code.\\ The hull of a code is not invariant under monomial equivalence if $q\geq 4$. We show that every ${\mathbb F}_q $-linear code is monomial equivalent with an LCD code in case $q \geq 4$. The proof uses techniques from Gröbner basis theory. We conclude that if there exists an ${\mathbb F}_q $-linear code with parameters $[n,k,d]_q$ and $q \geq 4$, then there exists also a LCD code with the same parameters. Hence this holds for optimal and MDS codes. In particular there exist LCD codes that are above the Gilbert-Varshamov bound if $q$ is a square and $q\geq 49$ by the existence of such codes that are algebraic geometric.\\ Similar results are obtained with respect to Hermitian LCD codes.
Algorithms for Approximate Subtropical Matrix Factorization
Venue: arXiv cs.LG 2017
Year: 2017

Matrix factorization methods are important tools in data mining and analysis. They can be used for many tasks, ranging from dimensionality reduction to visualization. In this paper we concentrate on the use of matrix factorizations for finding patterns from the data. Rather than using the standard algebra -- and the summation of the rank-1 components to build the approximation of the original matrix -- we use the subtropical algebra, which is an algebra over the nonnegative real values with the summation replaced by the maximum operator. Subtropical matrix factorizations allow "winner-takes-it-all" interpretations of the rank-1 components, revealing different structure than the normal (nonnegative) factorizations. We study the complexity and sparsity of the factorizations, and present a framework for finding low-rank subtropical factorizations. We present two specific algorithms, called Capricorn and Cancer, that are part of our framework. They can be used with data that has been corrupted with different types of noise, and with different error metrics, including the sum-of-absolute differences, Frobenius norm, and Jensen--Shannon divergence. Our experiments show that the algorithms perform well on data that has subtropical structure, and that they can find factorizations that are both sparse and easy to interpret.
Inductive and Functional Types in Ludics
Venue: arXiv cs.LO 2017
Year: 2017

Ludics is a logical framework in which types/formulas are modelled by sets of terms with the same computational behaviour. This paper investigates the representation of inductive data types and functional types in ludics. We study their structure following a game semantics approach. Inductive types are interpreted as least fixed points, and we prove an internal completeness result giving an explicit construction for such fixed points. The interactive properties of the ludics interpretation of inductive and functional types are then studied. In particular, we identify which higher-order functions types fail to satisfy type safety, and we give a computational explanation.
An Introduction to OFDM-OQAM
Venue: arXiv cs.IT 2017
Year: 2017

The Filter Bank MultiCarrier (FBMC) modulation with Offset QAM (OQAM), also know as OFDM-OQAM, has been very well studied in, roughly speaking, the last 15 years. A rich literature exists on the principle itself, discrete-time version and implementation, equalization, extension to MIMO, etc. This text, written in a tutorial style, explains the idea of Offset QAM and why it works from a Communications Engineer point of view. The language is very simple and the math elementary. Students and researchers in universities or practitioners who are interested in gaining an intuition into the logic behind OFDM-OQAM will hopefully enjoy reading this text. On the other hand, those interested in a quick understanding of the idea, just enough to start using the waveform, can find far better material.
Strawman: an Ensemble of Deep Bag-of-Ngrams for Sentiment Analysis
Venue: arXiv cs.CL 2017
Year: 2017

This paper describes a builder entry, named "strawman", to the sentence-level sentiment analysis task of the "Build It, Break It" shared task of the First Workshop on Building Linguistically Generalizable NLP Systems. The goal of a builder is to provide an automated sentiment analyzer that would serve as a target for breakers whose goal is to find pairs of minimally-differing sentences that break the analyzer.
Fundamental Limits on Latency in Transceiver Cache-Aided HetNets
Venue: arXiv cs.IT 2017
Year: 2017

Stringent mobile usage characteristics force wire- less networks to undergo a paradigm shift from conventional connection-centric to content-centric deployment. With respect to 5G, caching and heterogeneous networks (HetNet) are key technologies that will facilitate the evolution of highly content- centric networks by facilitating unified quality of service in terms of low-latency communication. In this paper, we study the impact of transceiver caching on the latency for a HetNet consisting of a single user, a receiver and one cache-assisted transceiver. We define an information-theoretic metric, the delivery time per bit (DTB), that captures the delivery latency. We establish coinciding lower and upper bounds on the DTB as a function of cache size and wireless channel parameters; thus, enabling a complete characterization of the DTB optimality of the network under study. As a result, we identify cache beneficial and non-beneficial channel regimes.
Enabling Mutation Testing for Android Apps
Venue: arXiv cs.SE 2017
Year: 2017

Mutation testing has been widely used to assess the fault-detection effectiveness of a test suite, as well as to guide test case generation or prioritization. Empirical studies have shown that, while mutants are generally representative of real faults, an effective application of mutation testing requires "traditional" operators designed for programming languages to be augmented with operators specific to an application domain and/or technology. This paper proposes MDroid+, a framework for effective mutation testing of Android apps. First, we systematically devise a taxonomy of 262 types of Android faults grouped in 14 categories by manually analyzing 2,023 software artifacts from different sources (e.g., bug reports, commits). Then, we identified a set of 38 mutation operators, and implemented an infrastructure to automatically seed mutations in Android apps with 35 of the identified operators. The taxonomy and the proposed operators have been evaluated in terms of stillborn/trivial mutants generated and their capacity to represent real faults in Android apps, as compared to other well know mutation tools.
A Shared Task on Bandit Learning for Machine Translation
Venue: arXiv cs.CL 2017
Year: 2017

We introduce and describe the results of a novel shared task on bandit learning for machine translation. The task was organized jointly by Amazon and Heidelberg University for the first time at the Second Conference on Machine Translation (WMT 2017). The goal of the task is to encourage research on learning machine translation from weak user feedback instead of human references or post-edits. On each of a sequence of rounds, a machine translation system is required to propose a translation for an input, and receives a real-valued estimate of the quality of the proposed translation for learning. This paper describes the shared task's learning and evaluation setup, using services hosted on Amazon Web Services (AWS), the data and evaluation metrics, and the results of various machine translation architectures and learning protocols.
An Open Source C++ Implementation of Multi-Threaded Gaussian Mixture Models, k-Means and Expectation Maximisation
Venue: arXiv cs.MS 2017
Year: 2017

Modelling of multivariate densities is a core component in many signal processing, pattern recognition and machine learning applications. The modelling is often done via Gaussian mixture models (GMMs), which use computationally expensive and potentially unstable training algorithms. We provide an overview of a fast and robust implementation of GMMs in the C++ language, employing multi-threaded versions of the Expectation Maximisation (EM) and k-means training algorithms. Multi-threading is achieved through reformulation of the EM and k-means algorithms into a MapReduce-like framework. Furthermore, the implementation uses several techniques to improve numerical stability and modelling accuracy. We demonstrate that the multi-threaded implementation achieves a speedup of an order of magnitude on a recent 16 core machine, and that it can achieve higher modelling accuracy than a previously well-established publically accessible implementation. The multi-threaded implementation is included as a user-friendly class in recent releases of the open source Armadillo C++ linear algebra library. The library is provided under the permissive Apache~2.0 license, allowing unencumbered use in commercial products.
Data-Driven Stochastic Robust Optimization: A General Computational Framework and Algorithm for Optimization under Uncertainty in the Big Data Era
Venue: arXiv cs.LG 2017
Year: 2017

A novel data-driven stochastic robust optimization (DDSRO) framework is proposed for optimization under uncertainty leveraging labeled multi-class uncertainty data. Uncertainty data in large datasets are often collected from various conditions, which are encoded by class labels. Machine learning methods including Dirichlet process mixture model and maximum likelihood estimation are employed for uncertainty modeling. A DDSRO framework is further proposed based on the data-driven uncertainty model through a bi-level optimization structure. The outer optimization problem follows a two-stage stochastic programming approach to optimize the expected objective across different data classes; adaptive robust optimization is nested as the inner problem to ensure the robustness of the solution while maintaining computational tractability. A decomposition-based algorithm is further developed to solve the resulting multi-level optimization problem efficiently. Case studies on process network design and planning are presented to demonstrate the applicability of the proposed framework and algorithm.