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.

Pre-Admission and Post-Hospital Management of Heart Failure in Patients not Enrolled in Specialist Programs

Aim: To review the management of heart failure in patients not enrolled in specialist multidisciplinary programs. Method: A prospective clinical audit of patients admitted to hospital with either a current or past diagnosis of heart failure and not enrolled in a specialist heart failure program or under the direct care of the cardiology unit. Results: 81 eligible patients were enrolled (1 August to 1 October 2008). The median age was 81 9.4 years and 48% were male. Most patients (63%) were in New York Heart Association Class II or Class III heart failure. On discharge, 59% of patients were prescribed angiotensin converting enzyme inhibitors and 43% were prescribed beta-blockers. During hospitalisation, 8.6% of patients with a past diagnosis of heart failure were started on an angiotensin converting enzyme inhibitor and 4.9% on a beta-blocker. There was evidence of suboptimal dosage on admission and discharge for angiotensin converting enzyme inhibitors (19% and 7.4%) and beta-blockers (29% and 17%). The results compared well with international reports regarding the under-treatment of heart failure. Conclusion: The demonstrated practice gap provides excellent opportunities for the involvement of pharmacists to improve the continuation of care for heart failure patients discharged from hospital in the areas of medication management review, dose titration and monitoring.