On the Classification of Recursive Languages

A one-sided classifier for a given class of languages converges to 1 on every language from the class and outputs 0 infinitely often on languages outside the class. A two-sided classifier, on the other hand, converges to 1 on languages from the class and converges to 0 on languages outside the class. The present paper investigates one-sided and two-sided classification for classes of recursive languages. Theorems are presented that help assess the classifiability of natural classes. The relationships of classification to inductive learning theory and to structural complexity theory in terms of Turing degrees are studied. Furthermore, the special case of classification from only positive data is also investigated.

On the data consumption benefits of accepting increased uncertainty

In the context of learning paradigms of identification in the limit, we address the question: why is uncertainty sometimes desirable? We use mind change bounds on the output hypotheses as a measure of uncertainty, and interpret ‘desirable’ as reduction in data memorization, also defined in terms of mind change bounds. The resulting model is closely related to iterative learning with bounded mind change complexity, but the dual use of mind change bounds — for hypotheses and for data — is a key distinctive feature of our approach. We show that situations exists where the more mind changes the learner is willing to accept, the lesser the amount of data it needs to remember in order to converge to the correct hypothesis. We also investigate relationships between our model and learning from good examples, set-driven, monotonic and strong-monotonic learners, as well as class-comprising versus class-preserving learnability.

Towards a model for the analysis and description of mathematical knowledge and understanding

Mathematics education literature has called for an abandonment of ontological and epistemological ideologies that have often divided theory-based practice. Instead, a consilience of theories has been sought which would leverage the strengths of each learning theory and so positively impact upon contemporary educational practice. This research activity is based upon Popper’s notion of three knowledge worlds which differentiates the knowledge shared in a community from the personal knowledge of the individual, and Bereiter’s characterisation of understanding as the individual’s relationship to tool-like knowledge. Using these notions, a re-conceptualisation of knowledge and understanding and a subsequent re-consideration of learning theories are proposed as a way to address the challenge set by literature. Referred to as the alternative theoretical framework, the proposed theory accounts for the scaffolded transformation of each individual’s unique understanding, whilst acknowledging the existence of a body of domain knowledge shared amongst participants in a scientific community of practice. The alternative theoretical framework is embodied within an operational model that is accompanied by a visual nomenclature with which to describe consensually developed shared knowledge and personal understanding. This research activity has sought to iteratively evaluate this proposed theory through the practical application of the operational model and visual nomenclature to the domain of early-number counting, addition and subtraction. This domain of mathematical knowledge has been comprehensively analysed and described. Through this process, the viability of the proposed theory as a tool with which to discuss and thus improve the knowledge and understanding with the domain of mathematics has been validated. Putting of the proposed theory into practice has lead to the theory’s refinement and the subsequent achievement of a solid theoretical base for the future development of educational tools to support teaching and learning practice, including computer-mediated learning environments. Such future activity, using the proposed theory, will advance contemporary mathematics educational practice by bringing together the strengths of cognitivist, constructivist and post-constructivist learning theories.

A Stochastic View of Optimal Regret through Minimax Duality

We study the regret of optimal strategies for online convex optimization games. Using von Neumann's minimax theorem, we show that the optimal regret in this adversarial setting is closely related to the behavior of the empirical minimization algorithm in a stochastic process setting: it is equal to the maximum, over joint distributions of the adversary's action sequence, of the difference between a sum of minimal expected losses and the minimal empirical loss. We show that the optimal regret has a natural geometric interpretation, since it can be viewed as the gap in Jensen's inequality for a concave functional--the minimizer over the player's actions of expected loss--defined on a set of probability distributions. We use this expression to obtain upper and lower bounds on the regret of an optimal strategy for a variety of online learning problems. Our method provides upper bounds without the need to construct a learning algorithm; the lower bounds provide explicit optimal strategies for the adversary. Peter L. Bartlett, Alexander Rakhlin

Illegal street racing and associated (hooning) behaviours

