OpenRaiser/Intern-Atlas huggingface dataset:
Self-Organization in Traffic Lights: Evolution of Signal Control with Advances in Sensors and Communications
Venue: arXiv cs.SY 2017
Year: 2017

Traffic signals are ubiquitous devices that first appeared in 1868. Recent advances in information and communications technology (ICT) have led to unprecedented improvements in such areas as mobile handheld devices (i.e., smartphones), the electric power industry (i.e., smart grids), transportation infrastructure, and vehicle area networks. Given the trend towards interconnectivity, it is only a matter of time before vehicles communicate with one another and with infrastructure. In fact, several pilots of such vehicle-to-vehicle and vehicle-to-infrastructure (e.g. traffic lights and parking spaces) communication systems are already operational. This survey of autonomous and self-organized traffic signaling control has been undertaken with these potential developments in mind. Our research results indicate that, while many sophisticated techniques have attempted to improve the scheduling of traffic signal control, either real-time sensing of traffic patterns or a priori knowledge of traffic flow is required to optimize traffic. Once this is achieved, communication between traffic signals will serve to vastly improve overall traffic efficiency.
Transforming Coroutining Logic Programs into Equivalent CHR Programs
Venue: arXiv cs.PL 2017
Year: 2017

We extend a technique called Compiling Control. The technique transforms coroutining logic programs into logic programs that, when executed under the standard left-to-right selection rule (and not using any delay features) have the same computational behavior as the coroutining program. In recent work, we revised Compiling Control and reformulated it as an instance of Abstract Conjunctive Partial Deduction. This work was mostly focused on the program analysis performed in Compiling Control. In the current paper, we focus on the synthesis of the transformed program. Instead of synthesizing a new logic program, we synthesize a CHR(Prolog) program which mimics the coroutining program. The synthesis to CHR yields programs containing only simplification rules, which are particularly amenable to certain static analysis techniques. The programs are also more concise and readable and can be ported to CHR implementations embedded in other languages than Prolog.
Generating Loop Invariants for Program Verification by Transformation
Venue: arXiv cs.LO 2017
Year: 2017

Loop invariants play a central role in the verification of imperative programs. However, finding these invariants is often a difficult and time-consuming task for the programmer. We have previously shown how program transformation can be used to facilitate the verification of functional programs, but the verification of imperative programs is more challenging due to the need to discover these loop invariants. In this paper, we describe a technique for automatically discovering loop invariants. Our approach is similar to the induction-iteration method, but avoids the potentially exponential blow-up in clauses that can result when using this and other methods. Our approach makes use of the distil- lation program transformation algorithm to transform clauses into a simplified form that facilitates the identification of similarities and differences between them and thus help discover invariants. We prove that our technique terminates, and demonstrate its successful application to example programs that have proven to be problematic using other approaches. We also characterise the situations where our technique fails to find an invariant, and show how this can be ameliorated to a certain extent.
A Study on Neural Network Language Modeling
Venue: arXiv cs.CL 2017
Year: 2017

An exhaustive study on neural network language modeling (NNLM) is performed in this paper. Different architectures of basic neural network language models are described and examined. A number of different improvements over basic neural network language models, including importance sampling, word classes, caching and bidirectional recurrent neural network (BiRNN), are studied separately, and the advantages and disadvantages of every technique are evaluated. Then, the limits of neural network language modeling are explored from the aspects of model architecture and knowledge representation. Part of the statistical information from a word sequence will loss when it is processed word by word in a certain order, and the mechanism of training neural network by updating weight matrixes and vectors imposes severe restrictions on any significant enhancement of NNLM. For knowledge representation, the knowledge represented by neural network language models is the approximate probabilistic distribution of word sequences from a certain training data set rather than the knowledge of a language itself or the information conveyed by word sequences in a natural language. Finally, some directions for improving neural network language modeling further is discussed.
Error exponents of typical random codes
Venue: arXiv cs.IT 2017
Year: 2017

