OpenRaiser/Intern-Atlas huggingface dataset:
SAT-based Distributed Reactive Control Protocol Synthesis for Boolean Networks
Venue: arXiv cs.SY 2016
Year: 2016

This paper considers the synthesis of distributed reactive control protocols for a Boolean network in a distributed manner. We start with a directed acyclic graph representing a network of Boolean subsystems and a global contract, given as an assumption-guarantee pair. Assumption captures the environment behavior, and guarantee is the requirements to be satisfied by the system. Local assumption-guarantee contracts, together with local control protocols ensuring these local contracts, are computed recursively for each subsystem based on the partial order structure induced by the directed acyclic graph. By construction, implementing these local control protocols together guarantees the satisfaction of the global assumption-guarantee contract. Moreover, local control protocol synthesis reduces to quantified satisfiability (QSAT) problems in this setting. We also discuss structural properties of the network that affect the completeness of the proposed algorithm. As an application, we show how an aircraft electric power system can be represented as a Boolean network, and we synthesize distributed control protocols from a global assumption-guarantee contract. The assumptions capture possible failures of the system components, and the guarantees capture safety requirements related to power distribution.
Open-Vocabulary Semantic Parsing with both Distributional Statistics and Formal Knowledge
Venue: arXiv cs.CL 2016
Year: 2016

Traditional semantic parsers map language onto compositional, executable queries in a fixed schema. This mapping allows them to effectively leverage the information contained in large, formal knowledge bases (KBs, e.g., Freebase) to answer questions, but it is also fundamentally limiting---these semantic parsers can only assign meaning to language that falls within the KB's manually-produced schema. Recently proposed methods for open vocabulary semantic parsing overcome this limitation by learning execution models for arbitrary language, essentially using a text corpus as a kind of knowledge base. However, all prior approaches to open vocabulary semantic parsing replace a formal KB with textual information, making no use of the KB in their models. We show how to combine the disparate representations used by these two approaches, presenting for the first time a semantic parser that (1) produces compositional, executable representations of language, (2) can successfully leverage the information contained in both a formal KB and a large corpus, and (3) is not limited to the schema of the underlying KB. We demonstrate significantly improved performance over state-of-the-art baselines on an open-domain natural language question answering task.
Local Distributed Algorithms for Selfish Agents
Venue: arXiv cs.DC 2016
Year: 2016

In the classical framework of local distributed network computing, it is generally assumed that the entities executing distributed algorithms are altruistic. However, in various scenarios, the value of the output produced by an entity may have a tremendous impact on its future. This is for instance the case of tasks such as computing maximal independent sets (MIS) in networks. Indeed, a node belonging to the MIS may be later asked more than to a node not in the MIS, e.g., because MIS in networks are often used as backbones to collect, transfer, and broadcast information, which is costly. In this paper, we revisit typical local distributed network computing tasks in the framework of algorithmic game theory. Specifically, we focus on the construction of solutions for locally checkable labeling (LCL) tasks, which form a large class of distributed tasks, including MIS, coloring, maximal matching, etc., and which have been studied for more than 20 years in distributed computing. Given an LCL task, the nodes are collectively aiming at computing a solution, but, at the individual level, every node plays rationally and selfishly with the objective of optimizing its own profit. Surprisingly, the classical frameworks for game theory are not fully appropriate for the purpose of our study. Moreover, we show that classical notions like Nash equilibria may yield algorithms requiring an arbitrarily large number of rounds to converge. Nevertheless, by extending and generalizing core results from game theory, we establish the existence of a so-called trembling-hand perfect equilibria, a subset of Nash equilibria that is well suited to LCL construction tasks. The main outcome of the paper is therefore that, for essentially all distributed tasks whose solutions are locally checkable, there exist construction algorithms which are robust to selfishness.
Hierarchical learning for DNN-based acoustic scene classification
Venue: arXiv cs.SD 2016
Year: 2016

In this paper, we present a deep neural network (DNN)-based acoustic scene classification framework. Two hierarchical learning methods are proposed to improve the DNN baseline performance by incorporating the hierarchical taxonomy information of environmental sounds. Firstly, the parameters of the DNN are initialized by the proposed hierarchical pre-training. Multi-level objective function is then adopted to add more constraint on the cross-entropy based loss function. A series of experiments were conducted on the Task1 of the Detection and Classification of Acoustic Scenes and Events (DCASE) 2016 challenge. The final DNN-based system achieved a 22.9% relative improvement on average scene classification error as compared with the Gaussian Mixture Model (GMM)-based benchmark system across four standard folds.
Sequential Cost-Sensitive Feature Acquisition
Venue: arXiv cs.LG 2016
Year: 2016

