OpenRaiser/Intern-Atlas huggingface dataset:
Optimal Energy Management for Energy Harvesting Transmitter and Receiver with Helper
Venue: arXiv cs.IT 2016
Year: 2016

We study energy harvesting (EH) transmitter and receiver, where the receiver decodes data using the harvested energy from the nature and from an independent EH node, named helper. Helper cooperates with the receiver by transferring its harvested energy to the receiver over an orthogonal fading channel. We study an offline optimal power management policy to maximize the reliable information rate. The harvested energy in all three nodes are assumed to be known. We consider four different scenarios; First, for the case that both transmitter and the receiver have batteries, we show that the optimal policy is transferring the helper harvested energy to the receiver, immediately. Next, for the case of non-battery receiver and full power transmitter, we model a virtual EH receiver with minimum energy constraint to achieve an optimal policy. Then, we consider a non-battery EH receiver and EH transmitter with battery. Finally, we derive optimal power management wherein neither the transmitter nor the receiver have batteries. We propose three iterative algorithms to compute optimal energy management policies. Numerical results are presented to corroborate the advantage of employing the helper.
Some medical applications of example-based super-resolution
Venue: arXiv cs.CV 2016
Year: 2016

Example-based super-resolution (EBSR) reconstructs a high-resolution image from a low-resolution image, given a training set of high-resolution images. In this note I propose some applications of EBSR to medical imaging. A particular interesting application, which I call "x-ray voxelization", approximates the result of a CT scan from an x-ray image.
A Hybrid Performance Analysis Technique for Distributed Real-Time Embedded Systems
Venue: arXiv cs.PF 2016
Year: 2016

It remains a challenging problem to tightly estimate the worst case response time of an application in a distributed embedded system, especially when there are dependencies between tasks. We discovered that the state-of-the art techniques considering task dependencies either fail to obtain a conservative bound or produce a loose upper bound. We propose a novel conservative performance analysis, called hybrid performance analysis, combining the response time analysis technique and the scheduling time bound analysis technique to compute a tighter bound fast. Through extensive experiments with randomly generated graphs, superior performance of our proposed approach compared with previous methods is confirmed.
A Band-independent Variable Step Size Proportionate Normalized Subband Adaptive Filter Algorithm
Venue: arXiv cs.SY 2016
Year: 2016

Proportionate-type normalized suband adaptive filter (PNSAF-type) algorithms are very attractive choices for echo cancellation. To further obtain both fast convergence rate and low steady-state error, in this paper, a variable step size (VSS) version of the presented improved PNSAF (IPNSAF) algorithm is proposed by minimizing the square of the noise-free a posterior subband error signals. A noniterative shrinkage method is used to recover the noise-free a priori subband error signals from the noisy subband error signals. Significantly, the proposed VSS strategy can be applied to any other PNSAF-type algorithm, since it is independent of the proportionate principles. Simulation results in the context of acoustic echo cancellation have demonstrated the effectiveness of the proposed method.
Effective inter-symbol interference mitigation with a limited amount of enzymes in molecular communications
Venue: arXiv cs.ET 2016
Year: 2016

In molecular communication via diffusion (MCvD), the inter-symbol interference (ISI) is a well known severe problem that deteriorates both data rates and link reliability. ISI mainly occurs due to the slow and highly random propagation of the messenger molecules, which causes the emitted molecules from the previous symbols to interfere with molecules from the current symbol. An effective way to mitigate the ISI is using enzymes to degrade undesired molecules. Prior work on ISI mitigation by enzymes has assumed an infinite amount of enzymes randomly distributed around the molecular channel. Taking a different approach, this paper assumes an MCvD channel with a limited amount of enzymes. The main question this paper addresses is how to deploy these enzymes in an effective structure so that ISI mitigation is maximized. To find an effective MCvD channel environment, this study considers optimization of the shape of the transmitter node, the deployment location and structure, the size of the enzyme deployed area, and the half-lives of the enzymes. It also analyzes the dependence of the optimum size of the enzyme area on the distance and half-life.
Annotation Order Matters: Recurrent Image Annotator for Arbitrary Length Image Tagging
Venue: arXiv cs.CV 2016
Year: 2016

