OpenRaiser/Intern-Atlas huggingface dataset:
Attention-Based Convolutional Neural Network for Machine Comprehension
Venue: arXiv cs.CL 2016
Year: 2016

Understanding open-domain text is one of the primary challenges in natural language processing (NLP). Machine comprehension benchmarks evaluate the system's ability to understand text based on the text content only. In this work, we investigate machine comprehension on MCTest, a question answering (QA) benchmark. Prior work is mainly based on feature engineering approaches. We come up with a neural network framework, named hierarchical attention-based convolutional neural network (HABCNN), to address this task without any manually designed features. Specifically, we explore HABCNN for this task by two routes, one is through traditional joint modeling of passage, question and answer, one is through textual entailment. HABCNN employs an attention mechanism to detect key phrases, key sentences and key snippets that are relevant to answering the question. Experiments show that HABCNN outperforms prior deep learning approaches by a big margin.
BPCMont: Business Process Change Management Ontology
Venue: arXiv cs.AI 2016
Year: 2016

Change management for evolving collaborative business process development is crucial when the business logic, transections and workflow change due to changes in business strategies or organizational and technical environment. During the change implementation, business processes are analyzed and improved ensuring that they capture the proposed change and they do not contain any undesired functionalities or change side-effects. This paper presents Business Process Change Management approach for the efficient and effective implementation of change in the business process. The key technology behind our approach is our proposed Business Process Change Management Ontology (BPCMont) which is the main contribution of this paper. BPCMont, as a formalized change specification, helps to revert BP into a consistent state in case of system crash, intermediate conflicting stage or unauthorized change done, aid in change traceability in the new and old versions of business processes, change effects can be seen and estimated effectively, ease for Stakeholders to validate and verify change implementation, etc.
Linear Separability in Spatial Databases
Venue: arXiv cs.DS 2016
Year: 2016

Given two point sets $R$ and $B$ in the plane, with cardinalities $m$ and $n$, respectively, and each set stored in a separate R-tree, we present an algorithm to decide whether $R$ and $B$ are linearly separable. Our algorithm exploits the structure of the R-trees, loading into the main memory only relevant data, and runs in $O(m\log m + n\log n)$ time in the worst case. As experimental results, we implement the proposed algorithm and executed it on several real and synthetic point sets, showing that the percentage of nodes of the R-trees that are accessed and the memory usage are low in these cases. We also present an algorithm to compute the convex hull of $n$ planar points given in an R-tree, running in $O(n\log n)$ time in the worst case.
Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits
Venue: arXiv cs.DC 2016
Year: 2016

This paper considers the basic $\mathcal{PULL}$ model of communication, in which in each round, each agent extracts information from few randomly chosen agents. We seek to identify the smallest amount of information revealed in each interaction (message size) that nevertheless allows for efficient and robust computations of fundamental information dissemination tasks. We focus on the Majority Bit Dissemination problem that considers a population of $n$ agents, with a designated subset of source agents. Each source agent holds an input bit and each agent holds an output bit. The goal is to let all agents converge their output bits on the most frequent input bit of the sources (the majority bit). Note that the particular case of a single source agent corresponds to the classical problem of Broadcast. We concentrate on the severe fault-tolerant context of self-stabilization, in which a correct configuration must be reached eventually, despite all agents starting the execution with arbitrary initial states. We first design a general compiler which can essentially transform any self-stabilizing algorithm with a certain property that uses $\ell$-bits messages to one that uses only $\log \ell$-bits messages, while paying only a small penalty in the running time. By applying this compiler recursively we then obtain a self-stabilizing Clock Synchronization protocol, in which agents synchronize their clocks modulo some given integer $T$, within $\tilde O(\log n\log T)$ rounds w.h.p., and using messages that contain $3$ bits only. We then employ the new Clock Synchronization tool to obtain a self-stabilizing Majority Bit Dissemination protocol which converges in $\tilde O(\log n)$ time, w.h.p., on every initial configuration, provided that the ratio of sources supporting the minority opinion is bounded away from half. Moreover, this protocol also uses only 3 bits per interaction.
Joint Pushing and Caching with a Finite Receiver Buffer: Optimal Policies and Throughput Analysis
Venue: arXiv cs.IT 2016
Year: 2016

