OpenRaiser/Intern-Atlas huggingface dataset:
The linear nature of pseudowords
Venue: arXiv cs.FL 2017
Year: 2017

Given a pseudoword over suitable pseudovarieties, we associate to it a labeled linear order determined by the factorizations of the pseudoword. We show that, in the case of the pseudovariety of aperiodic finite semigroups, the pseudoword can be recovered from the labeled linear order.
Parallelization of Path Planning Algorithms for AUVs Concepts, Opportunities, and Program-Technical Implementation
Venue: arXiv cs.RO 2017
Year: 2017

Modern autonomous underwater vehicles (AUVs) have advanced sensing capabilities including sonar, cameras, acoustic communication, and diverse bio-sensors. Instead of just sensing its environment and storing the data for post-Mission inspection, an AUV could use the collected information to gain an understanding of its environment, and based on this understanding autonomously adapt its behavior to enhance the overall effectiveness of its mission. Many such tasks are highly computation intensive. This paper presents the results of a case study that illustrates the effectiveness of an energy-aware, many-core computing architecture to perform on-board path planning within a batteryoperated AUV. A previously published path planning algorithm was ported onto the SCC, an experimental 48 core single-chip system developed by Intel. The performance, power, and energy consumption of the application were measured for different numbers of cores and other system parameters. This case study shows that computation intensive tasks can be executed within an AUV that relies mainly on battery power. Future plans include the deployment and testing of an SCC system within a Teledyne Webb Research Slocum glider.
Guidance of an Autonomous Underwater Vehicle in Special Situations
Venue: arXiv cs.RO 2017
Year: 2017

This article describes a guidance system of the autonomous underwater vehicle "DeepC" [1] in Special situations. A special situation occurs when one or more objects interfere with the planned route of a mission. The possible reactions are evasion or identification of the objects. The paper presents these two tasks in overview. The special demands challenges of the underwater environment, computer parameters, sensors and the maneuverability of the vehicle are considered in the selection and development of the required strategies. Such challenges include the sea current, maneuver in the 3-D space and the limited perceptive faculty of the sonar.
A Critical Improvement On Open Shop Scheduling Algorithm For Routing In Interconnection Networks
Venue: arXiv cs.NI 2017
Year: 2017

In the past years, Interconnection Networks have been used quite often and especially in applications where parallelization is critical. Message packets transmitted through such networks can be interrupted using buffers in order to maximize network usage and minimize the time required for all messages to reach their destination. However, preempting a packet will result in topology reconfiguration and consequently in time cost. The problem of scheduling message packets through such a network is referred to as PBS and is known to be NP-Hard. In this paper we have improved, critically, variations of polynomially solvable instances of Open Shop to approximate PBS. We have combined these variations and called the induced algorithm IHSA, Improved Hybridic Scheduling Algorithm. We ran experiments to establish the efficiency of IHSA and found that in all datasets used it produces schedules very close to the optimal. In addition, we tested IHSA with datasets that follow non-uniform distributions and provided statistical data which illustrates better its performance.To further establish the efficiency of IHSA we ran tests to compare it to SGA, another algorithm which when tested in the past has yielded excellent results.
DepQBF 6.0: A Search-Based QBF Solver Beyond Traditional QCDCL
Venue: arXiv cs.LO 2017
Year: 2017

We present the latest major release version 6.0 of the quantified Boolean formula (QBF) solver DepQBF, which is based on QCDCL. QCDCL is an extension of the conflict-driven clause learning (CDCL) paradigm implemented in state of the art propositional satisfiability (SAT) solvers. The Q-resolution calculus (QRES) is a QBF proof system which underlies QCDCL. QCDCL solvers can produce QRES proofs of QBFs in prenex conjunctive normal form (PCNF) as a byproduct of the solving process. In contrast to traditional QCDCL based on QRES, DepQBF 6.0 implements a variant of QCDCL which is based on a generalization of QRES. This generalization is due to a set of additional axioms and leaves the original Q-resolution rules unchanged. The generalization of QRES enables QCDCL to potentially produce exponentially shorter proofs than the traditional variant. We present an overview of the features implemented in DepQBF and report on experimental results which demonstrate the effectiveness of generalized QRES in QCDCL.
Independent Set Size Approximation in Graph Streams
Venue: arXiv cs.DS 2017
Year: 2017

