OpenRaiser/Intern-Atlas huggingface dataset:
Deep Reinforcement Learning for Join Order Enumeration
Venue: arXiv cs.DB 2018
Year: 2018

Join order selection plays a significant role in query performance. However, modern query optimizers typically employ static join enumeration algorithms that do not receive any feedback about the quality of the resulting plan. Hence, optimizers often repeatedly choose the same bad plan, as they do not have a mechanism for "learning from their mistakes". In this paper, we argue that existing deep reinforcement learning techniques can be applied to address this challenge. These techniques, powered by artificial neural networks, can automatically improve decision making by incorporating feedback from their successes and failures. Towards this goal, we present ReJOIN, a proof-of-concept join enumerator, and present preliminary results indicating that ReJOIN can match or outperform the PostgreSQL optimizer in terms of plan quality and join enumeration efficiency.
Intelligent Irrigation System Based on Arduino
Venue: arXiv cs.CY 2018
Year: 2018

This paper explains how to build an intelligent irrigation system using Arduino (a micro- controller) and many devices (humidity, temperature, pressure and water flow sensors). Our irrigation system combines a precise method to determine water balance of soils with an automatic response to water content oscillations. Thus, it is an example of how we can perform better irrigation systems by increasing the precision of measurements but also by automating decisions.
Improving Sentiment Analysis in Arabic Using Word Representation
Venue: arXiv cs.CL 2018
Year: 2018

The complexities of Arabic language in morphology, orthography and dialects makes sentiment analysis for Arabic more challenging. Also, text feature extraction from short messages like tweets, in order to gauge the sentiment, makes this task even more difficult. In recent years, deep neural networks were often employed and showed very good results in sentiment classification and natural language processing applications. Word embedding, or word distributing approach, is a current and powerful tool to capture together the closest words from a contextual text. In this paper, we describe how we construct Word2Vec models from a large Arabic corpus obtained from ten newspapers in different Arab countries. By applying different machine learning algorithms and convolutional neural networks with different text feature selections, we report improved accuracy of sentiment classification (91%-95%) on our publicly available Arabic language health sentiment dataset [1]
Modeling reverse thinking for machine learning
Venue: arXiv cs.LG 2018
Year: 2018

Human inertial thinking schemes can be formed through learning, which are then applied to quickly solve similar problems later. However, when problems are significantly different, inertial thinking generally presents the solutions that are definitely imperfect. In such cases, people will apply creative thinking, such as reverse thinking, to solve problems. Similarly, machine learning methods also form inertial thinking schemes through learning the knowledge from a large amount of data. However, when the testing data are vastly difference, the formed inertial thinking schemes will inevitably generate errors. This kind of inertial thinking is called illusion inertial thinking. Because all machine learning methods do not consider illusion inertial thinking, in this paper we propose a new method that uses reverse thinking to correct illusion inertial thinking, which increases the generalization ability of machine learning methods. Experimental results on benchmark datasets are used to validate the proposed method.
A Hybrid Artificial-Noise and Secret-Key Scheme for Securing OFDM Transmissions in V2G Networks
Venue: arXiv cs.IT 2018
Year: 2018

We propose a new scheme to enhance the physical-layer security of wireless single-input single-output orthogonal-frequency division-multiplexing (OFDM) transmissions from an electric vehicle, Alice, to the aggregator, Bob, in the presence of an eavesdropper, Eve. To prevent information leakage to Eve, Alice exploits the wireless channel randomness to extract secret key symbols that are used to encrypt some data symbols which are then multiplexed in the frequency domain with the remaining unencrypted data symbols. To secure the unencrypted data symbols, Alice transmits an artificial-noise (AN) signal superimposed over her data signal. We propose a three-level optimization procedure to increase the average secrecy rate of this wiretap channel by optimizing the transmit power allocation between the encrypted data symbols, unencrypted data symbols and the AN symbols. Our numerical results show that the proposed scheme achieves considerable secrecy rate gains compared to the benchmark cases
Strong subgraph $k$-connectivity bounds
Venue: arXiv cs.DM 2018
Year: 2018

