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.

A unifying view of multiple kernel learning

Recent research on multiple kernel learning has lead to a number of approaches for combining kernels in regularized risk minimization. The proposed approaches include different formulations of objectives and varying regularization strategies. In this paper we present a unifying optimization criterion for multiple kernel learning and show how existing formulations are subsumed as special cases. We also derive the criterion’s dual representation, which is suitable for general smooth optimization algorithms. Finally, we evaluate multiple kernel learning in this framework analytically using a Rademacher complexity bound on the generalization error and empirically in a set of experiments.

Shifting : one-inclusion mistake bounds and sample compression

We present new expected risk bounds for binary and multiclass prediction, and resolve several recent conjectures on sample compressibility due to Kuzmin and Warmuth. By exploiting the combinatorial structure of concept class F, Haussler et al. achieved a VC(F)/n bound for the natural one-inclusion prediction strategy. The key step in their proof is a d = VC(F) bound on the graph density of a subgraph of the hypercube—oneinclusion graph. The first main result of this paper is a density bound of n [n−1 <=d-1]/[n <=d] < d, which positively resolves a conjecture of Kuzmin and Warmuth relating to their unlabeled Peeling compression scheme and also leads to an improved one-inclusion mistake bound. The proof uses a new form of VC-invariant shifting and a group-theoretic symmetrization. Our second main result is an algebraic topological property of maximum classes of VC-dimension d as being d contractible simplicial complexes, extending the well-known characterization that d = 1 maximum classes are trees. We negatively resolve a minimum degree conjecture of Kuzmin and Warmuth—the second part to a conjectured proof of correctness for Peeling—that every class has one-inclusion minimum degree at most its VCdimension. Our final main result is a k-class analogue of the d/n mistake bound, replacing the VC-dimension by the Pollard pseudo-dimension and the one-inclusion strategy by its natural hypergraph generalization. This result improves on known PAC-based expected risk bounds by a factor of O(logn) and is shown to be optimal up to an O(logk) factor. The combinatorial technique of shifting takes a central role in understanding the one-inclusion (hyper)graph and is a running theme throughout.

Shifting : one-inclusion mistake bounds and sample compression

We present new expected risk bounds for binary and multiclass prediction, and resolve several recent conjectures on sample compressibility due to Kuzmin and Warmuth. By exploiting the combinatorial structure of concept class F, Haussler et al. achieved a VC(F)/n bound for the natural one-inclusion prediction strategy. The key step in their proof is a d=VC(F) bound on the graph density of a subgraph of the hypercube—one-inclusion graph. The first main result of this report is a density bound of n∙choose(n-1,≤d-1)/choose(n,≤d) < d, which positively resolves a conjecture of Kuzmin and Warmuth relating to their unlabeled Peeling compression scheme and also leads to an improved one-inclusion mistake bound. The proof uses a new form of VC-invariant shifting and a group-theoretic symmetrization. Our second main result is an algebraic topological property of maximum classes of VC-dimension d as being d-contractible simplicial complexes, extending the well-known characterization that d=1 maximum classes are trees. We negatively resolve a minimum degree conjecture of Kuzmin and Warmuth—the second part to a conjectured proof of correctness for Peeling—that every class has one-inclusion minimum degree at most its VC-dimension. Our final main result is a k-class analogue of the d/n mistake bound, replacing the VC-dimension by the Pollard pseudo-dimension and the one-inclusion strategy by its natural hypergraph generalization. This result improves on known PAC-based expected risk bounds by a factor of O(log n) and is shown to be optimal up to a O(log k) factor. The combinatorial technique of shifting takes a central role in understanding the one-inclusion (hyper)graph and is a running theme throughout

A unifying view of multiple kernel learning

Recent research on multiple kernel learning has lead to a number of approaches for combining kernels in regularized risk minimization. The proposed approaches include different formulations of objectives and varying regularization strategies. In this paper we present a unifying general optimization criterion for multiple kernel learning and show how existing formulations are subsumed as special cases. We also derive the criterion's dual representation, which is suitable for general smooth optimization algorithms. Finally, we evaluate multiple kernel learning in this framework analytically using a Rademacher complexity bound on the generalization error and empirically in a set of experiments.

Aspiration levels and educational choices: An experimental study

