This thesis is concerned with the problem of how to make decisions in an uncertain world. We use a model of uncertainty based on Markov decision problems, and develop a number of algorithms for decision-making both for the planning problem, in which the model is known in advance, and for the reinforcement learning problem in which the decision-making agent does not know the model and must learn to make good decisions by trial and error. The basis for much of this work is the use of structural representations of problems. If a problem is represented in a structured way we can compute or learn plans that take advantage of this structure for computational gains. This is because the structure allows us to perform abstraction. Rather than reasoning about each situation in which a decision must be made individually, abstraction allows us to group situations together and reason about a whole set of them in a single step. Our approach to abstraction has the additional advantage that we can dynamically change the level of abstraction, splitting a group of situations in two if they need to be reasoned about separately to find an acceptable plan, or merging two groups together if they no longer need to be distinguished. We present two planning algorithms and one learning algorithm that use this approach. A second idea we present in this thesis is a novel approach to the exploration problem in reinforcement learning. The problem is to select actions to perform given that we would like good performance now and in the future. We can select the current best action to perform, but this may prevent us from discovering that another action is better, or we can take an exploratory action, but we risk performing poorly now as a result. Our Bayesian approach makes this tradeoff explicit by representing our uncertainty about the values of states and using this measure of uncertainty to estimate the value of the information we could gain by performing each action. We present both model-free and model-based reinforcement learning algorithms that make use of this exploration technique. Finally, we show how these ideas fit together to produce a reinforcement learning algorithm that uses structure to represent both the problem being solved and the plan it learns, and that selects actions to perform in order to learn using our Bayesian approach to exploration.

This study seeks to design algorithms that may be used to determine if a given lattice is a good approximation to a given rigid protein structure. Ideal lattice models discovered using our techniques may then be used in algorithms for protein folding and inverse protein folding. In this study we develop methods based on dynamic programming and branch and bound in an effort to identify “ideal” lattice models. To further our understanding of the concepts behind the methods we have utilized a simple cubic lattice for our analysis. The algorithms may be adapted to work on any lattice. We describe two algorithms. One for aligning the protein backbone to the lattice as a walk. This algorithm runs in polynomial time. The second algorithm for aligning a protein backbone as a path to the lattice. Both the algorithms seek to minimize the CRMS deviation of the alignment. The second problem was recently shown to be NP-Complete, hence it is highly unlikely that an efficient algorithm exists. The first algorithm gives a lower bound on the optimal solution to the second problem, and can be used in a branch and bound procedure. Further, we perform an empirical evaluation of our algorithm on proteins from the Protein Data Bank (PDB). / ix, 47 leaves ; 29 cm.

An algorithmic method for the recognition of fungal spore cells in microscopic images, as well as its development and its origin, are described and demonstrated. The process is designed for a machine vision project which automatically identifies fungal spores within field samples for epidemiological simulation models. The method consists of a three-pass system that successfully recognizes spores in any position and which is tolerant of occlusion. / The algorithm, as implemented, demonstrated an accuracy of $ pm$5.3% on low quality images which is less than the assumed error of humans performing the same task. The processing speed also compared favorably with the performance of humans. / The method developed presents a framework of description that, through the first two passes, highlights certain distinctive aspects within an image. Those highlighted aspects are then recognized by the third pass. The system is loosely based on biological vision, is extremely versatile and could be adapted for the recognition of virtually any object in a digitized image.

No description available.

