OpenRaiser/Intern-Atlas huggingface dataset:
The Hardest Halfspace
Venue: arXiv cs.CC 2019
Year: 2019

We study the approximation of halfspaces $h:\{0,1\}^n\to\{0,1\}$ in the infinity norm by polynomials and rational functions of any given degree. Our main result is an explicit construction of the "hardest" halfspace, for which we prove polynomial and rational approximation lower bounds that match the trivial upper bounds achievable for all halfspaces. This completes a lengthy line of work started by Myhill and Kautz (1961). As an application, we construct a communication problem that achieves essentially the largest possible separation, of $O(n)$ versus $2^{-Ω(n)},$ between the sign-rank and discrepancy. Equivalently, our problem exhibits a gap of $\log n$ versus $Ω(n)$ between the communication complexity with unbounded versus weakly unbounded error, improving quadratically on previous constructions and completing a line of work started by Babai, Frankl, and Simon (FOCS 1986). Our results further generalize to the $k$-party number-on-the-forehead model, where we obtain an explicit separation of $\log n$ versus $Ω(n/4^{n})$ for communication with unbounded versus weakly unbounded error. This gap is a quadratic improvement on previous work and matches the state of the art for number-on-the-forehead lower bounds.
Mobile Information Retrieval
Venue: arXiv cs.IR 2019
Year: 2019

Mobile Information Retrieval (Mobile IR) is a relatively recent branch of Information Retrieval (IR) that is concerned with enabling users to carry out, using a mobile device, all the classical IR operations that they were used to carry out on a desktop. This includes finding content available on local repositories or on the web in response to a user query, interacting with the system in an explicit or implicit way, reformulate the query and/or visualise the content of the retrieved documents, as well as providing relevance judgments to improve the retrieval process. This book is structured as follows. Chapter 2 provides a very brief overview of IR and of Mobile IR, briefly outlining what in Mobile IR is different from IR. Chapter 3 provides the foundations of Mobile IR, looking at the characteristics of mobile devices and what they bring to IR, but also looking at how the concept of relevance changed from standard IR to Mobile IR. Chapter 4 presents an overview of the document collections that are searchable by a Mobile IR system, and that are somehow different from classical IR ones; available for experimentation, including collections of data that have become complementary to Mobile IR. Similarly, Chapter 5 reviews mobile information needs studies and users log analysis. Chapter 6 reviews studies aimed at adapting and improving the users interface to the needs of Mobile IR. Chapter 7, instead, reviews work on context awareness, which studies the many aspects of the user context that Mobile IR employs. Chapter 8 reviews some of evaluation work done in Mobile IR, highlighting the distinctions with classical IR from the perspectives of two main IR evaluation methodologies: users studies and test collections. Finally, Chapter 9 reports the conclusions of this review, highlighting briefly some trends in Mobile IR that we believe will drive research in the next few years.
Do We Preach What We Practice? Investigating the Practical Relevance of Requirements Engineering Syllabi - The IREB Case
Venue: arXiv cs.SE 2019
Year: 2019

Nowadays, there exist a plethora of different educational syllabi for Requirements Engineering (RE), all aiming at incorporating practically relevant educational units (EUs). Many of these syllabi are based, in one way or the other, on the syllabi provided by the International Requirements Engineering Board (IREB), a non-profit organisation devoted to standardised certification programs for RE. IREB syllabi are developed by RE experts and are, thus, based on the assumption that they address topics of practical relevance. However, little is known about to what extent practitioners actually perceive those contents as useful. We have started a study to investigate the relevance of the EUs included in the IREB Foundation Level certification programme. In a first phase reported in this paper, we have surveyed practitioners mainly from DACH countries (Germany, Austria and Switzerland) participating in the IREB certification. Later phases will widen the scope both by including other countries and by not requiring IREB-certified participants. The results shall foster a critical reflection on the practical relevance of EUs built upon the de-facto standard syllabus of IREB.
Inferring the strength of social ties: a community-driven approach
Venue: arXiv cs.DS 2019
Year: 2019