Pushing and caching hold the promise of significantly increasing the throughput of content-centric wireless networks. However, the throughput gain of these techniques is limited by the buffer size of the receiver. To overcome this, this paper presents a Joint Pushing and Caching (JPC) method that jointly determines the contents to be pushed to, and to be removed from, the receiver buffer in each timeslot. An offline and two online JPC policies are proposed respectively based on noncausal, statistical, and causal content Request Delay Information (RDI), which predicts a user's request time for certain content. It is shown that the effective throughput of JPC is increased with the receiver buffer size and the pushing channel capacity. Furthermore, the causal feedback of user requests is found to greatly enhance the performance of online JPC without inducing much signalling overhead in practice.
Embracing Error to Enable Rapid Crowdsourcing
Venue: arXiv cs.HC 2016
Year: 2016

Microtask crowdsourcing has enabled dataset advances in social science and machine learning, but existing crowdsourcing schemes are too expensive to scale up with the expanding volume of data. To scale and widen the applicability of crowdsourcing, we present a technique that produces extremely rapid judgments for binary and categorical labels. Rather than punishing all errors, which causes workers to proceed slowly and deliberately, our technique speeds up workers' judgments to the point where errors are acceptable and even expected. We demonstrate that it is possible to rectify these errors by randomizing task order and modeling response latency. We evaluate our technique on a breadth of common labeling tasks such as image verification, word similarity, sentiment analysis and topic classification. Where prior work typically achieves a 0.25x to 1x speedup over fixed majority vote, our approach often achieves an order of magnitude (10x) speedup.
Data Load Balancing in Heterogeneous Dynamic Networks
Venue: arXiv cs.DC 2016
Year: 2016

Data load balancing is a challenging task in the P2P systems. Distributed hash table (DHT) abstraction, heterogeneous nodes, and non uniform distribution of objects are the reasons to cause load imbalance in structured P2P overlay networks. Previous works solved the load balancing problem by assuming the homogeneous capabilities of nodes, unawareness of the link latency during transferring load, and imposing logical structures to collect and reassign load. We propose a distributed load balancing algorithm with the topology awareness feature by using the concept of virtual servers. In our approach, each node collects neighborhood load information from physically close nodes and reassigns virtual servers to overlay nodes based upon the topology of underlying network. Consequently, our approach converges data load balancing quickly and it also reduces the load transfer cost between nodes. Moreover, our approach increases the quality of load balancing among close nodes of overlay and it also introduces a new tradeoff between the quality of load balancing and load transfer cost among all overlay nodes. Our simulations show that our approach reduces the load transfer cost and it saves network bandwidth respectively. Finally, we show that the in-degree imbalance of nodes, as a consequence of topology awareness, cannot lead to a remarkable problem in topology aware overlays.
Extending the Nested Parallel Model to the Nested Dataflow Model with Provably Efficient Schedulers
Venue: arXiv cs.DC 2016
Year: 2016