In an Australian context, the term hooning refers to risky driving behaviours such as illegal street racing and speed trials, as well as behaviours that involve unnecessary noise and smoke, which include burn outs, donuts, fish tails, drifting and other skids. Hooning receives considerable negative media attention in Australia, and since the 1990s all Australian jurisdictions have implemented vehicle impoundment programs to deal with the problem. However, there is limited objective evidence of the road safety risk associated with hooning behaviours. Attempts to estimate the risk associated with hooning are limited by official data collection and storage practices, and the willingness of drivers to admit to their illegal behaviour in the event of a crash. International evidence suggests that illegal street racing is associated with only a small proportion of fatal crashes; however, hooning in an Australian context encompasses a broader group of driving behaviours than illegal street racing alone, and it is possible that the road safety risks will differ with these behaviours. There is evidence from North American jurisdictions that vehicle impoundment programs are effective for managing drink driving offenders, and drivers who continue to drive while disqualified or suspended both during and post-impoundment. However, these programs used impoundment periods of 30 – 180 days (depending on the number of previous offences). In Queensland the penalty for a first hooning offence is 48 hours, while the vehicle can be impounded for up to 3 months for a second offence, or permanently for a third or subsequent offence within three years. Thus, it remains unclear whether similar effects will be seen for hooning offenders in Australia, as no evaluations of vehicle impoundment programs for hooning have been published. To address these research needs, this program of research consisted of three complementary studies designed to: (1) investigate the road safety implications of hooning behaviours in terms of the risks associated with the specific behaviours, and the drivers who engage in these behaviours; and (2) assess the effectiveness of current approaches to dealing with the problem; in order to (3) inform policy and practice in the area of hooning behaviour. Study 1 involved qualitative (N = 22) and quantitative (N = 290) research with drivers who admitted engaging in hooning behaviours on Queensland roads. Study 2 involved a systematic profile of a large sample of drivers (N = 834) detected and punished for a hooning offence in Queensland, and a comparison of their driving and crash histories with a randomly sampled group of Queensland drivers with the same gender and age distribution. Study 3 examined the post-impoundment driving behaviour of hooning offenders (N = 610) to examine the effects of vehicle impoundment on driving behaviour. The theoretical framework used to guide the research incorporated expanded deterrence theory, social learning theory, and driver thrill-seeking perspectives. This framework was used to explore factors contributing to hooning behaviours, and interpret the results of the aspects of the research designed to explore the effectiveness of vehicle impoundment as a countermeasure for hooning. Variables from each of the perspectives were related to hooning measures, highlighting the complexity of the behaviour. This research found that the road safety risk of hooning behaviours appears low, as only a small proportion of the hooning offences in Study 2 resulted in a crash. However, Study 1 found that hooning-related crashes are less likely to be reported than general crashes, particularly when they do not involve an injury, and that higher frequencies of hooning behaviours are associated with hooning-related crash involvement. Further, approximately one fifth of drivers in Study 1 reported being involved in a hooning-related crash in the previous three years, which is comparable to general crash involvement among the general population of drivers in Queensland. Given that hooning-related crashes represented only a sub-set of crash involvement for this sample, this suggests that there are risks associated with hooning behaviour that are not apparent in official data sources. Further, the main evidence of risk associated with the behaviour appears to relate to the hooning driver, as Study 2 found that these drivers are likely to engage in other risky driving behaviours (particularly speeding and driving vehicles with defects or illegal modifications), and have significantly more traffic infringements, licence sanctions and crashes than drivers of a similar (i.e., young) age. Self-report data from the Study 1 samples indicated that Queensland’s vehicle impoundment and forfeiture laws are perceived as severe, and that many drivers have reduced their hooning behaviour to avoid detection. However, it appears that it is more common for drivers to have simply changed the location of their hooning behaviour to avoid detection. When the post-impoundment driving behaviour of the sample of hooning offenders was compared to their pre-impoundment behaviour to examine the effectiveness of vehicle impoundment in Study 3, it was found that there was a small but significant reduction in hooning offences, and also for other traffic infringements generally. As Study 3 was observational, it was not possible to control for extraneous variables, and is, therefore, possible that some of this reduction was due to other factors, such as a reduction in driving exposure, the effects of changes to Queensland’s Graduated Driver Licensing scheme that were implemented during the study period and affected many drivers in the offender sample due to their age, or the extension of vehicle impoundment to other types of offences in Queensland during the post-impoundment period. However, there was a protective effect observed, in that hooning offenders did not show the increase in traffic infringements in the post period that occurred within the comparison sample. This suggests that there may be some effect of vehicle impoundment on the driving behaviour of hooning offenders, and that this effect is not limited to their hooning driving behaviour. To be more confident in these results, it is necessary to measure driving exposure during the post periods to control for issues such as offenders being denied access to vehicles. While it was not the primary aim of this program of research to compare the utility of different theoretical perspectives, the findings of the research have a number of theoretical implications. For example, it was found that only some of the deterrence variables were related to hooning behaviours, and sometimes in the opposite direction to predictions. Further, social learning theory variables had stronger associations with hooning. These results suggest that a purely legal approach to understanding hooning behaviours, and designing and implementing countermeasures designed to reduce these behaviours, are unlikely to be successful. This research also had implications for policy and practice, and a number of recommendations were made throughout the thesis to improve the quality of relevant data collection practices. Some of these changes have already occurred since the expansion of the application of vehicle impoundment programs to other offences in Queensland. It was also recommended that the operational and resource costs of these laws should be compared to the road safety benefits in ongoing evaluations of effectiveness to ensure that finite traffic policing resources are allocated in a way that produces maximum road safety benefits. However, as the evidence of risk associated with the hooning driver is more compelling than that associated with hooning behaviour, it was argued that the hooning driver may represent the better target for intervention. Suggestions for future research include ongoing evaluations of the effectiveness of vehicle impoundment programs for hooning and other high-risk driving behaviours, and the exploration of additional potential targets for intervention to reduce hooning behaviour. As the body of knowledge regarding the factors contributing to hooning increases, along with the identification of potential barriers to the effectiveness of current countermeasures, recommendations for changes in policy and practice for hooning behaviours can be made.

