Statistical methods with applications to machine learning and artificial intelligence

This thesis consists of four chapters. The first chapter is on function estimation via regularization. The second and third chapters are about static/dynamic path planning algorithms, respectively. The last chapter is application-oriented, focusing on spikes prediction in electricity prices. Chapter 1 focuses on theoretical results on high-order laplacian-based regularization in function estimation. Thin-plate splines are widely used for estimating an unknown function in nonparametric regression, but it performs poorly over complex regions (i.e., regions with hole) and therefore soap-film smoother is proposed which introduces the laplacian-based regularization and allows for certain degree of freedom along the boundary. Besides, in machine learning community, unsupervised learning algorithm such as laplacian eigenmap also adopts the graphical laplacian regularization as a control for unsmoothness of the underlying manifold. However, the theoretical justification for Laplacian-based regularization in terms of optimal convergence rate has been missing in the literatures. In Chapter 1, we study the iterated laplacian regularization in the context of supervised learning in order to achieve both nice theoretical properties (like thin-plate splines) and good performance over complex region (like soap film smoother). We first derive a closed-form function estimation in the context of nonparametric smoothing based on the graphical laplacian regularization. It is shown that soap film is one special case of this smoother when the order of penalty is 2. We then prove that the smoother achieves the optimal rate of convergence. The essential part of proof is to study the asymptotic properties of the penalty matrix's eigenvalues, which relies on the Sobolev semi-norms, spectrum analysis of elliptic operator and the relationship between heat kernel and laplacian operator. The last part of chapter 1 is devoted to the proof of asymptotic optimality of tuning parameter selected by generalized cross-validation (GCV). In Chapter 2, we propose an innovative static path-planning algorithm called m-A* within an environment full of obstacles, which has lower worst-case order magnitude of computation complexity and reduces the number of vertex expansion compared to the benchmark A* algorithm in the simulation study. More specifically, the proposed graph structure first employs a recursive dyadic partitioning to divide the environment into “block" of different sizes. The block sizes are determined by the relative importance of information within those blocks. The preprocessing of information within each block is handled by an innovative bottom-u p fusion algorithm, which accumulates distance information from finer scale to coarser scale, therefore we only need the boundary vertices in each block to conduct the shortest path planning (In other words, we obtain a sparsity representation of the environment). We then show that modified A* based on beamlet graphical structure reduces the number of vertex expansion from O(n2 log(n)) to O( n2), when the environment is a n× n image. In the simulation study, our approach outperforms A* armed with both standard L1 heuristic and stronger ones such as True-Distance heuristics (TDH), yielding faster query time, adequate usage of memory and reasonable preprocessing time. More generally, the recursive dyadic partitioning scheme and bottom-up fusion algorithm do not rely on A* algorithm and therefore can be adapted to any other path-planning approach that involves multiscale strategy. Chapter 3 proposes m-LPA* algorithm that extends the m-A* algorithm proposed in Chapter 2 in the context of dynamic path-planning and shows that m- LPA* achieves better performance compared to the benchmark: lifelong planning A* (LPA*) in terms of robustness and worst-case computational complexity. Employing the same beamlet graphical structure as m-A*, m-LPA* encodes the information of the environment in a hierarchical, multiscale fashion, keeping track of \long-range" interaction between the vertices in the beamlet graph. When the update of original graph induces \local dead-end", which causes the surprisingly huge number of vertex expansion in the replanning, the information is transmitted by modifying the hierarchical structure of beamlet graph, so no more \dead-ends" exist in the new graph, and hence it produces a more robust dynamic path-planning algorithm. The analysis of computational complexity reveals that, in the worst case, the proposed algorithm has a lower order of complexity than the LPA* algorithm. In our numerical experiments, it shows that the m-LPA* algorithm can dramatically reduce the number of vertex expansions in the worst scenarios. Chapter 4 focuses on an approach for the prediction of spot electricity spikes via a combination of boosting and wavelet analysis. It has been well recognized in finance that modeling spikes (i.e., jumps) is an essential task in asset pricing, risk management and trading activity. Due to the complexity and uncertainties in the power grid, spot electricity prices are highly volatile and normally carry with spikes, which may be tens or even hundreds of times higher than the normal price. Another issue comes from modeling the intraday seaonality and its evolution over time. The first part of our proposed scheme considers the hourly spot prices within one day as a high dimensional vector and applys the nondecimated wavelet analysis to detect the spikes for training. The second part utilizes the gradient boosting trees for the spikes prediction with carefully selected predictors from Australian electricity markets. Extensive numerical experiments show that our approach improves the prediction accuracy, thanks to the fact that the gradient boosting trees method inherits the good properties of decision trees such as robustness to the irrelevant covariates, fast computational capability and good interpretation.