Thesis (PhD)--Stellenbosch University, 2013. / ENGLISH ABSTRACT: An area of data mining and statistics that is currently receiving considerable attention is the field of multi-label learning. Problems in this field are concerned with scenarios where each data case can be associated with a set of labels instead of only one. In this thesis, we review the field of multi-label learning and discuss the lack of suitable benchmark data available for evaluating multi-label algorithms. We propose a technique for simulating multi-label data, which allows good control over different data characteristics and which could be useful for conducting comparative studies in the multi-label field. We also discuss the explosion in data in recent years, and highlight the need for some form of dimension reduction in order to alleviate some of the challenges presented by working with large datasets. Feature (or variable) selection is one way of achieving dimension reduction, and after a brief discussion of different feature selection techniques, we propose a new technique for feature selection in a multi-label context, based on the concept of independent probes. This technique is empirically evaluated by using simulated multi-label data and it is shown to achieve classification accuracy with a reduced set of features similar to that achieved with a full set of features. The proposed technique for feature selection is then also applied to the field of music information retrieval (MIR), specifically the problem of musical instrument recognition. An overview of the field of MIR is given, with particular emphasis on the instrument recognition problem. The particular goal of (polyphonic) musical instrument recognition is to automatically identify the instruments playing simultaneously in an audio clip, which is not a simple task. We specifically consider the case of duets – in other words, where two instruments are playing simultaneously – and approach the problem as a multi-label classification one. In our empirical study, we illustrate the complexity of musical instrument data and again show that our proposed feature selection technique is effective in identifying relevant features and thereby reducing the complexity of the dataset without negatively impacting on performance. / AFRIKAANSE OPSOMMING: ‘n Area van dataontginning en statistiek wat tans baie aandag ontvang, is die veld van multi-etiket leerteorie. Probleme in hierdie veld beskou scenarios waar elke datageval met ‘n stel etikette geassosieer kan word, instede van slegs een. In hierdie skripsie gee ons ‘n oorsig oor die veld van multi-etiket leerteorie en bespreek die gebrek aan geskikte standaard datastelle beskikbaar vir die evaluering van multi-etiket algoritmes. Ons stel ‘n tegniek vir die simulasie van multi-etiket data voor, wat goeie kontrole oor verskillende data eienskappe bied en wat nuttig kan wees om vergelykende studies in die multi-etiket veld uit te voer. Ons bespreek ook die onlangse ontploffing in data, en beklemtoon die behoefte aan ‘n vorm van dimensie reduksie om sommige van die uitdagings wat deur sulke groot datastelle gestel word die hoof te bied. Veranderlike seleksie is een manier van dimensie reduksie, en na ‘n vlugtige bespreking van verskillende veranderlike seleksie tegnieke, stel ons ‘n nuwe tegniek vir veranderlike seleksie in ‘n multi-etiket konteks voor, gebaseer op die konsep van onafhanklike soek-veranderlikes. Hierdie tegniek word empiries ge-evalueer deur die gebruik van gesimuleerde multi-etiket data en daar word gewys dat dieselfde klassifikasie akkuraatheid behaal kan word met ‘n verminderde stel veranderlikes as met die volle stel veranderlikes. Die voorgestelde tegniek vir veranderlike seleksie word ook toegepas in die veld van musiek dataontginning, spesifiek die probleem van die herkenning van musiekinstrumente. ‘n Oorsig van die musiek dataontginning veld word gegee, met spesifieke klem op die herkenning van musiekinstrumente. Die spesifieke doel van (polifoniese) musiekinstrument-herkenning is om instrumente te identifiseer wat saam in ‘n oudiosnit speel. Ons oorweeg spesifiek die geval van duette – met ander woorde, waar twee instrumente saam speel – en hanteer die probleem as ‘n multi-etiket klassifikasie een. In ons empiriese studie illustreer ons die kompleksiteit van musiekinstrumentdata en wys weereens dat ons voorgestelde veranderlike seleksie tegniek effektief daarin slaag om relevante veranderlikes te identifiseer en sodoende die kompleksiteit van die datastel te verminder sonder ‘n negatiewe impak op klassifikasie akkuraatheid.

