We address the problem of learning discrete hidden Markov models from very long sequences of observations. Incremental versions of the Baum-Welch algorithm that approximate the beta-values used in the backward procedure are commonly used for this problem since their memory complexity is independent of the sequence length. However, traditional approaches have two main disadvantages: the approximation of the beta-values deviates far from the real values, and the learning algorithm requires previous knowledge of the topology of the model. This dissertation describes a new incremental Baum-Welch algorithm with a novel backward procedure that improves the approximation of the â-values based on a one-step lookahead in the training sequence and investigates heuristics to prune unnecessary states from an initial complex model. Two new approaches for pruning, greedy and controlled, are introduced and a novel method for identification of ill-conditioned models is presented. Incremental learning of multiple independent observations is also investigated. We justify the new approaches analytically and report empirical results that show they converge faster than the traditional Baum-Welch algorithm using fewer computer resources. Furthermore, we demonstrate that the new learning algorithms converge faster than the previous incremental approaches and can be used to perform online learning of high-quality models useful for classification tasks. Finally, this dissertation explores the use of the new algorithms for anomaly detection in computer systems, that improve our previous research work on detectors based on hidden Markov models integrated into real-world monitoring systems of high-performance computers.

No description available.

No description available.

No description available.

No description available.

No description available.

Purinerge P2X3-Rezeptoren spielen eine bedeutende Rolle in der Vermittlung chronischer Schmerzen, welche ein führendes Problem des Gesundheitswesens mit vielen sozioökonomischen Konsequenzen darstellen. Die Tatsache, dass P2X3-Rezeptoren fast ausschließlich von nozizeptiven Neuronen exprimiert werden, macht sie trotz ihres besonderen Desensitisierungsverhaltens zu vielversprechenden Angriffspunkten zukünftiger Schmerztherapien, beispielsweise mithilfe kompetitiver Antagonisten an diesen Rezeptoren. Zur Analyse der Wechselwirkungen zwischen Agonist und kompetitivem Antagonist wird meist der Schild-Plot benutzt. Jedoch ist dieser im Falle der sehr schnell desensitisierenden P2X3-Rezeptoren ungeeignet, da die Vorbedingung eines stabilen Gleichgewichts zwischen Agonist und Antagonist aufgrund der Desensitisierung nicht erfüllt ist. Ziel der vorliegenden Arbeit war es, eine neue Methode zur Analyse der Interaktion kompetitiver Antagonisten mit ihrer Bindungsstelle am Beispiel des P2X3-Rezeptors zu entwickeln und so für die Antagonistenbindung bedeutende Aminosäuren der Bindungsstelle zu identifizieren. Mittels der Patch-Clamp-Technik wurden die Effekte der Antagonisten A-317491, TNP-ATP und PPADS auf die vom P2X1,3-Rezeptor-selektiven Agonisten α,β-MeATP induzierten Ströme am P2X3-Wildtyp-Rezeptor und an fünf Rezeptormutanten mit veränderter Ligandenbindungsstelle untersucht. Alle Rezeptoren wurden in HEK293-Zellen exprimiert. Anhand der gemessenen Daten wurde ein Hidden Markov Model (HMM) erstellt, welches die sequentiellen Übergänge des Rezeptors von geschlossen zu offen und desensitisiert in An- und Abwesenheit des Antagonisten miteinander kombiniert. Die am P2X3-Rezeptor induzierten Ströme konnten mithilfe dieses Modells korrekt gefittet und die für die Antagonistenbindung wichtigen Aminosäuren innerhalb der Bindungsstelle bestimmt werden. Als Resultat dieser Arbeit konnte außerdem gezeigt werden, dass das HMM eine geeignete Methode zur Analyse der Wirkung kompetitiver Antagonisten an schnell desensitisierenden Rezeptoren darstellt. Die untersuchten Antagonisten A-317491 und TNP-ATP haben einen kompetitiven Wirkmechanismus, während PPADS eine pseudoirreversible Blockade verursacht.