Online social networks are growing and becoming denser. The social connections of a given person may have very high variability: from close friends and relatives to acquaintances to people who hardly know. Inferring the strength of social ties is an important ingredient for modeling the interaction of users in a network and understanding their behavior. Furthermore, the problem has applications in computational social science, viral marketing, and people recommendation. In this paper we study the problem of inferring the strength of social ties in a given network. Our work is motivated by a recent approach [27], which leverages the strong triadic closure (STC) principle, a hypothesis rooted in social psychology [13]. To guide our inference process, in addition to the network structure, we also consider as input a collection of tight communities. Those are sets of vertices that we expect to be connected via strong ties. Such communities appear in different situations, e.g., when being part of a community implies a strong connection to one of the existing members. We consider two related problem formalizations that reflect the assumptions of our setting: small number of STC violations and strong-tie connectivity in the input communities. We show that both problem formulations are NP-hard. We also show that one problem formulation is hard to approximate, while for the second we develop an algorithm with approximation guarantee. We validate the proposed method on real-world datasets by comparing with baselines that optimize STC violations and community connectivity separately.
Dynamic hierarchies in temporal directed networks
Venue: arXiv cs.DS 2019
Year: 2019

The outcome of interactions in many real-world systems can be often explained by a hierarchy between the participants. Discovering hierarchy from a given directed network can be formulated as follows: partition vertices into levels such that, ideally, there are only forward edges, that is, edges from upper levels to lower levels. In practice, the ideal case is impossible, so instead we minimize some penalty function on the backward edges. One practical option for such a penalty is agony, where the penalty depends on the severity of the violation. In this paper we extend the definition of agony to temporal networks. In this setup we are given a directed network with time stamped edges, and we allow the rank assignment to vary over time. We propose 2 strategies for controlling the variation of individual ranks. In our first variant, we penalize the fluctuation of the rankings over time by adding a penalty directly to the optimization function. In our second variant we allow the rank change at most once. We show that the first variant can be solved exactly in polynomial time while the second variant is NP-hard, and in fact inapproximable. However, we develop an iterative method, where we first fix the change point and optimize the ranks, and then fix the ranks and optimize the change points, and reiterate until convergence. We show empirically that the algorithms are reasonably fast in practice, and that the obtained rankings are sensible.
Situational Grounding within Multimodal Simulations
Venue: arXiv cs.AI 2019
Year: 2019

In this paper, we argue that simulation platforms enable a novel type of embodied spatial reasoning, one facilitated by a formal model of object and event semantics that renders the continuous quantitative search space of an open-world, real-time environment tractable. We provide examples for how a semantically-informed AI system can exploit the precise, numerical information provided by a game engine to perform qualitative reasoning about objects and events, facilitate learning novel concepts from data, and communicate with a human to improve its models and demonstrate its understanding. We argue that simulation environments, and game engines in particular, bring together many different notions of "simulation" and many different technologies to provide a highly-effective platform for developing both AI systems and tools to experiment in both machine and human intelligence.
Real-time Communication between Robot PLC and PC over Ethernet-based Protocols
Venue: arXiv cs.NI 2019
Year: 2019

The article provides a comparative analysis of four communication protocols between Omron PLC and PC for their use in real-time control of an industrial robot. The need for real-time communication appears when the robot control system is located on an external PC. The subject of the study is the FINS, CIP, UDP, and OPC protocols. The physical medium for data transmission is Fast Ethernet 100 Mbit/s. The average time characteristics of reading, writing, and write/read cycle for each protocol are given. The evaluation of the applicability of protocols for real-time robot control and the convenience of their use is also given.
Semi-supervised learning via Feedforward-Designed Convolutional Neural Networks
Venue: arXiv cs.CV 2019
Year: 2019

