A trajectory piecewise-linear (TPWL) approach is developed for a computational fluid dynamics (CFD) model of the two-dimensional Euler equations. The approach uses a weighted combination of linearized models to represent the nonlinear CFD system. The proper orthogonal decomposition (POD) is then used to create a reduced-space basis, onto which the TPWL model is projected. This projection yields an efficient reduced-order model of the nonlinear system, which does not require the evaluation of any full-order system residuals. The method is applied to the case of flow through an actively controlled supersonic diffuser. With an appropriate choice of linearization points and POD basis vectors, the method is found to yield accurate results, including cases with significant shock motion. / Singapore-MIT Alliance (SMA)

Inference of regulatory relations in dynamical systems is a promising active research area. Recently, most of the investigations in this field have been stimulated by the researches in functional genomics. In this thesis, the inferential modeling problem for switching hybrid systems is studied. The hybrid systems refers to dynamical systems in which discrete and continuous variables regulate each other, in other words the jumps and flows are interrelated. In this study, piecewise linear approximations are used for modeling purposes and it is shown that piecewise linear models are capable of displaying the evolutionary characteristics of switching hybrid systems approxi- mately. For the mentioned systems, detection of switching instances and inference of locally linear parameters from empirical data provides a solid understanding about the system dynamics. Thus, the inference methodology is based on these issues. The primary difference of the inference algorithm is the idea of transforming the switch- ing detection problem into a jump detection problem by derivative estimation from discrete data. The jump detection problem has been studied extensively in signal processing literature. So, related techniques in the literature has been analyzed care- fully and suitable ones adopted in this thesis. The primary advantage of proposed method would be its robustness in switching detection and derivative estimation. The theoretical background of this robustness claim and the importance of robustness for real world applications are explained in detail.

[pt] O objetivo desta dissertação é propor um mecanismo de testes para a avaliação dos resultados obtidos em uma modelagem TS-TARX.A principal motivação é encontrar uma solução para um problema comum na modelagem TS-TARX : os modelos espúrios que são gerados durante o processo de divisão do espaço das variáveis independentes.O modelo é uma heurística baseada em análise de árvore de regressão, como discutido por Brieman -3, 1984-. O modelo proposto para a análise de séries temporais é chamado TARX - Threshold Autoregressive with eXternal variables-. A idéia central é encontrar limiares que separem regimes que podem ser explicados através de modelos lineares. Este processo é um algoritmo que preserva o método de regressão por mínimos quadrados recursivo -MQR-. Combinando a árvore de decisão com a técnica de regressão -MQR-, o modelo se tornou o TS-TARX -Tree Structured - Threshold AutoRegression with external variables-.Será estendido aqui o trabalho iniciado por Aranha em -1, 2001-. Onde a partir de uma base de dados conhecida, um algoritmo eficiente gera uma árvore de decisão por meio de regras, e as equações de regressão estimadas para cada um dos regimes encontrados. Este procedimento pode gerar alguns modelos espúrios ou por construção,devido a divisão binária da árvore, ou pelo fato de não existir neste momento uma metodologia de comparação dos modelos resultantes.Será proposta uma metodologia através de sucessivos testes de Chow -5, 1960- que identificará modelos espúrios e reduzirá a quantidade de regimes encontrados, e consequentemente de parâmetros a estimar. A complexidade do modelo final gerado é reduzida a partir da identificação de redundâncias, sem perder o poder preditivo dos modelos TS-TARX .O trabalho conclui com exemplos ilustrativos e algumas aplicações em bases de dados sintéticas, e casos reais que auxiliarão o entendimento. / [en] The goal of this dissertation is to propose a test mechanism to evaluate the results obtained from the TS-TARX modeling procedure.The main motivation is to find a solution to a usual problem related to TS-TARX modeling: spurious models are generated in the process of dividing the space state of the independent variables.The model is a heuristics based on regression tree analysis, as discussed by Brieman -3, 1984-. The model used to estimate the parameters of the time series is a TARX -Threshold Autoregressive with eXternal variables-.The main idea is to find thresholds that split the independent variable space into regimes which can be described by a local linear model. In this process, the recursive least square regression model is preserved. From the combination of regression tree analysis and recursive least square regression techniques, the model becomes TS-TARX -Tree Structured - Threshold Autoregression with eXternal variables-.The works initiated by Aranha in -1, 2001- will be extended. In his works, from a given data base, one efficient algorithm generates a decision tree based on splitting rules, and the corresponding regression equations for each one of the regimes found.Spurious models may be generated either from its building procedure, or from the fact that a procedure to compare the resulting models had not been proposed.To fill this gap, a methodology will be proposed. In accordance with the statistical tests proposed by Chow in -5, 196-, a series of consecutive tests will be performed.The Chow tests will provide the tools to identify spurious models and to reduce the number of regimes found. The complexity of the final model, and the number of parameters to estimate are therefore reduced by the identification and elimination of redundancies, without bringing risks to the TS-TARX model predictive power.This work is concluded with illustrative examples and some applications to real data that will help the readers understanding.

