OpenRaiser/Intern-Atlas huggingface dataset:
Timeline-based Planning and Execution with Uncertainty: Theory, Modeling Methodologies and Practice
Venue: arXiv cs.AI 2019
Year: 2019

Automated Planning is one of the main research field of Artificial Intelligence since its beginnings. Research in Automated Planning aims at developing general reasoners (i.e., planners) capable of automatically solve complex problems. Broadly speaking, planners rely on a general model characterizing the possible states of the world and the actions that can be performed in order to change the status of the world. Given a model and an initial known state, the objective of a planner is to synthesize a set of actions needed to achieve a particular goal state. The classical approach to planning roughly corresponds to the description given above. The timeline-based approach is a particular planning paradigm capable of integrating causal and temporal reasoning within a unified solving process. This approach has been successfully applied in many real-world scenarios although a common interpretation of the related planning concepts is missing. Indeed, there are significant differences among the existing frameworks that apply this technique. Each framework relies on its own interpretation of timeline-based planning and therefore it is not easy to compare these systems. Thus, the objective of this work is to investigate the timeline-based approach to planning by addressing several aspects ranging from the semantics of the related planning concepts to the modeling and solving techniques. Specifically, the main contributions of this PhD work consist of: (i) the proposal of a formal characterization of the timeline-based approach capable of dealing with temporal uncertainty; (ii) the proposal of a hierarchical modeling and solving approach; (iii) the development of a general purpose framework for planning and execution with timelines; (iv) the validation†of this approach in real-world manufacturing scenarios.
Online Anomaly Detection with Sparse Gaussian Processes
Venue: arXiv cs.LG 2019
Year: 2019

Online anomaly detection of time-series data is an important and challenging task in machine learning. Gaussian processes (GPs) are powerful and flexible models for modeling time-series data. However, the high time complexity of GPs limits their applications in online anomaly detection. Attributed to some internal or external changes, concept drift usually occurs in time-series data, where the characteristics of data and meanings of abnormal behaviors alter over time. Online anomaly detection methods should have the ability to adapt to concept drift. Motivated by the above facts, this paper proposes the method of sparse Gaussian processes with Q-function (SGP-Q). The SGP-Q employs sparse Gaussian processes (SGPs) whose time complexity is lower than that of GPs, thus significantly speeding up online anomaly detection. By using Q-function properly, the SGP-Q can adapt to concept drift well. Moreover, the SGP-Q makes use of few abnormal data in the training data by its strategy of updating training data, resulting in more accurate sparse Gaussian process regression models and better anomaly detection results. We evaluate the SGP-Q on various artificial and real-world datasets. Experimental results validate the effectiveness of the SGP-Q.
Proving Unrealizability for Syntax-Guided Synthesis
Venue: arXiv cs.PL 2019
Year: 2019

Proving Unrealizability for Syntax-Guided Synthesis We consider the problem of automatically establishing that a given syntax-guided-synthesis (SyGuS) problem is unrealizable (i.e., has no solution). Existing techniques have quite limited ability to establish unrealizability for general SyGuS instances in which the grammar describing the search space contains infinitely many programs. By encoding the synthesis problem's grammar G as a nondeterministic program P_G, we reduce the unrealizability problem to a reachability problem such that, if a standard program-analysis tool can establish that a certain assertion in P_G always holds, then the synthesis problem is unrealizable. Our method can be used to augment any existing SyGus tool so that it can establish that a successfully synthesized program q is optimal with respect to some syntactic cost -- e.g., q has the fewest possible if-then-else operators. Using known techniques, grammar G can be automatically transformed to generate exactly all programs with lower cost than q -- e.g., fewer conditional expressions. Our algorithm can then be applied to show that the resulting synthesis problem is unrealizable. We implemented the proposed technique in a tool called NOPE. NOPE can prove unrealizability for 59/134 variants of existing linear-integer-arithmetic SyGus benchmarks, whereas all existing SyGus solvers lack the ability to prove that these benchmarks are unrealizable, and time out on them.
Planted Hitting Set Recovery in Hypergraphs
Venue: arXiv cs.SI 2019
Year: 2019

In various application areas, networked data is collected by measuring interactions involving some specific set of core nodes. This results in a network dataset containing the core nodes along with a potentially much larger set of fringe nodes that all have at least one interaction with a core node. In many settings, this type of data arises for structures that are richer than graphs, because they involve the interactions of larger sets; for example, the core nodes might be a set of individuals under surveillance, where we observe the attendees of meetings involving at least one of the core individuals. We model such scenarios using hypergraphs, and we study the problem of core recovery: if we observe the hypergraph but not the labels of core and fringe nodes, can we recover the "planted" set of core nodes in the hypergraph? We provide a theoretical framework for analyzing the recovery of such a set of core nodes and use our theory to develop a practical and scalable algorithm for core recovery. The crux of our analysis and algorithm is that the core nodes are a hitting set of the hypergraph, meaning that every hyperedge has at least one node in the set of core nodes. We demonstrate the efficacy of our algorithm on a number of real-world datasets, outperforming competitive baselines derived from network centrality and core-periphery measures.
Task-Driven Data Verification via Gradient Descent
Venue: arXiv cs.LG 2019
Year: 2019