A semi-supervised learning framework using the feedforward-designed convolutional neural networks (FF-CNNs) is proposed for image classification in this work. One unique property of FF-CNNs is that no backpropagation is used in model parameters determination. Since unlabeled data may not always enhance semi-supervised learning, we define an effective quality score and use it to select a subset of unlabeled data in the training process. We conduct experiments on the MNIST, SVHN, and CIFAR-10 datasets, and show that the proposed semi-supervised FF-CNN solution outperforms the CNN trained by backpropagation (BP-CNN) when the amount of labeled data is reduced. Furthermore, we develop an ensemble system that combines the output decision vectors of different semi-supervised FF-CNNs to boost classification accuracy. The ensemble systems can achieve further performance gains on all three benchmarking datasets.
Scheduling and Trade-off Analysis for Multi-Source Multi-Processor Systems with Divisible Loads
Venue: arXiv cs.DC 2019
Year: 2019

The main goal of parallel processing is to provide users with performance that is much better than that of single processor systems. The execution of jobs is scheduled, which requires certain resources in order to meet certain criteria. Divisible load is a special but widely used type of data which can be divided into arbitrary sizes and independently processed in parallel. It can be used in applications which are processing a great amount of similar data units.
Robust Matrix Completion State Estimation in Distribution Systems
Venue: arXiv cs.LG 2019
Year: 2019

Due to the insufficient measurements in the distribution system state estimation (DSSE), full observability and redundant measurements are difficult to achieve without using the pseudo measurements. The matrix completion state estimation (MCSE) combines the matrix completion and power system model to estimate voltage by exploring the low-rank characteristics of the matrix. This paper proposes a robust matrix completion state estimation (RMCSE) to estimate the voltage in a distribution system under a low-observability condition. Tradition state estimation weighted least squares (WLS) method requires full observability to calculate the states and needs redundant measurements to proceed a bad data detection. The proposed method improves the robustness of the MCSE to bad data by minimizing the rank of the matrix and measurements residual with different weights. It can estimate the system state in a low-observability system and has robust estimates without the bad data detection process in the face of multiple bad data. The method is numerically evaluated on the IEEE 33-node radial distribution system. The estimation performance and robustness of RMCSE are compared with the WLS with the largest normalized residual bad data identification (WLS-LNR), and the MCSE.
KISS methodologies for network management and anomaly detection
Venue: arXiv cs.NI 2019
Year: 2019

Current networks are increasingly growing in size and complexity and so is the amount of monitoring data that they produce. As a result, network monitoring systems have to scale accordingly. As a possible approach, horizontal scalability can be achieved by large data centralization systems based on clusters, which are expensive and difficult to deploy in a real production scenario. In this paper we propose and evaluate a series of methodologies, deployed in real industrial production environments, for network monitoring and management, from the architecture design to the visualization system as well as for the anomaly detection methodologies, that intend to squeeze the vertical resources and overcome the difficulties of data collection and centralization.
Blind Signal Classification Analysis and Impact on User Scheduling and Power Allocation in Nonorthogonal Multiple Access
Venue: arXiv cs.IT 2019
Year: 2019

For a massive number of devices, nonorthogonal multiple access (NOMA) has been recognized as a promising technology for improving the spectral efficiency compared to orthogonal multiple access (OMA). However, it is difficult for a base station (BS) to provide all of the information about NOMA signals via a high layer owing to signaling overhead concerns. This paper studies blind signal classification, which determines whether or not the received NOMA signal requires successive interference cancellation (SIC) without a priori signal information. In this paper, two types of blind signal classification errors are analyzed: 1) the signal is classified as one that does not require SIC on the SIC user side and 2) the signal is classified as one for which SIC is necessary on the non-SIC user side. In addition, we formulate the joint optimization problem for user scheduling and power allocation, which maximizes the sum-rate gain of NOMA over OMA with constraints on the maximum classification error probability and minimum data rate. The proposed algorithm iteratively finds solutions for user scheduling and power allocation. Simulation results show that the proposed scheme outperforms existing user scheduling methods.
Space Navigator: a Tool for the Optimization of Collision Avoidance Maneuvers
Venue: arXiv cs.SY 2019
Year: 2019