Orchards demand large areas of land, thus they are often situated far from major population centres. As a result it is often difficult to obtain the necessary personnel, limiting both growth and productivity. However, if autonomous robots could be integrated into the operation of the orchard, the manpower demand could be reduced. A key problem for any autonomous robot is localisation; how does the robot know where it is? In agriculture robots, the most common approach is to use GPS positioning. However, in an orchard environment, the dense and tall vegetation restricts the usage to large robots that reach above the surroundings. In order to enable the use of smaller robots, it is instead necessary to use a GPS independent system. However, due to the similarity of the environment and the lack of strong recognisable features, it appears unlikely that typical non-GPS solutions will prove successful. Therefore we present a GPS independent localisation system, specifically aimed for orchards, that utilises the inherent structure of the surroundings. Furthermore, we examine and individually evaluate three related sub-problems. The proposed system utilises a 3D point cloud created from a 2D LIDAR and the robot’s movement. First, we show how the data can be segmented into individual trees using a Hidden Semi-Markov Model. Second, we introduce a set of descriptors for describing the geometric characteristics of the individual trees. Third, we present a robust localisation method based on Hidden Markov Models. Finally, we propose a method for detecting segmentation errors when associating new tree measurements with previously measured trees. Evaluation shows that the proposed segmentation method is accurate and yields very few segmentation errors. Furthermore, the introduced descriptors are determined to be consistent and informative enough to allow localisation. Third, we show that the presented localisation method is robust both to noise and segmentation errors. Finally it is shown that a significant majority of all segmentation errors can be detected without falsely labeling correct segmentations as incorrect. / Eftersom fruktodlingar kräver stora markområden är de ofta belägna långt från större befolkningscentra. Detta gör det svårt att finna tillräckligt med arbetskraft och begränsar expansionsmöjligheterna. Genom att integrera autonoma robotar i drivandet av odlingarna skulle arbetet kunna effektiviseras och behovet av arbetskraft minska. Ett nyckelproblem för alla autonoma robotar är lokalisering; hur vet roboten var den är? I jordbruksrobotar är standardlösningen att använda GPS-positionering. Detta är dock problematiskt i fruktodlingar, då den höga och täta vegetationen begränsar användandet till större robotar som når ovanför omgivningen. För att möjliggöra användandet av mindre robotar är det istället nödvändigt att använda ett GPS-oberoende lokaliseringssystem. Detta problematiseras dock av den likartade omgivningen och bristen på distinkta riktpunkter, varför det framstår som osannolikt att existerande standardlösningar kommer fungera i denna omgivning. Därför presenterar vi ett GPS-oberoende lokaliseringssystem, speciellt riktat mot fruktodlingar, som utnyttjar den naturliga strukturen hos omgivningen.Därutöver undersöker vi och utvärderar tre relaterade delproblem. Det föreslagna systemet använder ett 3D-punktmoln skapat av en 2D-LIDAR och robotens rörelse. Först visas hur en dold semi-markovmodell kan användas för att segmentera datasetet i enskilda träd. Därefter introducerar vi ett antal deskriptorer för att beskriva trädens geometriska form. Vi visar därefter hur detta kan kombineras med en dold markovmodell för att skapa ett robust lokaliseringssystem.Slutligen föreslår vi en metod för att detektera segmenteringsfel när nya mätningar av träd associeras med tidigare uppmätta träd. De föreslagna metoderna utvärderas individuellt och visar på goda resultat. Den föreslagna segmenteringsmetoden visas vara noggrann och ge upphov till få segmenteringsfel. Därutöver visas att de introducerade deskriptorerna är tillräckligt konsistenta och informativa för att möjliggöra lokalisering. Ytterligare visas att den presenterade lokaliseringsmetoden är robust både mot brus och segmenteringsfel. Slutligen visas att en signifikant majoritet av alla segmenteringsfel kan detekteras utan att felaktigt beteckna korrekta segmenteringar som inkorrekta.

