OpenRaiser/Intern-Atlas huggingface dataset:
Fast Algorithms for the computation of Fourier Extensions of arbitrary length
Venue: arXiv cs.NA 2015
Year: 2015

Fourier series of smooth, non-periodic functions on $[-1,1]$ are known to exhibit the Gibbs phenomenon, and exhibit overall slow convergence. One way of overcoming these problems is by using a Fourier series on a larger domain, say $[-T,T]$ with $T>1$, a technique called Fourier extension or Fourier continuation. When constructed as the discrete least squares minimizer in equidistant points, the Fourier extension has been shown shown to converge geometrically in the truncation parameter $N$. A fast ${\mathcal O}(N \log^2 N)$ algorithm has been described to compute Fourier extensions for the case where $T=2$, compared to ${\mathcal O}(N^3)$ for solving the dense discrete least squares problem. We present two ${\mathcal O}(N\log^2 N )$ algorithms for the computation of these approximations for the case of general $T$, made possible by exploiting the connection between Fourier extensions and Prolate Spheroidal Wave theory. The first algorithm is based on the explicit computation of so-called periodic discrete prolate spheroidal sequences, while the second algorithm is purely algebraic and only implicitly based on the theory.
Some Triangulated Surfaces without Balanced Splitting
Venue: arXiv cs.CG 2015
Year: 2015

Let G be the graph of a triangulated surface $Σ$ of genus $g\geq 2$. A cycle of G is splitting if it cuts $Σ$ into two components, neither of which is homeomorphic to a disk. A splitting cycle has type k if the corresponding components have genera k and g-k. It was conjectured that G contains a splitting cycle (Barnette '1982). We confirm this conjecture for an infinite family of triangulations by complete graphs but give counter-examples to a stronger conjecture (Mohar and Thomassen '2001) claiming that G should contain splitting cycles of every possible type.
Pearson codes
Venue: arXiv cs.IT 2015
Year: 2015

The Pearson distance has been advocated for improving the error performance of noisy channels with unknown gain and offset. The Pearson distance can only fruitfully be used for sets of $q$-ary codewords, called Pearson codes, that satisfy specific properties. We will analyze constructions and properties of optimal Pearson codes. We will compare the redundancy of optimal Pearson codes with the redundancy of prior art $T$-constrained codes, which consist of $q$-ary sequences in which $T$ pre-determined reference symbols appear at least once. In particular, it will be shown that for $q\le 3$ the $2$-constrained codes are optimal Pearson codes, while for $q\ge 4$ these codes are not optimal.
Cascade Markov Decision Processes: Theory and Applications
Venue: arXiv cs.SY 2015
Year: 2015

This paper considers the optimal control of time varying continuous time Markov chains whose transition rates are themselves Markov processes. In one set of problems the solution of an ordinary differential equation is shown to determine the optimal performance and feedback controls, while some other cases are shown to lead to singular optimal control problems which are more difficult to solve. Solution techniques are demonstrated using examples from finance to behavioral decision making.
Program Synthesis using Natural Language
Venue: arXiv cs.PL 2015
Year: 2015

Interacting with computers is a ubiquitous activity for millions of people. Repetitive or specialized tasks often require creation of small, often one-off, programs. End-users struggle with learning and using the myriad of domain-specific languages (DSLs) to effectively accomplish these tasks. We present a general framework for constructing program synthesizers that take natural language (NL) inputs and produce expressions in a target DSL. The framework takes as input a DSL definition and training data consisting of NL/DSL pairs. From these it constructs a synthesizer by learning optimal weights and classifiers (using NLP features) that rank the outputs of a keyword-programming based translation. We applied our framework to three domains: repetitive text editing, an intelligent tutoring system, and flight information queries. On 1200+ English descriptions, the respective synthesizers rank the desired program as the top-1 and top-3 for 80% and 90% descriptions respectively.
Sensor-Type Classification in Buildings
Venue: arXiv cs.LG 2015
Year: 2015

Many sensors/meters are deployed in commercial buildings to monitor and optimize their performance. However, because sensor metadata is inconsistent across buildings, software-based solutions are tightly coupled to the sensor metadata conventions (i.e. schemas and naming) for each building. Running the same software across buildings requires significant integration effort. Metadata normalization is critical for scaling the deployment process and allows us to decouple building-specific conventions from the code written for building applications. It also allows us to deal with missing metadata. One important aspect of normalization is to differentiate sensors by the typeof phenomena being observed. In this paper, we propose a general, simple, yet effective classification scheme to differentiate sensors in buildings by type. We perform ensemble learning on data collected from over 2000 sensor streams in two buildings. Our approach is able to achieve more than 92% accuracy for classification within buildings and more than 82% accuracy for across buildings. We also introduce a method for identifying potential misclassified streams. This is important because it allows us to identify opportunities to attain more input from experts -- input that could help improve classification accuracy when ground truth is unavailable. We show that by adjusting a threshold value we are able to identify at least 30% of the misclassified instances.
A Single-Query Manipulation Planner
Venue: arXiv cs.RO 2015
Year: 2015

