OpenRaiser/Intern-Atlas huggingface dataset:
Road to safe autonomy with data and formal reasoning
Venue: arXiv cs.SY 2017
Year: 2017

We present an overview of recently developed data-driven tools for safety analysis of autonomous vehicles and advanced driver assist systems. The core algorithms combine model-based, hybrid system reachability analysis with sensitivity analysis of components with unknown or inaccessible models. We illustrate the applicability of this approach with a new case study of emergency braking systems in scenarios with two or three vehicles. This problem is representative of the most common type of rear-end crashes, which is relevant for safety analysis of automatic emergency braking (AEB) and forward collision avoidance systems. We show that our verification tool can effectively prove the safety of certain scenarios (specified by several parameters like braking profiles, initial velocities, uncertainties in position and reaction times), and also compute the severity of accidents for unsafe scenarios. Through hundreds of verification experiments, we quantified the safety envelope of the system across relevant parameters. These results show that the approach is promising for design, debugging and certification. We also show how the reachability analysis can be combined with statistical information about the parameters, to assess the risk level of the control system, which in turn is essential, for example, for determining Automotive Safety Integrity Levels (ASIL) for the ISO26262 standard.
Time Series Prediction for Graphs in Kernel and Dissimilarity Spaces
Venue: arXiv cs.AI 2017
Year: 2017

Graph models are relevant in many fields, such as distributed computing, intelligent tutoring systems or social network analysis. In many cases, such models need to take changes in the graph structure into account, i.e. a varying number of nodes or edges. Predicting such changes within graphs can be expected to yield important insight with respect to the underlying dynamics, e.g. with respect to user behaviour. However, predictive techniques in the past have almost exclusively focused on single edges or nodes. In this contribution, we attempt to predict the future state of a graph as a whole. We propose to phrase time series prediction as a regression problem and apply dissimilarity- or kernel-based regression techniques, such as 1-nearest neighbor, kernel regression and Gaussian process regression, which can be applied to graphs via graph kernels. The output of the regression is a point embedded in a pseudo-Euclidean space, which can be analyzed using subsequent dissimilarity- or kernel-based processing methods. We discuss strategies to speed up Gaussian Processes regression from cubic to linear time and evaluate our approach on two well-established theoretical models of graph evolution as well as two real data sets from the domain of intelligent tutoring systems. We find that simple regression methods, such as kernel regression, are sufficient to capture the dynamics in the theoretical models, but that Gaussian process regression significantly improves the prediction error for real-world data.
A cost-effective isogeometric approach for composite plates based on a stress recovery procedure
Venue: arXiv cs.CE 2017
Year: 2017

This paper introduces a cost-effective strategy to simulate the behavior of laminated plates by means of isogeometric 3D solid elements. Exploiting the high continuity of spline functions and their properties, a proper out-of-plane stress state is recovered from a coarse displacement solution using a post-processing step based on the enforcement of equilibrium in strong form. Appealing results are obtained and the method is shown to be particularly Peffective on slender composite stacks with a large number of layers.
Service Chain (SC) Mapping with Multiple SC Instances in a Wide Area Network
Venue: arXiv cs.NI 2017
Year: 2017

Network Function Virtualization (NFV) aims to simplify deployment of network services by running Virtual Network Functions (VNFs) on commercial off-the-shelf servers. Service deployment involves placement of VNFs and in-sequence routing of traffic flows through VNFs comprising a Service Chain (SC). The joint VNF placement and traffic routing is usually referred as SC mapping. In a Wide Area Network (WAN), a situation may arise where several traffic flows, generated by many distributed node pairs, require the same SC, one single instance (or occurrence) of that SC might not be enough. SC mapping with multiple SC instances for the same SC turns out to be a very complex problem, since the sequential traversal of VNFs has to be maintained while accounting for traffic flows in various directions. Our study is the first to deal with SC mapping with multiple SC instances to minimize network resource consumption. Exact mathematical modeling of this problem results in a quadratic formulation. We propose a two-phase column-generation-based model and solution in order to get results over large network topologies within reasonable computational times. Using such an approach, we observe that an appropriate choice of only a small set of SC instances can lead to solution very close to the minimum bandwidth consumption.
Hierarchical Bayesian Data Fusion for Robotic Platform Navigation
Venue: arXiv cs.RO 2017
Year: 2017

Data fusion has become an active research topic in recent years. Growing computational performance has allowed the use of redundant sensors to measure a single phenomenon. While Bayesian fusion approaches are common in general applications, the computer vision field has largely relegated this approach. Most object following algorithms have gone towards pure machine learning fusion techniques that tend to lack flexibility. Consequently, a more general data fusion scheme is needed. Within this work, a hierarchical Bayesian fusion approach is proposed, which outperforms individual trackers by using redundant measurements. The adaptive framework is achieved by relying on each measurement's local statistics and a global softened majority voting. The proposed approach was validated in a simulated application and two robotic platforms.
Convolutional Neural Networks for Facial Expression Recognition
Venue: arXiv cs.CV 2017
Year: 2017