This thesis presents a method of algorithmic composition in which the music is seen as motion through a multidimensional musical space. An analogy is drawn between physical space and musical space, each direction of the physical space corresponding to a musical parameter. A computer program was developed using the MAX programming environment to simulate the goaldirected motion of a mobile robot through an environment containing obstacles. The potential field method of mobile robot path planning was used. The program maps the location of the robot to musical parameters in the musical space. Based on the instantaneous values of the musical parameters, the program generates melodic material and transmits the resulting MIDI data to a synthesizer. For this research, the program was limited to three spatial dimensions and one obstacle. The program successfully created simple compositions consisting of large musical gestures. A model composition was created. Suggestions were made for further development and more elaborate applications of the method. / School of Music

The G-Net research group at Ball State University previously developed a graph editor, written in Java, with limited algorithm support. This editor was modified until the code had the instability of a legacy system. It was decided that, rather than continue working with the old system, a new version would be created.The enhancements planned for this new version were more efficient data structures, easy addition of new algorithms, and animated algorithm output. Additionally, the new version was to be written in compliance with the latest Java standards. This paper describes the structure of this new program, Jedit3.1. An overview of the structure of the program and detailed descriptions of the material that future programmers will need to understand in order to add new algorithms is included. Appropriate descriptions are included for files that future programmers should understand but not necessarily modify. / Department of Computer Science

A pitch spelling algorithm predicts the pitch names (e.g., C♯4, B♭5 etc.) of the notes in a passage of tonal music, when given the onset-time, MIDI note number and possibly the duration and voice of each note. A new algorithm, called ps13, was compared with the algorithms of Longuet-Higgins, Cambouropoulos, Temperley and Chew and Chen by running various versions of these algorithms on a ‘clean’, score-derived test corpus, C, containing 195972 notes, equally divided between eight classical and baroque composers. The standard deviation of the accuracies achieved by each algorithm over the eight composers was used to measure style dependence (SD). The best versions of the algorithms were tested for robustness to temporal deviations by running them on a ‘noisy’ version of the test corpus, denoted by C'. A version of ps13 called PS13s1 was the most accurate of the algorithms tested, achieving note accuracies of 99.44% (SD = 0.45) on C and 99.41% (SD = 0.50) on C'. A real-time version of PS13s1 also out-performed the other real-time algorithms tested, achieving note accuracies of 99.19% (SD = 0.51) on C and 99.16% (SD = 0.53) on C'. PS13s1 was also as fast and easy to implement as any of the other algorithms. New, optimised versions of Chew and Chen’s algorithm were the least dependent on style over C. The most accurate of these achieved note accuracies of 99.15% (SD = 0.42) on C and 99.12% (SD = 0.47) on C'. It was proved that replacing the spiral array in Chew and Chen’s algorithm with the line of fifths never changes its output. A new, optimised version of Cambouropoulos’s algorithm made 8% fewer errors over C than the most accurate of the versions described by Cambouropoulos himself. This algorithm achieved note accuracies of 99.15% (SD = 0.47) on C and 99.07% (SD = 0.53) on C'. A new implementation of the most accurate of the versions described by Cambouropoulos achieved note accuracies of 99.07% (SD = 0.46) on C and 99.13% (SD = 0.39) on C', making it the least dependent on style over C'. However, Cambouropoulos’s algorithms were among the slowest of those tested. When Temperley and Sleator’s harmony and meter programs were used for pitch spelling, they were more affected by temporal deviations and tempo changes than any of the other algorithms tested. When enharmonic changes were ignored and the music was at a natural tempo, these programs achieved note accuracies of 99.27% (SD = 1.30) on C and 97.43% (SD = 1.69) on C'. A new implementation, called TPROne, of just the first preference rule in Temperley’s theory achieved note accuracies of 99.06% (SD = 0.63) on C and 99.16% (SD = 0.52) on C'. TPROne’s performance was independent of tempo and less dependent on style than that of the harmony and meter programs. Of the several versions of Longuet-Higgins’s algorithm tested, the best was the original one, implemented in his music.p program. This algorithm achieved note accuracies of 98.21% (SD = 1.79) on C and 98.25% (SD = 1.71) on C', but only when the data was processed a voice at a time. None of the attempts to take voice-leading into account in the algorithms considered in this study resulted in an increase in note accuracy and the most accurate algorithm, PS13s1, ignores voice-leading altogether. The line of fifths is used in most of the algorithms tested, including PS13s1. However, the superior accuracy achieved by PS13s1 suggests that pitch spelling accuracy can be optimised by modelling the local key as a pitch class frequency distribution instead of a point on the line of fifths, and by keeping pitch names close to the local tonic(s) on the line of fifths rather than close on the line of fifths to the pitch names of neighbouring notes.

