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

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

Politics and school education in Australia : a case of shifting purposes

Purpose – The paper aims to argue that there has been a privileging of the private (social mobility) and economic (social efficiency) purposes of schooling at the expense of the public (democratic equality) purposes of schooling. Design/methodology/approach – The paper employs a literature review, policy and document analysis. Findings – Since the late 1980s, the schooling agenda in Australia has been narrowed to one that gives primacy to purposes of schooling that highlight economic orientations (social efficiency) and private purposes (social mobility). Practical implications – The findings have wider relevance beyond Australia, as similar policy agendas are evident in many other countries raising the question as to how the shift in purposes of education in those countries might mirror those in Australia. Originality/value – While earlier writers have examined schooling policies in Australia and noted the implications of managerialism in relation to these policies, no study has analysed these policies from the perspective of the purposes of schooling. Conceptualising schooling, and its purposes in particular, in this way refocuses attention on how societies use their educational systems to promote (or otherwise) the public good.

A plasmonic 'ac Wheatstone bridge' circuit for high-sensitivity phase measurement and single-molecule detection

In this paper, a plasmonic “ac Wheatstone bridge” circuit is proposed and theoretically modeled for the first time. The bridge circuit consists of three metallic nanoparticles, shaped as rectangular prisms, with two nanoparticles acting as parallel arms of a resonant circuit and the third bridging nanoparticle acting as an optical antenna providing an output signal. Polarized light excites localized surface plasmon resonances in the two arms of the circuit, which generate an optical signal dependent on the phase-sensitive excitations of surface plasmons in the antenna. The circuit is analyzed using a plasmonic coupling theory and numerical simulations. The analyses show that the plasmonic circuit is sensitive to phase shifts between the arms of the bridge and has the potential to detect the presence of single molecules.

Multiculturalism, education for sustainable development (ESD) and the shifting discursive landscape of social inclusion

Australia has a long and sometimes turbulent relationship with the migrant Other. This paper examines a component of this relationship via the window of contemporary multicultural policy. The paper begins with an analysis of the political and social conditions that enabled a national and bipartisan policy of multiculturalism to emerge as formalised federal policy during the late 1960s and early 1970s. The paper re-problematises the influences that helped shape Australia's articulation of race and ethnicity and argues that multiculturalism, within a post-September 11 environment, can no longer be framed solely within its traditional framework of social justice. The paper positions education for sustainable development (ESD) as an emerging discursive field that provides educators with an alternative road map for critiquing Australia's fluid relationship with the migrant Other. By linking the tenets of multiculturalism with ESD, this paper suggests pre-service teacher educators are presented with a productive, and at the same time politically palatable, means for regaining pedagogical traction for a semi-dormant agenda of social inclusion.

Instantaneous phase of the autocorrelation and robustness to signal-dependent noise

The phase of an analytic signal constructed from the autocorrelation function of a signal contains significant information about the shape of the signal. Using Bedrosian's (1963) theorem for the Hilbert transform it is proved that this phase is robust to multiplicative noise if the signal is baseband and the spectra of the signal and the noise do not overlap. Higher-order spectral features are interpreted in this context and shown to extract nonlinear phase information while retaining robustness. The significance of the result is that prior knowledge of the spectra is not required.

International law and the regulation of violence : shifting perceptions of the legitimacy of the jus ad bellum?

International law’s capacity to influence state behaviour by regulating recourse to violence has been a longstanding source of debate among international lawyers and political scientists. On the one hand, sceptics assert that frequent violations of the prohibition on the use of force have rendered article 2(4) of the UN Charter redundant. They contend that national self-interest, rather than international law, is the key determinant of state behaviour regarding the use of force. On the other hand, defenders of article 2(4) argue first, that most states comply with the Charter framework, and second, that state rhetoric continues to acknowledge the existence of the jus ad bellum. In particular, the fact that violators go to considerable lengths to offer legal or factual justifications for their conduct – typically by relying on the right of self-defence – is advanced as evidence that the prohibition on the use of force retains legitimacy in the eyes of states. This paper identifies two potentially significant features of state practice since 2006 which may signal a shift in states’ perceptions of the normative authority of article 2(4). The first aspect is the recent failure by several states to offer explicit legal justifications for their use or force, or to report action taken in self-defence to the Security Council in accordance with Article 51. Four incidents linked to the global “war on terror” are examined here: Israeli airstrikes in Syria in 2007 and in Sudan in 2009, Turkey’s 2006-2008 incursions into northern Iraq, and Ethiopia’s 2006 intervention in Somalia. The second, more troubling feature is the international community’s apparent lack of concern over the legality of these incidents. Each use of force is difficult to reconcile with the strict requirements of the jus ad bellum; yet none attracted genuine legal scrutiny or debate among other states. While it is too early to conclude that these relatively minor incidents presage long term shifts in state practice, viewed together the two developments identified here suggest a possible downgrading of the role of international law in discussions over the use of force, at least in conflicts linked to the “war on terror”. This, in turn, may represent a declining perception of the normative authority of the jus ad bellum, and a concomitant admission of the limits of international law in regulating violence.