The nested parallel (a.k.a. fork-join) model is widely used for writing parallel programs. However, the two composition constructs, i.e. "$\parallel$" (parallel) and "$;$" (serial), are insufficient in expressing "partial dependencies" or "partial parallelism" in a program. We propose a new dataflow composition construct "$\leadsto$" to express partial dependencies in algorithms in a processor- and cache-oblivious way, thus extending the Nested Parallel (NP) model to the \emph{Nested Dataflow} (ND) model. We redesign several divide-and-conquer algorithms ranging from dense linear algebra to dynamic-programming in the ND model and prove that they all have optimal span while retaining optimal cache complexity. We propose the design of runtime schedulers that map ND programs to multicore processors with multiple levels of possibly shared caches (i.e, Parallel Memory Hierarchies) and provide theoretical guarantees on their ability to preserve locality and load balance. For this, we adapt space-bounded (SB) schedulers for the ND model. We show that our algorithms have increased "parallelizability" in the ND model, and that SB schedulers can use the extra parallelizability to achieve asymptotically optimal bounds on cache misses and running time on a greater number of processors than in the NP model. The running time for the algorithms in this paper is $O\left(\frac{\sum_{i=0}^{h-1} Q^{*}({\mathsf t};σ\cdot M_i)\cdot C_i}{p}\right)$, where $Q^{*}$ is the cache complexity of task ${\mathsf t}$, $C_i$ is the cost of cache miss at level-$i$ cache which is of size $M_i$, $σ\in(0,1)$ is a constant, and $p$ is the number of processors in an $h$-level cache hierarchy.
Relations Between Conditional Shannon Entropy and Expectation of $\ell_α$-Norm
Venue: arXiv cs.IT 2016
Year: 2016

The paper examines relationships between the conditional Shannon entropy and the expectation of $\ell_α$-norm for joint probability distributions. More precisely, we investigate the tight bounds of the expectation of $\ell_α$-norm with a fixed conditional Shannon entropy, and vice versa. As applications of the results, we derive the tight bounds between the conditional Shannon entropy and several information measures which are determined by the expectation of $\ell_α$-norm, e.g., the conditional Rényi entropy and the conditional $R$-norm information. Moreover, we apply these results to discrete memoryless channels under a uniform input distribution. Then, we show the tight bounds of Gallager's $E_{0}$ functions with a fixed mutual information under a uniform input distribution.
srsLTE: An Open-Source Platform for LTE Evolution and Experimentation
Venue: arXiv cs.NI 2016
Year: 2016

Testbeds are essential for experimental evaluation as well as for product development. In the context of LTE networks, existing testbed platforms are limited either in functionality and/or extensibility or are too complex to modify and customise. In this work we present srsLTE, an open-source platform for LTE experimentation designed for maximum modularity and code reuse and fully compliant with LTE Release 8. We show the potential of the srsLTE library by extending the baseline code to allow LTE transmissions in the unlicensed bands and coexistence with WiFi. We also expand previous results on this emerging research area by showing how different vendor-specific mechanisms in WiFi cards might affect coexistence.
Content Delivery in Erasure Broadcast Channels with Cache and Feedback
Venue: arXiv cs.IT 2016
Year: 2016

We study a content delivery problem in a K-user erasure broadcast channel such that a content providing server wishes to deliver requested files to users, each equipped with a cache of a finite memory. Assuming that the transmitter has state feedback and user caches can be filled during off-peak hours reliably by the decentralized content placement, we characterize the achievable rate region as a function of the memory sizes and the erasure probabilities. The proposed delivery scheme, based on the broadcasting scheme by Wang and Gatzianas et al., exploits the receiver side information established during the placement phase. Our results can be extended to centralized content placement as well as multi-antenna broadcast channels with state feedback.
Customizable Precision of Floating-Point Arithmetic with Bitslice Vector Types
Venue: arXiv cs.OH 2016
Year: 2016

Customizing the precision of data can provide attractive trade-offs between accuracy and hardware resources. We propose a novel form of vector computing aimed at arrays of custom-precision floating point data. We represent these vectors in bitslice format. Bitwise instructions are used to implement arithmetic circuits in software that operate on customized bit-precision. Experiments show that this approach can be efficient for vectors of low-precision custom floating point types, while providing arbitrary bit precision.
Efficient Representation of Low-Dimensional Manifolds using Deep Networks
Venue: arXiv cs.NE 2016
Year: 2016