The explanation of social inequalities in education is still a debated issue in economics. Recent empirical studies tend to downplay the potential role of credit constraint. This article tests a different potential explanation of social inequalities in education, specifically that social differences in aspiration level result in different educational choices. Having existed for a long time in the sociology of education, this explanation can be justified if aspiration levels are seen as reference points in a prospect theory framework. In order to test this explanation, this article applies the method of experimental economics to the issue of education choice and behaviour. One hundred and twenty-nine individuals participated in an experiment in which they had to perform a task over 15 stages grouped in three blocks or levels. In order to continue through the experiment, a minimum level of success was required at the end of each level. Rewards were dependent on the final level successfully reached. At the end of each level, participants could either choose to stop and take their reward or to pay a cost to continue further in order to possibly receive higher rewards. To test the impact of aspiration levels, outcomes were either presented as gains or losses relative to an initial sum. In accordance with the theoretical predictions, participants in the loss framing group choose to go further in the experiment. There was also a significant and interesting gender effect in the loss framing treatment, such that males performed better and reached higher levels.

Unbiased estimation of the half-life to price index convergence among U.S. cities

Estimates of the half-life to convergence of prices across a panel of cities are subject to bias from three potential sources: inappropriate cross-sectional aggregation of heterogeneous coefficients, presence of lagged dependent variables in a model with individual fixed effects, and time aggregation of commodity prices. This paper finds no evidence of heterogeneity bias in annual CPI data for 17 U.S. cities from 1918 to 2006, but correcting for the “Nickell bias” and time aggregation bias produces a half-life of 7.5 years, shorter than estimates from previous studies.

Predicting residue-wise contact orders in proteins by support vector regression

Background The residue-wise contact order (RWCO) describes the sequence separations between the residues of interest and its contacting residues in a protein sequence. It is a new kind of one-dimensional protein structure that represents the extent of long-range contacts and is considered as a generalization of contact order. Together with secondary structure, accessible surface area, the B factor, and contact number, RWCO provides comprehensive and indispensable important information to reconstructing the protein three-dimensional structure from a set of one-dimensional structural properties. Accurately predicting RWCO values could have many important applications in protein three-dimensional structure prediction and protein folding rate prediction, and give deep insights into protein sequence-structure relationships. Results We developed a novel approach to predict residue-wise contact order values in proteins based on support vector regression (SVR), starting from primary amino acid sequences. We explored seven different sequence encoding schemes to examine their effects on the prediction performance, including local sequence in the form of PSI-BLAST profiles, local sequence plus amino acid composition, local sequence plus molecular weight, local sequence plus secondary structure predicted by PSIPRED, local sequence plus molecular weight and amino acid composition, local sequence plus molecular weight and predicted secondary structure, and local sequence plus molecular weight, amino acid composition and predicted secondary structure. When using local sequences with multiple sequence alignments in the form of PSI-BLAST profiles, we could predict the RWCO distribution with a Pearson correlation coefficient (CC) between the predicted and observed RWCO values of 0.55, and root mean square error (RMSE) of 0.82, based on a well-defined dataset with 680 protein sequences. Moreover, by incorporating global features such as molecular weight and amino acid composition we could further improve the prediction performance with the CC to 0.57 and an RMSE of 0.79. In addition, combining the predicted secondary structure by PSIPRED was found to significantly improve the prediction performance and could yield the best prediction accuracy with a CC of 0.60 and RMSE of 0.78, which provided at least comparable performance compared with the other existing methods. Conclusion The SVR method shows a prediction performance competitive with or at least comparable to the previously developed linear regression-based methods for predicting RWCO values. In contrast to support vector classification (SVC), SVR is very good at estimating the raw value profiles of the samples. The successful application of the SVR approach in this study reinforces the fact that support vector regression is a powerful tool in extracting the protein sequence-structure relationship and in estimating the protein structural profiles from amino acid sequences.

Interest rate caps : protection or paternalism

In a context where over-indebtedness and financial exclusion have been recognised as problems in Australia, it is undesirable that those who can least afford it, pay a high cost for short-term consumer credit. Evidence points to an increase in consumer debt in Australia and consequential over-indebtedness which has been shown to lead to a wide range of social problems.2 There is also evidence of financial exclusion, where consumers suffer a lack of access to mainstream financial services, and in Australia this is particularly the case with regard to access to safe and affordable credit.3 Financial exclusion can only exacerbate over-indebtedness, given that financially excluded, predominantly low income consumers , have been shown to turn to high cost credit to meet their short term credit needs. This is a problem that has been explored most recently in the Victorian Consumer Credit Review...

Towards a service framework for remote sales support via augmented reality

Real-time sales assistant service is a problematic component of remote delivery of sales support for customers. Solutions involving web pages, telephony and video support prove problematic when seeking to remotely guide customers in their sales processes, especially with transactions revolving around physically complex artefacts. This process involves a number of services that are often complex in nature, ranging from physical compatibility and configuration factors, to availability and credit services. We propose the application of a combination of virtual worlds and augmented reality to create synthetic environments suitable for remote sales of physical artefacts, right in the home of the purchaser. A high level description of the service structure involved is shown, along with a use case involving the sale of electronic goods and services within an example augmented reality application. We expect this work to have application in many sales domains involving physical objects needing to be sold over the Internet.

