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

Renal and genitourinary emergencies

Genitourinary (GU) problems are a common complaint in the community and to the emergency department (ED). Urinary tract infections (UTIs) are the second most common bacterial disease. UTIs rank as the sixteenth most frequently reported problem to general practitioners in Australia1 and between 10% and 20% of women will experience at least one UTI in their lifetime. Over 1,000,000 Australians are currently suffering with nephrolithiasis (renal calculi) and it is hy-pothesised that Australia’s hot, dry climate causes more stone formation than many other coun-tries in the world. Acute kidney injury (AKI) is a common complication of any trauma. Hypovol-aemia results in severe hypotension and this precipitates the development of acute tubular necrosis and subsequent AKI. The incidence of chronic kidney disease (CKD) is rising across the world. CKD is classified into five stages with those in stage 5 being classified as being in end stage kidney disease (ESKD). It is estimated that there are over 1.5 million people in Australia with CKD and there were over 16,000 Australians and over 2900 individuals in New Zealand with ESKD.2 Indigenous populations from both countries (Aboriginals, Torres Strait Islanders, Maoris, and Pacific Islanders) are over-represented in the number of people with all stages of CKD in both countries. Patients with compromised renal function often require the assistance of paramedics and will arrive at the ED with life-threatening fluid and electrolyte imbalances. Spe-cific GU emergencies discussed in this chapter are acute renal failure, rhabdomyolysis, chronic kidney disease, UTIs, acute urinary retention, urinary calculi, testicular torsion, epididymitis, and priapism. Refer to Chapter 31 for discussion of sexually transmitted infections (STIs) in women and to Chapter X for discussion of genitourinary trauma.

Identity management : strengthening one-time password authentication through usability

Usability in HCI (Human-Computer Interaction) is normally understood as the simplicity and clarity with which the interaction with a computer program or a web site is designed. Identity management systems need to provide adequate usability and should have a simple and intuitive interface. The system should not only be designed to satisfy service provider requirements but it has to consider user requirements, otherwise it will lead to inconvenience and poor usability for users when managing their identities. With poor usability and a poor user interface with regard to security, it is highly likely that the system will have poor security. The rapid growth in the number of online services leads to an increasing number of different digital identities each user needs to manage. As a result, many people feel overloaded with credentials, which in turn negatively impacts their ability to manage them securely. Passwords are perhaps the most common type of credential used today. To avoid the tedious task of remembering difficult passwords, users often behave less securely by using low entropy and weak passwords. Weak passwords and bad password habits represent security threats to online services. Some solutions have been developed to eliminate the need for users to create and manage passwords. A typical solution is based on generating one-time passwords, i.e. passwords for single session or transaction usage. Unfortunately, most of these solutions do not satisfy scalability and/or usability requirements, or they are simply insecure. In this thesis, the security and usability aspects of contemporary methods for authentication based on one-time passwords (OTP) are examined and analyzed. In addition, more scalable solutions that provide a good user experience while at the same time preserving strong security are proposed.

Engaging middle school students in context-based science : One teacher's approach

In Australia, there is a crisis in science education with students becoming disengaged with canonical science in the middle years of schooling. One recent initiative that aims to improve student interest and motivation without diminishing conceptual understanding is the context-based approach. Contextual units that connect the canonical science with the students’ real world of their local community have been used in the senior years but are new in the middle years. This ethnographic study explored the learning transactions that occurred in one 9th grade science class studying an Environmental Science unit for 11 weeks. Data were derived from field notes, audio and video recorded conversations, interviews, student journals and classroom documents with a particular focus on two selected groups of students. Data were analysed qualitatively through coding for emergent themes. This paper presents an outline of the program and discussion of three assertions derived from the preliminary analysis of the data. Firstly, an integrated, coherent sequence of learning experiences that included weekly visits to a creek adjacent to the school enabled the teacher to contextualise the science in the students’ local community. Secondly, content was predominantly taught on a need-to-know basis and thirdly, the lesson sequence aligned with a model for context-based teaching. Research, teaching and policy implications of these results for promoting the context-based teaching of science in the middle years are discussed.

Pattern recognition using invariants defined from higher order spectra - one-dimensional inputs

A new approach to pattern recognition using invariant parameters based on higher order spectra is presented. In particular, invariant parameters derived from the bispectrum are used to classify one-dimensional shapes. The bispectrum, which is translation invariant, is integrated along straight lines passing through the origin in bifrequency space. The phase of the integrated bispectrum is shown to be scale and amplification invariant, as well. A minimal set of these invariants is selected as the feature vector for pattern classification, and a minimum distance classifier using a statistical distance measure is used to classify test patterns. The classification technique is shown to distinguish two similar, but different bolts given their one-dimensional profiles. Pattern recognition using higher order spectral invariants is fast, suited for parallel implementation, and has high immunity to additive Gaussian noise. Simulation results show very high classification accuracy, even for low signal-to-noise ratios.

Fixing the city one photo at a time : mobile logging of maintenance requests

We have designed a mobile application that takes advantage of the built-in features of smart phones such as camera and GPS that allow users to take geo-tagged photos while on the move. Urban residents can take pictures of broken street furniture and public property requiring repair, attach a brief description, and submit the information as a maintenance request to the local government organisation of their city. This paper discusses the design approach that led to the application, highlights a built-in mechanism to elicit user feedback, and evaluates the progress to date with user feedback and log statistics. It concludes with an outlook highlighting user requested features and our own design aspirations for moving from a reporting tool to a civic engagement tool.

One approach to finding evidence for the effectiveness of scientific visualisations in high school physics and chemistry education

Enormous amounts of money and energy are being devoted to the development, use and organisation of computer-based scientific visualisations (e.g. animations and simulations) in science education. It seems plausible that visualisations that enable students to gain visual access to scientific phenomena that are too large, too small or occur too quickly or too slowly to be seen by the naked eye, or to scientific concepts and models, would yield enhanced conceptual learning. When the literature is searched, however, it quickly becomes apparent that there is a dearth of quantitative evidence for the effectiveness of scientific visualisations in enhancing students’ learning of science concepts. This paper outlines an Australian project that is using innovative research methodology to gather evidence on this question in physics and chemistry classrooms.