We define the error exponent of the typical random code as the long-block limit of the negative normalized expectation of the logarithm of the error probability of the random code, as opposed to the traditional random coding error exponent, which is the limit of the negative normalized logarithm of the expectation of the error probability. For the ensemble of uniformly randomly drawn fixed composition codes, we provide exact error exponents of typical random codes for a general discrete memoryless channel (DMC) and a wide class of (stochastic) decoders, collectively referred to as the generalized likelihood decoder (GLD). This ensemble of fixed composition codes is shown to be no worse than any other ensemble of independent codewords that are drawn under a permutation--invariant distribution (e.g., i.i.d. codewords). We also present relationships between the error exponent of the typical random code and the ordinary random coding error exponent, as well as the expurgated exponent for the GLD. Finally, we demonstrate that our analysis technique is applicable also to more general communication scenarios, such as list decoding (for fixed-size lists) as well as decoding with an erasure/list option in Forney's sense.
Golden Angle Modulation: Geometric- and Probabilistic-shaping
Venue: arXiv cs.IT 2017
Year: 2017

Quadrature amplitude modulation (QAM), deployed in billions of communication devises, exhibits a shaping-loss of $π\mathrm{e}/6$ ($\approx 1.53$ dB) compared to the Shannon-Hartley theorem. With inspiration gained from special (leaf, flower petal, and seed) packing arrangements (so called spiral phyllotaxis) found among plants, we have designed a shape-versatile, circular symmetric, modulation scheme, \textit{the Golden angle modulation (GAM)}. Geometric- and probabilistic-shaping-based GAM schemes are designed that practically overcome the shaping-loss of 1.53 dB. Specifically, we consider mutual information (MI)-optimized geometric-, probabilistic-, and joint geometric-and-probabilistic-GAM, under SNR-equality, and PAPR-inequality, constraints. Out of those, the joint scheme yields the highest MI-performance, and then comes the probabilistic schemes. This study finds that GAM could be an interesting candidate for future communication systems. Transmitter resource limited links, such as space probe-to-earth, satellite, and mobile-to-basestation, are scenarios where capacity achieving GAM could be of particular value.
Power Allocation for Energy Efficiency and Secrecy of Interference Wireless Networks
Venue: arXiv cs.IT 2017
Year: 2017

Considering a multi-user interference network with an eavesdropper, this paper aims at the power allocation to optimize the worst secrecy throughput among the network links or the secure energy efficiency in terms of achieved secrecy throughput per Joule under link security requirements. Three scenarios for the access of channel state information are considered: the perfect channel state information, partial channel state information with channels from the transmitters to the eavesdropper exponentially distributed, and not perfectly known channels between the transmitters and the users with exponentially distributed errors. The paper develops various path-following procedures of low complexity and rapid convergence for the optimal power allocation. Their effectiveness and viability are illustrated through numerical examples. The power allocation schemes are shown to achieve both high secrecy throughput and energy efficiency.
Active Sampling of Pairs and Points for Large-scale Linear Bipartite Ranking
Venue: arXiv cs.LG 2017
Year: 2017

Bipartite ranking is a fundamental ranking problem that learns to order relevant instances ahead of irrelevant ones. The pair-wise approach for bi-partite ranking construct a quadratic number of pairs to solve the problem, which is infeasible for large-scale data sets. The point-wise approach, albeit more efficient, often results in inferior performance. That is, it is difficult to conduct bipartite ranking accurately and efficiently at the same time. In this paper, we develop a novel active sampling scheme within the pair-wise approach to conduct bipartite ranking efficiently. The scheme is inspired from active learning and can reach a competitive ranking performance while focusing only on a small subset of the many pairs during training. Moreover, we propose a general Combined Ranking and Classification (CRC) framework to accurately conduct bipartite ranking. The framework unifies point-wise and pair-wise approaches and is simply based on the idea of treating each instance point as a pseudo-pair. Experiments on 14 real-word large-scale data sets demonstrate that the proposed algorithm of Active Sampling within CRC, when coupled with a linear Support Vector Machine, usually outperforms state-of-the-art point-wise and pair-wise ranking approaches in terms of both accuracy and efficiency.
Wireless Network Design for Control Systems: A Survey
Venue: arXiv cs.SY 2017
Year: 2017