<p>Promoter detection, especially in prokaryotes, has always been an uphill task and may remain so, because of the many varieties of sigma factors employed by various organisms in transcription. The situation is made more complex by the fact, that any seemingly unimportant sequence segment may be turned into a promoter sequence by an activator or repressor (if the actual promoter sequence is made unavailable). Nevertheless, a computational approach to promoter detection has to be performed due to number of reasons. The obvious that comes to mind is the long and tedious process involved in elucidating promoters in the &lsquo / wet&rsquo / laboratories not to mention the financial aspect of such endeavors. Promoter detection/prediction of an organism with few characterized promoters (M.tuberculosis) as envisaged at the beginning of this work was never going to be easy. Even for the few known Mycobacterial promoters, most of the respective sigma factors associated with their transcription were not known. If the information (promoter-sigma) were available, the research would have been focused on categorizing the promoters according to sigma factors and training the methods on the respective categories. That is assuming that, there would be enough training data for the respective categories. Most promoter detection/prediction studies have been carried out on E.coli because of the availability of a number of experimentally characterized promoters (+- 310). Even then, no researcher to date has extended the research to the entire E.coli genome.</p>

The coverage of a learning algorithm is the number of concepts that can be learned by that algorithm from samples of a given size for given accuracy and confidence parameters. This thesis begins by asking whether good learning algorithms can be designed by maximizing their coverage. There are three questions raised by this approach: (i) For given sample size and other learning parameters, what is the largest possible coverage that any algorithm can achieve? (ii) Can we design a learning algorithm that attains this optimal coverage? (iii) What is the coverage of existing learning algorithms? This thesis contributes to answering each of these questions. First, we generalize the upper bound on coverage given in [Dietterich 89]. Next, we present two learning algorithms and determine their coverage analytically. The coverage of the first algorithm, Multi-Balls, is shown to be quite close to the upper bound. The coverage of the second algorithm, Large-Ball, turns out to be even better than Multi-Balls in many situations. Third, we considerably improve upon Dietterich's limited experiments for estimating the coverage of existing learning algorithms. We find that the coverage of Large-Ball exceeds the coverage of ID3 [Quinlan 86] and FRINGE [Pagano and Haussler 90] by more than an order of magnitude in most cases. Nevertheless, further analysis of Large-Ball shows that this algorithm is not likely to be of any practical help. Although this algorithm learns many concepts, these do not seem to be very interesting concepts. These results lead us to the conclusion that coverage maximization alone does not appear to yield practically-useful learning algorithms. The results motivate considering the biased-coverage under which different concepts are assigned different weight or importance based on given background assumptions. As an example of the new setting, we consider learning situations where many of the features present in the domain are irrelevant to the concept being learned. These situations are often encountered in practice. For this problem, we define and study the MIN-FEATURES bias in which hypotheses definable using a smaller number of features involved are preferred. We prove a tight bound on the number of examples needed for learning. Our results show that, if the MIN-FEATURES bias is implemented, then the presence of many irrelevant features does not make the learning problem substantially harder in terms of the needed number of examples. The thesis also introduces and evaluates a number of algorithms that implement or approximate the MIN-FEATURES bias. / Graduation date: 1993