Ein zunehmend wichtiges Thema in der Informatik ist der Umgang mit Ähnlichkeit in einer großen Anzahl unterschiedlicher Domänen. Derzeit existiert keine universell verwendbare Infrastruktur für die Ähnlichkeitssuche in allgemeinen metrischen Räumen. Ziel der Arbeit ist es, die Grundlage für eine derartige Infrastruktur zu legen, die in klassische Datenbankmanagementsysteme integriert werden könnte. Im Rahmen einer Analyse des State of the Art wird der M-Baum als am besten geeignete Basisstruktur identifiziert. Dieser wird anschließend zum EM-Baum erweitert, wobei strukturelle Kompatibilität mit dem M-Baum erhalten wird. Die Abfragealgorithmen werden im Hinblick auf eine Minimierung notwendiger Distanzberechnungen optimiert. Aufbauend auf einer mathematischen Analyse der Beziehung zwischen Baumstruktur und Abfrageaufwand werden Freiheitsgrade in Baumänderungsalgorithmen genutzt, um Bäume so zu konstruieren, dass Ähnlichkeitsanfragen mit einer minimalen Anzahl an Anfrageoperationen beantwortet werden können. / A topic of growing importance in computer science is the handling of similarity in multiple heterogenous domains. Currently there is no common infrastructure to support this for the general metric space. The goal of this work is lay the foundation for such an infrastructure, which could be integrated into classical data base management systems. After some analysis of the state of the art the M-Tree is identified as most suitable base and enhanced in multiple ways to the EM-Tree retaining structural compatibility. The query algorithms are optimized to reduce the number of necessary distance calculations. On the basis of a mathematical analysis of the relation between the tree structure and the query performance degrees of freedom in the tree edit algorithms are used to build trees optimized for answering similarity queries using a minimal number of distance calculations.

In Natural Language Processing (NLP), speech and text are parsed and generated with language models and parser models, and translated with translation models. Each model contains a set of numerical parameters which are found by applying a suitable training algorithm to a set of training data. Many such training algorithms are instances of the Expectation-Maximization (EM) algorithm. In [BSV15], a generic EM algorithm for NLP is described. This work presents a particular speech model, the Hidden Markov model, and its standard training algorithm, the Baum-Welch algorithm. It is then shown that the Baum-Welch algorithm is an instance of the generic EM algorithm introduced by [BSV15], from which follows that all statements about the generic EM algorithm also apply to the Baum-Welch algorithm, especially its correctness and convergence properties.:1 Introduction 1.1 N-gram models 1.2 Hidden Markov model 2 Expectation-maximization algorithms 2.1 Preliminaries 2.2 Algorithmic skeleton 2.3 Corpus-based step mapping 2.4 Simple counting step mapping 2.5 Regular tree grammars 2.6 Inside-outside step mapping 2.7 Review 3 The Hidden Markov model 3.1 Forward and backward algorithms 3.2 The Baum-Welch algorithm 3.3 Deriving the Baum-Welch algorithm 3.3.1 Model parameter and countable events 3.3.2 Tree-shaped hidden information 3.3.3 Complete-data corpus 3.3.4 Inside weights 3.3.5 Outside weights 3.3.6 Complete-data corpus (cont.) 3.3.7 Step mapping 3.4 Review Appendix A Elided proofs from Chapter 3 A.1 Proof of Lemma 3.8 A.2 Proof of Lemma 3.9 B Formulary for Chapter 3 Bibliography

This thesis explored the possibilities of using a Hidden Markov Model approach for multi-target localisation in an urban environment, with observations generated from Wi-Fi sensors. The area is modelled as a network of nodes and arcs, where the arcs represent sidewalks in the area and constitutes the hidden states in the model. The output of the model is the expected amount of people at each road segment throughout the day. In addition to this, two methods for analyzing the impact of events in the area are proposed. The first method is based on a time series analysis, and the second one is based on the updated transition matrix using the Baum-Welch algorithm. Both methods reveal which road segments are most heavily affected by a surge of traffic in the area, as well as potential bottleneck areas where congestion is likely to have occurred. / I det här examensarbetet har lokalisering av gångtrafikanter med hjälp av Hidden Markov Models utförts. Lokaliseringen är byggd på data från Wi-Fi sensorer i ett område i Stockholm. Området är modellerat som ett graf-baserat nätverk där linjerna mellan noderna representerar möjliga vägar för en person att befinna sig på. Resultatet för varje individ är aggregerat för att visa förväntat antal personer på varje segment över en hel dag. Två metoder för att analysera hur event påverkar området introduceras och beskrivs. Den första är baserad på tidsserieanalys och den andra är en maskinlärningsmetod som bygger på Baum-Welch algoritmen. Båda metoderna visar vilka segment som drabbas mest av en snabb ökning av trafik i området och var trängsel är troligt att förekomma.