The number of space objects will grow several times in a few years due to the planned launches of constellations of thousands microsatellites. It leads to a significant increase in the threat of satellite collisions. Spacecraft must undertake collision avoidance maneuvers to mitigate the risk. According to publicly available information, conjunction events are now manually handled by operators on the Earth. The manual maneuver planning requires qualified personnel and will be impractical for constellations of thousands satellites. In this paper we propose a new modular autonomous collision avoidance system called "Space Navigator". It is based on a novel maneuver optimization approach that combines domain knowledge with Reinforcement Learning methods.
Firefighting on Trees
Venue: arXiv cs.DS 2019
Year: 2019

In the Firefighter problem, introduced by Hartnell in 1995, a fire spreads through a graph while a player chooses which vertices to protect in order to contain it. In this paper, we focus on the case of trees and we consider as well the Fractional Firefighter game where the amount of protection allocated to a vertex lies between 0 and 1. While most of the work in this area deals with a constant amount of firefighters available at each turn, we consider three research questions which arise when including the sequence of firefighters as part of the instance. We first introduce the online version of both Firefighter and Fractional Firefighter, in which the number of firefighters available at each turn is revealed over time. We show that a greedy algorithm on finite trees is 1/2-competitive for both online versions, which generalises a result previously known for special cases of Firefighter. We also show that the optimal competitive ratio of online Firefighter ranges between 1/2 and the inverse of the golden ratio. Next, given two firefighter sequences, we discuss sufficient conditions for the existence of an infinite tree that separates them, in the sense that the fire can be contained with one sequence but not with the other. To this aim, we study a new purely numerical game called targeting game. Finally, we give sufficient conditions for the fire to be contained, expressed as the asymptotic comparison of the number of firefighters and the size of the tree levels.
Unstructured Multi-View Depth Estimation Using Mask-Based Multiplane Representation
Venue: arXiv cs.CV 2019
Year: 2019

This paper presents a novel method, MaskMVS, to solve depth estimation for unstructured multi-view image-pose pairs. In the plane-sweep procedure, the depth planes are sampled by histogram matching that ensures covering the depth range of interest. Unlike other plane-sweep methods, we do not rely on a cost metric to explicitly build the cost volume, but instead infer a multiplane mask representation which regularizes the learning. Compared to many previous approaches, we show that our method is lightweight and generalizes well without requiring excessive training. We outperform the current state-of-the-art and show results on the sun3d, scenes11, MVS, and RGBD test data sets.
Learning Taxonomies of Concepts and not Words using Contextualized Word Representations: A Position Paper
Venue: arXiv cs.CL 2019
Year: 2019

Taxonomies are semantic hierarchies of concepts. One limitation of current taxonomy learning systems is that they define concepts as single words. This position paper argues that contextualized word representations, which recently achieved state-of-the-art results on many competitive NLP tasks, are a promising method to address this limitation. We outline a novel approach for taxonomy learning that (1) defines concepts as synsets, (2) learns density-based approximations of contextualized word representations, and (3) can measure similarity and hypernymy among them.
A NURBS-based Inverse Analysis for Reconstruction of Nonlinear Deformations of Thin Shell Structures
Venue: arXiv cs.CE 2019
Year: 2019

This article presents original work combining a NURBS-based inverse analysis with both kinematic and constitutive nonlinearities to recover the applied loads and deformations of thin shell structures. The inverse formulation is tackled by gradient-based optimization algorithms based on computed and measured displacements at a number of discrete locations. The proposed method allows accurately recovering the target shape of shell structures such that instabilities due to snapping and buckling are captured. The results obtained show good performance and applicability of the proposed algorithms to computer-aided manufacturing of shell structures.
A Guiding Principle for Causal Decision Problems
Venue: arXiv cs.AI 2019
Year: 2019