Supervised learning of piecewise linear models is a well studied problem in machine learning community. The key idea in piecewise linear modeling is to properly partition the input space and learn a linear model for every partition. Decision trees and regression trees are classic examples of piecewise linear models for classification and regression problems. The existing approaches for learning decision/regression trees can be broadly classified in to two classes, namely, fixed structure approaches and greedy approaches. In the fixed structure approaches, tree structure is fixed before hand by fixing the number of non leaf nodes, height of the tree and paths from root node to every leaf node of the tree. Mixture of experts and hierarchical mixture of experts are examples of fixed structure approaches for learning piecewise linear models. Parameters of the models are found using, e.g., maximum likelihood estimation, for which expectation maximization(EM) algorithm can be used. Fixed structure piecewise linear models can also be learnt using risk minimization under an appropriate loss function. Learning an optimal decision tree using fixed structure approach is a hard problem. Constructing an optimal binary decision tree is known to be NP Complete. On the other hand, greedy approaches do not assume any parametric form or any fixed structure for the decision tree classifier. Most of the greedy approaches learn tree structured piecewise linear models in a top down fashion. These are built by binary or multi-way recursive partitioning of the input space. The main issues in top down decision tree induction is to choose an appropriate objective function to rate the split rules. The objective function should be easy to optimize. Top-down decision trees are easy to implement and understand, but there are no optimality guarantees due to their greedy nature. Regression trees are built in the similar way as decision trees. In regression trees, every leaf node is associated with a linear regression function. All piece wise linear modeling techniques deal with two main tasks, namely, partitioning of the input space and learning a linear model for every partition. However, Partitioning of the input space and learning linear models for different partitions are not independent problems. Simultaneous optimal estimation of partitions and learning linear models for every partition, is a combinatorial problem and hence computationally hard. However, piecewise linear models provide better insights in to the classification or regression problem by giving explicit representation of the structure in the data. The information captured by piecewise linear models can be summarized in terms of simple rules, so that, they can be used to analyze the properties of the domain from which the data originates. These properties make piecewise linear models, like decision trees and regression trees, extremely useful in many data mining applications and place them among top data mining algorithms. In this thesis, we address the problem of supervised learning of piecewise linear models for classification and regression. We propose novel algorithms for learning piecewise linear classifiers and regression functions. We also address the problem of noise tolerant learning of classifiers in presence of label noise. We propose a novel algorithm for learning polyhedral classifiers which are the simplest form of piecewise linear classifiers. Polyhedral classifiers are useful when points of positive class fall inside a convex region and all the negative class points are distributed outside the convex region. Then the region of positive class can be well approximated by a simple polyhedral set. The key challenge in optimally learning a fixed structure polyhedral classifier is to identify sub problems, where each sub problem is a linear classification problem. This is a hard problem and identifying polyhedral separability is known to be NP complete. The goal of any polyhedral learning algorithm is to efficiently handle underlying combinatorial problem while achieving good classification accuracy. Existing methods for learning a fixed structure polyhedral classifier are based on solving non convex constrained optimization problems. These approaches do not efficiently handle the combinatorial aspect of the problem and are computationally expensive. We propose a method of model based estimation of posterior class probability to learn polyhedral classifiers. We solve an unconstrained optimization problem using a simple two step algorithm (similar to EM algorithm) to find the model parameters. To the best of our knowledge, this is the first attempt to form an unconstrained optimization problem for learning polyhedral classifiers. We then modify our algorithm to find the number of required hyperplanes also automatically. We experimentally show that our approach is better than the existing polyhedral learning algorithms in terms of training time, performance and the complexity. Most often, class conditional densities are multimodal. In such cases, each class region may be represented as a union of polyhedral regions and hence a single polyhedral classifier is not sufficient. To handle such situation, a generic decision tree is required. Learning optimal fixed structure decision tree is a computationally hard problem. On the other hand, top-down decision trees have no optimality guarantees due to the greedy nature. However, top-down decision tree approaches are widely used as they are versatile and easy to implement. Most of the existing top-down decision tree algorithms (CART,OC1,C4.5, etc.) use impurity measures to assess the goodness of hyper planes at each node of the tree. These measures do not properly capture the geometric structures in the data. We propose a novel decision tree algorithm that ,at each node, selects hyperplanes based on an objective function which takes into consideration geometric structure of the class regions. The resulting optimization problem turns out to be a generalized eigen value problem and hence is efficiently solved. We show through empirical studies that our approach leads to smaller size trees and better performance compared to other top-down decision tree approaches. We also provide some theoretical justification for the proposed method of learning decision trees. Piecewise linear regression is similar to the corresponding classification problem. For example, in regression trees, each leaf node is associated with a linear regression model. Thus the problem is once again that of (simultaneous) estimation of optimal partitions and learning a linear model for each partition. Regression trees, hinge hyperplane method, mixture of experts are some of the approaches to learn continuous piecewise linear regression models. Many of these algorithms are computationally intensive. We present a method of learning piecewise linear regression model which is computationally simple and is capable of learning discontinuous functions as well. The method is based on the idea of K plane regression that can identify a set of linear models given the training data. K plane regression is a simple algorithm motivated by the philosophy of k means clustering. However this simple algorithm has several problems. It does not give a model function so that we can predict the target value for any given input. Also, it is very sensitive to noise. We propose a modified K plane regression algorithm which can learn continuous as well as discontinuous functions. The proposed algorithm still retains the spirit of k means algorithm and after every iteration it improves the objective function. The proposed method learns a proper Piece wise linear model that can be used for prediction. The algorithm is also more robust to additive noise than K plane regression. While learning classifiers, one normally assumes that the class labels in the training data set are noise free. However, in many applications like Spam filtering, text classification etc., the training data can be mislabeled due to subjective errors. In such cases, the standard learning algorithms (SVM, Adaboost, decision trees etc.) start over fitting on the noisy points and lead to poor test accuracy. Thus analyzing the vulnerabilities of classifiers to label noise has recently attracted growing interest from the machine learning community. The existing noise tolerant learning approaches first try to identify the noisy points and then learn classifier on remaining points. In this thesis, we address the issue of developing learning algorithms which are inherently noise tolerant. An algorithm is inherently noise tolerant if, the classifier it learns with noisy samples would have the same performance on test data as that learnt from noise free samples. Algorithms having such robustness (under suitable assumption on the noise) are attractive for learning with noisy samples. Here, we consider non uniform label noise which is a generic noise model. In non uniform label noise, the probability of the class label for an example being incorrect, is a function of the feature vector of the example.(We assume that this probability is less than 0.5 for all feature vectors.) This can account for most cases of noisy data sets. There is no provably optimal algorithm for learning noise tolerant classifiers in presence of non uniform label noise. We propose a novel characterization of noise tolerance of an algorithm. We analyze noise tolerance properties of risk minimization frame work as risk minimization is a common strategy for classifier learning. We show that risk minimization under 01 loss has the best noise tolerance properties. None of the other convex loss functions have such noise tolerance properties. Empirical risk minimization under 01 loss is a hard problem as 01 loss function is not differentiable. We propose a gradient free stochastic optimization technique to minimize risk under 01 loss function for noise tolerant learning of linear classifiers. We show (under some conditions) that the algorithm converges asymptotically to the global minima of the risk under 01 loss function. We illustrate the noise tolerance of our algorithm through simulations experiments. We demonstrate the noise tolerance of the algorithm through simulations.

Available security standards for RFID networks (e.g. ISO/IEC 29167) are designed to secure individual tag-reader sessions and do not protect against active attacks that could also compromise the system as a whole (e.g. tag cloning or replay attacks). Proper traffic characterization models of the communication within an RFID network can lead to better understanding of operation under “normal” system state conditions and can consequently help identify security breaches not addressed by current standards. This study of RFID traffic characterization considers two piecewise-constant data smoothing techniques, namely Bayesian blocks and Knuth’s algorithms, over time-tagged events and compares them in the context of rate-based anomaly detection. This was accomplished using data from experimental RFID readings and comparing (1) the event counts versus time if using the smoothed curves versus empirical histograms of the raw data and (2) the threshold-dependent alert-rates based on inter-arrival times obtained if using the smoothed curves versus that of the raw data itself. Results indicate that both algorithms adequately model RFID traffic in which inter-event time statistics are stationary but that Bayesian blocks become superior for traffic in which such statistics experience abrupt changes.