The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network

Sample complexity results from computational learning theory, when applied to neural network learning for pattern classification problems, suggest that for good generalization performance the number of training examples should grow at least linearly with the number of adjustable parameters in the network. Results in this paper show that if a large neural network is used for a pattern classification problem and the learning algorithm finds a network with small weights that has small squared error on the training patterns, then the generalization performance depends on the size of the weights rather than the number of weights. For example, consider a two-layer feedforward network of sigmoid units, in which the sum of the magnitudes of the weights associated with each unit is bounded by A and the input dimension is n. We show that the misclassification probability is no more than a certain error estimate (that is related to squared error on the training set) plus A3 √((log n)/m) (ignoring log A and log m factors), where m is the number of training patterns. This may explain the generalization performance of neural networks, particularly when the number of training examples is considerably smaller than the number of weights. It also supports heuristics (such as weight decay and early stopping) that attempt to keep the weights small during training. The proof techniques appear to be useful for the analysis of other pattern classifiers: when the input domain is a totally bounded metric space, we use the same approach to give upper bounds on misclassification probability for classifiers with decision boundaries that are far from the training examples.

Bounded parameter Markov Decision Processes with average reward criterion

Bounded parameter Markov Decision Processes (BMDPs) address the issue of dealing with uncertainty in the parameters of a Markov Decision Process (MDP). Unlike the case of an MDP, the notion of an optimal policy for a BMDP is not entirely straightforward. We consider two notions of optimality based on optimistic and pessimistic criteria. These have been analyzed for discounted BMDPs. Here we provide results for average reward BMDPs. We establish a fundamental relationship between the discounted and the average reward problems, prove the existence of Blackwell optimal policies and, for both notions of optimality, derive algorithms that converge to the optimal value function.