We study the problem of estimating the size of independent sets in a graph $G$ defined by a stream of edges. Our approach relies on the Caro-Wei bound, which expresses the desired quantity in terms of a sum over nodes of the reciprocal of their degrees, denoted by $β(G)$. Our results show that $β(G)$ can be approximated accurately, based on a provided lower bound on $β$. Stronger results are possible when the edges are promised to arrive grouped by an incident node. In this setting, we obtain a value that is at most a logarithmic factor below the true value of $β$ and no more than the true independent set size. To justify the form of this bound, we also show an $Ω(n/β)$ lower bound on any algorithm that approximates $β$ up to a constant factor.
System and source identification from operational vehicle responses: A novel modal model accounting for the track-vehicle interaction
Venue: arXiv cs.SY 2017
Year: 2017

Operational Modal Analysis (OMA) is a powerful tool, widely used in the fields of structural identification and health monitoring, and certainly eligible for identifying the real in-operation behaviour of vehicle systems. Several attempts can be found in the literature, for which the usage of algorithms based on the classical OMA formulation has been strained for the identification of passenger cars and industrial trucks. The interest is mainly focused on the assessment of suspension behaviour and, thus, on the identification of the so-called vehicle rigid body modes. But issues arise when the operational identification of a vehicle system is performed, basically related to the nature of the loads induced by the roughness of rolling profiles. The forces exerted on the wheels, in fact, depending on their location, are affected by time and/or spatial correlation, and, more over, do not fit the form of white noise sequences. Thus, the nature of the excitation strongly violate the hypotheses on which the formulation of classical OMA modal model relies, leading to pronounced modelling errors and, in turn, to poorly estimated modal parameters. In this paper, we develop a specialised modal model, that we refer to as the Track-Vehicle Interaction Modal Model, able to incorporate the character of road/rail inputs acting on vehicles during operation. Since in this novel modal model the relationship between vehicle system outputs and modal parameters is given explicitly, the development of new specific curve fitting techniques, in the time-lag or frequency domain, is now possible, making available simple and cost-effective tools for vehicle operational identification. More over, a second, but not less important outcome of the proposed modal model is the usage of the resulting techniques for the indirect characterisation of rolling surface roughness, that can be used to improve comfort and safety.
On Fienup Methods for Regularized Phase Retrieval
Venue: arXiv cs.IT 2017
Year: 2017

Alternating minimization, or Fienup methods, have a long history in phase retrieval. We provide new insights related to the empirical and theoretical analysis of these algorithms when used with Fourier measurements and combined with convex priors. In particular, we show that Fienup methods can be viewed as performing alternating minimization on a regularized nonconvex least-squares problem with respect to amplitude measurements. We then prove that under mild additional structural assumptions on the prior (semi-algebraicity), the sequence of signal estimates has a smooth convergent behaviour towards a critical point of the nonconvex regularized least-squares objective. Finally, we propose an extension to Fienup techniques, based on a projected gradient descent interpretation and acceleration using inertial terms. We demonstrate experimentally that this modification combined with an $\ell_1$ prior constitutes a competitive approach for sparse phase retrieval.
Clustering in Discrete Path Planning for Approximating Minimum Length Paths
Venue: arXiv cs.RO 2017
Year: 2017

