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.

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.

Supportive-expressive group therapy for women with metastatic breast cancer: Improving access for Australian women through use of teleconference

While supportive-expressive group therapy (SEGT) has been found to be effective in significantly reducing distress associated with life-threatening illness, the challenge in Australia is to develop a means of providing supportive interventions to rural women who may be isolated both by the experience of illness and by geographical location. In this study an adaptation of SEGT was provided to women with metastatic breast cancer (n =21), who attended face-to-face or by telephone conference call. Participants showed significant gains on standardised measures of well-being, including a reduction in negative affect and an increase in positive affect, over a 12-month period. A reduction in intrusive and avoidant stress symptoms was also observed over 12 months; however, this difference was not significant. These outcomes suggest that SEGT, delivered in an innovative way within a community setting, may be an effective means of moderating the adverse effects of a diagnosis of metastatic breast cancer while improving access to supportive care for rural women. These results are considered exploratory, as the study did not include a matched control group.

Stochastic models for regulatory networks of the genetic toggle switch

Bistability arises within a wide range of biological systems from the λ phage switch in bacteria to cellular signal transduction pathways in mammalian cells. Changes in regulatory mechanisms may result in genetic switching in a bistable system. Recently, more and more experimental evidence in the form of bimodal population distributions indicates that noise plays a very important role in the switching of bistable systems. Although deterministic models have been used for studying the existence of bistability properties under various system conditions, these models cannot realize cell-to-cell fluctuations in genetic switching. However, there is a lag in the development of stochastic models for studying the impact of noise in bistable systems because of the lack of detailed knowledge of biochemical reactions, kinetic rates, and molecular numbers. In this work, we develop a previously undescribed general technique for developing quantitative stochastic models for large-scale genetic regulatory networks by introducing Poisson random variables into deterministic models described by ordinary differential equations. Two stochastic models have been proposed for the genetic toggle switch interfaced with either the SOS signaling pathway or a quorum-sensing signaling pathway, and we have successfully realized experimental results showing bimodal population distributions. Because the introduced stochastic models are based on widely used ordinary differential equation models, the success of this work suggests that this approach is a very promising one for studying noise in large-scale genetic regulatory networks.

Intermittent access to 20% ethanol induces high ethanol consumption in Long-Evans and Wistar rats

BACKGROUND: There has been some difficulty getting standard laboratory rats to voluntarily consume large amounts of ethanol without the use of initiation procedures. It has previously been shown that standard laboratory rats will voluntarily consume high levels of ethanol if given intermittent-access to 20% ethanol in a 2-bottle-choice setting [Wise, Psychopharmacologia 29 (1973), 203]. In this study, we have further characterized this drinking model. METHODS: Ethanol-naïve Long-Evans rats were given intermittent-access to 20% ethanol (three 24-hour sessions per week). No sucrose fading was needed and water was always available ad libitum. Ethanol consumption, preference, and long-term drinking behaviors were investigated. Furthermore, to pharmacologically validate the intermittent-access 20% ethanol drinking paradigm, the efficacy of acamprosate and naltrexone in decreasing ethanol consumption were compared with those of groups given continuous-access to 10 or 20% ethanol, respectively. Additionally, ethanol consumption was investigated in Wistar and out-bred alcohol preferring (P) rats following intermittent-access to 20% ethanol. RESULTS: The intermittent-access 20% ethanol 2-bottle-choice drinking paradigm led standard laboratory rats to escalate their ethanol intake over the first 5 to 6 drinking sessions, reaching stable baseline consumption of high amounts of ethanol (Long-Evans: 5.1 +/- 0.6; Wistar: 5.8 +/- 0.8 g/kg/24 h, respectively). Furthermore, the cycles of excessive drinking and abstinence led to an increase in ethanol preference and increased efficacy of both acamprosate and naltrexone in Long-Evans rats. P-rats initiate drinking at a higher level than both Long-Evans and Wistar rats using the intermittent-access 20% ethanol paradigm and showed a trend toward a further escalation in ethanol intake over time (mean ethanol intake: 6.3 +/- 0.8 g/kg/24 h). CONCLUSION: Standard laboratory rats will voluntarily consume ethanol using the intermittent-access 20% ethanol drinking paradigm without the use of any initiation procedures. This model promises to be a valuable tool in the alcohol research field.

