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

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.

Improving patient privacy and confidentiality in one regional Emergency Department – a quality project

Background: Patient privacy and confidentiality (PPaC) is an important consideration for nurses and other members of the health care team. Can a patient expect to have confidentiality and in particular privacy in the current climate of emergency health care? Do staff who work in the Emergency Department (ED) see confidentiality as an important factor when providing emergency care? These questions are important to consider. Methods: This is a two phased quality improvement project, developed and implemented over a six month period in a busy regional, tertiary referral ED. Results: Issues identified for this department included department design and layout, overcrowding due to patient flow and access block, staff practices and department policies which were also impacted upon by culture of the team, and use of space. Conclusions: Changes successful in improving this issue include increased staff awareness about PPaC, intercom paging prior to nursing handover to remove visitors during handover, one visitor per patient policy, designated places for handover, allocated bed space for patient reviews/assessment and a strategy to temporarily move the patient if procedures would have been undertaken in shared bed space. These are important issues when considering policy, practice and department design in the ED.