We have developed convolutional neural networks (CNN) for a facial expression recognition task. The goal is to classify each facial image into one of the seven facial emotion categories considered in this study. We trained CNN models with different depth using gray-scale images. We developed our models in Torch and exploited Graphics Processing Unit (GPU) computation in order to expedite the training process. In addition to the networks performing based on raw pixel data, we employed a hybrid feature strategy by which we trained a novel CNN model with the combination of raw pixel data and Histogram of Oriented Gradients (HOG) features. To reduce the overfitting of the models, we utilized different techniques including dropout and batch normalization in addition to L2 regularization. We applied cross validation to determine the optimal hyper-parameters and evaluated the performance of the developed models by looking at their training histories. We also present the visualization of different layers of a network to show what features of a face can be learned by CNN models.
A general private information retrieval scheme for MDS coded databases with colluding servers
Venue: arXiv cs.IT 2017
Year: 2017

The problem of private information retrieval gets renewed attentions in recent years due to its information-theoretic reformulation and applications in distributed storage systems. PIR capacity is the maximal number of bits privately retrieved per one bit of downloaded bit. The capacity has been fully solved for some degenerating cases. For a general case where the database is both coded and colluded, the exact capacity remains unknown. We build a general private information retrieval scheme for MDS coded databases with colluding servers. Our scheme achieves the rate $(1+R+R^2+\cdots+R^{M-1})$, where $R=1-\frac{{{N-T}\choose K}}{N\choose K}$. Compared to existing PIR schemes, our scheme performs better for a certain range of parameters and is suitable for any underlying MDS code used in the distributed storage system.
Simulation Theorems via Pseudorandom Properties
Venue: arXiv cs.CC 2017
Year: 2017

We generalize the deterministic simulation theorem of Raz and McKenzie [RM99], to any gadget which satisfies certain hitting property. We prove that inner-product and gap-Hamming satisfy this property, and as a corollary we obtain deterministic simulation theorem for these gadgets, where the gadget's input-size is logarithmic in the input-size of the outer function. This answers an open question posed by Göös, Pitassi and Watson [GPW15]. Our result also implies the previous results for the Indexing gadget, with better parameters than was previously known. A preliminary version of the results obtained in this work appeared in [CKL+17].
The Value of Sharing Intermittent Spectrum
Venue: arXiv cs.GT 2017
Year: 2017

Recent initiatives by regulatory agencies to increase spectrum resources available for broadband access include rules for sharing spectrum with high-priority incumbents. We study a model in which wireless Service Providers (SPs) charge for access to their own exclusive-use (licensed) band along with access to an additional shared band. The total, or delivered price in each band is the announced price plus a congestion cost, which depends on the load, or total users normalized by the bandwidth. The shared band is intermittently available with some probability, due to incumbent activity, and when unavailable, any traffic carried on that band must be shifted to licensed bands. The SPs then compete for quantity of users. We show that the value of the shared band depends on the relative sizes of the SPs: large SPs with more bandwidth are better able to absorb the variability caused by intermittency than smaller SPs. However, as the amount of shared spectrum increases, the large SPs may not make use of it. In that scenario shared spectrum creates more value than splitting it among the SPs for exclusive use. We also show that fixing the average amount of available shared bandwidth, increasing the reliability of the band is preferable to increasing the bandwidth.
Testing Symmetric Markov Chains from a Single Trajectory
Venue: arXiv cs.LG 2017
Year: 2017

Classical distribution testing assumes access to i.i.d. samples from the distribution that is being tested. We initiate the study of Markov chain testing, assuming access to a single trajectory of a Markov Chain. In particular, we observe a single trajectory X0,...,Xt,... of an unknown, symmetric, and finite state Markov Chain M. We do not control the starting state X0, and we cannot restart the chain. Given our single trajectory, the goal is to test whether M is identical to a model Markov Chain M0 , or far from it under an appropriate notion of difference. We propose a measure of difference between two Markov chains, motivated by the early work of Kazakos [Kaz78], which captures the scaling behavior of the total variation distance between trajectories sampled from the Markov chains as the length of these trajectories grows. We provide efficient testers and information-theoretic lower bounds for testing identity of symmetric Markov chains under our proposed measure of difference, which are tight up to logarithmic factors if the hitting times of the model chain M0 is O(n) in the size of the state space n.
Identify Critical Branches with Cascading Failure Chain Statistics and Hypertext-Induced Topic Search Algorithm
Venue: arXiv cs.SY 2017
Year: 2017