Optimal online prediction in adversarial environments

In many prediction problems, including those that arise in computer security and computational finance, the process generating the data is best modelled as an adversary with whom the predictor competes. Even decision problems that are not inherently adversarial can be usefully modeled in this way, since the assumptions are sufficiently weak that effective prediction strategies for adversarial settings are very widely applicable.

High-probability regret bounds for bandit online linear optimization

We present a modification of the algorithm of Dani et al. [8] for the online linear optimization problem in the bandit setting, which with high probability has regret at most O ∗ ( √ T) against an adaptive adversary. This improves on the previous algorithm [8] whose regret is bounded in expectation against an oblivious adversary. We obtain the same dependence on the dimension (n 3/2) as that exhibited by Dani et al. The results of this paper rest firmly on those of [8] and the remarkable technique of Auer et al. [2] for obtaining high probability bounds via optimistic estimates. This paper answers an open question: it eliminates the gap between the high-probability bounds obtained in the full-information vs bandit settings.

On a Syntactic Characterization of Classification with a Mind Change Bound

Most learning paradigms impose a particular syntax on the class of concepts to be learned; the chosen syntax can dramatically affect whether the class is learnable or not. For classification paradigms, where the task is to determine whether the underlying world does or does not have a particular property, how that property is represented has no implication on the power of a classifier that just outputs 1’s or 0’s. But is it possible to give a canonical syntactic representation of the class of concepts that are classifiable according to the particular criteria of a given paradigm? We provide a positive answer to this question for classification in the limit paradigms in a logical setting, with ordinal mind change bounds as a measure of complexity. The syntactic characterization that emerges enables to derive that if a possibly noncomputable classifier can perform the task assigned to it by the paradigm, then a computable classifier can also perform the same task. The syntactic characterization is strongly related to the difference hierarchy over the class of open sets of some topological space; this space is naturally defined from the class of possible worlds and possible data of the learning paradigm.

A Popperian consilience : modelling mathematical knowledge and understanding

Goldin (2003) and McDonald, Yanchar, and Osguthorpe (2005) have called for mathematics learning theory that reconciles the chasm between ideologies, and which may advance mathematics teaching and learning practice. This paper discusses the theoretical underpinnings of a recently completed PhD study that draws upon Popper’s (1978) three-world model of knowledge as a lens through which to reconsider a variety of learning theories, including Piaget’s reflective abstraction. Based upon this consideration of theories, an alternative theoretical framework and complementary operational model was synthesised, the viability of which was demonstrated by its use to analyse the domain of early-number counting, addition and subtraction.

A Regularization Approach to Metrical Task Systems

We address the problem of constructing randomized online algorithms for the Metrical Task Systems (MTS) problem on a metric δ against an oblivious adversary. Restricting our attention to the class of “work-based” algorithms, we provide a framework for designing algorithms that uses the technique of regularization. For the case when δ is a uniform metric, we exhibit two algorithms that arise from this framework, and we prove a bound on the competitive ratio of each. We show that the second of these algorithms is ln n + O(loglogn) competitive, which is the current state-of-the art for the uniform MTS problem.

A comparison of the psychological, social, and legal factors contributing to speeding and drink driving behaviour