In manipulation tasks, a robot interacts with movable object(s). The configuration space in manipulation planning is thus the Cartesian product of the configuration space of the robot with those of the movable objects. It is the complex structure of such a "Composite Configuration Space" that makes manipulation planning particularly challenging. Previous works approximate the connectivity of the Composite Configuration Space by means of discretization or by creating random roadmaps. Such approaches involve an extensive pre-processing phase, which furthermore has to be re-done each time the environment changes. In this paper, we propose a high-level Grasp-Placement Table similar to that proposed by Tournassoud et al. (1987), but which does not require any discretization or heavy pre-processing. The table captures the potential connectivity of the Composite Configuration Space while being specific only to the movable object: in particular, it does not require to be re-computed when the environment changes. During the query phase, the table is used to guide a tree-based planner that explores the space systematically. Our simulations and experiments show that the proposed method enables improvements in both running time and trajectory quality as compared to existing approaches.
Model Checking Epistemic Halpern-Shoham Logic Extended with Regular Expressions
Venue: arXiv cs.LO 2015
Year: 2015

The Epistemic Halpern-Shoham logic (EHS) is a temporal-epistemic logic that combines the interval operators of the Halpern-Shoham logic with epistemic modalities. The semantics of EHS is based on interpreted systems whose labelling function is defined on the endpoints of intervals. We show that this definition can be generalised by allowing the labelling function to be based on the whole interval by means of regular expressions. We prove that all the positive results known for EHS, notably the attractive complexity of its model checking problem for some of its fragments, still hold for its generalisation. We also propose the new logic EHSre which operates on standard Kripke structures and has expressive power equivalent to that of EHS with regular expressions. We compare the expressive power of EHSre with standard temporal logics.
Stay Awhile and Listen: User Interactions in a Crowdsourced Platform Offering Emotional Support
Venue: arXiv cs.SI 2015
Year: 2015

Internet and online-based social systems are rising as the dominant mode of communication in society. However, the public or semi-private environment under which most online communications operate under do not make them suitable channels for speaking with others about personal or emotional problems. This has led to the emergence of online platforms for emotional support offering free, anonymous, and confidential conversations with live listeners. Yet very little is known about the way these platforms are utilized, and if their features and design foster strong user engagement. This paper explores the utilization and the interaction features of hundreds of thousands of users on 7 Cups of Tea, a leading online platform offering online emotional support. It dissects the level of activity of hundreds of thousands of users, the patterns by which they engage in conversation with each other, and uses machine learning methods to find factors promoting engagement. The study may be the first to measure activities and interactions in a large-scale online social system that fosters peer-to-peer emotional support.
Interference-Assisted Wireless Energy Harvesting in Cognitive Relay Network with Multiple Primary Transceivers
Venue: arXiv cs.IT 2015
Year: 2015

We consider a spectrum sharing scenario, where a secondary network coexists with a primary network of multiple transceivers. The secondary network consists of an energy-constrained decode-and-forward secondary relay which assists the communication between a secondary transmitter and a destination in the presence of the interference from multiple primary transmitters. The secondary relay harvests energy from the received radio-frequency signals, which include the information signal from the secondary transmitter and the primary interference. The harvested energy is then used to decode the secondary information and forward it to the secondary destination. At the relay, we adopt a time switching policy due to its simplicity that switches between the energy harvesting and information decoding over time. Specifically, we derive a closed-form expression for the secondary outage probability under the primary outage constraint and the peak power constraint at both secondary transmitter and relay. In addition, we investigate the effect of the number of primary transceivers on the optimal energy harvesting duration that minimizes the secondary outage probability. By utilizing the primary interference as a useful energy source in the energy harvesting phase, the secondary network achieves a better outage performance.
On-the-Fly Learning in a Perpetual Learning Machine
Venue: arXiv cs.LG 2015
Year: 2015

