The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network

Sample complexity results from computational learning theory, when applied to neural network learning for pattern classification problems, suggest that for good generalization performance the number of training examples should grow at least linearly with the number of adjustable parameters in the network. Results in this paper show that if a large neural network is used for a pattern classification problem and the learning algorithm finds a network with small weights that has small squared error on the training patterns, then the generalization performance depends on the size of the weights rather than the number of weights. For example, consider a two-layer feedforward network of sigmoid units, in which the sum of the magnitudes of the weights associated with each unit is bounded by A and the input dimension is n. We show that the misclassification probability is no more than a certain error estimate (that is related to squared error on the training set) plus A3 √((log n)/m) (ignoring log A and log m factors), where m is the number of training patterns. This may explain the generalization performance of neural networks, particularly when the number of training examples is considerably smaller than the number of weights. It also supports heuristics (such as weight decay and early stopping) that attempt to keep the weights small during training. The proof techniques appear to be useful for the analysis of other pattern classifiers: when the input domain is a totally bounded metric space, we use the same approach to give upper bounds on misclassification probability for classifiers with decision boundaries that are far from the training examples.

Boosting the margin: A new explanation for the effectiveness of voting methods

One of the surprising recurring phenomena observed in experiments with boosting is that the test error of the generated classifier usually does not increase as its size becomes very large, and often is observed to decrease even after the training error reaches zero. In this paper, we show that this phenomenon is related to the distribution of margins of the training examples with respect to the generated voting classification rule, where the margin of an example is simply the difference between the number of correct votes and the maximum number of votes received by any incorrect label. We show that techniques used in the analysis of Vapnik's support vector classifiers and of neural networks with small weights can be applied to voting methods to relate the margin distribution to the test error. We also show theoretically and experimentally that boosting is especially effective at increasing the margins of the training examples. Finally, we compare our explanation to those based on the bias-variance decomposition.

Rademacher and Gaussian complexities: Risk bounds and structural results

We investigate the use of certain data-dependent estimates of the complexity of a function class, called Rademacher and Gaussian complexities. In a decision theoretic setting, we prove general risk bounds in terms of these complexities. We consider function classes that can be expressed as combinations of functions from basis classes and show how the Rademacher and Gaussian complexities of such a function class can be bounded in terms of the complexity of the basis classes. We give examples of the application of these techniques in finding data-dependent risk bounds for decision trees, neural networks and support vector machines.

Learning and teaching from the edge to centre stage : Critical factors in embedding sustainable university-wide engagement in external awards and grants funding initiatives.

Teaching awards, grants and fellowships are strategies used to recognise outstanding contributions to learning and teaching, encourage innovation, and to shift learning and teaching from the edge to centre stage. Examples range from school, faculty and institutional award and grant schemes to national schemes such as those offered by the Australian Learning and Teaching Council (ALTC), the Carnegie Foundation for the Advancement of Teaching in the United States, and the Fund for the Development of Teaching and Learning in higher education in the United Kingdom. The Queensland University of Technology (QUT) has experienced outstanding success in all areas of the ALTC funding since the inception of the Carrick Institute for Learning and Teaching in 2004. This paper reports on a study of the critical factors that have enabled sustainable and resilient institutional engagement with ALTC programs. As a lens for examining the QUT environment and practices, the study draws upon the five conditions of the framework for effective dissemination of innovation developed by Southwell, Gannaway, Orrell, Chalmers and Abraham (2005, 2010): 1. Effective, multi-level leadership and management 2. Climate of readiness for change 3. Availability of resources 4. Comprehensive systems in institutions and funding bodies 5. Funding design The discussion on the critical factors and practical and strategic lessons learnt for successful university-wide engagement offer insights for university leaders and staff who are responsible for learning and teaching award, grant and associated internal and external funding schemes.

Exponentiated gradient algorithms for conditional random fields and max-margin Markov Networks

Log-linear and maximum-margin models are two commonly-used methods in supervised machine learning, and are frequently used in structured prediction problems. Efficient learning of parameters in these models is therefore an important problem, and becomes a key factor when learning from very large data sets. This paper describes exponentiated gradient (EG) algorithms for training such models, where EG updates are applied to the convex dual of either the log-linear or max-margin objective function; the dual in both the log-linear and max-margin cases corresponds to minimizing a convex function with simplex constraints. We study both batch and online variants of the algorithm, and provide rates of convergence for both cases. In the max-margin case, O(1/ε) EG updates are required to reach a given accuracy ε in the dual; in contrast, for log-linear models only O(log(1/ε)) updates are required. For both the max-margin and log-linear cases, our bounds suggest that the online EG algorithm requires a factor of n less computation to reach a desired accuracy than the batch EG algorithm, where n is the number of training examples. Our experiments confirm that the online algorithms are much faster than the batch algorithms in practice. We describe how the EG updates factor in a convenient way for structured prediction problems, allowing the algorithms to be efficiently applied to problems such as sequence learning or natural language parsing. We perform extensive evaluation of the algorithms, comparing them to L-BFGS and stochastic gradient descent for log-linear models, and to SVM-Struct for max-margin models. The algorithms are applied to a multi-class problem as well as to a more complex large-scale parsing task. In all these settings, the EG algorithms presented here outperform the other methods.