An effective way to suppress the cascading failure risk is the branch capacity upgrade, whose optimal decision making, however, may incur high computational burden. A practical way is to find out some critical branches as the candidates in advance. This paper proposes a simulation data oriented approach to identify the critical branches with higher importance in cascading failure propagation. First, a concept of cascading failure chain (CFC) is introduced and numerous samples of CFC are generated with an AC power flow based cascading failure simulator. Then, a directed weighted graph is constructed, whose edges denotes the severities of branch interactions. Third, the weighted hypertext-induced topic search (HITS) algorithm is used to rate and rank this graph's vertices,through which the critical branches can be identified accordingly. Validations on IEEE 118bus and RTS96 systems show that the proposed approach can identify critical branches whose capacity upgrades suppress cascading failure risk more greatly. Moreover, it is also shown that structural importance of a branch does not agree with its importance in cascading failure, which indicates the effectiveness of the proposed approach compared with structure vulnerabilities based identifying methods.
Proxy Templates for Inverse Compositional Photometric Bundle Adjustment
Venue: arXiv cs.CV 2017
Year: 2017

Recent advances in 3D vision have demonstrated the strengths of photometric bundle adjustment. By directly minimizing reprojected pixel errors, instead of geometric reprojection errors, such methods can achieve sub-pixel alignment accuracy in both high and low textured regions. Typically, these problems are solved using a forwards compositional Lucas-Kanade formulation parameterized by 6-DoF rigid camera poses and a depth per point in the structure. For large problems the most CPU-intensive component of the pipeline is the creation and factorization of the Hessian matrix at each iteration. For many warps, the inverse compositional formulation can offer significant speed-ups since the Hessian need only be inverted once. In this paper, we show that an ordinary inverse compositional formulation does not work for warps of this type of parameterization due to ill-conditioning of its partial derivatives. However, we show that it is possible to overcome this limitation by introducing the concept of a proxy template image. We show an order of magnitude improvement in speed, with little effect on quality, going from forwards to inverse compositional in our own photometric bundle adjustment method designed for object-centric structure from motion. This means less processing time for large systems or denser reconstructions under the same real-time constraints. We additionally show that this theory can be readily applied to existing methods by integrating it with the recently released Direct Sparse Odometry SLAM algorithm.
Efficiently Computing Real Roots of Sparse Polynomials
Venue: arXiv cs.SC 2017
Year: 2017

We propose an efficient algorithm to compute the real roots of a sparse polynomial $f\in\mathbb{R}[x]$ having $k$ non-zero real-valued coefficients. It is assumed that arbitrarily good approximations of the non-zero coefficients are given by means of a coefficient oracle. For a given positive integer $L$, our algorithm returns disjoint disks $Δ_{1},\ldots,Δ_{s}\subset\mathbb{C}$, with $s<2k$, centered at the real axis and of radius less than $2^{-L}$ together with positive integers $μ_{1},\ldots,μ_{s}$ such that each disk $Δ_{i}$ contains exactly $μ_{i}$ roots of $f$ counted with multiplicity. In addition, it is ensured that each real root of $f$ is contained in one of the disks. If $f$ has only simple real roots, our algorithm can also be used to isolate all real roots. The bit complexity of our algorithm is polynomial in $k$ and $\log n$, and near-linear in $L$ and $τ$, where $2^{-τ}$ and $2^τ$ constitute lower and upper bounds on the absolute values of the non-zero coefficients of $f$, and $n$ is the degree of $f$. For root isolation, the bit complexity is polynomial in $k$ and $\log n$, and near-linear in $τ$ and $\logσ^{-1}$, where $σ$ denotes the separation of the real roots.
New Two-Stage Automorphism Group Decoders for Cyclic Codes in the Erasure Channel
Venue: arXiv cs.IT 2017
Year: 2017

Recently, error correcting codes in the erasure channel have drawn great attention for various applications such as distributed storage systems and wireless sensor networks, but many of their decoding algorithms are not practical because they have higher decoding complexity and longer delay. Thus, the automorphism group decoder (AGD) for cyclic codes in the erasure channel was introduced, which has good erasure decoding performance with low decoding complexity. In this paper, we propose new two-stage AGDs (TS-AGDs) for cyclic codes in the erasure channel by modifying the parity check matrix and introducing the preprocessing stage to the AGD scheme. The proposed TS-AGD has been analyzed for the perfect codes, BCH codes, and maximum distance separable (MDS) codes. Through numerical analysis, it is shown that the proposed decoding algorithm has good erasure decoding performance with lower decoding complexity and delay than the conventional AGD. For some cyclic codes, it is shown that the proposed TS-AGD achieves the perfect decoding in the erasure channel, that is, the same decoding performance as the maximum likelihood (ML) decoder. For MDS codes, TS-AGDs with the expanded parity check matrix and the submatrix inversion are also proposed and analyzed.
Group-based Sparse Representation for Image Compressive Sensing Reconstruction with Non-Convex Regularization
Venue: arXiv cs.CV 2017
Year: 2017

