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

An examination of the psychologists' attitudes towards complementary and alternative therapies scale within a practitioner sample

This study assessed the validity of a scale measuring psychologists' attitudes towards complementary and alternative therapies and compared the attitudes of psychologists with a previous sample of psychology students. The scale, derived from existing measures for medical professionals and previously tested on a sample of psychology students, was completed by practising psychologists (N = 122). The data were factor analysed, and three correlated subscales were identified, assessing the perceived importance of knowledge about available therapies, attitudes towards integration with psychological practice, and concerns about associated risks of use. This structure was similar, but not identical, to that found in a previous sample of psychology students; however, psychologists expressed more concern for risks associated with integration and were less likely to hold a positive attitude towards integration. This scale will be useful in gauging changes in psychologists' attitudes towards integrative practice over time.

Are you telling the truth? Psychopathy assessment and impression management in a community sample

Objectives: Researchers have suggested that approximately 1% of individuals within the community have psychopathic tendencies (Neumann and Hare, 2008), although confirmatory evidence is scant. Design: The current study aimed to extend previous research beyond university student samples to explore the effect of impression management and self-deception on the identification of psychopathic traits. Methods: A non-incarcerated community sample comprising of 300 adults completed the Self-Reported Psychopathy scale – version 3 (SRP-III; Paulhus, Hemphill & Hare, in press) as well as the Paulhus Deception Scales (PDS; Paulhus, 1998). Results: Results indicated that at least 1% of the current community sample had clear psychopathic tendencies, and that such tendencies were found in younger males who mis-used alcohol. Conclusions: Importantly, individuals with psychopathic traits did not present with an inflated propensity to distort assessment responses, which provides support for future research endeavours that aim to conduct larger-scale psychopathy assessments within the community. This paper further outlines the study implications in regards to the practical assessment of psychopathy.