In this paper we consider discrete robot path planning problems on metric graphs. We propose a clustering method, Gamma-Clustering for the planning graph that significantly reduces the number of feasible solutions, yet retains a solution within a constant factor of the optimal. By increasing the input parameter Gamma, the constant factor can be decreased, but with less reduction in the search space. We provide a simple polynomial- time algorithm for finding optimal Gamma-Clusters, and show that for a given Gamma, this optimal is unique. We demonstrate the effectiveness of the clustering method on traveling salesman instances, showing that for many instances we obtain significant reductions in computation time with little to no reduction in solution quality.
Depth Separation for Neural Networks
Venue: arXiv cs.LG 2017
Year: 2017

Let $f:\mathbb{S}^{d-1}\times \mathbb{S}^{d-1}\to\mathbb{S}$ be a function of the form $f(\mathbf{x},\mathbf{x}') = g(\langle\mathbf{x},\mathbf{x}'\rangle)$ for $g:[-1,1]\to \mathbb{R}$. We give a simple proof that shows that poly-size depth two neural networks with (exponentially) bounded weights cannot approximate $f$ whenever $g$ cannot be approximated by a low degree polynomial. Moreover, for many $g$'s, such as $g(x)=\sin(πd^3x)$, the number of neurons must be $2^{Ω\left(d\log(d)\right)}$. Furthermore, the result holds w.r.t.\ the uniform distribution on $\mathbb{S}^{d-1}\times \mathbb{S}^{d-1}$. As many functions of the above form can be well approximated by poly-size depth three networks with poly-bounded weights, this establishes a separation between depth two and depth three networks w.r.t.\ the uniform distribution on $\mathbb{S}^{d-1}\times \mathbb{S}^{d-1}$.
Don't Fear the Reaper: Refuting Bostrom's Superintelligence Argument
Venue: arXiv cs.AI 2017
Year: 2017

In recent years prominent intellectuals have raised ethical concerns about the consequences of artificial intelligence. One concern is that an autonomous agent might modify itself to become "superintelligent" and, in supremely effective pursuit of poorly specified goals, destroy all of humanity. This paper considers and rejects the possibility of this outcome. We argue that this scenario depends on an agent's ability to rapidly improve its ability to predict its environment through self-modification. Using a Bayesian model of a reasoning agent, we show that there are important limitations to how an agent may improve its predictive ability through self-modification alone. We conclude that concern about this artificial intelligence outcome is misplaced and better directed at policy questions around data access and storage.
eXpose: A Character-Level Convolutional Neural Network with Embeddings For Detecting Malicious URLs, File Paths and Registry Keys
Venue: arXiv cs.CR 2017
Year: 2017

For years security machine learning research has promised to obviate the need for signature based detection by automatically learning to detect indicators of attack. Unfortunately, this vision hasn't come to fruition: in fact, developing and maintaining today's security machine learning systems can require engineering resources that are comparable to that of signature-based detection systems, due in part to the need to develop and continuously tune the "features" these machine learning systems look at as attacks evolve. Deep learning, a subfield of machine learning, promises to change this by operating on raw input signals and automating the process of feature design and extraction. In this paper we propose the eXpose neural network, which uses a deep learning approach we have developed to take generic, raw short character strings as input (a common case for security inputs, which include artifacts like potentially malicious URLs, file paths, named pipes, named mutexes, and registry keys), and learns to simultaneously extract features and classify using character-level embeddings and convolutional neural network. In addition to completely automating the feature design and extraction process, eXpose outperforms manual feature extraction based baselines on all of the intrusion detection problems we tested it on, yielding a 5%-10% detection rate gain at 0.1% false positive rate compared to these baselines.
Learning Vector Autoregressive Models with Latent Processes
Venue: arXiv cs.LG 2017
Year: 2017

We study the problem of learning the support of transition matrix between random processes in a Vector Autoregressive (VAR) model from samples when a subset of the processes are latent. It is well known that ignoring the effect of the latent processes may lead to very different estimates of the influences among observed processes, and we are concerned with identifying the influences among the observed processes, those between the latent ones, and those from the latent to the observed ones. We show that the support of transition matrix among the observed processes and lengths of all latent paths between any two observed processes can be identified successfully under some conditions on the VAR model. From the lengths of latent paths, we reconstruct the latent subgraph (representing the influences among the latent processes) with a minimum number of variables uniquely if its topology is a directed tree. Furthermore, we propose an algorithm that finds all possible minimal latent graphs under some conditions on the lengths of latent paths. Our results apply to both non-Gaussian and Gaussian cases, and experimental results on various synthetic and real-world datasets validate our theoretical results.
Depth Creates No Bad Local Minima
Venue: arXiv cs.LG 2017
Year: 2017