Within Australia, motor vehicle injury is the leading cause of hospital admissions and fatalities. Road crash data reveals that among the factors contributing to crashes in Queensland, speed and alcohol continue to be overrepresented. While alcohol is the number one contributing factor to fatal crashes, speeding also contributes to a high proportion of crashes. Research indicates that risky driving is an important contributor to road crashes. However, it has been debated whether all risky driving behaviours are similar enough to be explained by the same combination of factors. Further, road safety authorities have traditionally relied upon deterrence based countermeasures to reduce the incidence of illegal driving behaviours such as speeding and drink driving. However, more recent research has focussed on social factors to explain illegal driving behaviours. The purpose of this research was to examine and compare the psychological, legal, and social factors contributing to two illegal driving behaviours: exceeding the posted speed limit and driving when over the legal blood alcohol concentration (BAC) for the drivers licence type. Complementary theoretical perspectives were chosen to comprehensively examine these two behaviours including Akers’ social learning theory, Stafford and Warr’s expanded deterrence theory, and personality perspectives encompassing alcohol misuse, sensation seeking, and Type-A behaviour pattern. The program of research consisted of two phases: a preliminary pilot study, and the main quantitative phase. The preliminary pilot study was undertaken to inform the development of the quantitative study and to ensure the clarity of the theoretical constructs operationalised in this research. Semi-structured interviews were conducted with 11 Queensland drivers recruited from Queensland Transport Licensing Centres and Queensland University of Technology (QUT). These interviews demonstrated that the majority of participants had engaged in at least one of the behaviours, or knew of someone who had. It was also found among these drivers that the social environment in which both behaviours operated, including family and friends, and the social rewards and punishments associated with the behaviours, are important in their decision making. The main quantitative phase of the research involved a cross-sectional survey of 547 Queensland licensed drivers. The aim of this study was to determine the relationship between speeding and drink driving and whether there were any similarities or differences in the factors that contribute to a driver’s decision to engage in one or the other. A comparison of the participants self-reported speeding and self-reported drink driving behaviour demonstrated that there was a weak positive association between these two behaviours. Further, participants reported engaging in more frequent speeding at both low (i.e., up to 10 kilometres per hour) and high (i.e., 10 kilometres per hour or more) levels, than engaging in drink driving behaviour. It was noted that those who indicated they drove when they may be over the legal limit for their licence type, more frequently exceeded the posted speed limit by 10 kilometres per hour or more than those who complied with the regulatory limits for drink driving. A series of regression analyses were conducted to investigate the factors that predict self-reported speeding, self-reported drink driving, and the preparedness to engage in both behaviours. In relation to self-reported speeding (n = 465), it was found that among the sociodemographic and person-related factors, younger drivers and those who score high on measures of sensation seeking were more likely to report exceeding the posted speed limit. In addition, among the legal and psychosocial factors it was observed that direct exposure to punishment (i.e., being detected by police), direct punishment avoidance (i.e., engaging in an illegal driving behaviour and not being detected by police), personal definitions (i.e., personal orientation or attitudes toward the behaviour), both the normative and behavioural dimensions of differential association (i.e., refers to both the orientation or attitude of their friends and family, as well as the behaviour of these individuals), and anticipated punishments were significant predictors of self-reported speeding. It was interesting to note that associating with significant others who held unfavourable definitions towards speeding (the normative dimension of differential association) and anticipating punishments from others were both significant predictors of a reduction in self-reported speeding. In relation to self-reported drink driving (n = 462), a logistic regression analysis indicated that there were a number of significant predictors which increased the likelihood of whether participants had driven in the last six months when they thought they may have been over the legal alcohol limit. These included: experiences of direct punishment avoidance; having a family member convicted of drink driving; higher levels of Type-A behaviour pattern; greater alcohol misuse (as measured by the AUDIT); and the normative dimension of differential association (i.e., associating with others who held favourable attitudes to drink driving). A final logistic regression analysis examined the predictors of whether the participants reported engaging in both drink driving and speeding versus those who reported engaging in only speeding (the more common of the two behaviours) (n = 465). It was found that experiences of punishment avoidance for speeding decreased the likelihood of engaging in both speeding and drink driving; whereas in the case of drink driving, direct punishment avoidance increased the likelihood of engaging in both behaviours. It was also noted that holding favourable personal definitions toward speeding and drink driving, as well as higher levels of on Type-A behaviour pattern, and greater alcohol misuse significantly increased the likelihood of engaging in both speeding and drink driving. This research has demonstrated that the compliance with the regulatory limits was much higher for drink driving than it was for speeding. It is acknowledged that while speed limits are a fundamental component of speed management practices in Australia, the countermeasures applied to both speeding and drink driving do not appear to elicit the same level of compliance across the driving population. Further, the findings suggest that while the principles underpinning the current regime of deterrence based countermeasures are sound, current enforcement practices are insufficient to force compliance among the driving population, particularly in the case of speeding. Future research should further examine the degree of overlap between speeding and drink driving behaviour and whether punishment avoidance experiences for a specific illegal driving behaviour serve to undermine the deterrent effect of countermeasures aimed at reducing the incidence of another illegal driving behaviour. Furthermore, future work should seek to understand the factors which predict engaging in speeding and drink driving behaviours at the same time. Speeding has shown itself to be a pervasive and persistent behaviour, hence it would be useful to examine why road safety authorities have been successful in convincing the majority of drivers of the dangers of drink driving, but not those associated with speeding. In conclusion, the challenge for road safety practitioners will be to convince drivers that speeding and drink driving are equally risky behaviours, with the ultimate goal to reduce the prevalence of both behaviours.

