Given the "right" representation, learning is easy. This thesis studies representation learning and meta-learning, with a special focus on sparse representations. Meta-learning is fundamental to machine learning, and it translates to learning to learn itself. The presentation unfolds in two parts. In the first part, we establish learning theoretic results for learning sparse representations. The second part introduces new multi-task and meta-learning paradigms for representation learning. On the sparse representations front, our main pursuits are generalization error bounds to support a supervised dictionary learning model for Lasso-style sparse coding. Such predictive sparse coding algorithms have been applied with much success in the literature; even more common have been applications of unsupervised sparse coding followed by supervised linear hypothesis learning. We present two generalization error bounds for predictive sparse coding, handling the overcomplete setting (more original dimensions than learned features) and the infinite-dimensional setting. Our analysis led to a fundamental stability result for the Lasso that shows the stability of the solution vector to design matrix perturbations. We also introduce and analyze new multi-task models for (unsupervised) sparse coding and predictive sparse coding, allowing for one dictionary per task but with sharing between the tasks' dictionaries. The second part introduces new meta-learning paradigms to realize unprecedented types of learning guarantees for meta-learning. Specifically sought are guarantees on a meta-learner's performance on new tasks encountered in an environment of tasks. Nearly all previous work produced bounds on the expected risk, whereas we produce tail bounds on the risk, thereby providing performance guarantees on the risk for a single new task drawn from the environment. The new paradigms include minimax multi-task learning (minimax MTL) and sample variance penalized meta-learning (SVP-ML). Regarding minimax MTL, we provide a high probability learning guarantee on its performance on individual tasks encountered in the future, the first of its kind. We also present two continua of meta-learning formulations, each interpolating between classical multi-task learning and minimax multi-task learning. The idea of SVP-ML is to minimize the task average of the training tasks' empirical risks plus a penalty on their sample variance. Controlling this sample variance can potentially yield a faster rate of decrease for upper bounds on the expected risk of new tasks, while also yielding high probability guarantees on the meta-learner's average performance over a draw of new test tasks. An algorithm is presented for SVP-ML with feature selection representations, as well as a quite natural convex relaxation of the SVP-ML objective.

The purpose of this autoethnographic study was to examine three questions: (a) how did my view of myself as a non-Aboriginal educator change as a result of teaching in an Aboriginal cultural context, (b) how did my teaching philosophy and pedagogical approach change as a result of teaching in an Aboriginal cultural context, and (c) how did my sense of community and relatedness to the people I interacted with change due to increased cultural awareness and exposure to Aboriginal cultures? Data from my time in my teacher education program and teaching in Klemtu, BC was collected, and Mezirow’s (1997) transformative learning theory was used to analyze the shift that I made in these three areas. Finally, recommendations were made to teacher education programs and future non-Aboriginal educators who choose to teach in Aboriginal-run schools.