Automatic image annotation has been an important research topic in facilitating large scale image management and retrieval. Existing methods focus on learning image-tag correlation or correlation between tags to improve annotation accuracy. However, most of these methods evaluate their performance using top-k retrieval performance, where k is fixed. Although such setting gives convenience for comparing different methods, it is not the natural way that humans annotate images. The number of annotated tags should depend on image contents. Inspired by the recent progress in machine translation and image captioning, we propose a novel Recurrent Image Annotator (RIA) model that forms image annotation task as a sequence generation problem so that RIA can natively predict the proper length of tags according to image contents. We evaluate the proposed model on various image annotation datasets. In addition to comparing our model with existing methods using the conventional top-k evaluation measures, we also provide our model as a high quality baseline for the arbitrary length image tagging task. Moreover, the results of our experiments show that the order of tags in training phase has a great impact on the final annotation performance.
Complexity Dichotomies for Unweighted Scoring Rules
Venue: arXiv cs.CC 2016
Year: 2016

Scoring systems are an extremely important class of election systems. We study the complexity of manipulation, constructive control by deleting voters (CCDV), and bribery for scoring systems. For manipulation, we show that for all scoring rules with a constant number of different coefficients, manipulation is in P. And we conjecture that there is no dichotomy theorem. On the other hand, we obtain dichotomy theorems for CCDV and bribery problem. More precisely, we show that both of these problems are easy for 1-approval, 2-approval, 1-veto, 2-veto, 3-veto, generalized 2-veto, and (2,1,...,1,0), and hard in all other cases. These results are the "dual" of the dichotomy theorem for the constructive control by adding voters (CCAV) problem from (Hemaspaandra, Hemaspaandra, Schnoor, AAAI 2014), but do not at all follow from that result. In particular, proving hardness for CCDV is harder than for CCAV since we do not have control over what the controller can delete, and proving easiness for bribery tends to be harder than for control, since bribery can be viewed as control followed by manipulation.
A Model-based Approach for Effective Service Delivery
Venue: arXiv cs.SE 2016
Year: 2016

With the prevalence of X-as-a-Service (e.g., software as a service, platform as a service, infrastructure as a service, etc.) and users' growing demand on good services, QoS (Quality of Service) assurance is becoming increasingly important to service delivery. Traditional service delivery mainly focuses on function or information provisioning, and does not give high priority to quality assurance. In this paper, we tackle the QoS assurance problem in a systematic way, from model to system. We first decompose traditional services into three components - namely software application, data and resource, then define models for these three kinds of basic services, and propose a set of operations for service publishing and composition. To illustrate our approach, we present a prototype system, the Platform as a Service (PaaS) system, which is developed in support of our framework and shows how QoS can be ensured through real-time monitoring and dynamic scaling (up or down).
Coverage analysis of information dissemination in throwbox-augmented DTN
Venue: arXiv cs.DC 2016
Year: 2016

This paper uses a bipartite network model to calculate the coverage achieved by a delay-tolerant information dissemination algorithm in a specialized setting. The specialized Delay Tolerant Network (DTN) system comprises static message buffers or throwboxes kept in popular places besides the mobile agents hopping from one place to another. We identify that an information dissemination technique that exploits the throwbox infrastructure can cover only a fixed number of popular places irrespective of the time spent. We notice that such DTN system has a natural bipartite network correspondence where two sets are the popular places and people visiting those places. This helps leveraging the theories of evolving bipartite networks (BNW) to provide an appropriate explanation of the observed temporal invariance of information coverage over the DTN. In this work, we first show that information coverage can be estimated by the size of the largest component in the thresholded one-mode projection of BNW. Next, we also show that exploiting a special property of BNW, the size of the largest component size can be calculated from the degree distribution. Combining these two, we derive a closed form simple equation to accurately predict the amount of information coverage in DTN which is almost impossible to achieve using the traditional techniques such as epidemic or Markov modeling. The equation shows that full coverage quickly becomes extremely difficult to achieve if the number of places increases while variation in agent's activity helps in covering more places.
Comparative Study of Instance Based Learning and Back Propagation for Classification Problems
Venue: arXiv cs.LG 2016
Year: 2016

