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)

abstract: A core reform area of President Obama’s Race to the Top (RTT) framework, the Statewide Longitudinal Data Systems (SLDS) program, offered funding to states for the development of their own data systems. As a result, Arizona received funding to build a longitudinal student data system. However the targeted audience—teachers—needed training to move from a state of ‘data rich but information poor’ to one of developing actionable knowledge. In this mixed methods action research study, six teachers from three schools participated in job-embedded data-informed decision making (DIDM) and root cause analysis (RCA) professional development to improve their abilities to employ DIDM and RCA strategies to determine root causes for student achievement gaps. This study was based on the theories of situated learning, specifically the concept of communities of practice (CoP), change theory, and the Concerns-Based Adoption Model (CBAM). Because teachers comprise most of the workforce in a district, it is important to encourage them to shift from working in isolation to effectively implement and sustain changes in practice. To address this concern, an online wiki provided an avenue for participants to interact, reflect, and share experiences across schools as they engaged in the application of new learning. The results from this ten-week study indicated an increase in participant readiness levels to: (a) use and manage data sources, (b) apply strategies, and (c) collaborate with others to solve problems of practice. Results also showed that participants engaged in collaborative conversation using the online wiki when they wanted to share concerns or gain further information to make decisions. The online collaboration results indicated higher levels of online discussion occurred when participants were attempting to solve a problem of practice during the learning process. Overall, participants (a) used collaborative strategies to seek, create, and/or utilize multiple sources of data, not just student learning data, (b) worked through implementation challenges when making changes in practice, and (c) sought further types of data collection to inform their decisions about root causes. Implications from this study warrant further investigation into the use of an online CoP as an avenue for increasing teacher collaboration across schools. / Dissertation/Thesis / Doctoral Dissertation Leadership and Innovation 2016

abstract: According to national data, there continues to be an ongoing achievement gap between students with disabilities and their non-disabled peers (USDE, n.d.b). This data is representative of a continued disparity in academic performance for students in local Arizona school districts. To address this gap, many districts have implemented inclusion models in which students with disabilities spend increasing amounts of time in general education classrooms, in some cases for the majority of or all of their school day. However, the persistence of the achievement gap suggests that general education teachers working in inclusion models may be lacking systematic instructional methods for ensuring access to the curriculum for those with disabilities and other diverse learning needs. The purpose of this action research study was to examine the impact that a series of professional development workshops had on teacher beliefs and understanding of disability, intelligence, and accessible pedagogy. The study was conducted over the course of a school semester at a kindergarten through 8th grade school in a large, semi-rural school district in southeastern Arizona. Ten teachers from a variety of grade levels and subject areas participated in the study along with a school psychologist and two school administrators. Theoretical frameworks guiding this project included critical disability theory, growth mindset, universal design for learning, and transformative learning theory. A mixed-methods action research approach was used to collect both qualitative and quantitative data in the form of surveys, interviews, and written reflections. The workshop series included five modules that began with activities fostering critical reflection of assumptions regarding disability and intelligence and ended with pedagogical strategies in the form of universal design for learning. The results indicate that the innovation was successful in reshaping participant views of disability, intelligence, and pedagogy; however, changes in classroom instruction were small. Implications for future research and practice include more extended sessions on universal design for learning and a more diverse sample of participants. Workshop sessions utilized a variety of active learning activities that were well received by participants and will be included in future professional learning plans across the district. / Dissertation/Thesis / Doctoral Dissertation Leadership and Innovation 2018