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.

Corrigendum to “Shifting : one-inclusion mistake bounds and sample compression” [J. Comput. System Sci. 75 (1) (2009) 37–59]

H. Simon and B. Szörényi have found an error in the proof of Theorem 52 of “Shifting: One-inclusion mistake bounds and sample compression”, Rubinstein et al. (2009). In this note we provide a corrected proof of a slightly weakened version of this theorem. Our new bound on the density of one-inclusion hypergraphs is again in terms of the capacity of the multilabel concept class. Simon and Szörényi have recently proved an alternate result in Simon and Szörényi (2009).

Optimal strategies and minimax lower bounds for online convex games

A number of learning problems can be cast as an Online Convex Game: on each round, a learner makes a prediction x from a convex set, the environment plays a loss function f, and the learner’s long-term goal is to minimize regret. Algorithms have been proposed by Zinkevich, when f is assumed to be convex, and Hazan et al., when f is assumed to be strongly convex, that have provably low regret. We consider these two settings and analyze such games from a minimax perspective, proving minimax strategies and lower bounds in each case. These results prove that the existing algorithms are essentially optimal.

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

Filter and control performance bounds in the presence of model uncertainties with aerospace applications

This thesis establishes performance properties for approximate filters and controllers that are designed on the basis of approximate dynamic system representations. These performance properties provide a theoretical justification for the widespread application of approximate filters and controllers in the common situation where system models are not known with complete certainty. This research also provides useful tools for approximate filter designs, which are applied to hybrid filtering of uncertain nonlinear systems. As a contribution towards applications, this thesis also investigates air traffic separation control in the presence of measurement uncertainties.

Entropic bounds for multi-scale and multi-physics coupling in earth sciences

The ability to understand and predict how thermal, hydrological,mechanical and chemical (THMC) processes interact is fundamental to many research initiatives and industrial applications. We present (1) a new Thermal– Hydrological–Mechanical–Chemical (THMC) coupling formulation, based on non-equilibrium thermodynamics; (2) show how THMC feedback is incorporated in the thermodynamic approach; (3) suggest a unifying thermodynamic framework for multi-scaling; and (4) formulate a new rationale for assessing upper and lower bounds of dissipation for THMC processes. The technique is based on deducing time and length scales suitable for separating processes using a macroscopic finite time thermodynamic approach. We show that if the time and length scales are suitably chosen, the calculation of entropic bounds can be used to describe three different types of material and process uncertainties: geometric uncertainties,stemming from the microstructure; process uncertainty, stemming from the correct derivation of the constitutive behavior; and uncertainties in time evolution, stemming from the path dependence of the time integration of the irreversible entropy production. Although the approach is specifically formulated here for THMC coupling we suggest that it has a much broader applicability. In a general sense it consists of finding the entropic bounds of the dissipation defined by the product of thermodynamic force times thermodynamic flux which in material sciences corresponds to generalized stress and generalized strain rates, respectively.

Structure and palaeoenvironmental implications of inter-branch coenosteum-rich skeleton in corymbose Acropora species

Coral reefs provide an increasingly important archive of palaeoclimate data that can be used to constrain climate model simulations. Reconstructing past environmental conditions may also provide insights into the potential of reef systems to survive changes in the Earth’s climate. Reef-based palaeoclimate reconstructions are predominately derived from colonies of massive Porites, with the most abundant genus in the Indo-Pacific—Acropora—receiving little attention owing to their branching growth trajectories, high extension rates and secondary skeletal thickening. However, inter-branch skeleton (consisting of both coenosteum and corallites) near the bases of corymbose Acropora colonies holds significant potential as a climate archive. This region of Acropora skeleton is atypical, having simple growth trajectories with parallel corallites, approximately horizontal density banding, low apparent extension rates and a simple microstructure with limited secondary thickening. Hence, inter-branch skeleton in Acropora bears more similarities to the coralla of massive corals, such as Porites, than to traditional Acropora branches. Cyclic patterns of Sr/Ca ratios in this structure suggest that the observed density banding is annual in nature, thus opening up the potential to use abundant corymbose Acropora for palaeoclimate reconstruction.

The long and short of it: branch lengths and the problem of placing the New Zealand short-tailed bat.

