<p>In this thesis, we present algorithms for local and global minimization of some <i>Procrustes</i> type problems. Typically, these problems are about rotating and scaling a known set of data to fit another set with applications related to determination of rigid body movements, factor analysis and multidimensional scaling. The known sets of data are usually represented as matrices, and the rotation to be determined is commonly a matrix <i>Q</i> with orthonormal columns.</p><p>The algorithms presented use Newton and Gauss-Newton search directions with optimal step lengths, which in most cases result in a fast computation of a solution.</p><p>Some of these problems are known to have several minima, e.g., the weighted orthogonal Procrustes problem (WOPP). A study on the maximal amount of minima has been done for this problem. Theoretical results and empirical observations gives strong indications that there are not more than 2ⁿ minimizers, where <i>n</i> is the number of columns in <i>Q</i>. A global optimization method to compute all 2ⁿ minima is presented.</p><p>Also considered in this thesis is a cubically convergent iteration method for solving nonlinear equations. The iteration method presented uses second order information (derivatives) when computing a search direction. Normally this is a computational heavy task, but if the second order derivatives are constant, which is the case for quadratic equations, a performance gain can be obtained. This is confirmed by a small numerical study.</p><p>Finally, regularization of ill-posed nonlinear least squares problems is considered. The quite well known L-curve for linear least squares problems is put in context for nonlinear problems.</p>

Jobs arriving over time must be non-preemptively processed on one of m parallel machines, each of which running at its own speed, so as to minimize a weighted sum of the job completion times. In this on-line environment, the processing requirement and weight of a job are not known before the job arrives. The Weighted Shortest Processing Requirement (WSPR) on-line heuristic is a simple extension of the well known WSPT heuristic, which is optimal for the single machine problem without release dates. We prove that the WSPR heuristic is asymptotically optimal for all instances with bounded job processing requirements and weights. This implies that the WSPR algorithm generates a solution whose relative error approaches zero as the number of jobs increases. Our proof does not require any probabilistic assumption on the job parameters and relies extensively on properties of optimal solutions to a single machine relaxation of the problem. / Singapore-MIT Alliance (SMA)

Example-based methods are effective for parameter estimation problems when the underlying system is simple or the dimensionality of the input is low. For complex and high-dimensional problems such as pose estimation, the number of required examples and the computational complexity rapidly becme prohibitively high. We introduce a new algorithm that learns a set of hashing functions that efficiently index examples relevant to a particular estimation task. Our algorithm extends a recently developed method for locality-sensitive hashing, which finds approximate neighbors in time sublinear in the number of examples. This method depends critically on the choice of hash functions; we show how to find the set of hash functions that are optimally relevant to a particular estimation problem. Experiments demonstrate that the resulting algorithm, which we call Parameter-Sensitive Hashing, can rapidly and accurately estimate the articulated pose of human figures from a large database of example images.

Tactile and proprioceptive input provided by weighted vests is thought to decrease sensory modulation dysfunction in children with autism. This study investigated behavioural and physiological effects of weighted vests for ten children with autism, ages 3 to 10, in a classroom setting. A single-case, ABCBC design was used where A =behavioural baseline without vest or heart rate monitor; B = unweighted vest and heart rate monitor; C = vest with 5-10% body weight and heart rate monitor. Observers, blinded to treatment condition, rated targeted behaviours for each participant through video taken during structured table-top activities typical of the classroom routine. Teachers, also blinded to treatment condition, rated each childs behaviour with the Conners Global Index following each phase of the study. Educational aides, not blinded to treatment condition, provided subjective feedback about the effects of the weighted vest for each participant. Heart rate was collected when participants wore the vest. Results were mixed regarding the effects of weighted vests for children with autism. Objective data provided evidence to support the use of weighted vests to decrease off-task behaviours with some, but not all, children with autism and sensory modulation dysfunction. Weighted vests did not decrease motoric stereotyped behaviours in any participant, but did decrease verbal stereotyped behaviours in one participant. Heart rate did not decrease with the weighted vest. Subjectively, all aides reported that weighted vests were effective in improving behaviours in all participants at least some of the time. All teachers and aides reported that weighted vests were appropriate modalities to use in the classroom and wanted to continue using weighted vests following the study. Although weighted vests may be an appropriate modality to include as a component of intervention with some children with autism, results were not strong or consistent across participants. The results do not support the use of weighted vests in isolation to improve classroom function in children with autism. / Rehabilitation Science

An important task of information retrieval is to induce classifiers capable of categorizing text documents. The fact that the same document can simultaneously belong to two or more categories is referred by the term multi-label classification (or categorization). Domains of this kind have been encountered in diverse fields even outside information retrieval. This dissertation discusses one challenging aspect of text categorization: the documents (i.e., training examples) are characterized by an extremely large number of features. As a result, many existing machine learning techniques are in such domains prohibitively expensive. This dissertation seeks to reduce these costs significantly. The proposed scheme consists of two steps. The first runs a so-called baseline induction algorithm (BIA) separately on different versions of the data, each time inducing a different subclassifier---more specifically, BIA is run always on the same training documents that are each time described by a different subset of the features. The second step then combines the subclassifiers by a fusion algorithm: when a document is to be classified, each subclassifier outputs a set of class labels accompanied by its confidence in these labels; these outputs are then combined into a single multi-label recommendation. The dissertation investigates a few alternative fusion techniques, including an original one, inspired by the Dempster-Shafer Theory. The main contribution is a mechanism for assigning the mass function to individual labels from subclassifiers. The system's behavior is illustrated on two real-world data sets. As indicated, in each of them the examples are described by thousands of features, and each example is labeled with a subset of classes. Experimental evidence indicates that the method can scale up well and achieves impressive computational savings in exchange for only a modest loss in the classification performance. The fusion method proposed is also shown to be more accurate than other more traditional fusion mechanisms. For a very large multi-label data set, the proposed mechanism not only speeds up the total induction time, but also facilitates the execution of the task on a small computer. The fact that subclassifiers can be constructed independently and more conveniently from small subsets of features provides an avenue for parallel processing that might offer further increase in computational efficiency.