Despite the promise of brain-inspired machine learning, deep neural networks (DNN) have frustratingly failed to bridge the deceptively large gap between learning and memory. Here, we introduce a Perpetual Learning Machine; a new type of DNN that is capable of brain-like dynamic 'on the fly' learning because it exists in a self-supervised state of Perpetual Stochastic Gradient Descent. Thus, we provide the means to unify learning and memory within a machine learning framework. We also explore the elegant duality of abstraction and synthesis: the Yin and Yang of deep learning.
Secrecy Wireless Information and Power Transfer in OFDMA Systems
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we consider simultaneous wireless information and power transfer (SWIPT) in orthogonal frequency division multiple access (OFDMA) systems with the coexistence of information receivers (IRs) and energy receivers (ERs). The IRs are served with best-effort secrecy data and the ERs harvest energy with minimum required harvested power. To enhance physical-layer security and yet satisfy energy harvesting requirements, we introduce a new frequency-domain artificial noise based approach. We study the optimal resource allocation for the weighted sum secrecy rate maximization via transmit power and subcarrier allocation. The considered problem is non-convex, while we propose an efficient algorithm for solving it based on Lagrange duality method. Simulation results illustrate the effectiveness of the proposed algorithm as compared against other heuristic schemes.
Exploiting Heterogeneous Robotic Systems in Cooperative Missions
Venue: arXiv cs.RO 2015
Year: 2015

In this paper we consider the problem of coordinating robotic systems with different kinematics, sensing and vision capabilities to achieve certain mission goals. An approach that makes use of a heterogeneous team of agents has several advantages when cost, integration of capabilities, or large search areas need to be considered. A heterogeneous team allows for the robots to become "specialized", accomplish sub-goals more effectively, and thus increase the overall mission efficiency. Two main scenarios are considered in this work. In the first case study we exploit mobility to implement a power control algorithm that increases the Signal to Interference plus Noise Ratio (SINR) among certain members of the network. We create realistic sensing fields and manipulation by using the geometric properties of the sensor field-of-view and the manipulability metric, respectively. The control strategy for each agent of the heterogeneous system is governed by an artificial physics law that considers the different kinematics of the agents and the environment, in a decentralized fashion. Through simulation results we show that the network is able to stay connected at all times and covers the environment well. The second scenario studied in this paper is the biologically-inspired coordination of heterogeneous physical robotic systems. A team of ground rovers, designed to emulate desert seed-harvester ants, explore an experimental area using behaviors fine-tuned in simulation by a genetic algorithm. Our robots coordinate with a base station and collect clusters of resources scattered within the experimental space. We demonstrate experimentally that through coordination with an aerial vehicle, our ant-like ground robots are able to collect resources two times faster than without the use of heterogeneous coordination.
Ordered Tomlinson-Harashima Precoding in G.fast Downstream
Venue: arXiv cs.IT 2015
Year: 2015

G.fast is an upcoming next generation DSL standard envisioned to use bandwidth up to 212 MHz. Far-end crosstalk (FEXT) at these frequencies greatly overcomes direct links. Its cancellation based on non-linear Tomlinson-Harashima Precoding (THP) proved to show significant advantage over standard linear precoding. This paper proposes a novel THP structure in which ordering of successive interference pre-cancellation can be optimized for downstream with non-cooperating receivers. The optimized scheme is compared to existing THP structure denoted as equal-rate THP which is widely adopted in wireless downlink. Structure and performance of both methods differ significantly favoring the proposed scheme. The ordering that maximizes the minimum rate (max-min fairness) for each tone of the discrete multi-tone modulation is the familiar V-BLAST ordering. However, V-BLAST does not lead to the global maximum when applied independently on each tone. The proposed novel Dynamic Ordering (DO) strategy takes into account asymmetric channel statistics to yield the highest minimum aggregated rate.
Generating Weather Forecast Texts with Case Based Reasoning
Venue: arXiv cs.AI 2015
Year: 2015

Several techniques have been used to generate weather forecast texts. In this paper, case based reasoning (CBR) is proposed for weather forecast text generation because similar weather conditions occur over time and should have similar forecast texts. CBR-METEO, a system for generating weather forecast texts was developed using a generic framework (jCOLIBRI) which provides modules for the standard components of the CBR architecture. The advantage in a CBR approach is that systems can be built in minimal time with far less human effort after initial consultation with experts. The approach depends heavily on the goodness of the retrieval and revision components of the CBR process. We evaluated CBRMETEO with NIST, an automated metric which has been shown to correlate well with human judgements for this domain. The system shows comparable performance with other NLG systems that perform the same task.
An Ant Colonization Routing Algorithm to Minimize Network Power Consumption
Venue: arXiv cs.NI 2015
Year: 2015

Rising energy consumption of IT infrastructure concerns have spurred the development of more power efficient networking equipment and algorithms. When \emph{old} equipment just drew an almost constant amount of power regardless of the traffic load, there were some efforts to minimize the total energy usage by modifying routing decisions to aggregate traffic in a minimal set of links, creating the opportunity to power off some unused equipment during low traffic periods. New equipment, with power profile functions depending on the offered load, presents new challenges for optimal routing. The goal now is not just to power some links down, but to aggregate and/or spread the traffic so that devices operate in their sweet spot in regards to network usage. In this paper we present an algorithm that, making use of the ant colonization algorithm, computes, in a decentralized manner, the routing tables so as to minimize global energy consumption. Moreover, the resulting algorithm is also able to track changes in the offered load and react to them in real time.
Machine Learning Methods to Analyze Arabidopsis Thaliana Plant Root Growth
Venue: arXiv cs.LG 2015
Year: 2015