We propose a reinforcement learning based approach to tackle the cost-sensitive learning problem where each input feature has a specific cost. The acquisition process is handled through a stochastic policy which allows features to be acquired in an adaptive way. The general architecture of our approach relies on representation learning to enable performing prediction on any partially observed sample, whatever the set of its observed features are. The resulting model is an original mix of representation learning and of reinforcement learning ideas. It is learned with policy gradient techniques to minimize a budgeted inference cost. We demonstrate the effectiveness of our proposed method with several experiments on a variety of datasets for the sparse prediction problem where all features have the same cost, but also for some cost-sensitive settings.
Re-presenting a Story by Emotional Factors using Sentimental Analysis Method
Venue: arXiv cs.CL 2016
Year: 2016

Remembering an event is affected by personal emotional status. We examined the psychological status and personal factors; depression (Center for Epidemiological Studies - Depression, Radloff, 1977), present affective (Positive Affective and Negative Affective Schedule, Watson et al., 1988), life orient (Life Orient Test, Scheier & Carver, 1985), self-awareness (Core Self Evaluation Scale, Judge et al., 2003), and social factor (Social Support, Sarason et al., 1983) of undergraduate students (N=64) and got summaries of a story, Chronicle of a Death Foretold (Gabriel Garcia Marquez, 1981) from them. We implement a sentimental analysis model based on convolutional neural network (LeCun & Bengio, 1995) to evaluate each summary. From the same vein used for transfer learning (Pan & Yang, 2010), we collected 38,265 movie review data to train the model and then use them to score summaries of each student. The results of CES-D and PANAS show the relationship between emotion and memory retrieval as follows: depressed people have shown a tendency of representing a story more negatively, and they seemed less expressive. People with full of emotion - high in PANAS - have retrieved their memory more expressively than others, using more negative words then others. The contributions of this study can be summarized as follows: First, lightening the relationship between emotion and its effect during times of storing or retrieving a memory. Second, suggesting objective methods to evaluate the intensity of emotion in natural language format, using a sentimental analysis model.
Generating Cycloidal Gears for 3D Printing
Venue: arXiv cs.OH 2016
Year: 2016

(Shortened version of abstract in article itself) This article describes an algorithm for producing, for any desired resolution and any desired numbers of wheel and pinion teeth, polygonal approximations to the shapes of a pair of cycloidal gears that mesh correctly. An Octave implementation of the algorithm, mostly written in 2014, is included. The Octave implementation contains a (crude, but evidently adequate, at least for reasonable numbers of wheel and pinion teeth) solution of the problem of iteratively finding the generating wheel angle corresponding to the tips of the tooth addenda. However, this Octave implementation does not contain a good solution to the problem of automatically determining the generating wheel angles required to produce a polygon which approximates the curved addenda to a resolution specified by the user. A proposed better solution to this problem, involving a priority queue, is discussed.
Strategies with Parallel Causes
Venue: arXiv cs.LO 2016
Year: 2016

In a distributed game we imagine a team Player engaging a team Opponent in a distributed fashion. Such games and their strategies have been formalised in concurrent games based on event structures. However there are limitations in founding strategies on traditional event structures. Sometimes a probabilistic distributed strategy relies on certain benign races where, intuitively, several members of team Player may race each other to make a common move. Although there are event structures which support such parallel causes, in which an event is enabled in several compatible ways, they do not support an operation of hiding central to the composition of strategies; nor do they support probability adequately. An extension of traditional event structures is devised which supports parallel causes and hiding, as well as the mix of probability and nondeterminism needed to account for probabilistic distributed strategies. The extension is tested in the construction of a bicategory of probabilistic distributed strategies with parallel causes. The bicategory is rich in operations relevant to probabilistic as well as deterministic parallel programming.
Analysis of Software Delivery Process Shortcomings and Architectural Pitfalls
Venue: arXiv cs.SE 2016
Year: 2016

This paper highlights the common pitfalls of overcomplicating the software architecture, development and delivery process by examining two enterprise level web application products built using Microsoft.Net framework. The aim of this paper is to identify, discuss and analyze architectural, development and deployment issues and learn lessons using real world examples from the chosen software products as case studies.
VisiSploit: An Optical Covert-Channel to Leak Data through an Air-Gap
Venue: arXiv cs.CR 2016
Year: 2016