The paper presents a comparative study of the performance of Back Propagation and Instance Based Learning Algorithm for classification tasks. The study is carried out by a series of experiments will all possible combinations of parameter values for the algorithms under evaluation. The algorithm's classification accuracy is compared over a range of datasets and measurements like Cross Validation, Kappa Statistics, Root Mean Squared Value and True Positive vs False Positive rate have been used to evaluate their performance. Along with performance comparison, techniques of handling missing values have also been compared that include Mean or Mode replacement and Multiple Imputation. The results showed that parameter adjustment plays vital role in improving an algorithm's accuracy and therefore, Back Propagation has shown better results as compared to Instance Based Learning. Furthermore, the problem of missing values was better handled by Multiple imputation method, however, not suitable for less amount of data.
Acyclic Constraint Logic and Games
Venue: arXiv cs.CC 2016
Year: 2016

Non-deterministic Constraint Logic is a family of graph games introduced by Demaine and Hearn that facilitates the construction of complexity proofs. It is convenient for the analysis of games, providing a uniform view. We focus on the acyclic version, apply this to Klondike, Mahjong Solitaire and Nonogram (that requires planarity), and discuss the more complicated game of Dou Shou Qi. While for the first three games we reobtain known characterizations in a simple and uniform manner, the result for Dou Shou Qi is new.
Count-Min Tree Sketch: Approximate counting for NLP
Venue: arXiv cs.IR 2016
Year: 2016

The Count-Min Sketch is a widely adopted structure for approximate event counting in large scale processing. In a previous work we improved the original version of the Count-Min-Sketch (CMS) with conservative update using approximate counters instead of linear counters. These structures are computationaly efficient and improve the average relative error (ARE) of a CMS at constant memory footprint. These improvements are well suited for NLP tasks, in which one is interested by the low-frequency items. However, if Log counters allow to improve ARE, they produce a residual error due to the approximation. In this paper, we propose the Count-Min Tree Sketch (Copyright 2016 eXenSa. All rights reserved) variant with pyramidal counters, which are focused toward taking advantage of the Zipfian distribution of text data.
Pebbling Meets Coloring: Reversible Pebble Game On Trees
Venue: arXiv cs.CC 2016
Year: 2016

The reversible pebble game is a combinatorial game played on rooted DAGs. This game was introduced by Bennett (1989) motivated by applications in designing space efficient reversible algorithms. Recently, Chan (2013) showed that the reversible pebble game number of any DAG is the same as its Dymond-Tompa pebble number and Raz-Mckenzie pebble number. We show, as our main result, that for any rooted directed tree T, its reversible pebble game number is always just one more than the edge rank coloring number of the underlying undirected tree U of T. It is known that given a DAG G as input, determining its reversible pebble game number is PSPACE-hard. Our result implies that the reversible pebble game number of trees can be computed in polynomial time. We also address the question of finding the number of steps required to optimally pebble various families of trees. It is known that trees can be pebbled in $n^{O(\log(n))}$ steps where $n$ is the number of nodes in the tree. Using the equivalence between reversible pebble game and the Dymond-Tompa pebble game (Chan, 2013), we show that complete binary trees can be pebbled in $n^{O(\log\log(n))}$ steps, a substantial improvement over the naive upper bound of $n^{O(\log(n))}$. It remains open whether complete binary trees can be pebbled in polynomial (in $n$) number of steps. Towards this end, we show that almost optimal (i.e., within a factor of $(1 + ε)$ for any constant $ε> 0$) pebblings of complete binary trees can be done in polynomial number of steps. We also show a time-space trade-off for reversible pebbling for families of bounded degree trees by a divide-and-conquer approach: for any constant $ε> 0$, such families can be pebbled using $O(n^ε)$ pebbles in $O(n)$ steps. This generalizes an analogous result of Kralovic (2001) for chains.
Joint Coordinated Precoding and Discrete Rate Selection in Multicell MIMO Networks
Venue: arXiv cs.IT 2016
Year: 2016