We consider the ability of deep neural networks to represent data that lies near a low-dimensional manifold in a high-dimensional space. We show that deep networks can efficiently extract the intrinsic, low-dimensional coordinates of such data. We first show that the first two layers of a deep network can exactly embed points lying on a monotonic chain, a special type of piecewise linear manifold, mapping them to a low-dimensional Euclidean space. Remarkably, the network can do this using an almost optimal number of parameters. We also show that this network projects nearby points onto the manifold and then embeds them with little error. We then extend these results to more general manifolds.
Affine computation and affine automaton
Venue: arXiv cs.FL 2016
Year: 2016

We introduce a quantum-like classical computational model, called affine computation, as a generalization of probabilistic computation. After giving the basics of affine computation, we define affine finite automata (AfA) and compare it with quantum and probabilistic finite automata (QFA and PFA, respectively) with respect to three basic language recognition modes. We show that, in the cases of bounded and unbounded error, AfAs are more powerful than QFAs and PFAs, and, in the case of nondeterministic computation, AfAs are more powerful than PFAs but equivalent to QFAs.
Delay and Cooperation in Nonstochastic Bandits
Venue: arXiv cs.LG 2016
Year: 2016

We study networks of communicating learning agents that cooperate to solve a common nonstochastic bandit problem. Agents use an underlying communication network to get messages about actions selected by other agents, and drop messages that took more than $d$ hops to arrive, where $d$ is a delay parameter. We introduce \textsc{Exp3-Coop}, a cooperative version of the {\sc Exp3} algorithm and prove that with $K$ actions and $N$ agents the average per-agent regret after $T$ rounds is at most of order $\sqrt{\bigl(d+1 + \tfrac{K}{N}α_{\le d}\bigr)(T\ln K)}$, where $α_{\le d}$ is the independence number of the $d$-th power of the connected communication graph $G$. We then show that for any connected graph, for $d=\sqrt{K}$ the regret bound is $K^{1/4}\sqrt{T}$, strictly better than the minimax regret $\sqrt{KT}$ for noncooperating agents. More informed choices of $d$ lead to bounds which are arbitrarily close to the full information minimax regret $\sqrt{T\ln K}$ when $G$ is dense. When $G$ has sparse components, we show that a variant of \textsc{Exp3-Coop}, allowing agents to choose their parameters according to their centrality in $G$, strictly improves the regret. Finally, as a by-product of our analysis, we provide the first characterization of the minimax regret for bandit learning with delay.
Greedy Ants Colony Optimization Strategy for Solving the Curriculum Based University Course Timetabling Problem
Venue: arXiv cs.NE 2016
Year: 2016

Timetabling is a problem faced in all higher education institutions. The International Timetabling Competition (ITC) has published a dataset that can be used to test the quality of methods used to solve this problem. A number of meta-heuristic approaches have obtained good results when tested on the ITC dataset, however few have used the ant colony optimization technique, particularly on the ITC 2007 curriculum based university course timetabling problem. This study describes an ant system that solves the curriculum based university course timetabling problem and the quality of the algorithm is tested on the ITC 2007 dataset. The ant system was able to find feasible solutions in all instances of the dataset and close to optimal solutions in some instances. The ant system performs better than some published approaches, however results obtained are not as good as those obtained by the best published approaches. This study may be used as a benchmark for ant based algorithms that solve the curriculum based university course timetabling problem.
Constructive Patterns of Logical Truth
Venue: arXiv cs.CC 2016
Year: 2016

The simplified linguistic relation between syntax and semantics as intrinsic property of classic Arabic motivates a dedicated look at P vs. NP in light of efforts and solutions presented by ancient Arab- and Muslim scholars to facilitate logical- and mathematical deduction. In Islamic Jurisprudence (Fikh) it has recently been shown [Abdelwahab et al. 2014] that if a formal system expressing Fikh is chosen in such a way that it is both, logically complete and decidable, the question of a complete and consistent legislation is decidable. If this formal Fikh-system is additionally chosen to be at least as expressive as propositional logic, the deduction of detailed sentences is efficient while the deduction of general rules is NP-complete. Further investigation reveals that ancient scholars adopted a very efficient approach for checking the validity of assertions with regard to both, language and logical argument which was mainly characterized by the extensive use of syntactical patterns already existent in input-variables. Accordingly, this paper introduces efficient pattern-oriented procedures for 3-SAT as well as 2-approximation algorithms for MinFBDD. It opens up the possibility of constructing polynomial sized FBDDs for all Boolean functions expressed in a compact way. Eventually, an application of this new 3-SAT-solver is shown to enable polynomial upper bounds of the number of nodes in FBDDs constructed for finite projective planes problems overhauling the currently known exponential lower bounds.
Prompt Delay
Venue: arXiv cs.GT 2016
Year: 2016