Matrix regularization techniques for online multitask learning

In this paper we examine the problem of prediction with expert advice in a setup where the learner is presented with a sequence of examples coming from different tasks. In order for the learner to be able to benefit from performing multiple tasks simultaneously, we make assumptions of task relatedness by constraining the comparator to use a lesser number of best experts than the number of tasks. We show how this corresponds naturally to learning under spectral or structural matrix constraints, and propose regularization techniques to enforce the constraints. The regularization techniques proposed here are interesting in their own right and multitask learning is just one application for the ideas. A theoretical analysis of one such regularizer is performed, and a regret bound that shows benefits of this setup is reported.

Relative entropy rate based design for linear hybrid system models

Hybrid system representations have been applied to many challenging modeling situations. In these hybrid system representations, a mixture of continuous and discrete states is used to capture the dominating behavioural features of a nonlinear, possible uncertain, model under approximation. Unfortunately, the problem of how to best design a suitable hybrid system model has not yet been fully addressed. This paper proposes a new joint state measurement relative entropy rate based approach for this design purpose. Design examples and simulation studies are presented which highlight the benefits of our proposed design approaches.

Co-constructing self-efficacy narratives : a study of four mature age university students

This thesis reports on a study in which research participants, four mature aged females starting an undergraduate degree at a regional Australian university, collaborated with the researcher in co-constructing a self-efficacy narrative. For the purpose of the study, self-efficacy was conceptualized as a means by which an individual initiates action to engage in a task or set of tasks, applies effort to perform the task or set of tasks, and persists in the face of obstacles encountered in order to achieve successful completion of the task or set of tasks. Qualitative interviews were conducted with the participants, initially investigating their respective life histories for an understanding of how they made the decision to embark on their respective academic program. Additional data were generated from a written exercise, prompting participants to furnish specific examples of self-efficacy. These data were incorporated into the individual's self-efficacy narrative, produced as the outcome of the "narrative analysis". Another aspect of the study entailed "analysis of narrative" in which analytic procedures were used to identify themes common to the self-efficacy narratives. Five main themes were identified: (a) participants' experience of schooling . for several participants their formative experience of school was not always positive, and yet their narratives demonstrated their agency in persevering and taking on university-level studies as mature aged persons; (b) recognition of family as an early influence . these influences were described as being both positive, in the sense of being supportive and encouraging, as well as posing obstacles that participants had to overcome in order to pursue their goals; (c) availability of supportive persons – the support of particular persons was acknowledged as a factor that enabled participants to persist in their respective endeavours; (d) luck or chance factors were recognised as placing participants at the right place at the right time, from which circumstances they applied considerable effort in order to convert the opportunity into a successful outcome; and (e) self-efficacy was identified as a major theme found in the narratives. The study included an evaluation of the research process by participants. A number of themes were identified in respect of the manner in which the research process was experienced as a helpful process. Participants commented that: (a) the research process was helpful in clarifying their respective career goals; (b) they appreciated opportunities provided by the research process to view their life from a different perspective and to better understand what motivated them, and what their preferred learning styles were; (c) their past successes in a range of different spheres were made more evident to them as they were guided in self-reflection, and their self-efficacious behaviour was affirmed; and (d) the opportunities provided by their participation in the research process to identify strengths of which they had not been consciously aware, to find confirmation of strengths they knew they possessed, and in some instances to rectify misconceptions they had held about aspects of their personality. The study made three important contributions to knowledge. Firstly, it provided a detailed explication of a qualitative narrative method in exploring self-efficacy, with the potential for application to other issues in educational, counselling and psychotherapy research. Secondly, it consolidated and illustrated social cognitive theory by proposing a dynamic model of self-efficacy, drawing on constructivist and interpretivist paradigms and extending extant theory and models. Finally, the study made a contribution to the debate concerning the nexus of qualitative research and counselling by providing guidelines for ethical practice in both endeavours for the practitioner-researcher.

Robotics, Vision and Control : Fundamental Algorithms in MATLAB

The practice of robotics and computer vision each involve the application of computational algorithms to data. The research community has developed a very large body of algorithms but for a newcomer to the field this can be quite daunting. For more than 10 years the author has maintained two open-source MATLAB® Toolboxes, one for robotics and one for vision. They provide implementations of many important algorithms and allow users to work with real problems, not just trivial examples. This new book makes the fundamental algorithms of robotics, vision and control accessible to all. It weaves together theory, algorithms and examples in a narrative that covers robotics and computer vision separately and together. Using the latest versions of the Toolboxes the author shows how complex problems can be decomposed and solved using just a few simple lines of code. The topics covered are guided by real problems observed by the author over many years as a practitioner of both robotics and computer vision. It is written in a light but informative style, it is easy to read and absorb, and includes over 1000 MATLAB® and Simulink® examples and figures. The book is a real walk through the fundamentals of mobile robots, navigation, localization, arm-robot kinematics, dynamics and joint level control, then camera models, image processing, feature extraction and multi-view geometry, and finally bringing it all together with an extensive discussion of visual servo systems.