One of the challenging problems in biology is to classify plants based on their reaction on genetic mutation. Arabidopsis Thaliana is a plant that is so interesting, because its genetic structure has some similarities with that of human beings. Biologists classify the type of this plant to mutated and not mutated (wild) types. Phenotypic analysis of these types is a time-consuming and costly effort by individuals. In this paper, we propose a modified feature extraction step by using velocity and acceleration of root growth. In the second step, for plant classification, we employed different Support Vector Machine (SVM) kernels and two hybrid systems of neural networks. Gated Negative Correlation Learning (GNCL) and Mixture of Negatively Correlated Experts (MNCE) are two ensemble methods based on complementary feature of classical classifiers; Mixture of Expert (ME) and Negative Correlation Learning (NCL). The hybrid systems conserve of advantages and decrease the effects of disadvantages of NCL and ME. Our Experimental shows that MNCE and GNCL improve the efficiency of classical classifiers, however, some SVM kernels function has better performance than classifiers based on neural network ensemble method. Moreover, kernels consume less time to obtain a classification rate.
Probabilistic Neural Network Training for Semi-Supervised Classifiers
Venue: arXiv cs.LG 2015
Year: 2015

In this paper, we propose another version of help-training approach by employing a Probabilistic Neural Network (PNN) that improves the performance of the main discriminative classifier in the semi-supervised strategy. We introduce the PNN-training algorithm and use it for training the support vector machine (SVM) with a few numbers of labeled data and a large number of unlabeled data. We try to find the best labels for unlabeled data and then use SVM to enhance the classification rate. We test our method on two famous benchmarks and show the efficiency of our method in comparison with pervious methods.
Stability Analysis of Discrete-time Lure Systems with Slope-restricted Odd Monotonic Nonlinearities
Venue: arXiv cs.SY 2015
Year: 2015

Many nonlinear dynamical systems can be written as Lure systems, which are described by a linear time-invariant system interconnected with a diagonal static sector-bounded nonlinearity. Sufficient conditions are derived for the global asymptotic stability analysis of discrete-time Lure systems in which the nonlinearities have restricted slope and/or are odd, which is the usual case in real applications. A Lure-Postnikov-type Lyapunov function is proposed that is used to derive sufficient analysis conditions in terms of linear matrix inequalities (LMIs). The derived stability critera are provably less conservative than criteria published in the literature, with numerical examples indicating that conservatism can be reduced by orders of magnitude.
End-vertices of LBFS of (AT-free) bigraphs
Venue: arXiv cs.DM 2015
Year: 2015

Lexicographic Breadth First Search (LBFS) is one of fundamental graph search algorithms that has numerous applications, including recognition of graph classes, computation of graph parameters, and detection of certain graph structures. The well-known result of Rose, Tarjan and Lueker on the end-vertices of LBFS of chordal graphs has tempted researchers to study the end-vertices of LBFS of various classes of graphs, including chordal graphs, split graphs, interval graphs, and asteroidal triple-free (AT-free) graphs. In this paper we study the end-vertices of LBFS of bipartite graphs. We show that deciding whether a vertex of a bipartite graph is the end-vertex of an LBFS is an NP-complete problem. In contrast we characterize the end-vertices of LBFS of AT-free bipartite graphs. Our characterization implies that the problem of deciding whether a vertex of an AT-free bipartite graph is the end-vertex of an LBFS is solvable in polynomial time. Key words: Lexicographic breadth first search, end-vertex, bipartite graphs, AT-free, proper interval bigraph, characterization, algorithm.
On Optimizing Replica Migration in Distributed Cloud Storage Systems
Venue: arXiv cs.NI 2015
Year: 2015

With the wide adoption of large-scale Internet services and big data, the cloud has become the ideal environment to satisfy the ever-growing storage demand, thanks to its seemingly limitless capacity, high availability and faster access time. In this context, data replication has been touted as the ultimate solution to improve data availability and reduce access time. However, replica placement systems usually need to migrate and create a large number of data replicas over time between and within data centers, incurring a large overhead in terms of network load and availability. In this paper, we propose CRANE, an effiCient Replica migrAtion scheme for distributed cloud Storage systEms. CRANE complements any replica placement algorithm by efficiently managing replica creation in geo-distributed infrastructures by (1) minimizing the time needed to copy the data to the new replica location, (2) avoiding network congestion, and (3) ensuring a minimal availability of the data. Our results show that, compared to swift (the OpenStack project for managing data storage), CRANE is able to minimize up to 30% of the replica creation time and 25% of inter-data center network traffic, while ensuring the minimum required availability of the data.