Let $D=(V,A)$ be a digraph of order $n$, $S$ a subset of $V$ of size $k$ and $2\le k\leq n$. Strong subgraphs $D_1, \dots , D_p$ containing $S$ are said to be internally disjoint if $V(D_i)\cap V(D_j)=S$ and $A(D_i)\cap A(D_j)=\emptyset$ for all $1\le i<j\le p$. Let $κ_S(D)$ be the maximum number of internally disjoint strong digraphs containing $S$ in $D$. The strong subgraph $k$-connectivity is defined as $$κ_k(D)=\min\{κ_S(D)\mid S\subseteq V, |S|=k\}.$$ A digraph $D=(V, A)$ is called minimally strong subgraph $(k,\ell)$-connected if $κ_k(D)\geq \ell$ but for any arc $e\in A$, $κ_k(D-e)\leq \ell-1$. In this paper, we first give a sharp upper bound for the parameter $κ_k(D)$ and then study the minimally strong subgraph $(k,\ell)$-connected digraphs.
Diversity and degrees of freedom in regression ensembles
Venue: arXiv cs.LG 2018
Year: 2018

Ensemble methods are a cornerstone of modern machine learning. The performance of an ensemble depends crucially upon the level of diversity between its constituent learners. This paper establishes a connection between diversity and degrees of freedom (i.e. the capacity of the model), showing that diversity may be viewed as a form of inverse regularisation. This is achieved by focusing on a previously published algorithm Negative Correlation Learning (NCL), in which model diversity is explicitly encouraged through a diversity penalty term in the loss function. We provide an exact formula for the effective degrees of freedom in an NCL ensemble with fixed basis functions, showing that it is a continuous, convex and monotonically increasing function of the diversity parameter. We demonstrate a connection to Tikhonov regularisation and show that, with an appropriately chosen diversity parameter, an NCL ensemble can always outperform the unregularised ensemble in the presence of noise. We demonstrate the practical utility of our approach by deriving a method to efficiently tune the diversity parameter. Finally, we use a Monte-Carlo estimator to extend the connection between diversity and degrees of freedom to ensembles of deep neural networks.
Left ventricle segmentation By modelling uncertainty in prediction of deep convolutional neural networks and adaptive thresholding inference
Venue: arXiv cs.CV 2018
Year: 2018

Deep neural networks have shown great achievements in solving complex problems. However, there are fundamental problems that limit their real world applications. Lack of measurable criteria for estimating uncertainty in the network outputs is one of these problems. In this paper, we address this limitation by introducing deformation to the network input and measuring the level of stability in the network's output. We calculate simple random transformations to estimate the prediction uncertainty of deep convolutional neural networks. For a real use-case, we apply this method to left ventricle segmentation in MRI cardiac images. We also propose an adaptive thresholding method to consider the deep neural network uncertainty. Experimental results demonstrate state-of-the-art performance and highlight the capabilities of simple methods in conjunction with deep neural networks.
Tractable and Scalable Schatten Quasi-Norm Approximations for Rank Minimization
Venue: arXiv cs.LG 2018
Year: 2018

The Schatten quasi-norm was introduced to bridge the gap between the trace norm and rank function. However, existing algorithms are too slow or even impractical for large-scale problems. Motivated by the equivalence relation between the trace norm and its bilinear spectral penalty, we define two tractable Schatten norms, i.e.\ the bi-trace and tri-trace norms, and prove that they are in essence the Schatten-$1/2$ and $1/3$ quasi-norms, respectively. By applying the two defined Schatten quasi-norms to various rank minimization problems such as MC and RPCA, we only need to solve much smaller factor matrices. We design two efficient linearized alternating minimization algorithms to solve our problems and establish that each bounded sequence generated by our algorithms converges to a critical point. We also provide the restricted strong convexity (RSC) based and MC error bounds for our algorithms. Our experimental results verified both the efficiency and effectiveness of our algorithms compared with the state-of-the-art methods.
Sequentialization and Procedural Complexity in Automata Networks
Venue: arXiv cs.DM 2018
Year: 2018

