OpenRaiser/Intern-Atlas huggingface dataset:
Sequential Linear Quadratic Optimal Control for Nonlinear Switched Systems
Venue: arXiv cs.SY 2017
Year: 2017

In this contribution, we introduce an efficient method for solving the optimal control problem for an unconstrained nonlinear switched system with an arbitrary cost function. We assume that the sequence of the switching modes are given but the switching time in between consecutive modes remains to be optimized. The proposed method uses a two-stage approach as introduced by Xu and Antsaklis (2004) where the original optimal control problem is transcribed into an equivalent problem parametrized by the switching times and the optimal control policy is obtained based on the solution of a two-point boundary value differential equation. The main contribution of this paper is to use a Sequential Linear Quadratic approach to synthesize the optimal controller instead of solving a boundary value problem. The proposed method is numerically more efficient and scales very well to the high dimensional problems. In order to evaluate its performance, we use two numerical examples as benchmarks to compare against the baseline algorithm. In the third numerical example, we apply the proposed algorithm to the Center of Mass control problem in a quadruped robot locomotion task.
On Performance Modeling for MANETs under General Limited Buffer Constraint
Venue: arXiv cs.IT 2017
Year: 2017

Understanding the real achievable performance of mobile ad hoc networks (MANETs) under practical network constraints is of great importance for their applications in future highly heterogeneous wireless network environments. This paper explores, for the first time, the performance modeling for MANETs under a general limited buffer constraint, where each network node maintains a limited source buffer of size $B_s$ to store its locally generated packets and also a limited shared relay buffer of size $B_r$ to store relay packets for other nodes. Based on the Queuing theory and birth-death chain theory, we first develop a general theoretical framework to fully depict the source/relay buffer occupancy process in such a MANET, which applies to any distributed MAC protocol and any mobility model that leads to the uniform distribution of nodes' locations in steady state. With the help of this framework, we then derive the exact expressions of several key network performance metrics, including achievable throughput, throughput capacity, and expected end-to-end delay. We further conduct case studies under two network scenarios and provide the corresponding theoretical/simulation results to demonstrate the application as well as the efficiency of our theoretical framework. Finally, we present extensive numerical results to illustrate the impacts of buffer constraint on the performance of a buffer-limited MANET.
Voltage stabilization in DC microgrids: an approach based on line-independent plug-and-play controllers
Venue: arXiv cs.SY 2017
Year: 2017

We consider the problem of stabilizing voltages in DC microGrids (mGs) given by the interconnection of Distributed Generation Units (DGUs), power lines and loads. We propose a decentralized control architecture where the primary controller of each DGU can be designed in a Plug-and-Play (PnP) fashion, allowing the seamless addition of new DGUs. Differently from several other approaches to primary control, local design is independent of the parameters of power lines. Moreover, differently from the PnP control scheme in [1], the plug-in of a DGU does not require to update controllers of neighboring DGUs. Local control design is cast into a Linear Matrix Inequality (LMI) problem that, if unfeasible, allows one to deny plug-in requests that might be dangerous for mG stability. The proof of closed-loop stability of voltages exploits structured Lyapunov functions, the LaSalle invariance theorem and properties of graph Laplacians. Theoretical results are backed up by simulations in PSCAD.
Typing weak MSOL properties
Venue: arXiv cs.LO 2017
Year: 2017

We consider lambda-Y-calculus as a non-interpreted functional programming language: the result of the execution of a program is its normal form that can be seen as the tree of calls to built-in operations. Weak monadic second-order logic (wMSOL) is well suited to express properties of such trees. We give a type system for ensuring that the result of the execution of a lambda-Y-program satisfies a given wMSOL property. In order to prove soundness and completeness of the system we construct a denotational semantics of lambda-Y-calculus that is capable of computing properties expressed in wMSOL.
Algorithmic Aspects of Regular Graph Covers
Venue: arXiv cs.DM 2017
Year: 2017

A graph $G$ covers a graph $H$ if there exists a locally bijective homomorphism from $G$ to $H$. We deal with regular covers where this homomorphism is prescribed by the action of a semiregular subgroup of $\textrm{Aut}(G)$. We study computational aspects of regular covers that have not been addressed before. The decision problem RegularCover asks for given graphs $G$ and $H$ whether $G$ regularly covers $H$. When $|H|=1$, this problem becomes Cayley graph recognition for which the complexity is still unresolved. Another special case arises for $|G| = |H|$ when it becomes the graph isomorphism problem. Our main result is an involved FPT algorithm solving RegularCover for planar inputs $G$ in time $O^*(2^{e(H)/2})$ where $e(H)$ denotes the number of edges of $H$. The algorithm is based on dynamic programming and employs theoretical results proved in a related structural paper. Further, when $G$ is 3-connected, $H$ is 2-connected or the ratio $|G|/|H|$ is an odd integer, we can solve the problem RegularCover in polynomial time. In comparison, Bílka et al. (2011) proved that testing general graph covers is NP-complete for planar inputs $G$ when $H$ is a small fixed graph such as $K_4$ or $K_5$.
Sequential Deep Trajectory Descriptor for Action Recognition with Three-stream CNN
Venue: arXiv cs.CV 2017
Year: 2017