In recent years, various out-of-band covert channels have been proposed that demonstrate the feasibility of leaking data out of computers without the need for network connectivity. The methods proposed have been based on different type of electromagnetic, acoustic, and thermal emissions. However, optical channels have largely been considered less covert: because they are visible to the human eye and hence can be detected, they have received less attention from researchers. In this paper, we introduce VisiSploit, a new type of optical covert channel which, unlike other optical methods, is also stealthy. Our method exploits the limitations of human visual perception in order to unobtrusively leak data through a standard computer LCD display. Our experiments show that very low contrast or fast flickering images which are invisible to human subjects, can be recovered from photos taken by a camera. Consequentially, we show that malicious code on a compromised computer can obtain sensitive data (e.g., images, encryption keys, passwords), and project it onto a computer LCD screen, invisible and unbeknownst to users, allowing an attacker to reconstruct the data using a photo taken by a nearby (possibly hidden) camera. In order to demonstrate the feasibility of this type of attack and evaluate the channel's stealth, we conducted a battery of tests with 40 human subjects. We also examined the channel's boundaries under various parameters, with different types of encoded objects, at several distances, and using several kinds of cameras. Our results show that binary data can be leaked via our covert channel. Further research and discussion may widen the scope of this field beyond its current boundaries, yielding novel attack paradigms that exploit the subtle mechanisms of human visual perception.
Filter Design for Generalized Frequency-Division Multiplexing
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, optimal filter design for generalized frequency-division multiplexing (GFDM) is considered under two design criteria: rate maximization and out-of-band (OOB) emission minimization. First, the problem of GFDM filter optimization for rate maximization is formulated by expressing the transmission rate of GFDM as a function of GFDM filter coefficients. It is shown that Dirichlet filters are rate-optimal in additive white Gaussian noise (AWGN) channels with no carrier frequency offset (CFO) under linear zero-forcing (ZF) or minimum mean-square error (MMSE) receivers, but in general channels perturbed by CFO a properly designed nontrivial GFDM filter can yield better performance than Dirichlet filters by adjusting the subcarrier waveform to cope with the channel-induced CFO. Next, the problem of GFDM filter design for OOB emission minimization is formulated by expressing the power spectral density (PSD) of the GFDM transmit signal as a function of GFDM filter coefficients, and it is shown that the OOB emission can be reduced significantly by designing the GFDM filter properly. Finally, joint design of GFDM filter and window for the two design criteria is considered.
Adaptive Gray World-Based Color Normalization of Thin Blood Film Images
Venue: arXiv cs.CV 2016
Year: 2016

This paper presents an effective color normalization method for thin blood film images of peripheral blood specimens. Thin blood film images can easily be separated to foreground (cell) and background (plasma) parts. The color of the plasma region is used to estimate and reduce the differences arising from different illumination conditions. A second stage normalization based on the database-gray world algorithm transforms the color of the foreground objects to match a reference color character. The quantitative experiments demonstrate the effectiveness of the method and its advantages against two other general purpose color correction methods: simple gray world and Retinex.
General Sub-packetized Access-Optimal Regenerating Codes
Venue: arXiv cs.IT 2016
Year: 2016

This paper presents a novel construction of $(n,k,d=n-1)$ access-optimal regenerating codes for an arbitrary sub-packetization level $α$ for exact repair of any systematic node. We refer to these codes as general sub-packetized because we provide an algorithm for constructing codes for any $α$ less than or equal to $r^{\lceil \frac{k}{r} \rceil}$ where $\frac{k}{r}$ is not necessarily an integer. This leads to a flexible construction of codes for different code rates compared to existing approaches. We derive the lower and the upper bound of the repair bandwidth. The repair bandwidth depends on the code parameters and $α$. The repair process of a failed systematic node is linear and highly parallelized, which means that a set of $\lceil \fracα{r} \rceil$ symbols is independently repaired first and used along with the accessed data from other nodes to recover the remaining symbols.
Strong completions of spaces
Venue: arXiv cs.LO 2016
Year: 2016

A non-empty subset of a topological space is irreducible if whenever it is covered by the union of two closed sets, then already it is covered by one of them. Irreducible sets occur in proliferation: (1) every singleton set is irreducible, (2) directed subsets (which of fundamental status in domain theory) of a poset are exactly its Alexandroff irreducible sets, (3) directed subsets (with respect to the specialization order) of a $T_0$ space are always irreducible, and (4) the topological closure of every irreducible set is again irreducible. In recent years, the usefulness of irreducible sets in domain theory and non-Hausdorff topology has expanded. Notably, Zhao and Ho (2009) developed the core of domain theory directly in the context of $T_0$ spaces by choosing the irreducible sets as the topological substitute for directed sets. Just as the existence of suprema of directed subsets is featured prominently in domain theory (and hence the notion of a dcpo -- a poset in which all directed suprema exist), so too is that of irreducible subsets in the topological domain theory developed by Zhao and Ho (2009). The topological counterpart of a dcpo is thus this: A $T_0$ space is said to be strongly complete if the suprema of all irreducible subsets exist. In this paper, we show that the category, $\mathbf{scTop^+}$, of strongly complete $T_0$ spaces forms are reflective subcategory of a certain lluf subcategory, $\mathbf{Top^+}$, of $T_0$ spaces.
Edit Distance: Sketching, Streaming and Document Exchange
Venue: arXiv cs.DS 2016
Year: 2016