Many practical wireless communications systems select their transmit rate from a finite set of modulation and coding schemes, which correspond to a set of discrete rates. In this paper, we therefore formulate a joint coordinated precoding and discrete rate selection problem for multiple-input multiple-output (MIMO) multicell networks. Compared to the common assumption of using the continuous Shannon rates as the user utilities, explicitly accounting for the discrete rates more accurately models practical wireless communication systems. The optimization problem that we formulate is combinatorial and non-convex, however, and is thus hard to solve. We therefore rewrite the problem using a discontinuous rate function, which we then bound using its concave envelope in some domain. Based on block coordinate descent, we provide a convergent resource allocation algorithm which can be implemented in a semi-distributed fashion. Numerical performance evaluation shows performance gains when the discrete rates are optimized using our model, as compared to the traditional methods which use the continuous Shannon rates as the user utilities.
Real-Time Contingency Analysis with Corrective Transmission Switching - Part II: Results and Discussion
Venue: arXiv cs.OH 2016
Year: 2016

This paper presents the performance of an AC transmission switching (TS) based real-time contingency analysis (RTCA) tool that is introduced in Part I of this paper. The approach quickly proposes high quality corrective switching actions for relief of potential post-contingency network violations. The approach is confirmed by testing it on actual EMS snapshots of two large-scale systems, the Electric Reliability Council of Texas (ERCOT) and the Pennsylvania New Jersey Maryland (PJM) Interconnection; the approach is also tested on data provided by the Tennessee Valley Authority (TVA). The results show that the tool effectively reduces post-contingency violations. Fast heuristics are used along with parallel computing to reduce the computational difficulty of the problem. The tool is able to handle the PJM system in about five minutes with a standard desktop computer. Time-domain simulations are performed to check system stability with corrective transmission switching (CTS). In conclusion, the paper shows that corrective switching is ripe for industry adoption. CTS can provide significant reliability benefits that can be translated into significant cost savings.
Document Retrieval using Predication Similarity
Venue: arXiv cs.IR 2016
Year: 2016

Document retrieval has been an important research problem over many years in the information retrieval community. State-of-the-art techniques utilize various methods in matching documents to a given document including keywords, phrases, and annotations. In this paper, we propose a new approach for document retrieval that utilizes predications (subject-predicate-object triples) extracted from the documents. We represent documents as sets of predications. We measure the similarity between predications to compute the similarity between documents. Our approach utilizes the hierarchical information available in ontologies in computing concept-concept similarity, making the approach flexible. Predication-based document similarity is more precise and forms the basis for a semantically aware document retrieval system. We show that the approach is competitive with an existing state-of-the-art related document retrieval technique in the biomedical domain.
Procedural urban environments for FPS games
Venue: arXiv cs.AI 2016
Year: 2016

This paper presents a novel approach to procedural generation of urban maps for First Person Shooter (FPS) games. A multi-agent evolutionary system is employed to place streets, buildings and other items inside the Unity3D game engine, resulting in playable video game levels. A computational agent is trained using machine learning techniques to capture the intent of the game designer as part of the multi-agent system, and to enable a semi-automated aesthetic selection for the underlying genetic algorithm.
Liveness-Based Garbage Collection for Lazy Languages
Venue: arXiv cs.PL 2016
Year: 2016