Wireless networked control systems (WNCS) are composed of spatially distributed sensors, actuators, and con- trollers communicating through wireless networks instead of conventional point-to-point wired connections. Due to their main benefits in the reduction of deployment and maintenance costs, large flexibility and possible enhancement of safety, WNCS are becoming a fundamental infrastructure technology for critical control systems in automotive electrical systems, avionics control systems, building management systems, and industrial automation systems. The main challenge in WNCS is to jointly design the communication and control systems considering their tight interaction to improve the control performance and the network lifetime. In this survey, we make an exhaustive review of the literature on wireless network design and optimization for WNCS. First, we discuss what we call the critical interactive variables including sampling period, message delay, message dropout, and network energy consumption. The mutual effects of these communication and control variables motivate their joint tuning. We discuss the effect of controllable wireless network parameters at all layers of the communication protocols on the probability distribution of these interactive variables. We also review the current wireless network standardization for WNCS and their corresponding methodology for adapting the network parameters. Moreover, we discuss the analysis and design of control systems taking into account the effect of the interactive variables on the control system performance. Finally, we present the state-of-the-art wireless network design and optimization for WNCS, while highlighting the tradeoff between the achievable performance and complexity of various approaches. We conclude the survey by highlighting major research issues and identifying future research directions.
The Weisfeiler-Leman Dimension of Planar Graphs is at most 3
Venue: arXiv cs.DM 2017
Year: 2017

We prove that the Weisfeiler-Leman (WL) dimension of the class of all finite planar graphs is at most 3. In particular, every finite planar graph is definable in first-order logic with counting using at most 4 variables. The previously best known upper bounds for the dimension and number of variables were 14 and 15, respectively. First we show that, for dimension 3 and higher, the WL-algorithm correctly tests isomorphism of graphs in a minor-closed class whenever it determines the orbits of the automorphism group of any arc-colored 3-connected graph belonging to this class. Then we prove that, apart from several exceptional graphs (which have WL-dimension at most 2), the individualization of two correctly chosen vertices of a colored 3-connected planar graph followed by the 1-dimensional WL-algorithm produces the discrete vertex partition. This implies that the 3-dimensional WL-algorithm determines the orbits of a colored 3-connected planar graph. As a byproduct of the proof, we get a classification of the 3-connected planar graphs with fixing number 3.
A Non-Convex Optimization Technique for Sparse Blind Deconvolution -- Initialization Aspects and Error Reduction Properties
Venue: arXiv cs.IT 2017
Year: 2017

Sparse blind deconvolution is the problem of estimating the blur kernel and sparse excitation, both of which are unknown. Considering a linear convolution model, as opposed to the standard circular convolution model, we derive a sufficient condition for stable deconvolution. The columns of the linear convolution matrix form a Riesz basis with the tightness of the Riesz bounds determined by the autocorrelation of the blur kernel. Employing a Bayesian framework results in a non-convex, non-smooth cost function consisting of an $\ell_2$ data-fidelity term and a sparsity promoting $\ell_p$-norm ($0 \le p \le 1$) regularizer. Since the $\ell_p$-norm is not differentiable at the origin, we employ an $ε$-regularized $\ell_p$-norm as a surrogate. The data term is also non-convex in both the blur kernel and excitation. An iterative scheme termed alternating minimization (Alt. Min.) $\ell_p-\ell_2$ projections algorithm (ALPA) is developed for optimization of the $ε$-regularized cost function. Further, we demonstrate that, in every iteration, the $ε$-regularized cost function is non-increasing and more importantly, bounds the original $\ell_p$-norm-based cost. Due to non-convexity of the cost, the accuracy of estimation is largely influenced by the initialization. Considering regularized least-squares estimate as the initialization, we analyze how the initialization errors are concentrated, first in Gaussian noise, and then in bounded noise, the latter case resulting in tighter bounds. Comparisons with state-of-the-art blind deconvolution algorithms show that the deconvolution accuracy is higher in case of ALPA. In the context of natural speech signals, ALPA results in accurate deconvolution of a voiced speech segment into a sparse excitation and smooth vocal tract response.
A Fast Approximation Scheme for Low-Dimensional $k$-Means
Venue: arXiv cs.DS 2017
Year: 2017