An approach to access control under uncertainty

In dynamic and uncertain environments such as healthcare, where the needs of security and information availability are difficult to balance, an access control approach based on a static policy will be suboptimal regardless of how comprehensive it is. The uncertainty stems from the unpredictability of users’ operational needs as well as their private incentives to misuse permissions. In Role Based Access Control (RBAC), a user’s legitimate access request may be denied because its need has not been anticipated by the security administrator. Alternatively, even when the policy is correctly specified an authorised user may accidentally or intentionally misuse the granted permission. This paper introduces a novel approach to access control under uncertainty and presents it in the context of RBAC. By taking insights from the field of economics, in particular the insurance literature, we propose a formal model where the value of resources are explicitly defined and an RBAC policy (entailing those predictable access needs) is only used as a reference point to determine the price each user has to pay for access, as opposed to representing hard and fast rules that are always rigidly applied.

Optimal budget allocation in budget-based access control

In dynamic and uncertain environments, where the needs of security and information availability are difficult to balance, an access control approach based on a static policy will be suboptimal regardless of how comprehensive it is. Risk-based approaches to access control attempt to address this problem by allocating a limited budget to users, through which they pay for the exceptions deemed necessary. So far the primary focus has been on how to incorporate the notion of budget into access control rather than what or if there is an optimal amount of budget to allocate to users. In this paper we discuss the problems that arise from a sub-optimal allocation of budget and introduce a generalised characterisation of an optimal budget allocation function that maximises organisations expected benefit in the presence of self-interested employees and costly audit.

Computational approaches for modelling intrinsic noise and delays in genetic regulatory networks

This chapter focuses on the interactions and roles between delays and intrinsic noise effects within cellular pathways and regulatory networks. We address these aspects by focusing on genetic regulatory networks that share a common network motif, namely the negative feedback loop, leading to oscillatory gene expression and protein levels. In this context, we discuss computational simulation algorithms for addressing the interplay of delays and noise within the signaling pathways based on biological data. We address implementational issues associated with efficiency and robustness. In a molecular biology setting we present two case studies of temporal models for the Hes1 gene (Monk, 2003; Hirata et al., 2002), known to act as a molecular clock, and the Her1/Her7 regulatory system controlling the periodic somite segmentation in vertebrate embryos (Giudicelli and Lewis, 2004; Horikawa et al., 2006).

Emergent task-specific object semantics through distributed experience networks

Autonomous development of sensorimotor coordination enables a robot to adapt and change its action choices to interact with the world throughout its lifetime. The Experience Network is a structure that rapidly learns coordination between visual and haptic inputs and motor action. This paper presents methods which handle the high dimensionality of the network state-space which occurs due to the simultaneous detection of multiple sensory features. The methods provide no significant increase in the complexity of the underlying representations and also allow emergent, task-specific, semantic information to inform action selection. Experimental results show rapid learning in a real robot, beginning with no sensorimotor mappings, to a mobile robot capable of wall avoidance and target acquisition.

Evolving noisy oscillatory dynamics in genetic regulatory networks

We introduce a genetic programming (GP) approach for evolving genetic networks that demonstrate desired dynamics when simulated as a discrete stochastic process. Our representation of genetic networks is based on a biochemical reaction model including key elements such as transcription, translation and post-translational modifications. The stochastic, reaction-based GP system is similar but not identical with algorithmic chemistries. We evolved genetic networks with noisy oscillatory dynamics. The results show the practicality of evolving particular dynamics in gene regulatory networks when modelled with intrinsic noise.