In deep learning, \textit{depth}, as well as \textit{nonlinearity}, create non-convex loss surfaces. Then, does depth alone create bad local minima? In this paper, we prove that without nonlinearity, depth alone does not create bad local minima, although it induces non-convex loss surface. Using this insight, we greatly simplify a recently proposed proof to show that all of the local minima of feedforward deep linear neural networks are global minima. Our theoretical results generalize previous results with fewer assumptions, and this analysis provides a method to show similar results beyond square loss in deep linear models.
Statistical Information Fusion for Multiple-View Sensor Data in Multi-Object Tracking
Venue: arXiv cs.SY 2017
Year: 2017

This paper presents a novel statistical information fusion method to integrate multiple-view sensor data in multi-object tracking applications. The proposed method overcomes the drawbacks of the commonly used Generalized Covariance Intersection method, which considers constant weights allocated for sensors. Our method is based on enhancing the Generalized Covariance Intersection with adaptive weights that are automatically tuned based on the amount of information carried by the measurements from each sensor. To quantify information content, Cauchy-Schwarz divergence is used. Another distinguished characteristic of our method lies in the usage of the Labeled Multi-Bernoulli filter for multi-object tracking, in which the weight of each sensor can be separately adapted for each Bernoulli component of the filter. The results of numerical experiments show that our proposed method can successfully integrate information provided by multiple sensors with different fields of view. In such scenarios, our method significantly outperforms the state of art in terms of inclusion of all existing objects and tracking accuracy.
Towards Deeper Understanding of Variational Autoencoding Models
Venue: arXiv cs.LG 2017
Year: 2017

We propose a new family of optimization criteria for variational auto-encoding models, generalizing the standard evidence lower bound. We provide conditions under which they recover the data distribution and learn latent features, and formally show that common issues such as blurry samples and uninformative latent features arise when these conditions are not met. Based on these new insights, we propose a new sequential VAE model that can generate sharp samples on the LSUN image dataset based on pixel-wise reconstruction loss, and propose an optimization criterion that encourages unsupervised learning of informative latent features.
Optimal Categorical Attribute Transformation for Granularity Change in Relational Databases for Binary Decision Problems in Educational Data Mining
Venue: arXiv cs.AI 2017
Year: 2017

This paper presents an approach for transforming data granularity in hierarchical databases for binary decision problems by applying regression to categorical attributes at the lower grain levels. Attributes from a lower hierarchy entity in the relational database have their information content optimized through regression on the categories histogram trained on a small exclusive labelled sample, instead of the usual mode category of the distribution. The paper validates the approach on a binary decision task for assessing the quality of secondary schools focusing on how logistic regression transforms the students and teachers attributes into school attributes. Experiments were carried out on Brazilian schools public datasets via 10-fold cross-validation comparison of the ranking score produced also by logistic regression. The proposed approach achieved higher performance than the usual distribution mode transformation and equal to the expert weighing approach measured by the maximum Kolmogorov-Smirnov distance and the area under the ROC curve at 0.01 significance level.
Jamming-Resistant Receivers for the Massive MIMO Uplink
Venue: arXiv cs.IT 2017
Year: 2017