We define a Causal Decision Problem as a Decision Problem where the available actions, the family of uncertain events and the set of outcomes are related through the variables of a Causal Graphical Model $\mathcal{G}$. A solution criteria based on Pearl's Do-Calculus and the Expected Utility criteria for rational preferences is proposed. The implementation of this criteria leads to an on-line decision making procedure that has been shown to have similar performance to classic Reinforcement Learning algorithms while allowing for a causal model of an environment to be learned. Thus, we aim to provide the theoretical guarantees of the usefulness and optimality of a decision making procedure based on causal information.
The role of a layer in deep neural networks: a Gaussian Process perspective
Venue: arXiv cs.LG 2019
Year: 2019

A fundamental question in deep learning concerns the role played by individual layers in a deep neural network (DNN) and the transferable properties of the data representations which they learn. To the extent that layers have clear roles, one should be able to optimize them separately using layer-wise loss functions. Such loss functions would describe what is the set of good data representations at each depth of the network and provide a target for layer-wise greedy optimization (LEGO). Here we derive a novel correspondence between Gaussian Processes and SGD trained deep neural networks. Leveraging this correspondence, we derive the Deep Gaussian Layer-wise loss functions (DGLs) which, we believe, are the first supervised layer-wise loss functions which are both explicit and competitive in terms of accuracy. Being highly structured and symmetric, the DGLs provide a promising analytic route to understanding the internal representations generated by DNNs.
Negative eigenvalues of the Hessian in deep neural networks
Venue: arXiv cs.LG 2019
Year: 2019

The loss function of deep networks is known to be non-convex but the precise nature of this nonconvexity is still an active area of research. In this work, we study the loss landscape of deep networks through the eigendecompositions of their Hessian matrix. In particular, we examine how important the negative eigenvalues are and the benefits one can observe in handling them appropriately.
Investigating Recurrent Neural Network Memory Structures using Neuro-Evolution
Venue: arXiv cs.NE 2019
Year: 2019

This paper presents a new algorithm, Evolutionary eXploration of Augmenting Memory Models (EXAMM), which is capable of evolving recurrent neural networks (RNNs) using a wide variety of memory structures, such as Delta-RNN, GRU, LSTM, MGU and UGRNN cells. EXAMM evolved RNNs to perform prediction of large-scale, real world time series data from the aviation and power industries. These data sets consist of very long time series (thousands of readings), each with a large number of potentially correlated and dependent parameters. Four different parameters were selected for prediction and EXAMM runs were performed using each memory cell type alone, each cell type with feed forward nodes, and with all possible memory cell types. Evolved RNN performance was measured using repeated k-fold cross validation, resulting in 1210 EXAMM runs which evolved 2,420,000 RNNs in 12,100 CPU hours on a high performance computing cluster. Generalization of the evolved RNNs was examined statistically, providing interesting findings that can help refine the RNN memory cell design as well as inform future neuro-evolution algorithms development.
Distributed Synthesis of Surveillance Strategies for Mobile Sensors
Venue: arXiv cs.AI 2019
Year: 2019

We study the problem of synthesizing strategies for a mobile sensor network to conduct surveillance in partnership with static alarm triggers. We formulate the problem as a multi-agent reactive synthesis problem with surveillance objectives specified as temporal logic formulas. In order to avoid the state space blow-up arising from a centralized strategy computation, we propose a method to decentralize the surveillance strategy synthesis by decomposing the multi-agent game into subgames that can be solved independently. We also decompose the global surveillance specification into local specifications for each sensor, and show that if the sensors satisfy their local surveillance specifications, then the sensor network as a whole will satisfy the global surveillance objective. Thus, our method is able to guarantee global surveillance properties in a mobile sensor network while synthesizing completely decentralized strategies with no need for coordination between the sensors. We also present a case study in which we demonstrate an application of decentralized surveillance strategy synthesis.