We introduce a novel algorithm for the detection of possible sample corruption such as mislabeled samples in a training dataset given a small clean validation set. We use a set of inclusion variables which determine whether or not any element of the noisy training set should be included in the training of a network. We compute these inclusion variables by optimizing the performance of the network on the clean validation set via "gradient descent on gradient descent" based learning. The inclusion variables as well as the network trained in such a way form the basis of our methods, which we call Corruption Detection via Gradient Descent (CDGD). This algorithm can be applied to any supervised machine learning task and is not limited to classification problems. We provide a quantitative comparison of these methods on synthetic and real world datasets.
Resource-aware Elastic Swap Random Forest for Evolving Data Streams
Venue: arXiv cs.LG 2019
Year: 2019

Continual learning based on data stream mining deals with ubiquitous sources of Big Data arriving at high-velocity and in real-time. Adaptive Random Forest ({\em ARF}) is a popular ensemble method used for continual learning due to its simplicity in combining adaptive leveraging bagging with fast random Hoeffding trees. While the default ARF size provides competitive accuracy, it is usually over-provisioned resulting in the use of additional classifiers that only contribute to increasing CPU and memory consumption with marginal impact in the overall accuracy. This paper presents Elastic Swap Random Forest ({\em ESRF}), a method for reducing the number of trees in the ARF ensemble while providing similar accuracy. {\em ESRF} extends {\em ARF} with two orthogonal components: 1) a swap component that splits learners into two sets based on their accuracy (only classifiers with the highest accuracy are used to make predictions); and 2) an elastic component for dynamically increasing or decreasing the number of classifiers in the ensemble. The experimental evaluation of {\em ESRF} and comparison with the original {\em ARF} shows how the two new components contribute to reducing the number of classifiers up to one third while providing almost the same accuracy, resulting in speed-ups in terms of per-sample execution time close to 3x.
Generative Design in Minecraft: Chronicle Challenge
Venue: arXiv cs.AI 2019
Year: 2019

We introduce the Chronicle Challenge as an optional addition to the Settlement Generation Challenge in Minecraft. One of the foci of the overall competition is adaptive procedural content generation (PCG), an arguably under-explored problem in computational creativity. In the base challenge, participants must generate new settlements that respond to and ideally interact with existing content in the world, such as the landscape or climate. The goal is to understand the underlying creative process, and to design better PCG systems. The Chronicle Challenge in particular focuses on the generation of a narrative based on the history of a generated settlement, expressed in natural language. We discuss the unique features of the Chronicle Challenge in comparison to other competitions, clarify the characteristics of a chronicle eligible for submission and describe the evaluation criteria. We furthermore draw on simulation-based approaches in computational storytelling as examples to how this challenge could be approached.
A Neural Network-Evolutionary Computational Framework for Remaining Useful Life Estimation of Mechanical Systems
Venue: arXiv cs.LG 2019
Year: 2019

This paper presents a framework for estimating the remaining useful life (RUL) of mechanical systems. The framework consists of a multi-layer perceptron and an evolutionary algorithm for optimizing the data-related parameters. The framework makes use of a strided time window to estimate the RUL for mechanical components. Tuning the data-related parameters can become a very time consuming task. The framework presented here automatically reshapes the data such that the efficiency of the model is increased. Furthermore, the complexity of the model is kept low, e.g. neural networks with few hidden layers and few neurons at each layer. Having simple models has several advantages like short training times and the capacity of being in environments with limited computational resources such as embedded systems. The proposed method is evaluated on the publicly available C-MAPSS dataset, its accuracy is compared against other state-of-the art methods for the same dataset.
Multi-Cap Optimization for Wireless Data Plans with Time Flexibility
Venue: arXiv cs.GT 2019
Year: 2019

