Add to Chrome
Add to Firefox
Add to EdgeQiang Lu
Prove Symbolic Regression is NP-hard by Symbol Graph
Apr 22, 2024
Symbolic regression (SR) is the task of discovering a symbolic expression that fits a given data set from the space of mathematical expressions. Despite the abundance of research surrounding the SR problem, there's a scarcity of works that confirm its NP-hard nature. Therefore, this paper introduces the concept of a symbol graph as a comprehensive representation of the entire mathematical expression space, effectively illustrating the NP-hard characteristics of the SR problem. Leveraging the symbol graph, we establish a connection between the SR problem and the task of identifying an optimally fitted degree-constrained Steiner Arborescence (DCSAP). The complexity of DCSAP, which is proven to be NP-hard, directly implies the NP-hard nature of the SR problem.
Exploring Hidden Semantics in Neural Networks with Symbolic Regression
Apr 22, 2022
Many recent studies focus on developing mechanisms to explain the black-box behaviors of neural networks (NNs). However, little work has been done to extract the potential hidden semantics (mathematical representation) of a neural network. A succinct and explicit mathematical representation of a NN model could improve the understanding and interpretation of its behaviors. To address this need, we propose a novel symbolic regression method for neural works (called SRNet) to discover the mathematical expressions of a NN. SRNet creates a Cartesian genetic programming (NNCGP) to represent the hidden semantics of a single layer in a NN. It then leverages a multi-chromosome NNCGP to represent hidden semantics of all layers of the NN. The method uses a (1+$\lambda$) evolutionary strategy (called MNNCGP-ES) to extract the final mathematical expressions of all layers in the NN. Experiments on 12 symbolic regression benchmarks and 5 classification benchmarks show that SRNet not only can reveal the complex relationships between each layer of a NN but also can extract the mathematical representation of the whole NN. Compared with LIME and MAPLE, SRNet has higher interpolation accuracy and trends to approximate the real model on the practical dataset.
LGSVL Simulator: A High Fidelity Simulator for Autonomous Driving
May 11, 2020
Testing autonomous driving algorithms on real autonomous vehicles is extremely costly and many researchers and developers in the field cannot afford a real car and the corresponding sensors. Although several free and open-source autonomous driving stacks, such as Autoware and Apollo are available, choices of open-source simulators to use with them are limited. In this paper, we introduce the LGSVL Simulator which is a high fidelity simulator for autonomous driving. The simulator engine provides end-to-end, full-stack simulation which is ready to be hooked up to Autoware and Apollo. In addition, simulator tools are provided with the core simulation engine which allow users to easily customize sensors, create new types of controllable objects, replace some modules in the core simulator, and create digital twins of particular environments.
Formal Scenario-Based Testing of Autonomous Vehicles: From Simulation to the Real World
Mar 17, 2020
We present a new approach to automated scenario-based testing of the safety of autonomous vehicles, especially those using advanced artificial intelligence-based components, spanning both simulation-based evaluation as well as testing in the real world. Our approach is based on formal methods, combining formal specification of scenarios and safety properties, algorithmic test case generation using formal simulation, test case selection for track testing, executing test cases on the track, and analyzing the resulting data. Experiments with a real autonomous vehicle at an industrial testing ground support our hypotheses that (i) formal simulation can be effective at identifying test cases to run on the track, and (ii) the gap between simulated and real worlds can be systematically evaluated and bridged.
Safe and Efficient Intersection Control of Connected and Autonomous Intersection Traffic
Jan 29, 2018
In this dissertation, we address a problem of safe and efficient intersection crossing traffic management of autonomous and connected ground traffic. Toward this objective, an algorithm that is called the Discrete-time occupancies trajectory based Intersection traffic Coordination Algorithm (DICA) is proposed. All vehicles in the system are Connected and Autonomous Vehicles (CAVs) and capable of wireless Vehicle-to-Intersection communication. In the proposed framework, an intersection coordinates the motions of CAVs based on their proposed DTOTs to let them cross the intersection efficiently while avoiding collisions. In case when there is a collision between vehicles' DTOTs, the intersection modifies conflicting DTOTs to avoid the collision and requests CAVs to approach and cross the intersection according to the modified DTOTs. We then prove that the basic DICA is deadlock free and also starvation free. We also show that the basic DICA is conservative in computational complexity and improve it by several computational approaches. Next, we addressed the problem of evacuating emergency vehicles as quickly as possible through autonomous and connected intersection traffic in this dissertation. The proposed intersection control algorithm Reactive DICA aims to determine an efficient vehicle-passing sequence which allows the emergency vehicle to cross an intersection as soon as possible while the travel times of other vehicles are minimally affected. When there are no emergency vehicles within the intersection area, the vehicles are controlled by DICA. When there are emergency vehicles entering communication range, we prioritize emergency vehicles through optimal ordering of vehicles. A genetic algorithm is proposed to solve the optimization problem which finds the optimal vehicle sequence that gives the emergency vehicles the highest priority.
Autonomous and Connected Intersection Crossing Traffic Management using Discrete-Time Occupancies Trajectory
May 12, 2017
In this paper, we address a problem of safe and efficient intersection crossing traffic management of autonomous and connected ground traffic. Toward this objective, we propose an algorithm that is called the Discrete-time occupancies trajectory based Intersection traffic Coordination Algorithm (DICA). We first prove that the basic DICA is deadlock free and also starvation free. Then, we show that the basic DICA has a computational complexity of $\mathcal{O}(n^2 L_m^3)$ where $n$ is the number of vehicles granted to cross an intersection and $L_m$ is the maximum length of intersection crossing routes. To improve the overall computational efficiency of the algorithm, the basic DICA is enhanced by several computational approaches that are proposed in this paper. The enhanced algorithm has the computational complexity of $\mathcal{O}(n^2 L_m \log_2 L_m)$. The improved computational efficiency of the enhanced algorithm is validated through simulation using an open source traffic simulator, called the Simulation of Urban MObility (SUMO). The overall throughput as well as the computational efficiency of the enhanced algorithm are also compared with those of an optimized traffic light control.
Qualitative detection of oil adulteration with machine learning approaches
May 14, 2013
The study focused on the machine learning analysis approaches to identify the adulteration of 9 kinds of edible oil qualitatively and answered the following three questions: Is the oil sample adulterant? How does it constitute? What is the main ingredient of the adulteration oil? After extracting the high-performance liquid chromatography (HPLC) data on triglyceride from 370 oil samples, we applied the adaptive boosting with multi-class Hamming loss (AdaBoost.MH) to distinguish the oil adulteration in contrast with the support vector machine (SVM). Further, we regarded the adulterant oil and the pure oil samples as ones with multiple labels and with only one label, respectively. Then multi-label AdaBoost.MH and multi-label learning vector quantization (ML-LVQ) model were built to determine the ingredients and their relative ratio in the adulteration oil. The experimental results on six measures show that ML-LVQ achieves better performance than multi-label AdaBoost.MH.
Theory and Algorithms for Partial Order Based Reduction in Planning
Jun 27, 2011
Search is a major technique for planning. It amounts to exploring a state space of planning domains typically modeled as a directed graph. However, prohibitively large sizes of the search space make search expensive. Developing better heuristic functions has been the main technique for improving search efficiency. Nevertheless, recent studies have shown that improving heuristics alone has certain fundamental limits on improving search efficiency. Recently, a new direction of research called partial order based reduction (POR) has been proposed as an alternative to improving heuristics. POR has shown promise in speeding up searches. POR has been extensively studied in model checking research and is a key enabling technique for scalability of model checking systems. Although the POR theory has been extensively studied in model checking, it has never been developed systematically for planning before. In addition, the conditions for POR in the model checking theory are abstract and not directly applicable in planning. Previous works on POR algorithms for planning did not establish the connection between these algorithms and existing theory in model checking. In this paper, we develop a theory for POR in planning. The new theory we develop connects the stubborn set theory in model checking and POR methods in planning. We show that previous POR algorithms in planning can be explained by the new theory. Based on the new theory, we propose a new, stronger POR algorithm. Experimental results on various planning domains show further search cost reduction using the new algorithm.