Delay games are two-player games of infinite duration in which one player may delay her moves to obtain a lookahead on her opponent's moves. Recently, such games with quantitative winning conditions in weak MSO with the unbounding quantifier were studied, but their properties turned out to be unsatisfactory. In particular, unbounded lookahead is in general necessary. Here, we study delay games with winning conditions given by Prompt-LTL, Linear Temporal Logic equipped with a parameterized eventually operator whose scope is bounded. Our main result shows that solving Prompt-LTL delay games is complete for triply-exponential time. Furthermore, we give tight triply-exponential bounds on the necessary lookahead and on the scope of the parameterized eventually operator. Thus, we identify Prompt-LTL as the first known class of well-behaved quantitative winning conditions for delay games. Finally, we show that applying our techniques to delay games with ω-regular winning conditions answers open questions in the cases where the winning conditions are given by non-deterministic, universal, or alternating automata.
Query Reranking As A Service
Venue: arXiv cs.DB 2016
Year: 2016

The ranked retrieval model has rapidly become the de facto way for search query processing in client-server databases, especially those on the web. Despite of the extensive efforts in the database community on designing better ranking functions/mechanisms, many such databases in practice still fail to address the diverse and sometimes contradicting preferences of users on tuple ranking, perhaps (at least partially) due to the lack of expertise and/or motivation for the database owner to design truly effective ranking functions. This paper takes a different route on addressing the issue by defining a novel {\em query reranking problem}, i.e., we aim to design a third-party service that uses nothing but the public search interface of a client-server database to enable the on-the-fly processing of queries with any user-specified ranking functions (with or without selection conditions), no matter if the ranking function is supported by the database or not. We analyze the worst-case complexity of the problem and introduce a number of ideas, e.g., on-the-fly indexing, domination detection and virtual tuple pruning, to reduce the average-case cost of the query reranking algorithm. We also present extensive experimental results on real-world datasets, in both offline and live online systems, that demonstrate the effectiveness of our proposed techniques.
Parameter Synthesis for Markov Models: Faster Than Ever
Venue: arXiv cs.LO 2016
Year: 2016

We propose a simple technique for verifying probabilistic models whose transition probabilities are parametric. The key is to replace parametric transitions by nondeterministic choices of extremal values. Analysing the resulting parameter-free model using off-the-shelf means yields (refinable) lower and upper bounds on probabilities of regions in the parameter space. The technique outperforms the existing analysis of parametric Markov chains by several orders of magnitude regarding both run-time and scalability. Its beauty is its applicability to various probabilistic models. It in particular provides the first sound and feasible method for performing parameter synthesis of Markov decision processes.
A Ranking Algorithm for Re-finding
Venue: arXiv cs.IR 2016
Year: 2016

Re-finding files from a personal computer is a frequent demand to users. When encountered a difficult re-finding task, people may not recall the attributes used by conventional re-finding methods, such as a file's path, file name, keywords etc., the re-finding would fail. We proposed a method to support difficult re-finding tasks. By asking the user a list of questions about the target, such as a document's pages, author numbers, accumulated reading time, last reading location etc. Then use the user's answers to filter out the target. After the user answered a list of questions about the target file, we evaluate the user's familiar degree about the target file based on the answers. We devise a ranking algorithm which sorts the candidates by comparing the user's familiarity degree about the target and the candidates. We also propose a method to generate re-finding tasks artificially based on the user's own document corpus.