In this thesis, we show results for some well-studied problems from learning theory and combinatorial optimization. Learning Parities under the Uniform Distribution: We study the learnability of parities in the agnostic learning framework of Haussler and Kearns et al. We show that under the uniform distribution, agnostically learning parities reduces to learning parities with random classification noise, commonly referred to as the noisy parity problem. Together with the parity learning algorithm of Blum et al, this gives the first nontrivial algorithm for agnostic learning of parities. We use similar techniques to reduce learning of two other fundamental concept classes under the uniform distribution to learning of noisy parities. Namely, we show that learning of DNF expressions reduces to learning noisy parities of just logarithmic number of variables and learning of k-juntas reduces to learning noisy parities of k variables. Agnostic Learning of Halfspaces: We give an essentially optimal hardness result for agnostic learning of halfspaces over rationals. We show that for any constant ε finding a halfspace that agrees with an unknown function on 1/2+ε fraction of examples is NP-hard even when there exists a halfspace that agrees with the unknown function on 1-ε fraction of examples. This significantly improves on a number of previous hardness results for this problem. We extend the result to ε = 2[superscript-Ω(sqrt{log n})] assuming NP is not contained in DTIME(2[superscript(log n)O(1)]). Majorities of Halfspaces: We show that majorities of halfspaces are hard to PAC-learn using any representation, based on the cryptographic assumption underlying the Ajtai-Dwork cryptosystem. This also implies a hardness result for learning halfspaces with a high rate of adversarial noise even if the learning algorithm can output any efficiently computable hypothesis. Max-Clique, Chromatic Number and Min-3Lin-Deletion: We prove an improved hardness of approximation result for two problems, namely, the problem of finding the size of the largest clique in a graph (also referred to as the Max-Clique problem) and the problem of finding the chromatic number of a graph. We show that for any constant γ > 0, there is no polynomial time algorithm that approximates these problems within factor n/2[superscript(log n)3/4+γ] in an n vertex graph, assuming NP is not contained in BPTIME(2[superscript(log n)O(1)]). This improves the hardness factor of n/2[superscript (log n)1-γ'] for some small (unspecified) constant γ' > 0 shown by Khot. Our main idea is to show an improved hardness result for the Min-3Lin-Deletion problem. An instance of Min-3Lin-Deletion is a system of linear equations modulo 2, where each equation is over three variables. The objective is to find the minimum number of equations that need to be deleted so that the remaining system of equations has a satisfying assignment. We show a hardness factor of 2[superscript sqrt{log n}] for this problem, improving upon the hardness factor of (log n)[superscriptβ] shown by Hastad, for some small (unspecified) constant β > 0. The hardness results for Max-Clique and chromatic number are then obtained using the reduction from Min-3Lin-Deletion as given by Khot. Monotone Multilinear Boolean Circuits for Bipartite Perfect Matching: A monotone Boolean circuit is said to be multilinear if for any AND gate in the circuit, the minimal representation of the two input functions to the gate do not have any variable in common. We show that monotone multilinear Boolean circuits for computing bipartite perfect matching require exponential size. In fact we prove a stronger result by characterizing the structure of the smallest monotone multilinear Boolean circuits for the problem.

Introduction: The purpose of this study was to improve family members' transfer from Intensive Care. A structured pre-transfer educational method of patient transfer was introduced and evaluated. Background of the study: Many studies have documented the needs of family members whilst in intensive care units (ICU) but few have evaluated interventions to support meeting these needs. No studies have documented 'uncertainty in illness' levels of family members around transfer from ICU or the relationship between uncertainty and anxiety. Method: The study used a quasi-experimental pre-test, post-test non-equivalent control group design based on the General System Theory (von Bertalanffy, 1972). There were four phases to the study with the intervention grounded in Knowles' Adult Learning Theory (1980). Family members of patients in an ICU were purposively allocated to a control(n = 80) and intervention group (n = 82). A pre-test, post-test strategy was used with data from the control group collected first and once completed, the intervention was introduced into the ICU. The intervention group data were then collected using the same data collection tools. The intervention group experienced a transfer method designed to improve communication with the bedside nurse in ICU whereas the control group received existing ad hoc transfer methods. Participants were surveyed before and after transfer using Spielberger et al.'s state anxiety inventory and Mishel's 'uncertainty in illness' scale. Demographic data were collected for both patients and family members together with family members' satisfaction with the transfer process they experienced. At the completion of the study, intensive care nurses (n = 40) were surveyed to assess their perception of the efficacy of the intervention. Results: Three factors were found to significantly affect levels of 'uncertainty in illness' and these included state anxiety scores (F = 50.9, p < .000), the relationship of the family member to the patient (F = 2.9, p = .022), and the unexpected nature of the admission (F = 23.09, p < .000). These factors accounted for 33% of the variance of 'uncertainty in illness' scores. State anxiety levels were significantly affected by the degree of family social support (F = 10.0, p = .002) and uncertainty as previously mentioned. State anxiety reduced significantly following transfer for both groups and 'uncertainty in illness' reduced significantly for the intervention group (t = 2.21, p = .03).When controlled for pre-transfer levels, however, there was no significant reduction in the intervention group when compared with the control group.' Uncertainty in illness' for the intervention group reduced, however, whereas scores for the control group did not. The intervention group experienced significantly higher levels of satisfaction with transfer (Z = -2.43, p = .015) and felt significantly better prepared for transfer(Z = -3.26, p = .001) than did the control group. The vast majority of ICU nurses(90.6%) thought the intervention provided a useful framework for discussing the patient's condition with family members and 94% thought it should be introduced for all transfers from ICU. Conclusions: Uncertainty is significantly related to state anxiety in this sample. Previous research suggests that individual's coping ability is affected by both anxiety and' uncertainty in illness' which limit their adaptation to the new ward situation. This results in relationship disturbances and psychological distress (Mishel, 1981)at a time when patients rely on family support. The intervention reduced uncertainty and improved family members' satisfaction with the transfer process by improved communication between family members and ICU nurses. The intervention was fully endorsed and supported by ICU nurses who recommended its introduction for all future transfers.

Among student modelling researches, domain-independent student models have usually been a rarity. They are valued because of reusability and economy. The demand on domain-independent student models is further increased by the need to stay competitive in the so-called knowledge economy nowadays and the widespread practice of lifelong learning. On the other hand, the popularity of student-oriented pedagogy triggers the need to provide cognitive support in virtual learning environments which in turn requires student models that create cognitive profiles of students. This study offers an innovative student modelling approach called cognitive trait model (CTM) to address both the needs mentioned above. CTM is a domain-independent and persistent student model that goes beyond traditional concept of student model. It is capable of taking the role of a learning companion who knows about the cognitive traits of the student and can supply this information when the student first starts using a new learning system. The behaviour of the students in the learning systems can then be used to update CTM. Three cognitive traits are included in the CTM in this study, they are working memory capacity, inductive reasoning ability and divergent associative learning. For the three cognitive traits, their domain-independence and persistence are studied and defined, their characteristics are examined, and behaviour patterns that can be used to indicate them are extracted. In this study, a learning system is developed to gather behaviour data of students. Several web-based psychometric tools are also developed to gather the psychometric data about the three cognitive traits of students. In the evaluations, Cognitive trait modelling is then applied on the behaviour data and the results are compared with the psychometric data. The findings prove the effectiveness of CTM and reveal important insights about the three cognitive traits.

Thesis (M.A.)--University of Melbourne, Dept. of History, 2007. / Typescript. Includes bibliographical references (leaves 62-68).

Thesis (M.A.)--Miami University, Dept. of Communication, 2008. / Title from first page of PDF document. Includes bibliographical references (p. 43-45).

Thesis (Ph. D.)--State University of New York at Binghamton, Thomas J. Watson School of Engineering and Applied Science, Department of Systems Science and Industrial Engineering, 2009. / Includes bibliographical references.

La notion de métrique joue un rôle clef dans les problèmes d’apprentissage automatique tels que la classification, le clustering et le ranking. L’apprentissage à partir de données de métriques adaptées à une tâche spécifique a suscité un intérêt croissant ces dernières années. Ce domaine vise généralement à trouver les meilleurs paramètres pour une métrique donnée sous certaines contraintes imposées par les données. La métrique apprise est utilisée dans un algorithme d’apprentissage automatique dans le but d’améliorer sa performance. La plupart des méthodes d’apprentissage de métriques optimisent les paramètres d’une distance de Mahalanobis pour des vecteurs de features. Les méthodes actuelles de l’état de l’art arrivent à traiter des jeux de données de tailles significatives. En revanche, le sujet plus complexe des séries temporelles multivariées n’a reçu qu’une attention limitée, malgré l’omniprésence de ce type de données dans les applications réelles. Une importante partie de la recherche sur les séries temporelles est basée sur la dynamic time warping (DTW), qui détermine l’alignement optimal entre deux séries temporelles. L’état actuel de l’apprentissage de métriques souffre de certaines limitations. La plus importante est probablement le manque de garanties théoriques concernant la métrique apprise et sa performance pour la classification. La théorie des fonctions de similarité (ℰ , ϓ, T)-bonnes a été l’un des premiers résultats liant les propriétés d’une similarité à celles du classifieur qui l’utilise. Une deuxième limitation vient du fait que la plupart des méthodes imposent des propriétés de distance, qui sont coûteuses en terme de calcul et souvent non justifiées. Dans cette thèse, nous abordons les limitations précédentes à travers deux contributions principales. La première est un nouveau cadre général pour l’apprentissage conjoint d’une fonction de similarité et d’un classifieur linéaire. Cette formulation est inspirée de la théorie de similarités (ℰ , ϓ, τ) -bonnes, fournissant un lien entre la similarité et le classifieur linéaire. Elle est convexe pour une large gamme de fonctions de similarité et de régulariseurs. Nous dérivons deux bornes de généralisation équivalentes à travers les cadres de robustesse algorithmique et de convergence uniforme basée sur la complexité de Rademacher, prouvant les propriétés théoriques de notre formulation. Notre deuxième contribution est une méthode d’apprentissage de similarités basée sur DTW pour la classification de séries temporelles multivariées. Le problème est convexe et utilise la théorie des fonctions (ℰ , ϓ, T)-bonnes liant la performance de la métrique à celle du classifieur linéaire associé. A l’aide de la stabilité uniforme, nous prouvons la consistance de la similarité apprise conduisant à la dérivation d’une borne de généralisation. / The notion of metric plays a key role in machine learning problems, such as classification, clustering and ranking. Learning metrics from training data in order to make them adapted to the task at hand has attracted a growing interest in the past years. This research field, known as metric learning, usually aims at finding the best parameters for a given metric under some constraints from the data. The learned metric is used in a machine learning algorithm in hopes of improving performance. Most of the metric learning algorithms focus on learning the parameters of Mahalanobis distances for feature vectors. Current state of the art methods scale well for datasets of significant size. On the other hand, the more complex topic of multivariate time series has received only limited attention, despite the omnipresence of this type of data in applications. An important part of the research on time series is based on the dynamic time warping (DTW) computing the optimal alignment between two time series. The current state of metric learning suffers from some significant limitations which we aim to address in this thesis. The most important one is probably the lack of theoretical guarantees for the learned metric and its performance for classification.The theory of (ℰ , ϓ, τ)-good similarity functions has been one of the first results relating the properties of a similarity to its classification performance. A second limitation in metric learning comes from the fact that most methods work with metrics that enforce distance properties, which are computationally expensive and often not justified. In this thesis, we address these limitations through two main contributions. The first one is a novel general framework for jointly learning a similarity function and a linear classifier. This formulation is inspired from the (ℰ , ϓ, τ)-good theory, providing a link between the similarity and the linear classifier. It is also convex for a broad range of similarity functions and regularizers. We derive two equivalent generalization bounds through the frameworks of algorithmic robustness and uniform convergence using the Rademacher complexity, proving the good theoretical properties of our framework. Our second contribution is a method for learning similarity functions based on DTW for multivariate time series classification. The formulation is convex and makes use of the(ℰ , ϓ, τ)-good framework for relating the performance of the metric to that of its associated linear classifier. Using uniform stability arguments, we prove the consistency of the learned similarity leading to the derivation of a generalization bound.

This study emerged from a desire to put to an end the crisis mentality surrounding the status of History as a subject in the secondary school. There appears to be consensus amongst didactitions and practitioners of the subject that the present malaise from which History teaching suffers derives from a number of complex sources. The study, however, takes as its point of departure the problem of the content orientated (product) syllabus which over-emphasises the acquisition of factual information and neglects the conceptual understanding (process) of the subject. Experience is providing the futility of teaching only content (information) to the modern adolescent. Therefore in order to resolve the problem the study focuses, inter alia, on concepts, structures and syllabuses. It is concluded that all subjects are based on conceptual structures which, in turn, have a direct bearing on the authentic education of pupils in general and conceptualization in particular. It is suggested, therefore, that historical content (product) can only have formative value if it is harnessed to facilitate conceptualization (process). Towards this end a History syllabus which embraces both the product and process approaches is advocated for implementation. In essence this means that the content of History is organised around concepts, that is, relevant concepts are chosen as themes around which the syllabus content is structured. Such an approach, it is believed, would not only help to develop universally valid generalizations but also facilitate the conceptualization process necessary for obtaining historical insight. A model, with examples, is presented as a suggestion for implementation in the classroom. Altenative proposals are also mentioned. If historical conceptualization is to be effevively realised in the classroom, then it becomes necessary to obtain a perspective on the learning-psychological processes involved in conceptualization. In this regard, specific theoris are highlighted to guide the History teacher in the classroom. Ti is finally hoped that the new approach suggested would assist teachers, at least to some extent, to resolve the problem of conceptualization in History teaching and thereby help to store the subject to its original position of respect in the school curriculum / Curriculum and Instructional Studies / D.Ed. (Didactics)