This thesis provides an in-depth analyze of expressed sequence tags (EST) that represent pieces of eukaryotic mRNA by using unsupervised hidden Markov model (HMM). ESTs are short nucleotide sequences that are used primarily for rapid identificationof new genes with potential coding regions (CDS). ESTs are made by sequencing on double-stranded cDNA and the synthesizedESTs are stored in digital form, usually in FASTA format. Since sequencing is often randomized and that parts of mRNA contain non-coding regions, some ESTs will not represent CDS.It is desired to remove these unwanted ESTs if the purpose is to identifygenes associated with CDS. Application of stochastic HMM allow identification of region contents in a EST. Softwares like ESTScanuse HMM in which a training of the HMM is done by supervised learning with annotated data. However, because there are not always annotated data at hand this thesis focus on the ability to train an HMM with unsupervised learning on data containing ESTs, both with and without CDS. But the data used for training is not annotated, i.e. the regions that an EST consists of are unknown. In this thesis a new HMM is introduced where the parameters of the HMM are in focus so that they are reasonablyconsistent with biologically important regionsof an mRNA such as the Kozak sequence, poly(A)-signals and poly(A)-tails to guide the training and decoding correctly with ESTs to proper statesin the HMM. Transition probabilities in the HMMhas been adapted so that it represents the mean length and distribution of the different regions in mRNA. Testing of the HMM's specificity and sensitivityhave been performed via BLAST by blasting each EST and compare the BLAST results with the HMM prediction results.A regression analysis test shows that the length of ESTs used when training the HMM is significantly important, the longer the better. The final resultsshows that it is possible to train an HMM with unsupervised machine learning but to be comparable to supervised machine learning as ESTScan, further expansion of the HMM is necessary such as frame-shift correction of ESTs byimproving the HMM's ability to choose correctly positioned start codons or nucleotides. Usually the false positive results are because of incorrectly positioned start codons leadingto too short CDS lengths. Since no frame-shift correction is implemented, short predicted CDS lengths are not acceptable and is hence not counted as coding regionsduring prediction. However, when there is a lack of supervised models then unsupervised HMM is a potential replacement with stable performance and able to be adapted forany eukaryotic organism.

Cette thèse consiste à analyser conjointement des signaux de mouvement des yeux et d’électroencéphalogrammes (EEG) multicanaux acquis simultanément avec des participants effectuant une tâche de lecture de recueil d'informations afin de prendre une décision binaire - le texte est-il lié à un sujet ou non? La recherche d'informations textuelles n'est pas un processus homogène dans le temps - ni d'un point de vue cognitif, ni en termes de mouvement des yeux. Au contraire, ce processus implique plusieurs étapes ou phases, telles que la lecture normale, le balayage, la lecture attentive - en termes d'oculométrie - et la création et le rejet d'hypothèses, la confirmation et la décision - en termes cognitifs.Dans une première contribution, nous discutons d'une méthode d'analyse basée sur des chaînes semi-markoviennes cachées sur les signaux de mouvement des yeux afin de mettre en évidence quatre phases interprétables en termes de stratégie d'acquisition d'informations: lecture normale, lecture rapide, lecture attentive et prise de décision.Dans une deuxième contribution, nous lions ces phases aux changements caractéristiques des signaux EEG et des informations textuelles. En utilisant une représentation en ondelettes des EEG, cette analyse révèle des changements de variance et de corrélation des coefficients inter-canaux, en fonction des phases et de la largeur de bande. En utilisant des méthodes de plongement des mots, nous relions l’évolution de la similarité sémantique au sujet tout au long du texte avec les changements de stratégie.Dans une troisième contribution, nous présentons un nouveau modèle dans lequel les EEG sont directement intégrés en tant que variables de sortie afin de réduire l’incertitude des états. Cette nouvelle approche prend également en compte les aspects asynchrones et hétérogènes des données. / This PhD thesis consists in jointly analyzing eye-tracking signals and multi-channel electroencephalograms (EEGs) acquired concomitantly on participants doing an information collection reading task in order to take a binary decision - is the text related to some topic or not ? Textual information search is not a homogeneous process in time - neither on a cognitive point of view, nor in terms of eye-movement. On the contrary, this process involves several steps or phases, such as normal reading, scanning, careful reading - in terms of oculometry - and creation and rejection of hypotheses, confirmation and decision - in cognitive terms.In a first contribution, we discuss an analysis method based on hidden semi-Markov chains on the eye-tracking signals in order to highlight four interpretable phases in terms of information acquisition strategy: normal reading, fast reading, careful reading, and decision making.In a second contribution, we link these phases with characteristic changes of both EEGs signals and textual information. By using a wavelet representation of EEGs, this analysis reveals variance and correlation changes of the inter-channels coefficients, according to the phases and the bandwidth. And by using word embedding methods, we link the evolution of semantic similarity to the topic throughout the text with strategy changes.In a third contribution, we present a new model where EEGs are directly integrated as output variables in order to reduce the state uncertainty. This novel approach also takes into consideration the asynchronous and heterogeneous aspects of the data.