Practical stability with respect to model mismatch of approximate discrete-time output feedback control

This paper establishes a practical stability result for discrete-time output feedback control involving mismatch between the exact system to be stabilised and the approximating system used to design the controller. The practical stability is in the sense of an asymptotic bound on the amount of error bias introduced by the model approximation, and is established using local consistency properties of the systems. Importantly, the practical stability established here does not require the approximating system to be of the same model type as the exact system. Examples are presented to illustrate the nature of our practical stability result.

Exploiting the 1,2,3-triazolium motif in anion-templated formation of a bromide-selective rotaxane host assembly

Stimulated by the efficacy of copper (I) catalysed Huisgen-type 1,3-dipolar cycloaddition of terminal alkynes and organic azides to generate 1,4-disubstituted 1,2,3-triazole derivatives, the importance of ‘click’ chemistry in the synthesis of organic and biological molecular systems is ever increasing.[1] The mild reaction conditions have also led to this reaction gaining favour in the construction of interlocked molecular architectures.[2-4] In the majority of cases however, the triazole group simply serves as a covalent linkage with no function in the resulting organic molecular framework. More recently a renewed interest has been shown in the transition metal coordination chemistry of triazole ligands.[3, 5, 6] In addition novel aryl macrocyclic and acyclic triazole based oligomers have been shown to recognise halide anions via cooperative triazole C5-H….anion hydrogen bonds.[7] In light of this it is surprising the potential anion binding affinity of the positively charged triazolium motif has not, with one notable exception,[8] been investigated. With the objective of manipulating the unique topological cavities of mechanically bonded molecules for anion recognition purposes, we have developed general methods of using anions to template the formation of interpenetrated and interlocked structures.[9-13] Herein we report the first examples of exploiting the 1,2,3-triazolium group in the anion templated formation of pseudorotaxane and rotaxane assemblies. In an unprecedented discovery the bromide anion is shown to be a superior templating reagent to chloride in the synthesis of a novel triazolium axle containing [2]rotaxane. Furthermore the resulting rotaxane interlocked host system exhibits the rare selectivity preference for bromide over chloride...

On the data consumption benefits of accepting increased uncertainty

In the context of learning paradigms of identification in the limit, we address the question: why is uncertainty sometimes desirable? We use mind change bounds on the output hypotheses as a measure of uncertainty and interpret ‘desirable’ as reduction in data memorization, also defined in terms of mind change bounds. The resulting model is closely related to iterative learning with bounded mind change complexity, but the dual use of mind change bounds — for hypotheses and for data — is a key distinctive feature of our approach. We show that situations exist where the more mind changes the learner is willing to accept, the less the amount of data it needs to remember in order to converge to the correct hypothesis. We also investigate relationships between our model and learning from good examples, set-driven, monotonic and strong-monotonic learners, as well as class-comprising versus class-preserving learnability.

Demand-compliant design

In this paper, we describe, in detail, a design method that assures that the designed product satisfies a set of prescribed demands while, at the same time, providing a concise representation of the design that facilitates communication in multidisciplinary design teams. This Demand Compliant Design (DeCoDe) method was in itself designed to comply with a set of demands. The demands on the method were determined by an analysis of some of the most widely used design methods and from the needs arising in the practice of design for quality. We show several modes of use of the DeCoDe method and illustrate with examples.

Sulfate anion templation of macrocycles, capsules, interpenetrated and interlocked structures

This review examines the potential of anions, in particular sulfate, to template the formation of complex molecular architectures. Until recently, sulfate has been largely overlooked in this area and the examples described herein demonstrate this anion’s versatility in templating the formation of a diverse range of molecular systems including macrocycles, helixes, molecular capsules, interpenetrated and interlocked assemblies such as catenanes. In addition sulfate has been shown to template the formation of interpenetrated structures on a range of solid surfaces including gold, polystyrene beads and silicate nanoparticles, highlighting the potential of this anion in the fabrication of functional sensory devices exhibiting highly selective binding behaviour.

The Bayesian conditional independence model for measurement error: applications in ecology

The measurement error model is a well established statistical method for regression problems in medical sciences, although rarely used in ecological studies. While the situations in which it is appropriate may be less common in ecology, there are instances in which there may be benefits in its use for prediction and estimation of parameters of interest. We have chosen to explore this topic using a conditional independence model in a Bayesian framework using a Gibbs sampler, as this gives a great deal of flexibility, allowing us to analyse a number of different models without losing generality. Using simulations and two examples, we show how the conditional independence model can be used in ecology, and when it is appropriate.