We design a jamming-resistant receiver scheme to enhance the robustness of a massive MIMO uplink system against jamming. We assume that a jammer attacks the system both in the pilot and data transmission phases. The key feature of the proposed scheme is that, in the pilot phase, we estimate not only the legitimate channel, but also the jamming channel by exploiting a purposely unused pilot sequence. The jamming channel estimate is used to constructed linear receive filters that reject the impact of the jamming signal. The performance of the proposed scheme is analytically evaluated using asymptotic properties of massive MIMO. The optimal regularized zero-forcing receiver and the optimal power allocation are also studied. Numerical results are provided to verify our analysis and show that the proposed scheme greatly improves the achievable rates, as compared to conventional receivers. Interestingly, the proposed scheme works particularly well under strong jamming attacks, since the improved estimate of the jamming channel outweighs the extra jamming power.
Distributed Temperature Control via Geothermal Heat Pump Systems in Energy Efficient Buildings
Venue: arXiv cs.SY 2017
Year: 2017

Geothermal Heat Pump (GHP) systems are heating and cooling systems that use the ground as the temperature exchange medium. GHP systems are becoming more and more popular in recent years due to their high efficiency. Conventional control schemes of GHP systems are mainly designed for buildings with a single thermal zone. For large buildings with multiple thermal zones, those control schemes either lose efficiency or become costly to implement requiring a lot of real-time measurement, communication and computation. In this paper, we focus on developing energy efficient control schemes for GHP systems in buildings with multiple zones. We present a thermal dynamic model of a building equipped with a GHP system for floor heating/cooling and formulate the GHP system control problem as a resource allocation problem with the objective to maximize user comfort in different zones and to minimize the building energy consumption. We then propose real-time distributed algorithms to solve the control problem. Our distributed multi-zone control algorithms are scalable and do not need to measure or predict any exogenous disturbances such as the outdoor temperature and indoor heat gains. Thus, it is easy to implement them in practice. Simulation results demonstrate the effectiveness of the proposed control schemes.
Probabilistic Perspectives on Collecting Human Uncertainty in Predictive Data Mining
Venue: arXiv cs.HC 2017
Year: 2017

In many areas of data mining, data is collected from humans beings. In this contribution, we ask the question of how people actually respond to ordinal scales. The main problem observed is that users tend to be volatile in their choices, i.e. complex cognitions do not always lead to the same decisions, but to distributions of possible decision outputs. This human uncertainty may sometimes have quite an impact on common data mining approaches and thus, the question of effective modelling this so called human uncertainty emerges naturally. Our contribution introduces two different approaches for modelling the human uncertainty of user responses. In doing so, we develop techniques in order to measure this uncertainty at the level of user inputs as well as the level of user cognition. With support of comprehensive user experiments and large-scale simulations, we systematically compare both methodologies along with their implications for personalisation approaches. Our findings demonstrate that significant amounts of users do submit something completely different (action) than they really have in mind (cognition). Moreover, we demonstrate that statistically sound evidence with respect to algorithm assessment becomes quite hard to realise, especially when explicit rankings shall be built.
Computers from plants we never made. Speculations
Venue: arXiv cs.ET 2017
Year: 2017

We discuss possible designs and prototypes of computing systems that could be based on morphological development of roots, interaction of roots, and analog electrical computation with plants, and plant-derived electronic components. In morphological plant processors data are represented by initial configuration of roots and configurations of sources of attractants and repellents; results of computation are represented by topology of the roots' network. Computation is implemented by the roots following gradients of attractants and repellents, as well as interacting with each other. Problems solvable by plant roots, in principle, include shortest-path, minimum spanning tree, Voronoi diagram, $α$-shapes, convex subdivision of concave polygons. Electrical properties of plants can be modified by loading the plants with functional nanoparticles or coating parts of plants of conductive polymers. Thus, we are in position to make living variable resistors, capacitors, operational amplifiers, multipliers, potentiometers and fixed-function generators. The electrically modified plants can implement summation, integration with respect to time, inversion, multiplication, exponentiation, logarithm, division. Mathematical and engineering problems to be solved can be represented in plant root networks of resistive or reaction elements. Developments in plant-based computing architectures will trigger emergence of a unique community of biologists, electronic engineering and computer scientists working together to produce living electronic devices which future green computers will be made of.