We consider the popular $k$-means problem in $d$-dimensional Euclidean space. Recently Friggstad, Rezapour, Salavatipour [FOCS'16] and Cohen-Addad, Klein, Mathieu [FOCS'16] showed that the standard local search algorithm yields a $(1+ε)$-approximation in time $(n \cdot k)^{1/ε^{O(d)}}$, giving the first polynomial-time approximation scheme for the problem in low-dimensional Euclidean space. While local search achieves optimal approximation guarantees, it is not competitive with the state-of-the-art heuristics such as the famous $k$-means++ and $D^2$-sampling algorithms. In this paper, we aim at bridging the gap between theory and practice by giving a $(1+ε)$-approximation algorithm for low-dimensional $k$-means running in time $n \cdot k \cdot (\log n)^{(dε^{-1})^{O(d)}}$, and so matching the running time of the $k$-means++ and $D^2$-sampling heuristics up to polylogarithmic factors. We speed-up the local search approach by making a non-standard use of randomized dissections that allows to find the best local move efficiently using a quite simple dynamic program. We hope that our techniques could help design better local search heuristics for geometric problems. We note that the doubly exponential dependency on $d$ is necessary as $k$-means is APX-hard in dimension $d = ω(\log n)$.
One-Way Trail Orientations
Venue: arXiv cs.DS 2017
Year: 2017

Given a graph, does there exist an orientation of the edges such that the resulting directed graph is strongly connected? Robbins' theorem [Robbins, Am. Math. Monthly, 1939] states that such an orientation exists if and only if the graph is $2$-edge connected. A natural extension of this problem is the following: Suppose that the edges of the graph is partitioned into trails. Can we orient the trails such that the resulting directed graph is strongly connected? We show that $2$-edge connectivity is again a sufficient condition and we provide a linear time algorithm for finding such an orientation, which is both optimal and the first polynomial time algorithm for deciding this problem. The generalised Robbins' theorem [Boesch, Am. Math. Monthly, 1980] for mixed multigraphs states that the undirected edges of a mixed multigraph can be oriented making the resulting directed graph strongly connected exactly when the mixed graph is connected and the underlying graph is bridgeless. We show that as long as all cuts have at least $2$ undirected edges or directed edges both ways, then there exists an orientation making the resulting directed graph strongly connected. This provides the first polynomial time algorithm for this problem and a very simple polynomial time algorithm to the previous problem.
FacePoseNet: Making a Case for Landmark-Free Face Alignment
Venue: arXiv cs.CV 2017
Year: 2017

We show how a simple convolutional neural network (CNN) can be trained to accurately and robustly regress 6 degrees of freedom (6DoF) 3D head pose, directly from image intensities. We further explain how this FacePoseNet (FPN) can be used to align faces in 2D and 3D as an alternative to explicit facial landmark detection for these tasks. We claim that in many cases the standard means of measuring landmark detector accuracy can be misleading when comparing different face alignments. Instead, we compare our FPN with existing methods by evaluating how they affect face recognition accuracy on the IJB-A and IJB-B benchmarks: using the same recognition pipeline, but varying the face alignment method. Our results show that (a) better landmark detection accuracy measured on the 300W benchmark does not necessarily imply better face recognition accuracy. (b) Our FPN provides superior 2D and 3D face alignment on both benchmarks. Finally, (c), FPN aligns faces at a small fraction of the computational cost of comparably accurate landmark detectors. For many purposes, FPN is thus a far faster and far more accurate face alignment method than using facial landmark detectors.
Learning Spatio-Temporal Features with 3D Residual Networks for Action Recognition
Venue: arXiv cs.CV 2017
Year: 2017