The taxonomic position of the endemic New Zealand bat genus Mystacina has vexed systematists ever since its erection in 1843. Over the years the genus has been linked with many microchiropteran families and superfamilies. Most recent classifications place it in the Vespertilionoidea, although some immunological evidence links it with the Noctilionoidea (=Phyllostomoidea). We have sequenced 402 bp of the mitochondrial cytochrome b gene for M. tuberculata (Gray in Dieffenbach, 1843), and using both our own and published DNA sequences for taxa in both superfamilies, we applied different tree reconstruction methods to find the appropriate phylogeny and different methods of estimating confidence in the parts of the tree. All methods strongly support the classification of Mystacina in the Noctilionoidea. Spectral analysis suggests that parsimony analysis may be misleading for Mystacina's precise placement within the Noctilionoidea because of its long terminal branch. Analyses not susceptible to long-branch attraction suggest that the Mystacinidae is a sister family to the Phyllostomidae. Dating the divergence times between the different taxa suggests that the extant chiropteran families radiated around and shortly after the Cretaceous–Tertiary boundary. We discuss the biogeographical implications of classifying Mystacina within the Noctilionoidea and contrast our result with those classifications placing Mystacina in the Vespertilionoidea, concluding that evidence for the latter is weak.

Error and variance bounds on sigmoidal neurons with weight and input errors

Bounds on the expectation and variance of errors at the output of a multilayer feedforward neural network with perturbed weights and inputs are derived. It is assumed that errors in weights and inputs to the network are statistically independent and small. The bounds obtained are applicable to both digital and analogue network implementations and are shown to be of practical value.

The Long and Short of It: Branch Lengths and the Problem of Placing the New Zealand Short-Tailed Bat, Mystacina

The taxonomic position of the endemic New Zealand bat genus Mystacina has vexed systematists ever since its erection in 1843. Over the years the genus has been linked with many microchiropteran families and superfamilies. Most recent classifications place it in the Vespertilionoidea, although some immunological evidence links it with the Noctilionoidea (=Phyllostomoidea). We have sequenced 402 bp of the mitochondrial cytochrome b gene for M. tuberculata (Gray in Dieffenbach, 1843), and using both our own and published DNA sequences for taxa in both superfamilies, we applied different tree reconstruction methods to find the appropriate phylogeny and different methods of estimating confidence in the parts of the tree. All methods strongly support the classification of Mystacina in the Noctilionoidea. Spectral analysis suggests that parsimony analysis may be misleading for Mystacina's precise placement within the Noctilionoidea because of its long terminal branch. Analyses not susceptible to long-branch attraction suggest that the Mystacinidae is a sister family to the Phyllostomidae. Dating the divergence times between the different taxa suggests that the extant chiropteran families radiated around and shortly after the Cretaceous-Tertiary boundary. We discuss the biogeographical implications of classifying Mystacina within the Noctilionoidea and contrast our result with those classifications placing Mystacina in the Vespertilionoidea, concluding that evidence for the latter is weak.

Exploring the nexus between tourism and output in Cook Islands: An ARDL bounds approach

Tourism plays an important role in the development of Cook Islands. In this paper we examine the nexus between tourism and growth using quarterly data over the period 2009Q1–2014Q2 using the recently upgraded ARDL bounds test to cointegration tool, Microfit 5.01, which provides sample adjusted bounds and hence is more reliable for small sample size studies. We perform the cointegration using the ARDL bounds test and examine the direction of causality. Using visitor arrival and output in per capita terms as respective proxy for tourism development and growth, we examine the long-run association and report the elasticity coefficient of tourism and causality nexus, accordingly. Using unit root break tests, we note that 2011Q1 and 2011Q2 are two structural break periods in the output series. However, we note that this period is not statistically significant in the ARDL model and hence excluded from the estimation. Subsequently, the regression results show the two series are cointegrated. The long-run elasticity coefficient of tourism is estimated to be 0.83 and the short-run is 0.73. A bidirectional causality between tourism and income is noted for Cook Islands which indicates that tourism development and income mutually reinforce each other. In light of this, socio-economic policies need to focus on broad-based, inclusive and income-generating tourism development projects which are expected to have feedback effect.