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).

On the optimality of sample-based estimates of the expectation of the empirical minimizer

We study sample-based estimates of the expectation of the function produced by the empirical minimization algorithm. We investigate the extent to which one can estimate the rate of convergence of the empirical minimizer in a data dependent manner. We establish three main results. First, we provide an algorithm that upper bounds the expectation of the empirical minimizer in a completely data-dependent manner. This bound is based on a structural result due to Bartlett and Mendelson, which relates expectations to sample averages. Second, we show that these structural upper bounds can be loose, compared to previous bounds. In particular, we demonstrate a class for which the expectation of the empirical minimizer decreases as O(1/n) for sample size n, although the upper bound based on structural properties is Ω(1). Third, we show that this looseness of the bound is inevitable: we present an example that shows that a sharp bound cannot be universally recovered from empirical data.

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

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.

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.

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.

On the natural convection boundary layer adjacent to an inclined flat plate subject to ramp heating

An investigation of the natural convection boundary layer adjacent to an inclined semi-infinite plate subject to a temperature boundary condition which follows a ramp function up until some specified time and then remains constant is reported. The development of the flow from start-up to a steadystate has been described based on scaling analyses and verified by numerical simulations. Attention in this study has been given to fluids having a Prandtl number Pr less than unity. 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 analysis of unsteady natural convection boundary layer for ramp heating

A scaling analysis for the natural convection boundary layer adjacent to an inclined semi-infinite plate subject to a non-instantaneous heating in the form of an imposed wall temperature which increases linearly up to a prescribed steady value over a prescribed time is reported. The development of the flow from start-up to a steady-state has been described based on scaling analyses and verified by numerical simulations. The analysis reveals that, if the period of temperature growth on the wall is sufficiently long, the boundary layer reaches a quasisteady mode before the growth of the temperature is completed. In this mode the thermal boundary layer at first grows in thickness and then contracts with increasing time. However, if the imposed wall temperature growth period is sufficiently short, the boundary layer develops differently, but after the wall temperature growth is completed, the boundary layer develops as though the start up had been instantaneous. The steady state values of the boundary layer for both cases are ultimately the same.

Scaling analysis of unsteady natural convection boundary layer for instantaneous heating

Natural convection thermal boundary layer adjacent to an instantaneous heated inclined flat plate is investigated through a scaling analysis and verified by direct numerical simulations. It is revealed from the analysis that the development of the boundary layer may be characterized by three distinct stages, i.e. a start-up stage, a transitional stage and a steady state stage. These three stages can be clearly identified from the numerical simulations. Major scales including the flow velocity, flow development time, and the thermal and viscous boundary layer thicknesses are established to quantify the flow development at different stages and over a wide range of flow parameters. Details of the scaling analysis are described in this paper.