La thèse se situe à la charnière de l'informatique théorique et de la logique mathématique. Elle se concentre en particulier sur les aspects mathématiques de la vérification et du contrôle. La thèse se focalise sur l'étude de deux sous-classes d'automates hybrides: les automates temporisés pondérés et les automates hybrides o-minimaux. Concernant les automates temporisés pondérés, en introduisant un nouvel algorithme, nous donnons une caractérisation exacte de la complexité du problème d'atteignabilité optimal en prouvant qu'il est PSpace-complet. Nous prouvons que le model-checking de la logique WCTL est en général indécidable. Nous nous intéressons alors à une restriction de la logique WCTL. Nous montrons que la décidabilité du model-checking de WCTL restreint dépend de la dimension de l'automate et du fait que le temps soit discret ou dense. Finalement pour, nous prouvons que le problème de contrôle optimal est en général indécidable. Nous prouvons cependant que ce même problème est décidable pour les automates temporisés pondérés de dimension 1. En ce qui concerne les automates hybrides o-minimaux, à l'aide d'un encodage symbolique des trajectoires par des mots, nous sommes parvenus à prouver l'existence d'une bisimulation finie pour ces automates. De plus (toujours en utilisant nos encodages des trajectoires par des mots), nous avons obtenu des résultats de décidabilité pour des problèmes de jeux sur ces mêmes automates hybrides o-minimaux. Pour une classe d'automates hybrides o-minimaux, nous avons prouvé (i) que l'existence de stratégie gagnante pouvait être décidée et (ii) que ces stratégies gagnantes pouvaient être synthétisées.

In this thesis, we present algorithms for local and global minimization of some Procrustes type problems. Typically, these problems are about rotating and scaling a known set of data to fit another set with applications related to determination of rigid body movements, factor analysis and multidimensional scaling. The known sets of data are usually represented as matrices, and the rotation to be determined is commonly a matrix Q with orthonormal columns. The algorithms presented use Newton and Gauss-Newton search directions with optimal step lengths, which in most cases result in a fast computation of a solution. Some of these problems are known to have several minima, e.g., the weighted orthogonal Procrustes problem (WOPP). A study on the maximal amount of minima has been done for this problem. Theoretical results and empirical observations gives strong indications that there are not more than 2n minimizers, where n is the number of columns in Q. A global optimization method to compute all 2n minima is presented. Also considered in this thesis is a cubically convergent iteration method for solving nonlinear equations. The iteration method presented uses second order information (derivatives) when computing a search direction. Normally this is a computational heavy task, but if the second order derivatives are constant, which is the case for quadratic equations, a performance gain can be obtained. This is confirmed by a small numerical study. Finally, regularization of ill-posed nonlinear least squares problems is considered. The quite well known L-curve for linear least squares problems is put in context for nonlinear problems.

We introduce methods for dealing with linear programming (LP) problems with uncertain data, using the notion of weighted analytic centers. Our methods are based on high interaction with the decision maker (DM) and try to find solutions which satisfy most of his/her important criteria/goals. Starting with the drawbacks of different methods for dealing with uncertainty in LP, we explain how our methods improve most of them. We prove that, besides many practical advantages, our approach is theoretically as strong as robust optimization. Interactive cutting-plane algorithms are developed for concave and quasi-concave utility functions. We present some probabilistic bounds for feasibility and evaluate our approach by means of computational experiments.

The literature reviewed on lot-sizing models with random yields is limited to certain random occurrences such as day to day administrative errors, minor machine repairs and random supply due to faulty delivery of parts. In reality however, the manufacturing industry faces other risks that are non random in nature. One example would be yield discrepancies caused by non random triggers such as a change in the production process, product or material. Yield uncertainties of these types are temporary in nature and usually pertain until the system stabilizes. One way of reducing the implications of such events is to have additional batches processed earlier in the production that can absorb the risk associated with the event. In this thesis, this particular approach is referred to as the <i>anticipatory batch insertion</i> to mitigate perceived risk. This thesis presents an exploratory study to analyze the performance of batch insertion under various scenarios. The scenarios are determined by sensitivity of products, schedule characteristics and magnitude of risks associated with causal triggers such as a process change. The results indicate that the highest return from batch insertion can be expected when there are slightly loose production schedules, high volumes of sensitive products are produced, there are high costs associated with the risks, and the risks can be predicted with some degree of certainty.

The literature reviewed on lot-sizing models with random yields is limited to certain random occurrences such as day to day administrative errors, minor machine repairs and random supply due to faulty delivery of parts. In reality however, the manufacturing industry faces other risks that are non random in nature. One example would be yield discrepancies caused by non random triggers such as a change in the production process, product or material. Yield uncertainties of these types are temporary in nature and usually pertain until the system stabilizes. One way of reducing the implications of such events is to have additional batches processed earlier in the production that can absorb the risk associated with the event. In this thesis, this particular approach is referred to as the <i>anticipatory batch insertion</i> to mitigate perceived risk. This thesis presents an exploratory study to analyze the performance of batch insertion under various scenarios. The scenarios are determined by sensitivity of products, schedule characteristics and magnitude of risks associated with causal triggers such as a process change. The results indicate that the highest return from batch insertion can be expected when there are slightly loose production schedules, high volumes of sensitive products are produced, there are high costs associated with the risks, and the risks can be predicted with some degree of certainty.