Convolutional neural networks with spatio-temporal 3D kernels (3D CNNs) have an ability to directly extract spatio-temporal features from videos for action recognition. Although the 3D kernels tend to overfit because of a large number of their parameters, the 3D CNNs are greatly improved by using recent huge video databases. However, the architecture of 3D CNNs is relatively shallow against to the success of very deep neural networks in 2D-based CNNs, such as residual networks (ResNets). In this paper, we propose a 3D CNNs based on ResNets toward a better action representation. We describe the training procedure of our 3D ResNets in details. We experimentally evaluate the 3D ResNets on the ActivityNet and Kinetics datasets. The 3D ResNets trained on the Kinetics did not suffer from overfitting despite the large number of parameters of the model, and achieved better performance than relatively shallow networks, such as C3D. Our code and pretrained models (e.g. Kinetics and ActivityNet) are publicly available at https://github.com/kenshohara/3D-ResNets.
A Function Approximation Method for Model-based High-Dimensional Inverse Reinforcement Learning
Venue: arXiv cs.LG 2017
Year: 2017

This works handles the inverse reinforcement learning problem in high-dimensional state spaces, which relies on an efficient solution of model-based high-dimensional reinforcement learning problems. To solve the computationally expensive reinforcement learning problems, we propose a function approximation method to ensure that the Bellman Optimality Equation always holds, and then estimate a function based on the observed human actions for inverse reinforcement learning problems. The time complexity of the proposed method is linearly proportional to the cardinality of the action set, thus it can handle high-dimensional even continuous state spaces efficiently. We test the proposed method in a simulated environment to show its accuracy, and three clinical tasks to show how it can be used to evaluate a doctor's proficiency.
From close the door to do not click and back. Security by design for older adults
Venue: arXiv cs.CY 2017
Year: 2017

With the growing number of older adults who adopt mobile technology in their life, a new form of challenge faces both them, as well as the software engineering communities. This challenge is the issue of safety, not only in the context of risk older adults already face on-line, but also, due to the mobile nature of the used applications, real life safety issues raising from the use of on-line solutions. In this paper, we wish to use a case study they conducted in order to address this issue of interrelating on-line and real life threats. We describe how the observation from the case study relate to the collected body off knowledge in the relevant topic, as well as propose a set of suggestion for improving the design of applications in regards to addressing the issue of older adults safety.
Efficient Adaptive Implementation of the Serial Schedule Generation Scheme using Preprocessing and Bloom Filters
Venue: arXiv cs.DS 2017
Year: 2017

The majority of scheduling metaheuristics use indirect representation of solutions as a way to efficiently explore the search space. Thus, a crucial part of such metaheuristics is a "schedule generation scheme" -- procedure translating the indirect solution representation into a schedule. Schedule generation scheme is used every time a new candidate solution needs to be evaluated. Being relatively slow, it eats up most of the running time of the metaheuristic and, thus, its speed plays significant role in performance of the metaheuristic. Despite its importance, little attention has been paid in the literature to efficient implementation of schedule generation schemes. We give detailed description of serial schedule generation scheme, including new improvements, and propose a new approach for speeding it up, by using Bloom filters. The results are further strengthened by automated control of parameters. Finally, we employ online algorithm selection to dynamically choose which of the two implementations to use. This hybrid approach significantly outperforms conventional implementation on a wide range of instances.