Ma thèse concerne des variantes de la propriété (T) de Kazhdan et de la conjecture de Baum-Connes tordues par des représentations de dimension finie qui ne sont pas nécessairement unitaires.<br />Soit G un groupe localement compact et (rho,V) une représentation de dimension finie non nécessairement unitaire de G.<br />Dans le Chapitre 1, nous avons défini un renforcement de la propriété (T) en considérant des produits tensoriels par rho de représentations unitaires de G. Nous avons alors défini deux algèbres de Banach de groupe tordues, Amax(rho) et A(rho), analogues aux C*-algèbres de groupe, C*(G) et C*r(G), et nous avons défini la propriété (T) tordue par rho en termes de Amax(rho). Nous avons ensuite montrer que la plupart des groupes de Lie semi-simples réels ayant la propriété (T) ont la propriété (T) tordue par n'importe quelle représentation irréductible de dimension finie.<br />Les Chapitres 2 et 3 sont consacrés au calcul de la K-théorie des algèbres tordues. Pour ceci, Nous avons défini deux applications d'assemblage tordues du membre de gauche du morphisme de Baum-Connes, noté Ktop(G), dans la K-théorie des algèbres tordues. Nous avons ensuite montrer, dans le Chapitre 3, que ce morphisme de Baum-Connes tordu est bijectif pour une large classe de groupes vérifiant la conjecture de Baum-Connes.<br />Dans le Chapitre 4, nous avons montré que le domaine de définition naturel d'un analogue en K-théorie du produit tensoriel par une représentation de dimension finie est la K-théorie des algèbres tordues et non pas la K-théorie des C*-algèbres de groupe.

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.

Thesis (doctoral)--Swedish University of Agricultural Sciences, 2001. / Includes bibliographical references.

The role of competition in tree communities is increasingly well understood, while little is known about the patterns and mechanisms of the interplay between above- and belowground competition in tree communities. This knowledge, however, is crucial for a better understanding of community dynamics and developing adaptive near-natural management strategies. We assessed neighbourhood interactions in an unmanaged old-growth European beech (Fagus sylvatica) forest by quantifying variation in the intensity of above- (shading) and belowground competition (crowding) among dominant and co-dominant canopy beech trees during tree maturation. Shading had on average a much larger impact on radial growth than crowding and the sensitivity to changes in competitive conditions was lowest for crowding effects. We found that each mode of competition reduced the effect of the other. Increasing crowding reduced the negative effect of shading, and at high levels of shading, crowding actually had a facilitative effect and increased growth. Our study demonstrates that complementarity in above- and belowground processes enable F. sylvatica to alter resource acquisition strategies, thus optimising tree radial growth. As a result, competition seemed to become less important in stands with a high growing stock and tree communities with a long continuity of anthropogenic undisturbed population dynamics. We suggest that growth rates do not exclusively depend on the density of potential competitors at the intraspecific level, but on the conspecific aggregation of large-diameter trees and their functional role for regulating biotic filtering processes. This finding highlights the potential importance of the rarely examined relationship between the spatial aggregation pattern of large-diameter trees and the outcome of neighbourhood interactions, which may be central to community dynamics and the related forest ecosystem services.

This dissertation explores a unique automated approach to map one phoneme set to another, based on the acoustic distances between the individual phonemes. Although the focus of this investigation is on cross-language applications, this automated approach can be extended to same-language but different-database applications as well. The main goal of this investigation is to be able to use the data of a source language, to train the initial acoustic models of a target language for which very little speech data may be available. To do this, an automatic technique for mapping the phonemes of the two data sets must be found. Using this technique, it would be possible to accelerate the development of a speech recognition system for a new language. The current research in the cross-language speech recognition field has focused on manual methods to map phonemes. This investigation has considered an English-to-Afrikaans phoneme mapping, as well as an Afrikaans-to-English phoneme mapping. This has been previously applied to these language instances, but utilising manual phoneme mapping methods. To determine the best phoneme mapping, different acoustic distance measures are compared. The distance measures that are considered are the Kullback-Leibler measure, the Bhattacharyya distance metric, the Mahalanobis measure, the Euclidean measure, the L2 metric and the Jeffreys-Matusita distance. The distance measures are tested by comparing the cross-database recognition results obtained on phoneme models created from the TIMIT speech corpus and a locally-compiled South African SUN Speech database. By selecting the most appropriate distance measure, an automated procedure to map phonemes from the source language to the target language can be done. The best distance measure for the mapping gives recognition rates comparable to a manual mapping process undertaken by a phonetic expert. This study also investigates the effect of the number of Gaussian mixture components on the mapping and on the speech recognition system’s performance. The results indicate that the recogniser’s performance increases up to a limit as the number of mixtures increase. In addition, this study has explored the effect of excluding the Mel Frequency delta and acceleration cepstral coefficients. It is found that the inclusion of these temporal features help improve the mapping and the recognition system’s phoneme recognition rate. Experiments are also carried out to determine the impact of the number of HMM recogniser states. It is found that single-state HMMs deliver the optimum cross-language phoneme recognition results. After having done the mapping, speaker adaptation strategies are applied on the recognisers to improve their target-language performance. The models of a fully trained speech recogniser in a source language are adapted to target-language models using Maximum Likelihood Linear Regression (MLLR) followed by Maximum A Posteriori (MAP) techniques. Embedded Baum-Welch re-estimation is used to further adapt the models to the target language. These techniques result in a considerable improvement in the phoneme recognition rate. Although a combination of MLLR and MAP techniques have been used previously in speech adaptation studies, the combination of MLLR, MAP and EBWR in cross-language speech recognition is a unique contribution of this study. Finally, a data pooling technique is applied to build a new recogniser using the automatically mapped phonemes from the target language as well as the source language phonemes. This new recogniser demonstrates moderate bilingual phoneme recognition capabilities. The bilingual recogniser is then further adapted to the target language using MAP and embedded Baum-Welch re-estimation techniques. This combination of adaptation techniques together with the data pooling strategy is uniquely applied in the field of cross-language recognition. The results obtained using this technique outperform all other techniques tested in terms of phoneme recognition rates, although it requires a considerably more time consuming training process. It displays only slightly poorer phoneme recognition than the recognisers trained and tested on the same language database. / Dissertation (MEng (Computer Engineering))--University of Pretoria, 2006. / Electrical, Electronic and Computer Engineering / unrestricted