Learning the spatial-temporal representation of motion information is crucial to human action recognition. Nevertheless, most of the existing features or descriptors cannot capture motion information effectively, especially for long-term motion. To address this problem, this paper proposes a long-term motion descriptor called sequential Deep Trajectory Descriptor (sDTD). Specifically, we project dense trajectories into two-dimensional planes, and subsequently a CNN-RNN network is employed to learn an effective representation for long-term motion. Unlike the popular two-stream ConvNets, the sDTD stream is introduced into a three-stream framework so as to identify actions from a video sequence. Consequently, this three-stream framework can simultaneously capture static spatial features, short-term motion and long-term motion in the video. Extensive experiments were conducted on three challenging datasets: KTH, HMDB51 and UCF101. Experimental results show that our method achieves state-of-the-art performance on the KTH and UCF101 datasets, and is comparable to the state-of-the-art methods on the HMDB51 dataset.
Quantifying the informativeness for biomedical literature summarization: An itemset mining method
Venue: arXiv cs.IR 2017
Year: 2017

Objective: Automatic text summarization tools can help users in the biomedical domain to access information efficiently from a large volume of scientific literature and other sources of text documents. In this paper, we propose a summarization method that combines itemset mining and domain knowledge to construct a concept-based model and to extract the main subtopics from an input document. Our summarizer quantifies the informativeness of each sentence using the support values of itemsets appearing in the sentence. Methods: To address the concept-level analysis of text, our method initially maps the original document to biomedical concepts using the UMLS. Then, it discovers the essential subtopics of the text using a data mining technique, namely itemset mining, and constructs the summarization model. The employed itemset mining algorithm extracts a set of frequent itemsets containing correlated and recurrent concepts of the input document. The summarizer selects the most related and informative sentences and generates the final summary. Results: We evaluate the performance of our itemset-based summarizer using the Recall-Oriented Understudy for Gisting Evaluation (ROUGE) metrics, performing a set of experiments. The results show that the itemset-based summarizer performs better than the compared methods. The itemset-based summarizer achieves the best scores for all the assessed ROUGE metrics . Conclusion: Compared to the statistical, similarity, and word frequency methods, the proposed method demonstrates that the summarization model obtained from the concept extraction and itemset mining provides the summarizer with an effective metric for measuring the informative content of sentences. This can lead to an improvement in the performance of biomedical literature summarization.
Multiplex visibility graphs to investigate recurrent neural networks dynamics
Venue: arXiv cs.NE 2017
Year: 2017

A recurrent neural network (RNN) is a universal approximator of dynamical systems, whose performance often depends on sensitive hyperparameters. Tuning of such hyperparameters may be difficult and, typically, based on a trial-and-error approach. In this work, we adopt a graph-based framework to interpret and characterize the internal RNN dynamics. Through this insight, we are able to design a principled unsupervised method to derive configurations with maximized performances, in terms of prediction error and memory capacity. In particular, we propose to model time series of neurons activations with the recently introduced horizontal visibility graphs, whose topological properties reflect important dynamical features of the underlying dynamic system. Successively, each graph becomes a layer of a larger structure, called multiplex. We show that topological properties of such a multiplex reflect important features of RNN dynamics and are used to guide the tuning procedure. To validate the proposed method, we consider a class of RNNs called echo state networks. We perform experiments and discuss results on several benchmarks and real-world dataset of call data records.
Learning Semantic Part-Based Models from Google Images
Venue: arXiv cs.CV 2017
Year: 2017

We propose a technique to train semantic part-based models of object classes from Google Images. Our models encompass the appearance of parts and their spatial arrangement on the object, specific to each viewpoint. We learn these rich models by collecting training instances for both parts and objects, and automatically connecting the two levels. Our framework works incrementally, by learning from easy examples first, and then gradually adapting to harder ones. A key benefit of this approach is that it requires no manual part location annotations. We evaluate our models on the challenging PASCAL-Part dataset [1] and show how their performance increases at every step of the learning, with the final models more than doubling the performance of directly training from images retrieved by querying for part names (from 12.9 to 27.2 AP). Moreover, we show that our part models can help object detection performance by enriching the R-CNN detector with parts.
Sensor-based Gait Parameter Extraction with Deep Convolutional Neural Networks
Venue: arXiv cs.LG 2017
Year: 2017