‘Show Me Your Wiki and I’ll Show you Mine’: Using Online Interactive Media to Improve Academic Writing and Research in a Public Health Under-Graduate Cohort

The number of Internet users in Australia has been steadily increasing, with over 10.9 million people currently subscribed to an internet provider (ABS, 2011). Over the past year, the most avid users of the Internet were 15 – 24 year olds, with approximately 95% accessing the internet on a regular basis (ABS, Social Trends, 2011). While the internet has been described as fundamental to higher education students, social and leisure internet tools are also increasingly being used by these students to generate and maintain their social and professional networks and interactions (Duffy & Bruns 2006). Rapid technological advancements have enabled greater and faster access to information for learning and education (Hemmi et al, 2009; Glassman and Kang, 2011). As such, we sought to integrate interactive, online social media into the assessment profile of a Public Health undergraduate cohort at the Queensland University of Technology (QUT). The aim of this exercise was to engage students to both develop and showcase their research on a range of complex, contemporary health issues within the online forum of Wikispaces (http://www.wikispaces.com/) for review and critique by their peers. We applied Bandura’s Social Learning Theory (SLT) to analyse the interactive processes from which students developed deeper and more sustained learning, and via which their overall academic writing standards were raised. This paper outlines the assessment task, and the students’ feedback on their learning outcomes in relation to the Attentional, Retentional, Motor Reproduction, and Motivational Processes outlined by Bandura in SLT. We conceptualise the findings in a theoretical model, and discuss the implications for this approach within the broader tertiary environment.

“They’re lunatics on the road” : Exploring the normative influences of parents, friends, and police on young novices’ risky driving decisions

Purpose: Young novice drivers experience significantly greater risk of being injured or killed in car crashes than older more experienced drivers. This research utilised a qualitative approach guided by the framework of Akers’ social learning theory. It explored young novice drivers’ perspectives on risky driving including rewards and punishments expected from and administered by parents, friends, and police, imitation of parents’ and friends’ driving, and advantages and disadvantages of risky driving. Methods: Twenty-one young drivers (12 females, 9 males) aged 16–25 years (M = 17.71 years, SD = 2.15) with a Learner (n = 11) or Provisional (n = 10) driver licence participated in individual or small group interviews. Findings and conclusions: Content analysis supported four themes: (1) rewards and (2) punishments for risky driving, and the influence of (3) parents and (4) friends. The young novice drivers differed in their vulnerability to the negative influences of friends and parents, with some novices advising they were able to resist risky normative influences whilst others felt they could not. The authority of the police as enforcers of road rules was either accepted and respected or seen as being used to persecute young novices. These findings suggest that road safety interventions should consider the normative influence of parents and friends on the risky and safe behaviour of young novices. Police were also seen as influential upon behaviour. Future research should explore the complicated relationship between parents, friends, the police, young novices, and their risky driving behaviour.