Cette thèse s'intéresse aux liens entre la correspondance de Langlands locale et le centre de Bernstein. Pour cela, un cadre a été introduit par Vogan puis développé par Haines : le centre de Bernstein stable. Nous commençons par étendre la correspondance de Springer généralisée au groupe (non connexe) orthogonal. Ensuite, nous énonçons une conjecture concernant les paramètres de Langlands (complets) des représentations supercuspidales d'un groupe p-adique déployé que nous vérifions pour les groupes classiques et le groupe linéaire à l'aide des travaux de Moeglin, Henniart et Harris et Taylor. Nous définissons à l'aide des travaux de Lusztig sur la correspondance de Springer généralisée une application de support cuspidal pour les paramètres de Langlands complets. Avec certains résultats d'Heiermann, nous obtenons un paramétrage de Langlands des représentations irréductibles d'un groupe classique. Par ailleurs, nous énonçons une conjecture « galoisienne » analogue à la conjecture d'Aubert-Baum-Plymen-Solleveld, que nous prouvons à l'aide des résultats précédents. Ceci est une nouvelle preuve de la validité de la conjecture ABPS pour les groupes classiques et explicite ses relations avec la correspondance de Langlands. En conséquence, on obtient la compatibilité de la correspondance de Langlands avec l'induction parabolique pour les groupes classiques. / This thesis focus on links between the local Langlands correspondence and the Bernstein center. A framework was introduced by Vogan and developed by Haines : the stable Bernstein center. We start by extending the generalized Springer correspondence to the orthogonal group (which is disconnected). Then we state a conjecture about (complete) Langlands parameters of supercuspidal representations of a p-adic split group and we prove it for classical and linear groups thanks to the work of M\oe glin, Henniart and Harris and Taylor. Based on the work of Lusztig on generalized Springer correspondence, we define a cuspidal support map for complete Langlands parameters. Referring to some results of Heiermann, we get a Langlands parametrization of the smooth dual of classical groups. Moreover, we state "Galois" version of the Aubert-Baum-Plymen-Solleveld conjecture and we prove that with the previous results. It gives a new proof of the validity of the ABPS conjecture for classical groups and it provides explicit relations with Langlands correspondence. As a corrolary, we obtain the compatibility of the Langlands correspondence with parabolic induction for classical groups.

The role of competition in tree communities is increasingly well understood, while little is known about the patterns and mechanisms of the interplay between above- and belowground competition in tree communities. This knowledge, however, is crucial for a better understanding of community dynamics and developing adaptive near-natural management strategies. We assessed neighbourhood interactions in an unmanaged old-growth European beech (Fagus sylvatica) forest by quantifying variation in the intensity of above- (shading) and belowground competition (crowding) among dominant and co-dominant canopy beech trees during tree maturation. Shading had on average a much larger impact on radial growth than crowding and the sensitivity to changes in competitive conditions was lowest for crowding effects. We found that each mode of competition reduced the effect of the other. Increasing crowding reduced the negative effect of shading, and at high levels of shading, crowding actually had a facilitative effect and increased growth. Our study demonstrates that complementarity in above- and belowground processes enable F. sylvatica to alter resource acquisition strategies, thus optimising tree radial growth. As a result, competition seemed to become less important in stands with a high growing stock and tree communities with a long continuity of anthropogenic undisturbed population dynamics. We suggest that growth rates do not exclusively depend on the density of potential competitors at the intraspecific level, but on the conspecific aggregation of large-diameter trees and their functional role for regulating biotic filtering processes. This finding highlights the potential importance of the rarely examined relationship between the spatial aggregation pattern of large-diameter trees and the outcome of neighbourhood interactions, which may be central to community dynamics and the related forest ecosystem services.