Measurement of stride-related, biomechanical parameters is the common rationale for objective gait impairment scoring. State-of-the-art double integration approaches to extract these parameters from inertial sensor data are, however, limited in their clinical applicability due to the underlying assumptions. To overcome this, we present a method to translate the abstract information provided by wearable sensors to context-related expert features based on deep convolutional neural networks. Regarding mobile gait analysis, this enables integration-free and data-driven extraction of a set of 8 spatio-temporal stride parameters. To this end, two modelling approaches are compared: A combined network estimating all parameters of interest and an ensemble approach that spawns less complex networks for each parameter individually. The ensemble approach is outperforming the combined modelling in the current application. On a clinically relevant and publicly available benchmark dataset, we estimate stride length, width and medio-lateral change in foot angle up to ${-0.15\pm6.09}$ cm, ${-0.09\pm4.22}$ cm and ${0.13 \pm 3.78^\circ}$ respectively. Stride, swing and stance time as well as heel and toe contact times are estimated up to ${\pm 0.07}$, ${\pm0.05}$, ${\pm 0.07}$, ${\pm0.07}$ and ${\pm0.12}$ s respectively. This is comparable to and in parts outperforming or defining state-of-the-art. Our results further indicate that the proposed change in methodology could substitute assumption-driven double-integration methods and enable mobile assessment of spatio-temporal stride parameters in clinically critical situations as e.g. in the case of spastic gait impairments.
FALCON: Feature Driven Selective Classification for Energy-Efficient Image Recognition
Venue: arXiv cs.CV 2017
Year: 2017

Machine-learning algorithms have shown outstanding image recognition or classification performance for computer vision applications. However, the compute and energy requirement for implementing such classifier models for large-scale problems is quite high. In this paper, we propose Feature Driven Selective Classification (FALCON) inspired by the biological visual attention mechanism in the brain to optimize the energy-efficiency of machine-learning classifiers. We use the consensus in the characteristic features (color/texture) across images in a dataset to decompose the original classification problem and construct a tree of classifiers (nodes) with a generic-to-specific transition in the classification hierarchy. The initial nodes of the tree separate the instances based on feature information and selectively enable the latter nodes to perform object specific classification. The proposed methodology allows selective activation of only those branches and nodes of the classification tree that are relevant to the input while keeping the remaining nodes idle. Additionally, we propose a programmable and scalable Neuromorphic Engine (NeuE) that utilizes arrays of specialized neural computational elements to execute the FALCON based classifier models for diverse datasets. The structure of FALCON facilitates the reuse of nodes while scaling up from small classification problems to larger ones thus allowing us to construct classifier implementations that are significantly more efficient. We evaluate our approach for a 12-object classification task on the Caltech101 dataset and 10-object task on CIFAR-10 dataset by constructing FALCON models on the NeuE platform in 45nm technology. Our results demonstrate significant improvement in energy-efficiency and training time for minimal loss in output quality.
Deep Coevolutionary Network: Embedding User and Item Features for Recommendation
Venue: arXiv cs.LG 2017
Year: 2017

Recommender systems often use latent features to explain the behaviors of users and capture the properties of items. As users interact with different items over time, user and item features can influence each other, evolve and co-evolve over time. The compatibility of user and item's feature further influence the future interaction between users and items. Recently, point process based models have been proposed in the literature aiming to capture the temporally evolving nature of these latent features. However, these models often make strong parametric assumptions about the evolution process of the user and item latent features, which may not reflect the reality, and has limited power in expressing the complex and nonlinear dynamics underlying these processes. To address these limitations, we propose a novel deep coevolutionary network model (DeepCoevolve), for learning user and item features based on their interaction graph. DeepCoevolve use recurrent neural network (RNN) over evolving networks to define the intensity function in point processes, which allows the model to capture complex mutual influence between users and items, and the feature evolution over time. We also develop an efficient procedure for training the model parameters, and show that the learned models lead to significant improvements in recommendation and activity prediction compared to previous state-of-the-arts parametric models.
Correlations of consumption patterns in social-economic networks
Venue: arXiv cs.SI 2017
Year: 2017

We analyze a coupled anonymized dataset collecting the mobile phone communication and bank transactions history of a large number of individuals. After mapping the social structure and introducing indicators of socioeconomic status, demographic features, and purchasing habits of individuals we show that typical consumption patterns are strongly correlated with identified socioeconomic classes leading to patterns of stratification in the social structure. In addition we measure correlations between merchant categories and introduce a correlation network, which emerges with a meaningful community structure. We detect multivariate relations between merchant categories and show correlations in purchasing habits of individuals. Our work provides novel and detailed insight into the relations between social and consuming behaviour with potential applications in recommendation system design.
Did the Train Reach its Destination: The Complexity of Finding a Witness
Venue: arXiv cs.CC 2017
Year: 2017