We consider the problem of reducing the memory required to run lazy first-order functional programs. Our approach is to analyze programs for liveness of heap-allocated data. The result of the analysis is used to preserve only live data---a subset of reachable data---during garbage collection. The result is an increase in the garbage reclaimed and a reduction in the peak memory requirement of programs. While this technique has already been shown to yield benefits for eager first-order languages, the lack of a statically determinable execution order and the presence of closures pose new challenges for lazy languages. These require changes both in the liveness analysis itself and in the design of the garbage collector. To show the effectiveness of our method, we implemented a copying collector that uses the results of the liveness analysis to preserve live objects, both evaluated (i.e., in WHNF) and closures. Our experiments confirm that for programs running with a liveness-based garbage collector, there is a significant decrease in peak memory requirements. In addition, a sizable reduction in the number of collections ensures that in spite of using a more complex garbage collector, the execution times of programs running with liveness and reachability-based collectors remain comparable.
Multiplayer Games for Learning Multirobot Coordination Algorithms
Venue: arXiv cs.RO 2016
Year: 2016

Humans have an impressive ability to solve complex coordination problems in a fully distributed manner. This ability, if learned as a set of distributed multirobot coordination strategies, can enable programming large groups of robots to collaborate towards complex coordination objectives in a way similar to humans. Such strategies would offer robustness, adaptability, fault-tolerance, and, importantly, distributed decision-making. To that end, we have designed a networked gaming platform to investigate human group behavior, specifically in solving complex collaborative coordinated tasks. Through this platform, we are able to limit the communication, sensing, and actuation capabilities provided to the players. With the aim of learning coordination algorithms for robots in mind, we define these capabilities to mimic those of a simple ground robot.
Circular Backbone Colorings: on matching and tree backbones of planar graphs
Venue: arXiv cs.DM 2016
Year: 2016

Given a graph $G$, and a spanning subgraph $H$ of $G$, a circular $q$-backbone $k$-coloring of $(G,H)$ is a proper $k$-coloring $c$ of $G$ such that $q\le \lvert c(u)-c(v)\rvert \le k-q$, for every edge $uv\in E(H)$. The circular $q$-backbone chromatic number of $(G,H)$, denoted by $CBC_q(G,H)$, is the minimum integer $k$ for which there exists a circular $q$-backbone $k$-coloring of $(G,H)$. The Four Color Theorem implies that whenever $G$ is planar, we have $CBC_2(G,H)\le 8$. It is conjectured that this upper bound can be improved to 7 when $H$ is a tree, and to 6 when $H$ is a matching. In this work, we show that: 1) if $G$ is planar and has no $C_4$ as subgraph, and $H$ is a linear spanning forest of $G$, then $CBC_2(G,H)\leq 7$; 2) if $G$ is a plane graph having no two 3-faces sharing an edge, and $H$ is a matching of $G$, then $CBC_2(G,H)\leq 6$; and 3) if $G$ is planar and has no $C_4$ nor $C_5$ as subgraph, and $H$ is a mathing of $G$, then $CBC_2(G,H)\leq 5$. These results partially answer questions posed by Broersma, Fujisawa and Yoshimoto (2003), and by Broersma, Fomin and Golovach (2007). It also points towards a positive answer for the Steinberg's Conjecture.
A topological insight into restricted Boltzmann machines
Venue: arXiv cs.NE 2016
Year: 2016

Restricted Boltzmann Machines (RBMs) and models derived from them have been successfully used as basic building blocks in deep artificial neural networks for automatic features extraction, unsupervised weights initialization, but also as density estimators. Thus, their generative and discriminative capabilities, but also their computational time are instrumental to a wide range of applications. Our main contribution is to look at RBMs from a topological perspective, bringing insights from network science. Firstly, here we show that RBMs and Gaussian RBMs (GRBMs) are bipartite graphs which naturally have a small-world topology. Secondly, we demonstrate both on synthetic and real-world datasets that by constraining RBMs and GRBMs to a scale-free topology (while still considering local neighborhoods and data distribution), we reduce the number of weights that need to be computed by a few orders of magnitude, at virtually no loss in generative performance. Thirdly, we show that, for a fixed number of weights, our proposed sparse models (which by design have a higher number of hidden neurons) achieve better generative capabilities than standard fully connected RBMs and GRBMs (which by design have a smaller number of hidden neurons), at no additional computational costs.