We show that in the document exchange problem, where Alice holds $x \in \{0,1\}^n$ and Bob holds $y \in \{0,1\}^n$, Alice can send Bob a message of size $O(K(\log^2 K+\log n))$ bits such that Bob can recover $x$ using the message and his input $y$ if the edit distance between $x$ and $y$ is no more than $K$, and output "error" otherwise. Both the encoding and decoding can be done in time $\tilde{O}(n+\mathsf{poly}(K))$. This result significantly improves the previous communication bounds under polynomial encoding/decoding time. We also show that in the referee model, where Alice and Bob hold $x$ and $y$ respectively, they can compute sketches of $x$ and $y$ of sizes $\mathsf{poly}(K \log n)$ bits (the encoding), and send to the referee, who can then compute the edit distance between $x$ and $y$ together with all the edit operations if the edit distance is no more than $K$, and output "error" otherwise (the decoding). To the best of our knowledge, this is the first result for sketching edit distance using $\mathsf{poly}(K \log n)$ bits. Moreover, the encoding phase of our sketching algorithm can be performed by scanning the input string in one pass. Thus our sketching algorithm also implies the first streaming algorithm for computing edit distance and all the edits exactly using $\mathsf{poly}(K \log n)$ bits of space.
Reliable MIMO Optical Wireless Communications Through Super-Rectangular Cover
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we consider an intensity modulated direct detection MIMO optical wireless communication (OWC) system. For such a system, a novel super-rectangular cover theory is developed to characterize both the unique identifiability and full reliability. This theory states that a transmitted matrix signal can be uniquely identified if and only if the cover order is equal to the transmitter aperture number, i.e., full cover. In addition, we prove that full reliability is guaranteed for space-time block coded MIMO-OWC over commonly used log-normal fading channels with an ML detector if and only if the STBC enables full cover. In addition, the diversity gain can be geometrically interpreted as the cover order of the super-rectangle, which should be maximized, and the volume of this super-rectangle, as the diversity loss, should be minimized. Using this established error performance criterion, the optimal linear STBC for block fading channels is proved to be spatial repetition code with an optimal power allocation. The design of the optimal non-linear STBC is shown to be equivalent to constructing the optimal multi-dimensional constellation. Specifically, a multi-dimensional constellation from Diophantine equations is proposed and then, shown to be more energy-efficient than the commonly used nonnegative pulse amplitude modulation constellation.
The Decision Tree Complexity for $k$-SUM is at most Nearly Quadratic
Venue: arXiv cs.CG 2016
Year: 2016

Following a recent improvement of Cardinal et al. on the complexity of a linear decision tree for $k$-SUM, resulting in $O(n^3 \log^3{n})$ linear queries, we present a further improvement to $O(n^2 \log^2{n})$ such queries.
Enclosed mmWave Wearable Networks: Feasibility and Performance
Venue: arXiv cs.IT 2016
Year: 2016

This paper investigates the feasibility of mmWave frequencies for personal networks of wireless wearable devices in enclosed settings (e.g., commuter trains, subways, airplanes, airports, or offices). At these frequencies, specular reflections off surfaces are expected to contribute intended signal power and, simultaneously, to aggravate the interference at the receivers. Meanwhile, blockages by obstacles and people---including the individuals wearing the devices---are expected to shield receivers from interference. With the aid of stochastic geometry and random shape theory, we assess the interplay of surface reflections and blockages for dense deployments of wearable networks equipped with directional antenna arrays in relevant indoor settings.
Model-Driven Feed-Forward Prediction for Manipulation of Deformable Objects
Venue: arXiv cs.CV 2016
Year: 2016

Robotic manipulation of deformable objects is a difficult problem especially because of the complexity of the many different ways an object can deform. Searching such a high dimensional state space makes it difficult to recognize, track, and manipulate deformable objects. In this paper, we introduce a predictive, model-driven approach to address this challenge, using a pre-computed, simulated database of deformable object models. Mesh models of common deformable garments are simulated with the garments picked up in multiple different poses under gravity, and stored in a database for fast and efficient retrieval. To validate this approach, we developed a comprehensive pipeline for manipulating clothing as in a typical laundry task. First, the database is used for category and pose estimation for a garment in an arbitrary position. A fully featured 3D model of the garment is constructed in real-time and volumetric features are then used to obtain the most similar model in the database to predict the object category and pose. Second, the database can significantly benefit the manipulation of deformable objects via non-rigid registration, providing accurate correspondences between the reconstructed object model and the database models. Third, the accurate model simulation can also be used to optimize the trajectories for manipulation of deformable objects, such as the folding of garments. Extensive experimental results are shown for the tasks above using a variety of different clothing.