Recently, Dohrau et al. studied a zero-player game on switch graphs and proved that deciding the termination of the game is in NP $\cap$ coNP. In this short paper, we show that the search version of this game on switch graphs, i.e., the task of finding a witness of termination (or of non-termination) is in PLS.
Image Decomposition Using a Robust Regression Approach
Venue: arXiv cs.CV 2017
Year: 2017

This paper considers how to separate text and/or graphics from smooth background in screen content and mixed content images and proposes an algorithm to perform this segmentation task. The proposed methods make use of the fact that the background in each block is usually smoothly varying and can be modeled well by a linear combination of a few smoothly varying basis functions, while the foreground text and graphics create sharp discontinuity. This algorithm separates the background and foreground pixels by trying to fit pixel values in the block into a smooth function using a robust regression method. The inlier pixels that can be well represented with the smooth model will be considered as background, while remaining outlier pixels will be considered foreground. We have also created a dataset of screen content images extracted from HEVC standard test sequences for screen content coding with their ground truth segmentation result which can be used for this task. The proposed algorithm has been tested on the dataset mentioned above and is shown to have superior performance over other methods, such as the hierarchical k-means clustering algorithm, shape primitive extraction and coding, and the least absolute deviation fitting scheme for foreground segmentation.
Formalizing Neurath's Ship: Approximate Algorithms for Online Causal Learning
Venue: arXiv cs.LG 2017
Year: 2017

Higher-level cognition depends on the ability to learn models of the world. We can characterize this at the computational level as a structure-learning problem with the goal of best identifying the prevailing causal relationships among a set of relata. However, the computational cost of performing exact Bayesian inference over causal models grows rapidly as the number of relata increases. This implies that the cognitive processes underlying causal learning must be substantially approximate. A powerful class of approximations that focuses on the sequential absorption of successive inputs is captured by the Neurath's ship metaphor in philosophy of science, where theory change is cast as a stochastic and gradual process shaped as much by people's limited willingness to abandon their current theory when considering alternatives as by the ground truth they hope to approach. Inspired by this metaphor and by algorithms for approximating Bayesian inference in machine learning, we propose an algorithmic-level model of causal structure learning under which learners represent only a single global hypothesis that they update locally as they gather evidence. We propose a related scheme for understanding how, under these limitations, learners choose informative interventions that manipulate the causal system to help elucidate its workings. We find support for our approach in the analysis of four experiments.
Unrestricted State Complexity of Binary Operations on Regular and Ideal Languages
Venue: arXiv cs.FL 2017
Year: 2017

We study the state complexity of binary operations on regular languages over different alphabets. It is known that if $L'_m$ and $L_n$ are languages of state complexities $m$ and $n$, respectively, and restricted to the same alphabet, the state complexity of any binary boolean operation on $L'_m$ and $L_n$ is $mn$, and that of product (concatenation) is $m 2^n - 2^{n-1}$. In contrast to this, we show that if $L'_m$ and $L_n$ are over different alphabets, the state complexity of union and symmetric difference is $(m+1)(n+1)$, that of difference is $mn+m$, that of intersection is $mn$, and that of product is $m2^n+2^{n-1}$. We also study unrestricted complexity of binary operations in the classes of regular right, left, and two-sided ideals, and derive tight upper bounds. The bounds for product of the unrestricted cases (with the bounds for the restricted cases in parentheses) are as follows: right ideals $m+2^{n-2}+2^{n-1}$ ($m+2^{n-2}$); left ideals $mn+m+n$ ($m+n-1$); two-sided ideals $m+2n$ ($m+n-1$). The state complexities of boolean operations on all three types of ideals are the same as those of arbitrary regular languages, whereas that is not the case if the alphabets of the arguments are the same. Finally, we update the known results about most complex regular, right-ideal, left-ideal, and two-sided-ideal languages to include the unrestricted cases.
On Memory Footprints of Partitioned Sparse Matrices
Venue: arXiv cs.NA 2017
Year: 2017

Runtime characteristics of sparse matrix computations and related processes may be often improved by reducing memory footprints of involved matrices. Such a reduction can be usually achieved when matrices are processed in a block-wise manner. The presented study analysed memory footprints of 563 representative benchmark sparse matrices with respect to their partitioning into uniformly-sized blocks. Different block sizes and different ways of storing blocks in memory were considered and statistically evaluated. Memory footprints of partitioned matrices were additionally compared with lower bounds and with the CSR storage format. The average measured memory savings against CSR in case of single and double precision were 42.3 and 28.7 percents, the corresponding worst-case savings 25.5 and 17.1 percents. Moreover, memory footprints of partitioned matrices were in average 5 times closer to their lower bounds than CSR. Based on the obtained results, generic suggestions for efficient partitioning and storage of sparse matrices in a computer memory are provided.