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.

Convexity, Classification, and Risk Bounds

Many of the classification algorithms developed in the machine learning literature, including the support vector machine and boosting, can be viewed as minimum contrast methods that minimize a convex surrogate of the 0–1 loss function. The convexity makes these algorithms computationally efficient. The use of a surrogate, however, has statistical consequences that must be balanced against the computational virtues of convexity. To study these issues, we provide a general quantitative relationship between the risk as assessed using the 0–1 loss and the risk as assessed using any nonnegative surrogate loss function. We show that this relationship gives nontrivial upper bounds on excess risk under the weakest possible condition on the loss function—that it satisfies a pointwise form of Fisher consistency for classification. The relationship is based on a simple variational transformation of the loss function that is easy to compute in many applications. We also present a refined version of this result in the case of low noise, and show that in this case, strictly convex loss functions lead to faster rates of convergence of the risk than would be implied by standard uniform convergence arguments. Finally, we present applications of our results to the estimation of convergence rates in function classes that are scaled convex hulls of a finite-dimensional base class, with a variety of commonly used loss functions.

On the consistency of multiclass classification methods

Binary classification methods can be generalized in many ways to handle multiple classes. It turns out that not all generalizations preserve the nice property of Bayes consistency. We provide a necessary and sufficient condition for consistency which applies to a large class of multiclass classification methods. The approach is illustrated by applying it to some multiclass methods proposed in the literature.

Classification with a reject option using a hinge loss

We consider the problem of binary classification where the classifier can, for a particular cost, choose not to classify an observation. Just as in the conventional classification problem, minimization of the sample average of the cost is a difficult optimization problem. As an alternative, we propose the optimization of a certain convex loss function φ, analogous to the hinge loss used in support vector machines (SVMs). Its convexity ensures that the sample average of this surrogate loss can be efficiently minimized. We study its statistical properties. We show that minimizing the expected surrogate loss—the φ-risk—also minimizes the risk. We also study the rate at which the φ-risk approaches its minimum value. We show that fast rates are possible when the conditional probability P(Y=1|X) is unlikely to be close to certain critical values.

On the consistency of multiclass classification methods

Binary classification is a well studied special case of the classification problem. Statistical properties of binary classifiers, such as consistency, have been investigated in a variety of settings. Binary classification methods can be generalized in many ways to handle multiple classes. It turns out that one can lose consistency in generalizing a binary classification method to deal with multiple classes. We study a rich family of multiclass methods and provide a necessary and sufficient condition for their consistency. We illustrate our approach by applying it to some multiclass methods proposed in the literature.

Public sector strategy classification system for shared service identification

The purpose of this conceptual paper is to address the lack of consistent means through which strategies are identified and discussed across theoretical perspectives in the field of business strategy. A standardised referencing system is offered to codify the means by which strategies can be identified, from which new business services and information systems may be derived. This taxonomy was developed using qualitative content analysis study of government agencies’ strategic plans. This taxonomy is useful for identifying strategy formation and determining gaps and opportunities. Managers will benefit from a more transparent strategic design process that reduces ambiguity, aids in identifying and correcting gaps in strategy formulation, and fosters enhanced strategic analysis. Key benefits to academics are the improved dialogue in strategic management field and suggest that progress in the field requires that fundamentals of strategy formulation and classification be considered more carefully. Finally, the formalization of strategy can lead to the clear identification of new business services, which inform ICT investment decisions and shared service prioritisation.

Exponentiated gradient algorithms for large-margin structured classification

We consider the problem of structured classification, where the task is to predict a label y from an input x, and y has meaningful internal structure. Our framework includes supervised training of Markov random fields and weighted context-free grammars as special cases. We describe an algorithm that solves the large-margin optimization problem defined in [12], using an exponential-family (Gibbs distribution) representation of structured objects. The algorithm is efficient—even in cases where the number of labels y is exponential in size—provided that certain expectations under Gibbs distributions can be calculated efficiently. The method for structured labels relies on a more general result, specifically the application of exponentiated gradient updates [7, 8] to quadratic programs.

Unsteady natural convection in a triangular enclosure under isothermal heating

The fluid flow and heat transfer inside a triangular enclosure due to instantaneous heating on the inclined walls are investigated using an improved scaling analysis and direct numerical simulations. The development of the unsteady natural convection boundary layer under the inclined walls may be classified into three distinct stages including a start-up stage, a transitional stage and a steady state stage, which can be clearly identified in the analytical and numerical results. A new triple-layer integral approach of scaling analysis has been considered to obtain major scaling relations of the velocity, thicknesses, Nusselt number and the flow development time of the natural convection boundary layer and verified by direct numerical simulations over a wide range of flow parameters.

Identification of area-level influences on regions of high cancer incidence in Queensland, Australia : a classification tree approach

Background: Strategies for cancer reduction and management are targeted at both individual and area levels. Area-level strategies require careful understanding of geographic differences in cancer incidence, in particular the association with factors such as socioeconomic status, ethnicity and accessibility. This study aimed to identify the complex interplay of area-level factors associated with high area-specific incidence of Australian priority cancers using a classification and regression tree (CART) approach. Methods: Area-specific smoothed standardised incidence ratios were estimated for priority-area cancers across 478 statistical local areas in Queensland, Australia (1998-2007, n=186,075). For those cancers with significant spatial variation, CART models were used to identify whether area-level accessibility, socioeconomic status and ethnicity were associated with high area-specific incidence. Results: The accessibility of a person’s residence had the most consistent association with the risk of cancer diagnosis across the specific cancers. Many cancers were likely to have high incidence in more urban areas, although male lung cancer and cervical cancer tended to have high incidence in more remote areas. The impact of socioeconomic status and ethnicity on these associations differed by type of cancer. Conclusions: These results highlight the complex interactions between accessibility, socioeconomic status and ethnicity in determining cancer incidence risk.