An assessment of development funding for new housing post GFC in Queensland, Australia

Purpose: The purpose of this paper is to identify changes in bank lending criteria due to the GFC and to explore the associated impacts on new housing supply in Queensland, Australia. Design/methodology/approach: This research involves a survey of each of Australia’s big four banks, as well as two prominent arrangers of development finance. Data on key lending criteria was collected: Pre GFC, during the GFC, and GFC recovery stage. Findings: The GFC has resulted in a retraction of funds available for residential development. The few institutions lending are filtering out only the best credit risks by way of constrictive loan covenants including: low loan to value ratios, high cash equity requirements, regional “no go” zones, and demonstrated borrower track record. The ability of developers to proceed with new housing developments is being constrained by their inability to obtain sufficient finance. Research limitations/implications: This research uses survey data, together with an understanding of the project finance process to extrapolate impacts on the residential development industry across Queensland. No regional or sub-market analysis is included. Future research will include subsequent surveys to track any loosening of credit policies over time and sub-market sector analysis. Practical implications: The inability to obtain project finance is identified as a key constraint to new housing supply. This research will inform policy makers and provide important quantitative evidence of the importance of availability of development finance in the housing supply chain. Social implications: Queensland is facing a supply shortfall, which if not corrected, may lead to upward pressure on house prices and falling housing affordability. Originality/value: There is very little academic research on development funding. This research is unique in linking bank lending criteria to new housing supply and demonstrating the impact on the development industry.

Deformation behaviours of coarse-grained and nanocrystalline Mg-5wt% Al alloys

Magnesium alloys have been of growing interest to various engineering applications, such as the automobile, aerospace, communication and computer industries due to their low density, high specific strength, good machineability and availability as compared with other structural materials. However, most Mg alloys suffer from poor plasticity due to their Hexagonal Close Packed structure. Grain refinement has been proved to be an effective method to enhance the strength and alter the ductility of the materials. Several methods have been proposed to produce materials with nanocrystalline grain structures. So far, most of the research work on nanocrystalline materials has been carried out on Face-Centered Cubic and Body-Centered Cubic metals. However, there has been little investigation of nanocrystalline Mg alloys. In this study, bulk coarse-grained and nanocrystalline Mg alloys were fabricated by a mechanical alloying method. The mixed powder of Mg chips and Al powder was mechanically milled under argon atmosphere for different durations of 0 hours (MA0), 10 hours (MA10), 20 hours (MA20), 30 hours (MA30) and 40 hours (MA40), followed by compaction and sintering. Then the sintered billets were hot-extruded into metallic rods with a 7 mm diameter. The obtained Mg alloys have a nominal composition of Mg–5wt% Al, with grain sizes ranging from 13 μm down to 50 nm, depending on the milling durations. The microstructure characterization and evolution after deformation were carried out by means of Optical microscopy, X-Ray Diffraction, Scanning Electron Microscopy, Transmission Electron Microscopy, Scanning Probe Microscopy and Neutron Diffraction techniques. Nanoindentaion, compression and micro-compression tests on micro-pillars were used to study the size effects on the mechanical behaviour of the Mg alloys. Two kinds of size effects on the mechanical behaviours and deformation mechanisms were investigated: grain size effect and sample size effect. The nanoindentation tests were composed of constant strain rate, constant loading rate and indentation creep tests. The normally reported indentation size effect in single crystal and coarse-grained crystals was observed in both the coarse-grained and nanocrystalline Mg alloys. Since the indentation size effect is correlated to the Geometrically Necessary Dislocations under the indenter to accommodate the plastic deformation, the good agreement between the experimental results and the Indentation Size Effect model indicated that, in the current nanocrystalline MA20 and MA30, the dislocation plasticity was still the dominant deformation mechanism. Significant hardness enhancement with decreasing grain size, down to 58 nm, was found in the nanocrystalline Mg alloys. Further reduction of grain size would lead to a drop in the hardness values. The failure of grain refinement strengthening with the relatively high strain rate sensitivity of nanocrystalline Mg alloys suggested a change in the deformation mechanism. Indentation creep tests showed that the stress exponent was dependent on the loading rate during the loading section of the indentation, which was related to the dislocation structures before the creep starts. The influence of grain size on the mechanical behaviour and strength of extruded coarse-grained and nanocrystalline Mg alloys were investigated using uniaxial compression tests. The macroscopic response of the Mg alloys transited from strain hardening to strain softening behaviour, with grain size reduced from 13 ìm to 50 nm. The strain hardening was related to the twinning induced hardening and dislocation hardening effect, while the strain softening was attributed to the localized deformation in the nanocrystalline grains. The tension–compression yield asymmetry was noticed in the nanocrystalline region, demonstrating the twinning effect in the ultra-fine-grained and nanocrystalline region. The relationship k tensions < k compression failed in the nanocrystalline Mg alloys; this was attributed to the twofold effect of grain size on twinning. The nanocrystalline Mg alloys were found to exhibit increased strain rate sensitivity with decreasing grain size, with strain rate ranging from 0.0001/s to 0.01/s. Strain rate sensitivity of coarse-grained MA0 was increased by more than 10 times in MA40. The Hall-Petch relationship broke down at a critical grain size in the nanocrystalline region. The breakdown of the Hall-Petch relationship and the increased strain rate sensitivity were due to the localized dislocation activities (generalization and annihilation at grain boundaries) and the more significant contribution from grain boundary mediated mechanisms. In the micro-compression tests, the sample size effects on the mechanical behaviours were studied on MA0, MA20 and MA40 micro-pillars. In contrast to the bulk samples under compression, the stress-strain curves of MA0 and MA20 micro-pillars were characterized with a number of discrete strain burst events separated by nearly elastic strain segments. Unlike MA0 and MA20, the stress-strain curves of MA40 micro-pillars were smooth, without obvious strain bursts. The deformation mechanisms of the MA0 and MA20 micro-pillars under micro-compression tests were considered to be initially dominated by deformation twinning, followed by dislocation mechanisms. For MA40 pillars, the deformation mechanisms were believed to be localized dislocation activities and grain boundary related mechanisms. The strain hardening behaviours of the micro-pillars suggested that the grain boundaries in the nanocrystalline micro-pillars would reduce the source (nucleation sources for twins/dislocations) starvation hardening effect. The power law relationship of the yield strength on pillar dimensions in MA0, MA20 supported the fact that the twinning mechanism was correlated to the pre-existing defects, which can promote the nucleation of the twins. Then, we provided a latitudinal comparison of the results and conclusions derived from the different techniques used for testing the coarse-grained and nanocrystalline Mg alloy; this helps to better understand the deformation mechanisms of the Mg alloys as a whole. At the end, we summarized the thesis and highlighted the conclusions, contributions, innovations and outcomes of the research. Finally, it outlined recommendations for future work.

