Esta tesis reune algunas contribuciones al reconocimiento de formas estadístico y, más especícamente, a varias tareas del procesamiento del lenguaje natural. Varias técnicas estadísticas bien conocidas se revisan en esta tesis, a saber: estimación paramétrica, diseño de la función de pérdida y modelado estadístico. Estas técnicas se aplican a varias tareas del procesamiento del lenguajes natural tales como clasicación de documentos, modelado del lenguaje natural y traducción automática estadística. En relación con la estimación paramétrica, abordamos el problema del suavizado proponiendo una nueva técnica de estimación por máxima verosimilitud con dominio restringido (CDMLEa ). La técnica CDMLE evita la necesidad de la etapa de suavizado que propicia la pérdida de las propiedades del estimador máximo verosímil. Esta técnica se aplica a clasicación de documentos mediante el clasificador Naive Bayes. Más tarde, la técnica CDMLE se extiende a la estimación por máxima verosimilitud por leaving-one-out aplicandola al suavizado de modelos de lenguaje. Los resultados obtenidos en varias tareas de modelado del lenguaje natural, muestran una mejora en términos de perplejidad. En a la función de pérdida, se estudia cuidadosamente el diseño de funciones de pérdida diferentes a la 0-1. El estudio se centra en aquellas funciones de pérdida que reteniendo una complejidad de decodificación similar a la función 0-1, proporcionan una mayor flexibilidad. Analizamos y presentamos varias funciones de pérdida en varias tareas de traducción automática y con varios modelos de traducción. También, analizamos algunas reglas de traducción que destacan por causas prácticas tales como la regla de traducción directa; y, así mismo, profundizamos en la comprensión de los modelos log-lineares, que son de hecho, casos particulares de funciones de pérdida. Finalmente, se proponen varios modelos de traducción monótonos basados en técnicas de modelado estadístico . / Andrés Ferrer, J. (2010). Statistical approaches for natural language modelling and monotone statistical machine translation [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/7109

Dans le canal sans fil, la communication coopérative permet à un ou plusieurs relais d’aider la transmission entre la source et la destination. L'objectif de cette thèse est de développer des outils d'analyse de performance pour les systèmes coopératifs utilisant des techniques HARQ. Le premier chapitre de cette thèse donne des informations sur le codage de réseau dans les réseaux coopératifs, et introduit la motivation pour ce travail. L’objectif du deuxième chapitre est d’analyser et d’évaluer les performances de la qualité de service (QoS) des schémas ARQ-STBC, HARQ et FEC, dans le contexte de l’efficacité énergétique, aux niveaux des couches MAC et IP. Afin d’atteindre ce but, une nouvelle méthode d'analyse est dérivé et appliqué au scénario de communication point à point (P2P). Ceci nous permet de comparer les schémas avec et sans retransmissions, et d’établir la consommation d’énergie de chaque système considéré. Cela nous permet de déterminer dans quelles conditions il est énergétiquement plus efficace d’utiliser la protection cross-layer, ou le simple codage de canal. Dans le troisième chapitre une classe de protocoles coopératifs déterministes est introduite. Les protocoles que nous considérons sont différents en termes du comportement de relais(s) de source(s), et de la destination. Nous considérons deux types de protocoles coopératifs: decode-and-forward (DCF), et demodulate-and-forward (DMF). Les performances de chacun de ces protocoles sont analysés, avec et sans combining à la destination. Les évaluations de QoS qui sont examinés sont: le taux d'erreur de trame, le délai, l'efficacité, et le goodput. Les dérivations analytiques sont effectuées à l'aide de la machine à états finis de Markov, ainsi que grâce à l’approche combinatoire. Cependant, il est démontré, que la complexité de ces dérivations augmente au moment ou le crédit de retransmissions et/ou des nœuds dans le réseau est augmentée. Donc cette approche devient non-traitable pour des grands schémas coopératifs. Le quatrième chapitre présente une classe de protocoles de communication probabilistes, où les nœuds retransmettent avec une certaine probabilité. Il est démontré l'existence d'une classe de protocoles probabilistes équivalents, qui permettent d’obtenir les mêmes performances des protocoles déterministes précédemment traités. En utilisant la preuve de concept, nous démontrons que le protocole probabiliste permet d’effectuer les évaluations analytiques de réseaux multi-nœuds, même dans le cas d'un grand nombre de nœuds dans le réseau. Basée sur cela, nous déduisons les paramètres QoS, et les évaluons également par des simulations Monte-Carlo. Les paramètres d'évaluation de performances dérivées sont optimisés en limitant le taux d'erreur de trame, et en essayant de trouver le nombre de transmissions optimal et le code rate qui maximisent le goodput. Il est également démontré que la classe de protocoles probabilistes peut atteindre une région d’optimalité plus grand que la classe de protocoles déterministes. / In the wireless channel, cooperative communications allow one or many relays to assist the communication between the source and the destination. The aim of this thesis is the development of tools for the analysis of cooperative systems, when HARQ techniques are employed to provide cross-layer error protection. The first chapter of the thesis gives background information on network coding in cooperative relay networks, and introduces the motivation for this work. The second chapter is devoted to the analysis of the energetic-fair performance evaluations of FEC, ARQ-STBC and HARQ schemes at the MAC and IP layers. New analytical framework is derived and applied to a point-to-point network scenario. This framework allows to make energetic fair comparisons between the schemes with and without retransmissions. We determine under which channel conditions the cross-layer error protection is energetically more efficient than the simple channel coding. In the third chapter of this thesis we study the cooperative deterministic protocols. The protocols that we consider differ based on the behaviour of the relay(s), source(s), and destination. We consider two major types of cooperative protocols: decode-and forward (DCF), and demodulate-and-forward (DMF). Each of these protocols in its turn is analysed with and without combining mechanisms at the destination. We derive the soft decoders at the destination side for each respective case, and compare the performances of these protocols at the MAC layer. The following quality of service metrics are evaluated: frame error rate, delay, efficiency, goodput. The analysis is done evaluating the steady-state, using finite state Markov chains and a combinatorial approach. The analysis, however, becomes very complex as the number of transmissions and/or nodes in the network increases. The fourth chapter introduces a class of probabilistic communication protocols, where the devices retransmit with a given probability. We prove the existence of an equivalent class of protocols, with the same performances as the deterministic class. Using proofs of concept it is shown that the probabilistic protocol class allows for tractable steady-state analysis, even for many nodes in the network. Based on this, we then derive the QoS metrics and evalute them also by simulations. The derived performance evaluation metrics are then optimized by constraining the frame error rate, and trying to find the most optimal transmissions number and code rates which maximize the goodput. It is furthermore shown, that the equivalent protocol has larger optimal region than the deterministic one.

Notre travail porte sur le développement d'algorithmes performants d'application de grammaires locales, en prenant comme référence ceux des logiciels libres existants: l'analyseur syntaxique descendant d'Unitex et l'analyseur syntaxique à la Earley d'Outilex. Les grammaires locales sont un formalisme de représentation de la syntaxe des langues naturelles basé sur les automates finis. Les grammaires locales sont un modèle de construction de descriptions précises et à grande échelle de la syntaxe des langues naturelles par le biais de l'observation systématique et l'accumulation méthodique de données. L'adéquation des grammaires locales pour cette tâche a été testée à l'occasion de nombreux travaux. À cause de la nature ambiguë des langues naturelles et des propriétés des grammaires locales, les algorithmes classiques d'analyse syntaxique tels que LR, CYK et Tomita ne peuvent pas être utilisés dans le contexte de ce travail. Les analyseurs descendant et Earley sont des alternatives possibles, cependant, ils ont des coûts asymptotiques exponentiels pour le cas des grammaires locales. Nous avons d'abord conçu un algorithme d'application de grammaires locales avec un coût polynomial dans le pire des cas. Ensuite, nous avons conçu des structures de données performantes pour la représentation d'ensembles d'éléments et de séquences. Elles ont permis d'améliorer la vitesse de notre algorithme dans le cas général. Nous avons mis en oeuvre notre algorithme et ceux des systèmes Unitex et Outilex avec les mêmes outils afin de les tester dans les mêmes conditions. En outre, nous avons mis en oeuvre différentes versions de chaque algorithme en utilisant nos structures de données et algorithmes pour la représentation d'ensembles et ceux fournis par la Standard Template Library (STL) de GNU. Nous avons comparé les performances des différents algorithmes et de leurs variantes dans le cadre d'un projet industriel proposé par l'entreprise Telefónica I+D: augmenter la capacité de compréhension d'un agent conversationnel qui fournit des services en ligne, voire l'envoi de SMS à des téléphones portables ainsi que des jeux et d'autres contenus numériques. Les conversations avec l'agent sont en espagnol et passent par Windows Live Messenger. En dépit du domaine limité et de la simplicité des grammaires appliquées, les temps d'exécution de notre algorithme, couplé avec nos structures de données et algorithmes pour la représentation d'ensembles, ont été plus courts. Grâce au coût asymptotique amélioré, on peut s'attendre à des temps d'exécution significativement inférieurs par rapport aux algorithmes utilisés dans les systèmes Unitex et Outilex, pour le cas des grammaires complexes et à large couverture.

This thesis presents a cross-layer design and optimization for emerging wideband wireless networks supporting multimedia applications, considering the interactions of the wireless channel characteristics, the physical and link layer protocols, and the user-perceived Quality-of-Service (QoS). As wireless channels are error-prone and broadcast in nature, both the error control mechanisms and the Media Access Control (MAC) protocols are critical for resource utilization and QoS provisioning. How to analyze, design and optimize the high-rate wireless networks by considering the characteristics of the propagation channels and wideband communication technologies is an open, challenging issue. In this thesis, we consider two important wideband wireless systems, the Ultra-Wideband (UWB) and the Orthogonal Frequency-Division Multiplexing (OFDM) systems. First, we propose the packet-level channel models based on Finite State Markov Chains (FSMCs) for the two systems, which present the statistical properties of the propagation channels and the transmission systems. Second, by incorporating the proposed packet-level channel models, we develop analytical frameworks for quantifying the performance of the high-rate wireless networks, combining the channel fading, physical- and link-layer error-control mechanisms and MAC protocols. Third, to mitigate the impact of channel fading and impairments, a cross-layer joint error-control mechanism is proposed. In addition, we also investigate the impact of channel fading on the video streaming applications, and propose a simple admission control algorithm to ensure QoS. As considering the physical-layer characteristics is critical for ensuring QoS and efficiency of resource utilization, the packet-level channel models, cross-layer analytical frameworks, networking protocols and simulation methodologies proposed in this dissertation are essential for future proliferation of high-rate wireless networks.

We study games where a team of agents needs to collaborate against an adversary to achieve a common goal. The agents make their moves simultaneously, and they have different perceptions about the system state after each move, due to different sensing capabilities. Each agent can only act based on its own experiences, since no communication is assumed during the game. However, before the game begins, the agents can agree on some strategy. A strategy is winning if it guarantees that the agents achieve their goal regardless of how the opponent acts. Identifying a winning strategy, or determining that none exists, is known as the strategy synthesis problem. In this thesis, we only consider a simple objective where the agents must force the game into a given state. Much of the literature is focused on strategies that either rely on that the agents (a) can remember everything that they have perceived or (b) can only remember the last thing that they have perceived. The strategy synthesis problem is (in the general case) undecidable in (a) and has exponential running time in (b). We are interested in the middle, where agents can have finite memory. Specifically, they should be able to keep a finite-state machine, which they update when they make new observations. In our case, the internal state of each agent represents its knowledge about the state of affairs. In other words, an agent is able to update its knowledge, and act based on it. We propose an algorithm for constructing the finite-state machine for each agent, and assigning actions to the internal states before the game begins. Not every winning strategy can be found by the algorithm, but we are convinced that the ones found are valid ones. An important building block for the algorithm is the knowledge-based subset construction (KBSC) used in the literature, which we generalise to games with multiple agents. With our construction, the game can be reduced to another game, still with uncertain state information, but with less or equal uncertainty. The construction can be applied arbitrarily many times, but it appears as if it stabilises (so that no new knowledge is gained) after only a few steps. We discuss this and other interesting properties of our algorithm in the final chapters of this thesis. / Vi studerar spel där ett lag agenter behöver samarbeta mot en motståndare för att uppnå ett mål. Agenterna agerar samtidigt, och vid varje steg av spelet så har de olika uppfattning om spelets tillstånd. De antas inte kunna kommunicera under spelets gång, så agenterna kan bara agera utifrån sina egna erfarenheter. Innan spelet börjar kan agenterna dock komma överrens om en strategi. En sådan strategi är vinnande om den garanterar att agenterna når sitt mål oavsett hur motståndaren beter sig. Att hitta en vinnande strategi är känt som syntesproblemet. I den här avhandlingen behandlar vi endast ett enkelt mål där agenterna måste tvinga in spelet i ett givet tillstånd. Mycket av litteraturen handlar om strategier där agenterna antingen antas (a) kunna minnas allt som de upplevt eller (b) bara kunna minnas det senaste de upplevt. Syntesproblemet är (i det generella fallet) oavgörbart i (a) och tar exponentiell tid i (b). Vi är intressede av fallet där agenter kan ha ändligt minne. De ska kunna ha en ändlig automat, som de kan uppdatera när de får nya observationer. I vårt fall så representerar det interna tillståndet agentens kunskap om spelets tillstånd. En agent kan då uppdatera sin kunskap och agera utifrån den. Vi föreslår en algoritm som konstruerar en ändlig automat åt varje agent, samt instruktioner för vad agenten ska göra i varje internt tillstånd. Varje vinnande strategi kan inte hittas av algoritmen, men vi är övertygade om att de som hittas är giltiga. En viktig byggsten är den kunskapsbaserade delmängskonstruktionen (KBSC), som vi generaliserar till spel med flera agenter. Med vår konstruktion kan spelet reduceras till ett annat spel som har mindre eller lika mycket osäkerhet. Detta kan göras godtyckligt många gånger, men det verkar som om att ingen ny kunskap tillkommer efter bara några gånger. Vi diskuterar detta vidare tillsammans med andra intressanta egenskaper hos algoritmen i de sista kapitlen i avhandlingen.

Esta tesis presenta diversas contribuciones en los campos de la clasificación automática de texto, traducción automática y traducción asistida por ordenador bajo el marco estadístico. En clasificación automática de texto, se propone una nueva aplicación llamada clasificación de texto bilingüe junto con una serie de modelos orientados a capturar dicha información bilingüe. Con tal fin se presentan dos aproximaciones a esta aplicación; la primera de ellas se basa en una asunción naive que contempla la independencia entre las dos lenguas involucradas, mientras que la segunda, más sofisticada, considera la existencia de una correlación entre palabras en diferentes lenguas. La primera aproximación dió lugar al desarrollo de cinco modelos basados en modelos de unigrama y modelos de n-gramas suavizados. Estos modelos fueron evaluados en tres tareas de complejidad creciente, siendo la más compleja de estas tareas analizada desde el punto de vista de un sistema de ayuda a la indexación de documentos. La segunda aproximación se caracteriza por modelos de traducción capaces de capturar correlación entre palabras en diferentes lenguas. En nuestro caso, el modelo de traducción elegido fue el modelo M1 junto con un modelo de unigramas. Este modelo fue evaluado en dos de las tareas más simples superando la aproximación naive, que asume la independencia entre palabras en differentes lenguas procedentes de textos bilingües. En traducción automática, los modelos estadísticos de traducción basados en palabras M1, M2 y HMM son extendidos bajo el marco de la modelización mediante mixturas, con el objetivo de definir modelos de traducción dependientes del contexto. Asimismo se extiende un algoritmo iterativo de búsqueda basado en programación dinámica, originalmente diseñado para el modelo M2, para el caso de mixturas de modelos M2. Este algoritmo de búsqueda n / Civera Saiz, J. (2008). Novel statistical approaches to text classification, machine translation and computer-assisted translation [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/2502

[ES] La detección de palabras clave (Keyword Spotting, en inglés), aplicada a documentos de texto manuscrito, tiene como objetivo recuperar los documentos, o partes de ellos, que sean relevantes para una cierta consulta (query, en inglés), indicada por el usuario, entre una gran colección de documentos. La temática ha recogido un gran interés en los últimos 20 años entre investigadores en Reconocimiento de Formas (Pattern Recognition), así como bibliotecas y archivos digitales. Esta tesis, en primer lugar, define el objetivo de la detección de palabras clave a partir de una perspectiva basada en la Teoría de la Decisión y una formulación probabilística adecuada. Más concretamente, la detección de palabras clave se presenta como un caso particular de Recuperación de la Información (Information Retrieval), donde el contenido de los documentos es desconocido, pero puede ser modelado mediante una distribución de probabilidad. Además, la tesis también demuestra que, bajo las distribuciones de probabilidad correctas, el marco de trabajo desarrollada conduce a la solución óptima del problema, según múltiples medidas de evaluación utilizadas tradicionalmente en el campo. Más tarde, se utilizan distintos modelos estadísticos para representar las distribuciones necesarias: Redes Neuronales Recurrentes o Modelos Ocultos de Markov. Los parámetros de estos son estimados a partir de datos de entrenamiento, y las respectivas distribuciones son representadas mediante Transductores de Estados Finitos con Pesos (Weighted Finite State Transducers). Con el objetivo de hacer que el marco de trabajo sea práctico en grandes colecciones de documentos, se presentan distintos algoritmos para construir índices de palabras a partir de modelos probabilísticos, basados tanto en un léxico cerrado como abierto. Estos índices son muy similares a los utilizados por los motores de búsqueda tradicionales. Además, se estudia la relación que hay entre la formulación probabilística presentada y otros métodos de gran influencia en el campo de la detección de palabras clave, destacando cuáles son las limitaciones de los segundos. Finalmente, todas la aportaciones se evalúan de forma experimental, no sólo utilizando pruebas académicas estándar, sino también en colecciones con decenas de miles de páginas provenientes de manuscritos históricos. Los resultados muestran que el marco de trabajo presentado permite construir sistemas de detección de palabras clave muy rápidos y precisos, con una sólida base teórica. / [CA] La detecció de paraules clau (Keyword Spotting, en anglès), aplicada a documents de text manuscrit, té com a objectiu recuperar els documents, o parts d'ells, que siguen rellevants per a una certa consulta (query, en anglès), indicada per l'usuari, dintre d'una gran col·lecció de documents. La temàtica ha recollit un gran interés en els últims 20 anys entre investigadors en Reconeixement de Formes (Pattern Recognition), així com biblioteques i arxius digitals. Aquesta tesi defineix l'objectiu de la detecció de paraules claus a partir d'una perspectiva basada en la Teoria de la Decisió i una formulació probabilística adequada. Més concretament, la detecció de paraules clau es presenta com un cas concret de Recuperació de la Informació (Information Retrieval), on el contingut dels documents és desconegut, però pot ser modelat mitjançant una distribució de probabilitat. A més, la tesi també demostra que, sota les distribucions de probabilitat correctes, el marc de treball desenvolupat condueix a la solució òptima del problema, segons diverses mesures d'avaluació utilitzades tradicionalment en el camp. Després, diferents models estadístics s'utilitzen per representar les distribucions necessàries: Xarxes Neuronal Recurrents i Models Ocults de Markov. Els paràmetres d'aquests són estimats a partir de dades d'entrenament, i les corresponents distribucions són representades mitjançant Transductors d'Estats Finits amb Pesos (Weighted Finite State Transducers). Amb l'objectiu de fer el marc de treball útil per a grans col·leccions de documents, es presenten distints algorismes per construir índexs de paraules a partir dels models probabilístics, tan basats en un lèxic tancat com en un obert. Aquests índexs són molt semblants als utilitzats per motors de cerca tradicionals. A més a més, s'estudia la relació que hi ha entre la formulació probabilística presentada i altres mètodes de gran influència en el camp de la detecció de paraules clau, destacant algunes limitacions dels segons. Finalment, totes les aportacions s'avaluen de forma experimental, no sols utilitzant proves acadèmics estàndard, sinó també en col·leccions amb desenes de milers de pàgines provinents de manuscrits històrics. Els resultats mostren que el marc de treball presentat permet construir sistemes de detecció de paraules clau molt acurats i ràpids, amb una sòlida base teòrica. / [EN] Keyword Spotting, applied to handwritten text documents, aims to retrieve the documents, or parts of them, that are relevant for a query, given by the user, within a large collection of documents. The topic has gained a large interest in the last 20 years among Pattern Recognition researchers, as well as digital libraries and archives. This thesis, first defines the goal of Keyword Spotting from a Decision Theory perspective. Then, the problem is tackled following a probabilistic formulation. More precisely, Keyword Spotting is presented as a particular instance of Information Retrieval, where the content of the documents is unknown, but can be modeled by a probability distribution. In addition, the thesis also proves that, under the correct probability distributions, the framework provides the optimal solution, under many of the evaluation measures traditionally used in the field. Later, different statistical models are used to represent the probability distribution over the content of the documents. These models, Hidden Markov Models or Recurrent Neural Networks, are estimated from training data, and the corresponding distributions over the transcripts of the images can be efficiently represented using Weighted Finite State Transducers. In order to make the framework practical for large collections of documents, this thesis presents several algorithms to build probabilistic word indexes, using both lexicon-based and lexicon-free models. These indexes are very similar to the ones used by traditional search engines. Furthermore, we study the relationship between the presented formulation and other seminal approaches in the field of Keyword Spotting, highlighting some limitations of the latter. Finally, all the contributions are evaluated experimentally, not only on standard academic benchmarks, but also on collections including tens of thousands of pages of historical manuscripts. The results show that the proposed framework and algorithms allow to build very accurate and very fast Keyword Spotting systems, with a solid underlying theory. / Puigcerver I Pérez, J. (2018). A Probabilistic Formulation of Keyword Spotting [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/116834

Die Nutzung historisch solider Lastannahmen, wie sie zum Beispiel die VDV Richtlinie 152 in der Fassung von 1992 festlegt, ist für die Festigkeitsauslegung neuartiger Straßen- und Stadtbahnfahrzeuge unzureichend, da die Annahmen und Methoden der Komplexität und insbesondere der Nichtlinearität moderner Fahrzeugkonzepte keine Rechnung tragen. Diese Arbeit zeigt auf, wie sich entstandene Lücken in den Lastannahmen durch Simulation und Messung von Fahrzeug und Gleis analysieren, verstehen und schließen lassen. Den Kern bildet dabei der Einsatz detaillierterer Simulationsmodelle von Fahrzeug und Gleis, deren Eingangsdaten mit Hilfe von Messungen gewonnen und deren Ausgangsdaten mit ihnen verifiziert und ergänzt werden müssen. Hierfür werden Methoden und Werkzeuge entwickelt, die ein ein vielseitiges Baukastensystem für die Fahrzeuganalyse, Modellvalidierung und Datenbewertung bilden, und zu sicheren Lastannahmen für die Fahrzeugauslegung führen.

Die Nutzung historisch solider Lastannahmen, wie sie zum Beispiel die VDV Richtlinie 152 in der Fassung von 1992 festlegt, ist für die Festigkeitsauslegung neuartiger Straßen- und Stadtbahnfahrzeuge unzureichend, da die Annahmen und Methoden der Komplexität und insbesondere der Nichtlinearität moderner Fahrzeugkonzepte keine Rechnung tragen. Diese Arbeit zeigt auf, wie sich entstandene Lücken in den Lastannahmen durch Simulation und Messung von Fahrzeug und Gleis analysieren, verstehen und schließen lassen. Den Kern bildet dabei der Einsatz detaillierterer Simulationsmodelle von Fahrzeug und Gleis, deren Eingangsdaten mit Hilfe von Messungen gewonnen und deren Ausgangsdaten mit ihnen verifiziert und ergänzt werden müssen. Hierfür werden Methoden und Werkzeuge entwickelt, die ein ein vielseitiges Baukastensystem für die Fahrzeuganalyse, Modellvalidierung und Datenbewertung bilden, und zu sicheren Lastannahmen für die Fahrzeugauslegung führen.