In this article we consider finite automata networks (ANs) with two kinds of update schedules: the parallel one (all automata are updated all together) and the sequential ones (the automata are updated periodically one at a time according to a total order w). The cost of sequentialization of a given AN h is the number of additional automata required to simulate h by a sequential AN with the same alphabet. We construct, for any n and q, an AN h of size n and alphabet size q whose cost of sequentialization is at least n/3. We also show that, if q $\ge$ 4, we can find one whose cost is at least n/2 -- log q (n). We prove that n/2 + log q (n/2 + 1) is an upper bound for the cost of sequentialization of any AN h of size n and alphabet size q. Finally, we exhibit the exact relation between the cost of sequentialization of h and its procedural complexity with unlimited memory and prove that its cost of sequentialization is less than or equal to the pathwidth of its interaction graph.
Optimal localist and distributed coding of spatiotemporal spike patterns through STDP and coincidence detection
Venue: arXiv cs.NE 2018
Year: 2018

Repeating spatiotemporal spike patterns exist and carry information. Here we investigated how a single spiking neuron can optimally respond to one given pattern (localist coding), or to either one of several patterns (distributed coding, i.e. the neuron's response is ambiguous but the identity of the pattern could be inferred from the response of multiple neurons), but not to random inputs. To do so, we extended a theory developed in a previous paper [Masquelier, 2017], which was limited to localist coding. More specifically, we computed analytically the signal-to-noise ratio (SNR) of a multi-pattern-detector neuron, using a threshold-free leaky integrate-and-fire (LIF) neuron model with non-plastic unitary synapses and homogeneous Poisson inputs. Surprisingly, when increasing the number of patterns, the SNR decreases slowly, and remains acceptable for several tens of independent patterns. In addition, we investigated whether spike-timing-dependent plasticity (STDP) could enable a neuron to reach the theoretical optimal SNR. To this aim, we simulated a LIF equipped with STDP, and repeatedly exposed it to multiple input spike patterns, embedded in equally dense Poisson spike trains. The LIF progressively became selective to every repeating pattern with no supervision, and stopped discharging during the Poisson spike trains. Furthermore, using certain STDP parameters, the resulting pattern detectors were optimal. Tens of independent patterns could be learned by a single neuron using a low adaptive threshold, in contrast with previous studies, in which higher thresholds led to localist coding only. Taken together these results suggest that coincidence detection and STDP are powerful mechanisms, fully compatible with distributed coding. Yet we acknowledge that our theory is limited to single neurons, and thus also applies to feed-forward networks, but not to recurrent ones.
A Generative Model for Non-Intrusive Load Monitoring in Commercial Buildings
Venue: arXiv cs.OH 2018
Year: 2018

In the recent years, there has been an increasing academic and industrial interest for analyzing the electrical consumption of commercial buildings. Whilst having similarities with the Non Intrusive Load Monitoring (NILM) tasks for residential buildings, the nature of the signals that are collected from large commercial buildings introduces additional difficulties to the NILM research causing existing NILM approaches to fail. On the other hand, the amount of publicly available datasets collected from commercial buildings is very limited, which makes the NILM research even more challenging for this type of large buildings. In this study, we aim at addressing these issues. We first present an extensive statistical analysis of both commercial and residential measurements from public and private datasets and show important differences. Secondly, we develop an algorithm for generating synthetic current waveforms. We then demonstrate using real measurement and quantitative metrics that both our device model and our simulations are realistic and can be used to evaluate NILM algorithms. Finally, to encourage research on commercial buildings we release a synthesized dataset.
Online Feature Ranking for Intrusion Detection Systems
Venue: arXiv cs.CR 2018
Year: 2018

Many current approaches to the design of intrusion detection systems apply feature selection in a static, non-adaptive fashion. These methods often neglect the dynamic nature of network data which requires to use adaptive feature selection techniques. In this paper, we present a simple technique based on incremental learning of support vector machines in order to rank the features in real time within a streaming model for network data. Some illustrative numerical experiments with two popular benchmark datasets show that our approach allows to adapt to the changes in normal network behaviour and novel attack patterns which have not been experienced before.
Discontinuities in Citation Relations among Journals: Self-organized Criticality as a Model of Scientific Revolutions and Change
Venue: arXiv cs.DL 2018
Year: 2018

Using three-year moving averages of the complete Journal Citation Reports 1994-2016 of the Science Citation Index and the Social Sciences Citation Index (combined), we analyze links between citing and cited journals in terms of (1) whether discontinuities among the networks of consecutive years have occurred; (2) are these discontinuities relatively isolated or networked? (3) Can these discontinuities be used as indicators of novelty, change, and innovation in the sciences? We examine each of the N2 links among the N journals across the years. We find power-laws for the top 10,000 instances of change, which we suggest interpreting in terms of "self-organized criticality": co-evolutions of avalanches in aggregated citation relations and meta-stable states in the knowledge base can be expected to drive the sciences towards the edges of chaos. The flux of journal-journal citations in new manuscripts may generate an avalanche in the meta-stable networks, but one can expect the effects to remain local (for example, within a specialty). The avalanches can be of any size; they reorient the relevant citation environments by inducing a rewrite of history in the affected partitions.
Finding steady-state solutions for ODE systems of zero, first and homogeneous second-order chemical reactions is NP-hard
Venue: arXiv cs.CC 2018
Year: 2018

In the context of modeling of cell signaling pathways, a relevant step is finding steady-state solutions for ODE systems that describe the kinetics of a set of chemical reactions, especially sets composed of zero, first, and second-order reactions. To compute a steady-state solution, one must set the left-hand side of each ODE as zero, hence obtaining a system of non-negative, quadratic polynomial equations. If all second-order reactions are homogeneous in respect to their reactants, then the obtained quadratic polynomial equation system will also have univariate monomials. Although it is a well-known fact that finding a root of a quadratic polynomial equation system is a NP-hard problem, it is not so easy to find a readily available proof of NP-hardness for special cases like the aforementioned one. Therefore, we provide here a self-contained proof that finding a root of non-negative, with univariate monomials quadratic polynomial equation system (NUMQ-PES) is NP-hard. This result implies that finding steady-state solutions for ODE systems of zero, first and homogeneous second-order chemical reactions is a NP-hard problem; hence, it is not a feasible approach to approximate non-homogeneous second-order reactions into homogeneous ones.
Memoryless Determinacy of Infinite Parity Games: Another Simple Proof
Venue: arXiv cs.GT 2018
Year: 2018

In 1998 Zielonka simplified the proofs of memoryless determinacy of infinite parity games. In 2018 Haddad simplified some proofs of memoryless determinacy of finite parity games. This article adapts Haddad's technique for infinite parity games. Two proofs are given, a shorter one and a more constructive one. None of them uses Zielonka's traps and attractors.
Throughput Maximization for Laser-Powered UAV Wireless Communication Systems
Venue: arXiv cs.IT 2018
Year: 2018

Laser power has become a viable solution to provide convenient and sustainable energy supply to unmanned aerial vehicles (UAVs). In this paper, we study a laser-powered UAV wireless communication system, where a laser transmitter sends laser beams to charge a fixed-wing UAV in flight, and the UAV uses the harvested laser energy to communicate with a ground station. To maintain the UAV's sustainable operation, its total energy consumption cannot exceed that harvested from the laser transmitter. Under such a laser energy harvesting constraint, we maximize the downlink communication throughput from the UAV to the ground station over a finite time duration, by jointly optimizing the UAV's trajectory and its transmit power allocation. However, due to the complicated UAV energy consumption model, this problem is non-convex and difficult to be solved. To tackle the problem, we first consider a special case with a double-circular UAV trajectory which balances the tradeoff between maximizing the performance of laser energy harvesting versus wireless communication at the UAV. Next, based on the obtained double-circular trajectory, we propose an efficient solution to the general problem, by applying the techniques of alternating optimization and sequential convex programming (SCP). Finally, numerical results are provided to validate the communication throughput performance of the proposed design.
QWIRE Practice: Formal Verification of Quantum Circuits in Coq
Venue: arXiv cs.LO 2018
Year: 2018

We describe an embedding of the QWIRE quantum circuit language in the Coq proof assistant. This allows programmers to write quantum circuits using high-level abstractions and to prove properties of those circuits using Coq's theorem proving features. The implementation uses higher-order abstract syntax to represent variable binding and provides a type-checking algorithm for linear wire types, ensuring that quantum circuits are well-formed. We formalize a denotational semantics that interprets QWIRE circuits as superoperators on density matrices, and prove the correctness of some simple quantum programs.
Age Group Classification with Speech and Metadata Multimodality Fusion
Venue: arXiv cs.CL 2018
Year: 2018

Children comprise a significant proportion of TV viewers and it is worthwhile to customize the experience for them. However, identifying who is a child in the audience can be a challenging task. Identifying gender and age from audio commands is a well-studied problem but is still very challenging to get good accuracy when the utterances are typically only a couple of seconds long. We present initial studies of a novel method which combines utterances with user metadata. In particular, we develop an ensemble of different machine learning techniques on different subsets of data to improve child detection. Our initial results show a 9.2\% absolute improvement over the baseline, leading to a state-of-the-art performance.
Representing Verbs as Argument Concepts
Venue: arXiv cs.CL 2018
Year: 2018

Verbs play an important role in the understanding of natural language text. This paper studies the problem of abstracting the subject and object arguments of a verb into a set of noun concepts, known as the "argument concepts". This set of concepts, whose size is parameterized, represents the fine-grained semantics of a verb. For example, the object of "enjoy" can be abstracted into time, hobby and event, etc. We present a novel framework to automatically infer human readable and machine computable action concepts with high accuracy.
Unsupervised Deep Single-Image Intrinsic Decomposition using Illumination-Varying Image Sequences
Venue: arXiv cs.CV 2018
Year: 2018

Machine learning based Single Image Intrinsic Decomposition (SIID) methods decompose a captured scene into its albedo and shading images by using the knowledge of a large set of known and realistic ground truth decompositions. Collecting and annotating such a dataset is an approach that cannot scale to sufficient variety and realism. We free ourselves from this limitation by training on unannotated images. Our method leverages the observation that two images of the same scene but with different lighting provide useful information on their intrinsic properties: by definition, albedo is invariant to lighting conditions, and cross-combining the estimated albedo of a first image with the estimated shading of a second one should lead back to the second one's input image. We transcribe this relationship into a siamese training scheme for a deep convolutional neural network that decomposes a single image into albedo and shading. The siamese setting allows us to introduce a new loss function including such cross-combinations, and to train solely on (time-lapse) images, discarding the need for any ground truth annotations. As a result, our method has the good properties of i) taking advantage of the time-varying information of image sequences in the (pre-computed) training step, ii) not requiring ground truth data to train on, and iii) being able to decompose single images of unseen scenes at runtime. To demonstrate and evaluate our work, we additionally propose a new rendered dataset containing illumination-varying scenes and a set of quantitative metrics to evaluate SIID algorithms. Despite its unsupervised nature, our results compete with state of the art methods, including supervised and non data-driven methods.
Maximum Volume Subset Selection for Anchored Boxes
Venue: arXiv cs.CG 2018
Year: 2018

Let $B$ be a set of $n$ axis-parallel boxes in $\mathbb{R}^d$ such that each box has a corner at the origin and the other corner in the positive quadrant of $\mathbb{R}^d$, and let $k$ be a positive integer. We study the problem of selecting $k$ boxes in $B$ that maximize the volume of the union of the selected boxes. This research is motivated by applications in skyline queries for databases and in multicriteria optimization, where the problem is known as the hypervolume subset selection problem. It is known that the problem can be solved in polynomial time in the plane, while the best known running time in any dimension $d \ge 3$ is $Ω\big(\binom{n}{k}\big)$. We show that: - The problem is NP-hard already in 3 dimensions. - In 3 dimensions, we break the bound $Ω\big(\binom{n}{k}\big)$, by providing an $n^{O(\sqrt{k})}$ algorithm. - For any constant dimension $d$, we present an efficient polynomial-time approximation scheme.