Locating 'Agency' Within Ubiquitous Computing Systems

The final shape of the "Internet of Things" ubiquitous computing promises relies on a cybernetic system of inputs (in the form of sensory information), computation or decision making (based on the prefiguration of rules, contexts, and user-generated or defined metadata), and outputs (associated action from ubiquitous computing devices). My interest in this paper lies in the computational intelligences that suture these positions together, and how positioning these intelligences as autonomous agents extends the dialogue between human-users and ubiquitous computing technology. Drawing specifically on the scenarios surrounding the employment of ubiquitous computing within aged care, I argue that agency is something that cannot be traded without serious consideration of the associated ethics.

Surrogacy - A Path of Obstacles

Surrogacy has become an effective and accepted form of reproductive technology. It enables couples, regardless of gender or sexuality, to achieve the dream of becoming a parent in circumstances where other forms of reproductive technology and adoption are either not possible or have failed. To its credit, the Queensland parliament has recently brought this state up to date by enacting surrogacy laws that are in line with the majority of statutes implemented throughout the country. The Surrogacy Act 2010 (Qld) allows for the court to make a parentage order in certain circumstances where parties have entered into a surrogacy arrangement. A parentage order effectively transfers parental rights from the birth mother (and her spouse or de facto if there is one) to the intended parents. The requirements which must be satisfied to obtain a parenting order are comprehensive and onerous, making the path to parenthood through a surrogacy arrangement by no means easy. At the heart of the surrogacy issue lies a question, the answer to which has shifted and continues to shift as reproductive technologies continue to increase in success, method and popularity - what is a parent? A recent decision of the Administrative Appeals Tribunal, Hudson v Minister for Immigration and Citizenship, brought to attention the meaning of the word ‘parent’ as it appears in s 16(2) Australian Citizenship Act 2007 (Cth) (‘the Act’). Section 16(2) deals with citizenship by descent and provides that a person born outside Australia may make an application to the Minister to become an Australian citizen if a parent of the person was an Australian citizen at the time of the birth.

Using the work system method with freshman information systems students

Recent surveys of information technology management professionals show that understanding business domains in terms of business productivity and cost reduction potential, knowledge of different vertical industry segments and their information requirements, understanding of business processes and client-facing skills are more critical for Information Systems personnel than ever before. In an attempt to restrucuture the information systems curriculum accordingly, our view it that information systems students need to develop an appreciation for organizational work systems in order to understand the operation and significance of information systems within such work systems.