Patch-based sparse representation modeling has shown great potential in image compressive sensing (CS) reconstruction. However, this model usually suffers from some limits, such as dictionary learning with great computational complexity, neglecting the relationship among similar patches. In this paper, a group-based sparse representation method with non-convex regularization (GSR-NCR) for image CS reconstruction is proposed. In GSR-NCR, the local sparsity and nonlocal self-similarity of images is simultaneously considered in a unified framework. Different from the previous methods based on sparsity-promoting convex regularization, we extend the non-convex weighted Lp (0 < p < 1) penalty function on group sparse coefficients of the data matrix, rather than conventional L1-based regularization. To reduce the computational complexity, instead of learning the dictionary with a high computational complexity from natural images, we learn the principle component analysis (PCA) based dictionary for each group. Moreover, to make the proposed scheme tractable and robust, we have developed an efficient iterative shrinkage/thresholding algorithm to solve the non-convex optimization problem. Experimental results demonstrate that the proposed method outperforms many state-of-the-art techniques for image CS reconstruction.
Energy Efficient User Association and Power Allocation in Millimeter Wave Based Ultra Dense Networks with Energy Harvesting Base Stations
Venue: arXiv cs.IT 2017
Year: 2017

Millimeter wave (mmWave) communication technologies have recently emerged as an attractive solution to meet the exponentially increasing demand on mobile data traffic. Moreover, ultra dense networks (UDNs) combined with mmWave technology are expected to increase both energy efficiency and spectral efficiency. In this paper, user association and power allocation in mmWave based UDNs is considered with attention to load balance constraints, energy harvesting by base stations, user quality of service requirements, energy efficiency, and cross-tier interference limits. The joint user association and power optimization problem is modeled as a mixed-integer programming problem, which is then transformed into a convex optimization problem by relaxing the user association indicator and solved by Lagrangian dual decomposition. An iterative gradient user association and power allocation algorithm is proposed and shown to converge rapidly to an optimal point. The complexity of the proposed algorithm is analyzed and the effectiveness of the proposed scheme compared with existing methods is verified by simulations.
$H(X)$ vs. $H(f(X))$
Venue: arXiv cs.IT 2017
Year: 2017

It is well known that the entropy $H(X)$ of a finite random variable is always greater or equal to the entropy $H(f(X))$ of a function $f$ of $X$, with equality if and only if $f$ is one-to-one. In this paper, we give tights bounds on $H(f(X))$ when the function $f$ is not one-to-one, and we illustrate a few scenarios where this matters. As an intermediate step towards our main result, we prove a lower bound on the entropy of a probability distribution, when only a bound on the ratio between the maximum and the minimum probability is known. Our lower bound improves previous results in the literature, and it could find applications outside the present scenario.
Evaluating and Modelling Hanabi-Playing Agents
Venue: arXiv cs.AI 2017
Year: 2017

Agent modelling involves considering how other agents will behave, in order to influence your own actions. In this paper, we explore the use of agent modelling in the hidden-information, collaborative card game Hanabi. We implement a number of rule-based agents, both from the literature and of our own devising, in addition to an Information Set Monte Carlo Tree Search (IS-MCTS) agent. We observe poor results from IS-MCTS, so construct a new, predictor version that uses a model of the agents with which it is paired. We observe a significant improvement in game-playing strength from this agent in comparison to IS-MCTS, resulting from its consideration of what the other agents in a game would do. In addition, we create a flawed rule-based agent to highlight the predictor's capabilities with such an agent.
Rethinking $(k,\ell)$-anonymity in social graphs: $(k,\ell)$-adjacency anonymity and $(k,\ell)$-(adjacency) anonymous transformations
Venue: arXiv cs.SI 2017
Year: 2017

This paper treats the privacy-preserving publication of social graphs in the presence of active adversaries, that is, adversaries with the ability to introduce sybil nodes in the graph prior to publication and leverage them to create unique fingerprints for a set of victim nodes and re-identify them after publication. Stemming from the notion of $(k,\ell)$-anonymity, we introduce $(k,\ell)$-anonymous transformations, characterising graph perturbation methods that ensure protection from active adversaries levaraging up to $\ell$ sybil nodes. Additionally, we introduce a new privacy property: $(k,\ell)$-adjacency anonymity, which relaxes the assumption made by $(k,\ell)$-anonymity that adversaries can control all distances between sybil nodes and the rest of the nodes in the graph. The new privacy property is in turn the basis for a new type of graph perturbation: $(k,\ell)$-adjacency anonymous transformations. We propose algorithms for obtaining $(k,1)$-adjacency anonymous transformations for arbitrary values of $k$, as well as $(2,\ell)$-adjacency anonymous transformations for small values of $\ell$.