An effective way for a Mobile network operator (MNO) to improve its revenue is price discrimination, i.e., providing different combinations of data caps and subscription fees. Rollover data plan (allowing the unused data in the current month to be used in the next month) is an innovative data mechanism with time flexibility. In this paper, we study the MNO's optimal multi-cap data plans with time flexibility in a realistic asymmetric information scenario. Specifically, users are associated with multi-dimensional private information, and the MNO designs a contract (with different data caps and subscription fees) to induce users to truthfully reveal their private information. This problem is quite challenging due to the multi-dimensional private information. We address the challenge in two aspects. First, we find that a feasible contract (satisfying incentive compatibility and individual rationality) should allocate the data caps according to users' willingness-to-pay (captured by the slopes of users' indifference curves). Second, for the non-convex data cap allocation problem, we propose a Dynamic Quota Allocation Algorithm, which has a low complexity and guarantees the global optimality. Numerical results show that the time-flexible data mechanisms increase both the MNO's profit (25% on average) and users' payoffs (8.2% on average) under price discrimination.
Origami Inspired Solar Panel Design
Venue: arXiv cs.NE 2019
Year: 2019

The goal of this paper was to take a flat solar panel and make cuts on the panel to make smaller, but still viable solar panels. These smaller solar panels could then be arranged in a tree-like design. The hope was that by having solar panels faced in different directions in 3-dimensional space, the tree system would be able to pick up more sunlight than a flat solar panel. The results were promising, but this project did not take every factor into account. Specifically, optimum shape, temperature and the resistance of system, reflection of sun-rays were not explored in this project. This paper will take an approach from origami paper folding to create the optimum arrangement that will allow the overall system to absorb the maximum energy. Since the system stays stationary throughout the day, it can reduce the maintenance cost and excess energy use because it does not require solar tracking. In this project we have implemented a variety of Evolutionary Algorithms to find the most efficient way to cut a flat solar panel and arrange the resulting smaller panels. Each solution in the population will be tested by computing the amount of solar energy that is absorbed at particular times of the day. The EA will be exploring different combinations of angles and heights of the smaller panels on the tree such that the system can produce the maximum amount of power throughout the day. The performance of our Evolutionary algorithms are comparable to the performance of flat solar panels. Keywords: - Evolutionary Programming, Evolution Strategy, Genetic Algorithm, Solar Panel Optimization.
Cooperative Relaying in LoRa Sensor Networks
Venue: arXiv cs.NI 2019
Year: 2019

We propose a communication scheme with relays to improve the reliability of a Long Range (LoRa) sensor network with duty-cycle limitations. The relays overhear the sensors' transmissions and forward them to a gateway. Simulations show that relaying is very beneficial, even though the nodes are not coordinated and duty cycling limits the number of sensor measurements that can be forwarded. In our setup, a single relay can halve the measurement loss rate and eight relays provide a gain of up to two orders of magnitude. Further improvements are achieved by including a few past measurements in each frame.
Byzantine Consensus in the Common Case
Venue: arXiv cs.DC 2019
Year: 2019

Modular methods to transform Byzantine consensus protocols into ones that are fast and communication efficient in the common cases are presented. Small and short protocol segments called layers are custom designed to optimize performance in the common case. When composed with a Byzantine consensus protocol of choice, they allow considerable control over the tradeoff in the combined protocol's behavior in the presence of failures and its performance in their absence. When runs are failure free in the common case, the resulting protocols decide in two rounds and require $2nt$ bits of communication. For the common case assumption that all processors propose 1 and no failures occur, we show a transformation in which decisions are made in one round, and no bits of communication are exchanged. The resulting protocols achieve better common-case complexity than all existing Byzantine consensus protocols. Finally, in the rare instances in which the common case does not occur, a small cost is added to the complexity of the original consensus protocol being transformed. The key ingredient of these layers that allows both time and communication efficiency in the common case is the use of {\it silent confirmation rounds}, which are rounds where considerable relevant information can be obtained in the absence of any communication whatsoever.
Semantic Search using Spreading Activation based on Ontology
Venue: arXiv cs.IR 2019
Year: 2019

Currently, the text document retrieval systems have many challenges in exploring the semantics of queries and documents. Each query implies information which does not appear in the query but the documents related with the information are also expected by user. The disadvantage of the previous spreading activation algorithms could be many irrelevant concepts added to the query. In this paper, a proposed novel algorithm is only activate and add to the query named entities which are related with original entities in the query and explicit relations in the query.
Scaling Distributed Training of Flood-Filling Networks on HPC Infrastructure for Brain Mapping
Venue: arXiv cs.DC 2019
Year: 2019

Mapping all the neurons in the brain requires automatic reconstruction of entire cells from volume electron microscopy data. The flood-filling network (FFN) architecture has demonstrated leading performance for segmenting structures from this data. However, the training of the network is computationally expensive. In order to reduce the training time, we implemented synchronous and data-parallel distributed training using the Horovod library, which is different from the asynchronous training scheme used in the published FFN code. We demonstrated that our distributed training scaled well up to 2048 Intel Knights Landing (KNL) nodes on the Theta supercomputer. Our trained models achieved similar level of inference performance, but took less training time compared to previous methods. Our study on the effects of different batch sizes on FFN training suggests ways to further improve training efficiency. Our findings on optimal learning rate and batch sizes agree with previous works.
An assisting Model Predictive Controller approach to Control over the Cloud
Venue: arXiv cs.SY 2019
Year: 2019

In this paper we develop a computational offloading strategy with graceful degradation for executing Model Predictive Control using the cloud. Backed up by previous work we simulate the control of a cyber-physical-system at high frequency and illustrate how the system can be improved using the edge while keeping the computational burden low.
Inquiry of P-reduction in Cook's 1971 Paper -- from Oracle machine to Turing machine
Venue: arXiv cs.OH 2019
Year: 2019

In this paper, we inquire the key concept P-reduction in Cook's theorem and reveal that there exists the fallacy of definition in P-reduction caused by the disguised displacement of NDTM from Oracle machine to Turing machine. The definition or derivation of P-reduction is essentially equivalent to Turing's computability. Whether NP problems might been reduced to logical forms (tautology or SAT) or NP problems might been reduced each other, they have not been really proven in Cook's 1971 paper.
Contextualized Spatial-Temporal Network for Taxi Origin-Destination Demand Prediction
Venue: arXiv cs.LG 2019
Year: 2019

Taxi demand prediction has recently attracted increasing research interest due to its huge potential application in large-scale intelligent transportation systems. However, most of the previous methods only considered the taxi demand prediction in origin regions, but neglected the modeling of the specific situation of the destination passengers. We believe it is suboptimal to preallocate the taxi into each region based solely on the taxi origin demand. In this paper, we present a challenging and worth-exploring task, called taxi origin-destination demand prediction, which aims at predicting the taxi demand between all region pairs in a future time interval. Its main challenges come from how to effectively capture the diverse contextual information to learn the demand patterns. We address this problem with a novel Contextualized Spatial-Temporal Network (CSTN), which consists of three components for the modeling of local spatial context (LSC), temporal evolution context (TEC) and global correlation context (GCC) respectively. Firstly, an LSC module utilizes two convolution neural networks to learn the local spatial dependencies of taxi demand respectively from the origin view and the destination view. Secondly, a TEC module incorporates both the local spatial features of taxi demand and the meteorological information to a Convolutional Long Short-term Memory Network (ConvLSTM) for the analysis of taxi demand evolution. Finally, a GCC module is applied to model the correlation between all regions by computing a global correlation feature as a weighted sum of all regional features, with the weights being calculated as the similarity between the corresponding region pairs. Extensive experiments and evaluations on a large-scale dataset well demonstrate the superiority of our CSTN over other compared methods for taxi origin-destination demand prediction.
Dynamic Neural Network Channel Execution for Efficient Training
Venue: arXiv cs.LG 2019
Year: 2019

Existing methods for reducing the computational burden of neural networks at run-time, such as parameter pruning or dynamic computational path selection, focus solely on improving computational efficiency during inference. On the other hand, in this work, we propose a novel method which reduces the memory footprint and number of computing operations required for training and inference. Our framework efficiently integrates pruning as part of the training procedure by exploring and tracking the relative importance of convolutional channels. At each training step, we select only a subset of highly salient channels to execute according to the combinatorial upper confidence bound algorithm, and run a forward and backward pass only on these activated channels, hence learning their parameters. Consequently, we enable the efficient discovery of compact models. We validate our approach empirically on state-of-the-art CNNs - VGGNet, ResNet and DenseNet, and on several image classification datasets. Results demonstrate our framework for dynamic channel execution reduces computational cost up to 4x and parameter count up to 9x, thus reducing the memory and computational demands for discovering and training compact neural network models.
An Online Pricing Mechanism for Electric Vehicle Parking Assignment and Charge Scheduling
Venue: arXiv cs.MA 2019
Year: 2019

In this paper, we design a pricing framework for online electric vehicle (EV) parking assignment and charge scheduling. Here, users with electric vehicles want to park and charge at electric-vehicle-supply-equipment (EVSEs) at different locations and arrive/depart throughout the day. The goal is to assign and schedule users to the available EVSEs while maximizing user utility and minimizing operational costs. Our formulation can accommodate multiple locations, limited resources, operational costs, as well as variable arrival patterns. With this formulation, the parking facility management can optimize for behind-the-meter solar integration and reduce costs due to procuring electricity from the grid. We use an online pricing mechanism to approximate the EVSE reservation problem's solution and we analyze the performance compared to the offline solution. Our numerical simulation validates the performance of the EVSE reservation system in a downtown area with multiple parking locations equipped with EVSEs.
On Norm-Agnostic Robustness of Adversarial Training
Venue: arXiv cs.LG 2019
Year: 2019

Adversarial examples are carefully perturbed in-puts for fooling machine learning models. A well-acknowledged defense method against such examples is adversarial training, where adversarial examples are injected into training data to increase robustness. In this paper, we propose a new attack to unveil an undesired property of the state-of-the-art adversarial training, that is it fails to obtain robustness against perturbations in $\ell_2$ and $\ell_\infty$ norms simultaneously. We discuss a possible solution to this issue and its limitations as well.