Scaling of natural convection of an inclined flat plate : ramp cooling condition

A scaling analysis is performed for the transient boundary layer established adjacent to an inclined flat plate following a ramp cooling boundary condition. The imposed wall temperature decreases linearly up to a specific value over a specific time. It is revealed that if the ramp time is sufficiently large then the boundary layer reaches quasi-steady mode before the growth of the temperature is finished. However, if the ramp time is shorter then the steady state of the boundary layer may be reached after the growth of the temperature is completed. In this case, the ultimate steady state is the same as if the start up had been instantaneous. Note that the cold boundary layer adjacent to the plate is potentially unstable to Rayleigh-Bénard instability if the Rayleigh number exceeds a certain critical value for this cooling case. The onset of instability may set in at different stages of the boundary layer development. A proper identification of the time when the instability may set in is discussed. A numerical verification of the time for the onset of instability is presented in this study. Different flow regimes based on the stability of the boundary layer have also been discussed with numerical results.

Natural convection boundary-layer adjacent to an inclined flat plate subject to sudden and ramp heating

The natural convection thermal boundary layer adjacent to an inclined flat plate subject to sudden heating and a temperature boundary condition which follows a ramp function up until a specified time and then remains constant is investigated. The development of the flow from start-up to a steady-state has been described based on scaling analyses and verified by numerical simulations. Different flow regimes based on the Rayleigh number are discussed with numerical results for both boundary conditions. For ramp heating, the boundary layer flow depends on the comparison of the time at which the ramp heating is completed and the time at which the boundary layer completes its growth. If the ramp time is long compared with the steady state time, the layer reaches a quasi steady mode in which the growth of the layer is governed solely by the thermal balance between convection and conduction. On the other hand, if the ramp is completed before the layer becomes steady; the subsequent growth is governed by the balance between buoyancy and inertia, as for the case of instantaneous heating.

Scaling of natural convection of an inclined flat plate : sudden cooling condition

The natural convection boundary layer adjacent to an inclined plate subject to sudden cooling boundary condition has been studied. It is found that the cold boundary layer adjacent to the plate is potentially unstable to Rayleigh-Bénard instability if the Rayleigh number exceeds a certain critical value. A scaling relation for the onset of instability of the boundary layer is achieved. The scaling relations have been developed by equating important terms of the governing equations based on the development of the boundary layer with time. The flow adjacent to the plate can be classified broadly into a conductive, a stable convective or an unstable convective regime determined by the Rayleigh number. Proper scales have been established to quantify the flow properties in each of these flow regimes. An appropriate identification of the time when the instability may set in is discussed. A numerical verification of the time for the onset of instability is also presented in this study. Different flow regimes based on the stability of the boundary layer have been discussed with numerical results.

Natural convection in attic-shaped spaces subject to sudden and ramp heating boundary conditions

In this study, a discussion of the fluid dynamics in the attic space is reported, focusing on its transient response to sudden and linear changes of temperature along the two inclined walls. The transient behaviour of an attic space is relevant to our daily life. The instantaneous and non-instantaneous (ramp) heating boundary condition is applied on the sloping walls of the attic space. A theoretical understanding of the transient behaviour of the flow in the enclosure is performed through scaling analysis. A proper identification of the timescales, the velocity and the thickness relevant to the flow that develops inside the cavity makes it possible to predict theoretically the basic flow features that will survive once the thermal flow in the enclosure reaches a steady state. A time scale for the heating-up of the whole cavity together with the heat transfer scales through the inclined walls has also been obtained through scaling analysis. All scales are verified by the numerical simulations.

Natural convection in attics subject to instantaneous and ramp cooling boundary conditions

A fundamental study of the fluid dynamics inside an attic shaped triangular enclosure with cold upper walls and adiabatic horizontal bottom wall is reported in this study. The transient behaviour of the attic fluid which is relevant to our daily life is examined based on a scaling analysis. The transient phenomenon begins with the instantaneous cooling and the cooling with linear decreases of temperature up to some specific time (ramp time) and then maintain constant of the upper sloped walls. It is shown that both inclined walls develop a thermal boundary layer whose thicknesses increase towards steady-state or quasi-steady values. A proper identification of the timescales, the velocity and the thickness relevant to the flow that develops inside the cavity makes it possible to predict theoretically the basic flow features that will survive once the thermal flow in the enclosure reaches a steady state. A time scale for the cooling-down of the whole cavity together with the heat transfer scales through the inclined walls has also been obtained through scaling analysis. All scales are verified by the numerical simulations.

Natural convection and heat transfer in attics subject to periodic thermal forcing

The heat transfer through the attics of buildings under realistic thermal forcing has been considered in this study. A periodic temperature boundary condition is applied on the sloping walls of the attic to show the basic flow features in the attic space over diurnal cycles. The numerical results reveal that, during the daytime heating stage, the flow in the attic space is stratified; whereas at the night-time cooling stage, the flow becomes unstable. A symmetrical solution is seen for relatively low Rayleigh numbers. However, as the Ra gradually increases, a transition occurs at a critical value of Ra. Above this critical value, an asymmetrical solution exhibiting a pitchfork bifurcation arises at the night-time. It is also found that the calculated heat transfer rate at the night-time cooling stage is much higher than that during the daytime heating stage.