La modélisation de la langue naturelle est l'un des défis fondamentaux de l'intelligence artificielle et de la conception de systèmes interactifs. Ses applications s'étendent à travers divers domaines, tels que les systèmes de dialogue, la génération de texte et la traduction automatique, et a été largement étudié au cours des derni ères décennies. Le problème commun à la plupart des applications du langage est la modélisation de la distribution d'un mot étant donné son contexte, généralement constitué d'une séquence de mots voisins dans le texte.

Les modèles de langue les plus simples sont basés sur la fréquence d'apparition de mots ou de séquences de mots. Comme la taille du vocabulaire est en genérale importante, de nombres occurences de phrase probables ne sont jamais observées dans un corpus de textes, donnant lieu a un un problème d'estimation ou le nombre de paramètres est largement supérieur à la taille de l'échantillon d'apprentissage. Cela entraine une surestimation de la probabilité des séquences observées et une sous-estimation des séquences non observées. Ainsi, il est nécessaire d'utiliser des connaissances ap r i o r iavant de modifier de maniére appropriée la distribution. Les fréquences empiriques sont souvent corrigées grâce àd e st e c h n i q u e sd el i s s a g e . L e sm é t h o d e sd ' a p p r e n t i s s a g es t a t i s t i q u e sb a s é e ss u rl am i nimisation d'un coût empirique correspondent à un modèle approprié aux données et sont une alternative interessante aux méthodes basés sur les fréquences. De nombreuses techniques d'apprentissage ont été appliquées à la construction de modèles de langue; modèles génératifs (Dirichlet, Pitman-Yor et les processus Pitman-Yor hiérarchiques), les modèles discriminants (entropie maximale, conditional random fields) et les représentations de distribution (réseaux de neurones, machines de Boltzman, modéles log-bilinéaire).

Nous proposons un modèle log-linéaire discriminatif donnant la distribution des mots qui suivent un contexte donné. En raison de la parcimonie des données, il est nécessaire de régulariser de manière approprièe le modèle en utilisant un terme de pénalité. Cependant, des choix simples de régularisation (comme `2 2 et `1 pénalités) ne parviennent pas à capturer les dépendances longues: ils sur-apprennent sur les données lorsqu'on augmente de la longueur de contexte, car ils sont agnostiques à la structure séquentielle du problème. Nous montrons qu'il est nécessaire de concevoir un terme de pénalité qui code correctement la structure de l'espace fonctionnel pour éviter le sur-apprentissage et d'améliorer la généralisation, tout en capturant de manière appropriée les dépendances à long terme. Quelques propriétés intéressantes de pénalités structurés spécifiques peuvent être utilisés pour réduire le nombre de paramètres requis pour coder le modèle. Le résultat est un modèle efficace qui capte suffisamment les dépendances longues sans occasionner une forte augmentation des resources en espace ou en temps.

Dans un modèle log-linéaire, les phases d'apprentissage et de tests deviennent de plus en plus chères avec un nombre croissant de classes. Cela est dû au fait que le facteur de iii 0.2. MÉTHODES EXISTANTES ix 0.2.2 Entropie maximale et maximum de vraisemblance Considérons un modèle de langue d'ordre (m+1) qui nécessitent d'estimer la loi conditionnelle P ME (y|x m ). Chaque séquence s de longueur inférieure à (m +1) dans le corpus C définit un "feature" (descripteur) : S = {s | s 2C^|s|m +1}. Un paramètre ! s est associée à chacun des features s dans S donnant lieu à un modèle avec potentiallement un grand nombre d = |S| de paramètres.

Les méthodes de maximum d'entropie correspondent à modéliser P ME (y|x m ) comme le logarithme d'une fonction linéaire et de maximiser la vraisemblance (voir Rosenfeld, 1998;

Abstract

Modeling natural language is among fundamental challenges of artificial intelligence and the design of interactive machines. It has applications spanning across various domains, such as dialogue systems, text generation and machine translation among others and has been studied extensively in the past decades. Among problems that are common to most applications of language is to model the distribution over a vocabulary of words that could follow a given sequence of words or the context.

The simplest of models in the literature are based on frequency counts. Since the size of the vocabulary is large, many possible sentences are never observed leading to sparse sampling or data sparsity. This causes overestimation of observed sequences and underestimation of the unobserved ones. Thus it is necessary to use prior knowledge to appropriately modify the distribution. Frequency counts are commonly modified using smoothing techniques.L e a r n i n g -b a s e dm e t h o d sa r ea na l t e r n a t i v et of r e q u e n c y -b a s e dm e t h o d st h a tfi t an appropriate model to the data. Numerous learning techniques have been applied to build language models; generative models (Dirichlet, Pitman-Yor and hierarchical Pitman-Yor pro cesses), discriminative mo dels (maximum entropy, conditional random fields) and distributional representations (neural networks, Boltzman machines, log-bilinear models).

We prop ose a discriminatively trained log-linear mo del to learn the distribution of words following a given context. Due to data sparsity, it is necessary to appropriately regularize the model using a penalty term. However, simple choices for regularization (like `2 2 and `1 penalties) fail to capture long range dependencies. They overfit severely with increasing context length because they are agnostic to the sequential structure of the problem. We show that it is necessary to design a penalty term that properly encodes the structure of the feature space to avoid overfitting and improve generalization while appropriately capturing long range dependencies. Some nice properties of specific structured penalties can be used to reduce the number of parameters required to encode the model. The outcome is an efficient model that suitably captures long dependencies in language without a significant increase in time or space requirements.

In a log-linear model, both training and testing become increasingly expensive with growing number of classes. This is because the normalization factor involved in computing the probabilities grows linearly with the number of classes or categories in the problem. The number of classes in a language model is the size of the vocabulary which is typically very large. A common trick is to cluster classes and apply the model in two-steps; the first step picks the most probable cluster and the second picks the most probable word from the chosen cluster. This idea can be generalized to a hierarchy of larger depth with multiple levels of clustering. However, the performance of the resulting hierarchical classifier depends on the suitability of the clustering to the problem and building a 'good' hierarchy is non-trivial. We study different strategies to build the hierarchy of categories from their i observations. We observe that the choice of the algorithm to build a hierarchy should depend on the data and that in certain situations a hierarchical classifier could improve performance over a simple multi-class classifier. normalisation impliqué dans le calcul des probabilités croît linéairement avec le nombre de classes ou de catégories dans le problème. Le nombre de classes dans un modèle de langue est la taille du vocabulaire, qui est généralement très importante. Une astuce courante consiste à appliquer le modèle en deux étapes: la première étape identifie le cluster le plus probable et la seconde prend le mot le plus probable du cluster choisi. Cette idée peut être généralisée à une hiérarchie de plus grande profondeur avec plusieurs niveaux de regroupement. Cependant, la performance du système de classification hiérarchique qui en résulte dépend du domaine d'application et de la construction d'une bonne hiérarchie n'est pas triviale. Nous étudions différentes stratégies pour construire la hiérarchie des catégories de leurs observations. Nous observons que le choix de l'algorithme pour construire une hiérarchie devrait dépendre des données et que, dans certaines situations, un classificateur hiérarchique peut améliorer les performances par rapport à un classificateur multi-classe simple.

Détail des contributions

Les modèles de langue probabilistes sont utilisés fréquemment pour une grande variété de tâches de traitement du langage et constituent une composante cruciale dans de nombreuses applications, comme le traitement de la parole, les systèmes de dialogues et la traduction automatique (cf. [START_REF] Jurafsky | Speech and Language Processing[END_REF]; [START_REF] Manning | Foundations of Statistical Natural Language Processing[END_REF]. Ces modèles ont été développés depuis une vingtaine d'années et emploient des techniques comme les fréquences d'apparition de mots, des méthodes basées sur le maximum de vraisemblance, des méthodes Bayésiennes, des réseaux de neurones ou des modèles basés sur des représentations distribuées. Les méthodes les plus simples utilisent des estimations des fréquences d'apparition à partir d'un corpus de texte (Chen and Goodman, 1998); les estimateurs obtenus par optimisation ont été développés à partir des méthodes basées sur les fréquences d'apparition par apprentissage de paramètres d'un modèle statistique aussi àp a r t i rd ec o r p u s ( Chen and Rosenfeld, 2000). Malgré la litérature considérable sur ces nombreux modèles, leur intégration dans un cadre d'apprentissage permettant d'obtenir une information pertinente à partir de corpus de textes reste un défi.

Les méthodes basées sur l'optimisation sont plus génériques et permettent plus naturellement que les méthodes basées sur les fréquences de regrouper l'information venant de sources multiples (Lau, 1994;[START_REF] Della Pietra | Inducing features of random variables[END_REF]. Cependant, une utilisation naïve de ces modèles ne permet de généraliser au-delà des exemples d'apprentissage. Ceci est dû au problème classique de sur-apprentissage des modèles statistiques de grande dimension appris à partir d'un échantillon trop faible (Hastie et al., 2009). Une solution classique est alors de restreindre l'espace des modèles pour contrôler l'erreur de généralisation, une technique courante étant la régularisation, ou pénalisation (Vapnik, 1998). Cependant, les choix standards de pénalisation ne sont pas satisfaisants pour les probèmes dont les paramètres ont des contraintes topologiques naturelles (Bach et al., 2012). Les pénalités doivent alors ètres construites pour prendre en compte cette structure. Dans ce manuscrit, nous étudions de telles pénalités pour la modélisation du langage, mais nos techniques s'appliquent plus généralement à la modélisation de séquences. L'optimisation d'une fonction objectif dédiée à l'apprentissage d'un modèle permet d'apprendre les paramètres à partir des données d'entrainement. Le processus de test permet alors une évaluation sur d'autres données du modèle appris. A la fois entrainer et tester deviennent très coûteux en présence d'un nombre important de catégories. Le nombre de classes pour un modèle de langue est la taille du vocabulaire, qui peut être très grande, typiquement de l'ordre de 10 4 mots ou plus. Ceci rend l'utilisation de modèles statistiques particulièrement astreignante en pratique. Une technique simple pour surpasser le problème est de v regrouper certaines classes (ici des mots) en "clusters" et d'appliquer un modèle à deux niveaux. En généralisant cette idée, il est possible de construire une hiérarchie de clusters et d'appliquer le modèle séquentiellement le long de cette hiérarchie. Un avantage immédiat d'une telle organisation est un gain significatif en temps de calcul pour la phase de test. Cette technique de construction de taxonomie à base d'arbres est générique et a des applications au-delà des modèles de langue.

La première contribution de ce manuscrit est le développement d'un modèle de langue avec une pénalité structurée qui permet une meillleure performance de généralisation que les méthodes précédentes. Un cadre d'optimisation efficace est aussi introduit et donne lieu à des résultats plus compacts qu'avec les méthodes traditionnelles. La deuxième contribution est un cadre algorithmique pour organiser automatiquement un problème multi-classe en une structure d'arbre. Plusieurs méthodes de construction d'arbres sont introduites, à partir de principes "top-down" ou "bottom-up". Ces méthodes sont alors testées sur des jeux de données de langage et de vision artificielle.

En Section 0.1,l ep r o b l è m ed em o d é l i s a t i o nd ul a n g a g ee s td é c r i t ;l e sm é t h o d e st r a d itionnelles (méthodes de lissages et méthodes par maximum d'entropie) sont présentées en Section 0.2. Enfin, les motivations sous-jacentes au travail effectué sont présentées en Section 0.3.F i n a l e m e n t ,l e sc o n t r i b u t i o n sd ec e t t et h è s es o n td é c r i t e se nd é t a i le nS e c t i o n0.4.

Modélisation de la langue naturelle

La modélisation du langage correspond à estimer des lois de probabilité sur des séquences de mots tirés d'un vocabulaire fini V .S o i t s =( s 1 ,s 2 , ••• ,s |s| ) une séquence de mots s i 2 V avec |s| la longueur de la séquence. Nous utilisons la notation s =(xy) pour décrire une séquence composée d'un mot y 2 V suivant le contexte x 2 V |s|-1 .L es u ffi x ed ' u n e séquence x de longueur m est noté x m et est la sous-séquence composée des m derniers mots de x.N o t r eb u te s td ed é v e l o p p e ru na l g o r i t h m eA permettant d'apprendre une loi P(s) sur les séquences à partir d'un corpus (i.e., une collection de séquences de mots de V ).

Etant donné le grand nombre de séquences d'une taille donnée, un corpus C de taille raisonnable ne peut pas contenir toutes les séquences grammaticalement correctes (qui sont déjà beaucoup moins nombreuses que l'ensemble des séquences). Ceci rend l'estimation d'une loi P(s) très difficile. Dans cette thèse nous allons étudier le problème plus simple d'estimation de la loi conditionnelle P(y | x) d'un mot y suivant le contexte x.L ad i s t r i b ution jointe d'une séquence sera obtenue en prenant des produits de ces lois conditionnelles. En pratique la taille des contextes considérés est bornée par le modélisateur: Les modèles "m-gram" correspondent à des séquences de taille au plus m.D a n sl e sm o d è l e sd e langue que nous considérons ci-après, la longueur m des contextes est utile pour tabuler les occurences de séquences.

où c(s) est le nombre de fois où s est observé dans C,q u en o u sd é n o m m e r o n s" c o m p t e " . En prenant le produit des probabilités conditionnelles, on obtient une loi

P ML (s)= Y (xy)2{(s 1 ,••• ,s i )} |s| i=1
P(y|x m ).

Ceci permet de donner une probabilité à tout le corpus C:

P ML (C)= Y s2C P(s).
Il s'avère que le modèle défini en (1)maximiselaprobabilitéP ML (C) ci-dessus par rapport aux modèles de langage d'ordre m (c'est l'estimateur de maximum de vraisemblance).

Ce modèle simple ne donne cependant pas satisfaction: soit m est trop petit et le modèle est trop pauvre pour prendre en compte les dépendances longues; soit m est trop grand, et il n'y pas assez de données pour apprendre tous ces paramètres avec de plus un comportement particulièrement problématique: une séquence jamais observée dans le corpus aura toujours une probabilité égale à zéro pour le modèle. Plusieurs techniques ont été développées pour résoudre ces problèmes.

Méthodes existantes

Dans cette section, nous décrivons les méthodes classiques permettant d'apprendre efficacement des modèles avec des longueurs de contexte m plus ou moins élevées.

Méthodes par lissage

Les méthodes de lissage sont basées sur l'estimateur en (1), i.e., sur des estimations empiriques des fréquences d'apparition, mais changent les lois de prédiction, soit en redistribuant la masse de probabilité, soit en mélengeant les distributions venant de plusieurs ordres (voir [START_REF] Chen | Performance prediction for exponential language models[END_REF]Goodman, 1996, 1998,p

o u ru n ed e s c r i p t i o nc o m p l è t ed ec e sm é t hodes).

Redistribution de la masse de probabilité.

Le lissage additif consiste à rajouter de faux exemples pour tous les contextes (comme si ils avaient été observés dans C). Ceci correspond au lissage classique de Laplace pour les données discrètes (Lidstone, 1920;Jefreys, 1948):

P LP (y|x m )= c(x m y)+d c(x m )+|V |d , avec 0 <d 1. (2)
pour un certain d.T o u t e sl e ss é q u e n c en o no b s e r v é e so n ta l o r sl am ê m em a s s e .A l t e r n ativement, l'estimateur de Good-Turning redistribue la masse plus harmonieusement (Good, 1953).

Lissage par marche arrière.

Afin d'estimer P(y|x m ),u n em é t h o d es i m p l ep o u ré v i t e rl e sz é r o se s td er e c h e r c h e rd e s contextes plus petits avec au moins une observation dans C. C'est le lissage par marche arrière proposé par [START_REF] Katz | Estimation of probabilities from sparse data for the language model component of a speech recognizer[END_REF]. Dans le cas extrème, le plus petit contexte possible m est égale à zéro et le modèle utilise alors la probabilité "uni-gram", où aucun contexte n'est observé. Afin d'obtenir une loi de probabilité sommant à un, un poids bien choisi ⌘(x m ) doit être utilisé et on a la définition récursive suivante:

P KZ (y|x m )= ( P(y|x m )
utiliser le modèle d'ordre supérieur si c(x m y) >⌧ ⌘(x m )P KZ (y|x m-1 ) sinon,

où ⌧ est un certain seuil. Les poids ⌘(x m ) peuvent alors être calculés récursivement.

Lissage par interpolation.

Une extension du lissage par marche arrière consiste a combiner linéairement les distributions d'ordres faibles et élevés. Ceci a été proposé par Jelinek and Mercer (1980)a v e cu n e loi définie récursivement comme suit P JM (y|x m )=γ(x m )P(y|x m )+(1-γ(x m ))P JM (y|x m-1 ), pour des poids bien choisis γ(x m ). Ceux-ci peuvent être estimés à partir de données en reduisant le nombre de paramêtres à apprendre par regroupements [START_REF] Bahl | A maximum likelihood approach to continuous speech recognition[END_REF].

Lissage de Kneser-Ney.

Une alternative à l'interpolation linéaire est (a) de soustraire explicitement les comptes des ordres élevés des comptes d'ordres inférieurs et (b) de repondérer les distributions obtenues. La méthode introduite par Ney et al. (1994)al af o r m es u i v a n t e :

P AD (y|x m )= max{c(x m )δ, 0} c(x m-1 ) +(1-γ(x m ))P AD (y|x m-1 ).

Kneser and Ney (1995)o n té t e n d uc e t t et e c h n i q u ee nu t i l i s a n td e sc o m p t e sm od i fi é spo u r les petits ordres de telle sorte que le lissage est optimisé pour les situations où les comptes d'ordres élevés sont petits.

Discussion sur les méthodes de lissage.

Ces méthodes donnent de bonnes performances et sont encore préférées à d'autres modèles moins attractifs en termes de temps de calcul, avec une utilisation classique du lissage de Kneser-Ney (et ses variantes). Cependant, l'absence de paramètres statistiques explicites peut s'avérer limitante car elle ne permet pas d'étendre ces méthodes naturellement à des situations plus complexes, en particulier lorsque certaines tâches precises de traitement du langage naturel sont considérées. Les méthode par maximum d'entropie constituent alors une classe d'alternatives intéressantes.

Le problème du maximum de vraisemblance devient donc:

L(C; !)=- X {xmy}2C ln P ME (y|x m ), et ! ⇤ =a r g m i n !2R d L(C; !). (6)
L'optimisation pour le problème convexe en ( 6)p e u tê t r er é s o l uàl ' a i d ed em é t h o d e sd u premier ordre convergeant vers le minimum global.

Relations avec les méthodes de lissage.

Contrairement aux méthodes de lissage, les méthodes par maximum d'entropie font une modélisation explicite de la loi avec optimisation de paramètres. Ceci permet une certaine flexibilité et ces méthodes ont été appliquées à de nombreuses tâches en traitement du langage naturel. Cependant, elles sont deux problèmes classiques: le sur-apprentissage et l'inefficacité computationnelle.

Motivations

En résumé, de nombreuses méthodes ont été développées pour modéliser le langage. Elles ont toutes des avantages et des inconvénients et certaines sont plus adaptées que d'autres pour certaines tâches. Alors que la plupart des méthodes se focalisent sur la modélisation de la probabilité conditionnelle d'un mot étant donné les mots le précédant, certaines méthodes rendent la tâche de modélisation plus aisée. Une application typique des modèles de langue nécessite plusieurs couches de traitement de l'information. Dans de telles situations, de nombreux facteurs rentrent en jeu pour déterminer l'applicabilité d'un modèle particulier. Des considérations comme la facilité d'intégration, des aspects de temps de calculs ou de coût en mémoire (à accès rapide ou lent), ou la possibilité d'intégrer des informations supplémentaires, sont importantes en pratique.

Notre principale motivation pour poursuivre le travail sur ces modèles et en proposer des améliorations est de pouvoir appliquer ces modèles à des problèmes discriminatifs,q u i constituent une classe particulière des modèles présentés en Section 0.2.2,po u rl e s q u e l sl a probabilité d'un mot dépend non seulement des mots précédents mais aussi potentiellement de variables exogènes. Dans ce qui suit, nous utiliserons la génération de texte dans des applications multi-media comme exemple. Nous décrirons ensuite les aspects des modèles discriminatifs que nous étudierions et enfin résumerons les contributions de la thèse.

Dans le contexte global de la compatibilité des modèles pour les applications, nous voyons les modèles discriminatifs comme les modèles permettant la flexibilité nécessaire à des scénarios applicatifs classiques où il est important de faire de la prédiction à partir de plusieurs sources d'informations, typiquement en combinant linéairement les descripteurs.

Par exemple, dans les applications multi-modales, le langage naturel peut être une des modalités (typiquement la modalité cible). Les autres modalités peuvent être un signal audio, une image ou une séquence vidéo (typiquement des modalités sources). La génération automatique de résumés décrivant une image est une application simple à fort impact.

En effet, le problème de la génération automatique de légendes textuelles destinées aux humains est un problème en pleine croissance (voir, par exemple, Gupta et al., 2009;Farhadi et al., 2010;Kulkarni et al., 2011;Yang et al., 2011;Mitchell et al., 2012). Les premiers modèles proposés utilisaient des constructions basées sur des modèles-types de phrases dont le choix était appris à partir de certaines informations dans l'image (obtenues par des techniques de vision artificielle) (Kulkarni et al., 2011). Ces méthodes basées sur des modèles-types sont connues pour être sous-optimales quand des variations textuelles sont nécessaires (Reiter and Dale, 1997). Ces techniques ont depuis été améliorées avec des méthodes qui génèrent directement des arbres syntaxiques permetant ensuite de produire un texte grammaticalement correct (Mitchell et al., 2012;Yang et al., 2011).

Cependant, ces méthodes traitent les deux modalités séparément avec un échange d'information uni-directionnel qui (a) résume une image en quelques mots, souvent des annotations de l'image avec quelques étiquettes et une certaine organisation spatiale (Mitchell et al., 2012;Yang et al., 2011;Farhadi et al., 2010;Ordonez et al., 2011), puis (b) envoie ces informations au modèle de langage pour créer une phrase. Le rôle du modèle de langage est alors de regrouper ces informations trop simples et de former une phrase cohérente en rajoutant typiquement beaucoup de mots autour des mots obtenus de l'image. Les phrases obtenues peuvent alors être cohérentes et grammaticalement correctes, mais ne correspondent plus à ce qu'il se passe réellement dans l'image ou la video (Mitchell et al., 2012).

Produire des phrases grammaticalement correctes et qui expriment correctement les signaux sources nécessite un modèle permettant d'utiliser à bon escient les grands corpus de textes (Li et al., 2011). Par ailleurs, ces modèles doivent pouvoir traiter les signaux sources en prédisant directement les distributions de mots sans passer par des étapes sursimplificatrices causant des pertes d'information. Dans de telles tâches, nous considérons les modèles discriminatifs comme naturellement adaptés: en effet, on peut utiliser un modèle de langue obtenus de sources variées que nous pouvons utiliser pour apprendre un modèle conditionnel pour nos données multi-modales. De plus, ces modèles discriminatifs peuvent gérer naturellement des aspects importants du langage, comme les variations de style ou de ton, en changeant certains termes dans les fonctions objectifs à optimiser.

Codage de contextes longs pour la modélisation discriminative.

La génération de phrases complètes dans un cadre discriminatif requiert le traitement adéquat des contextes longs, avec dans certains cas très longs si plusieurs phrases sont impliquées. Ceci pourrait être nécessaire pour plusieurs raisons. Par exemple, il pourrait s'avérer intéressant de supprimer certaines informations des phrases précédentes afin d'éviter des répétitions, ou de réduire la ré-utilisation de mêmes mots dans les mêmes phrases afin de maintenir une bonne lisibilité, ou de contrôler l'ordre dans lequel le contenu est délivré, etc. Dans de telles situations, un modèle discriminatif doit pouvoir coder de grandes phrases efficacement. C'est un des aspects que nous considérons dans notre travail.

Modèles log-linéaires avec grand nombre de classes.

Ce problème est d'importance plus générale que les modèles de langue, mais il est particulièrement important pour le langage naturel car le nombre de classes est égal au nombre de mots dans le vocabulaire (typiquement supérieur à 10 4 ). Le verrou computationnel est alors le calcul de la constante de normalisation pour lequel le nombre de produits scalaires à calculer croît linéairement avec le nombre de classes. Ceci ralentit l'apprentissage car à chaque étape d'une méthode de descente de gradient, il faut calculer cette constante.

Afin d'obtenir une complexité logarithmique dans le nombre de classes, il est classique d'organiser les classes dans un arbre pour accélérer à la fois l'entrainement et le test. La difficulté est de construire une telle hiérarchie sans détériorer la performance de prédiction. Dans notre travail, nous proposons différentes méthodes pour construire de telles hiérarchies et testons leur performance pratique.

Contributions et plan de la thèse

Cette thèse revisite les approches traditionnelles décrites ci-dessus à la lumière d'avancées récentes sur les pénalités structurées et l'optimisation convexe à grande échelle. En particulier, nous nous focalisons sur deux problèmes liées aux modèles de langage discriminatifs: (a) le sur-apprentissage et l'explosion du temps de calcul face à des contextes longs et (b) la nécessité de modèles de sortie hiérarchiques (il est intéressant de noter que les deux contributions utilisent des arbres mais que ces arbres n'y ont pas la même signification). Nos contributions peuvent être résumées comme suit.

Pénalités structurées pour la modélisation du langage

Les modèles de langage discriminatifs sont connus pour sur-apprendre en présence de contextes longs. En effet, le nombre de paramètres grandit rapidement avec la longueur du contexte. Les techniques classiques de régularisation (par pénalité `2, `1 ou leur combinaison) ne sont alors pas effectives, comme le montrent les performances prédictives obtenues lors de nos simulations sur un sous-ensemble du corpus "AP-news" (voir Chapitre 3).

Nous étudions ce problème de régularisation inadéquate en reformulant le modèle comme une distribution catégorielle avec une vraisemblance tres proche du modèle de maximum d'entropie en (5)maisavecunecontrainteenplus. Unpoint-cléestquelastructureséquentielle des phrases peut alors être interprétée comme une structure de données en arbre de suffixes.N o u sp o u v o n sa l o r sn a t u r e l l e m e n tu t i l i s e ru n ep é n a l i t éc o n v e x ea d a p t é eàc e t t e structure d'arbre. Cette pénalité permet d'introduire un a priori nouveau: un contexte long ne peut être choisi que si tous les contextes plus petits sont impliqués dans le prédicteur. Cette pénalité est non seulement adaptée statistiquement (meilleure performance de prédiction pour les longs contextes) mais aussi peut être utilisé à un moindre coût supplémentaire en utilisant finement la structure d'arbre de suffixes.

Les différents modèles à pénalité structurée que nous considérons sont implémentés et comparés aux modèles non-structurés. Cette évaluation montre des améliorations significatives en performance de prédiction quand le contexte augmente. Nous proposons aussi une analyse fine des résultats obtenus en groupant les mots suivant différents critères permettant de mieux comprendre les gains de performance. Cette analyse suggère des améloriations pour des travaux futurs.

Du côté des performances numériques, augmenter les longueurs de contexte augmente de manière très significative le nombre de descripteurs (car la taille du vocabulaire est grande). Sans utiliser la structure d'arbre de suffixes, la complexité serait trop importante. Dans le Chapitre 3, nous étudions la complexité numérique des différentes pénalités considérées et montrons comment certaines d'entre elles peuvent être utiliseées avec des contextes de très grande taille (en utilisant les arbres de suffixes, comme fait pour le lissage de Kneser-Ney). En particulier, nous proposons un nouvel algorithme qui améliore le temps de calcul. Ce travail a été publié au congrès Conference on Empirical Methods in Natural Language Processing (EMNLP), 2013.

Apprentissage de la taxonomie

L'idée de grouper des mots en "clusters" afin de rendre l'entrainement et le test plus efficaces en termes de temps de calcul a déjà été explorée dans différents modèles (voir (Goodman, 2001)po u rl e sm od è l e sàm a x i m u md ' e n t r o p i e , ( Morin and Bengio, 2005)po u rl e sr é s e a u x de neurones "feed-forward", (Mikolov et al., 2011)p o u rd e sr é s e a u xr é c u r r e n t se t ( Mnih and Hinton, 2008)po u rl e sm od è l e sl o g -b i l i n é a i r e s ) .

Cependant, la méthode de construction des clusters de mots dans les modèles ci-dessus est soit aléatoire soit ad-hoc, à l'exception de la technique de partitionement de Brown. Nous proposons plusieurs méthodes permettant de grouper les mots en utilisant leurs contextes. Ces méthodes sont génériques avec des applications à tous les problèmes avec beaucoup de classes, que les données soient séquentielles ou non (comme des problèmes àd e s c r i p t e u r sc o n t i n u s ,c o m m u n é m e n tu t i l i s é sp o u rl ar e c o n n a i s a n c ed ' o b j e t sd a n sl e s images).

Nous proposons deux approches. Dans l'approche "bottom-up", les classes sont regroupées petit à petit en utilisant un algorithme Hongrois avec un critère de corrélation entre classes. Dans l'approche "top-down", les classes sont divisées récursivement. Afin de diviser un groupe de classes en deux morceaux ou plus, nous utilisons des résultats récents de "clustering" discriminatif, où le but est de séparer les classes en deux morceaux, de telle sorte que si un séparateur linéaire est appris sur ces classes, alors la séparation est maximale. Cette approche donne lieu à une formulation en programmation semi-définie qui peut se résoudre efficacement.

Nous étudions le comportement de ces méthodes sur des jeux de données de textes et d'image et détaillons comment ces méthodes de constructions d'arbres doivent être choisies avec soin afin de ne pas perdre de performance prédictive par rapport à la structure plate. Il est intéressant de noter que dans certains cas, au-delà d'obtenir une meilleure complexité numérique, la performance de prédiction est aussi améliorée.

Plan de la thèse.

Le manuscrit est organisé comme suit. Le Chapitre 2 décrit le cadre de minimisation du risque empirique et la nécessité de régulariser avec un accent particulier sur les pénalités permettant d'incorporer la structure. Aussi, les différents algorithmes d'optimisation convexe adaptés à ces pénalités sont présentés. Le Chapitre 3 détaille les contributions nouvelles sur les pénalités structurées et leur utilisation efficace pour les modèles de langue. Le Chapitre 4 décrit les différentes nouvelles méthodes de regroupement des classes pour obtenir un arbre de classes. Nous résumons les contributions de la thèse et concluons en Chapitre 5,o ùs o n ta u s s ip r é s e n t é e sd e sp i s t e spo u rd e st r a v a u xf u t u r s .

Contents

BS y n t h e t i cD a t aG e n e r a t i o n 91

CE ff e c to fp a r a m e t e r s 93

List of figures

Introduction

Probabilistic language models are used extensively in a variety of language processing tasks and remain at the core of various applications like speech processing, dialogue systems, and machine translation (see [START_REF] Jurafsky | Speech and Language Processing[END_REF][START_REF] Manning | Foundations of Statistical Natural Language Processing[END_REF]. These models emerged over the last couple of decades and employ techniques like modified frequency counts, likelihood methods, Bayesian methods, neural networks and models involving distributed representations. The simplest method uses frequency estimates from at e x tc o r p u s( Chen and Goodman, 1998). Optimization-based estimators were developed following frequency-based methods that train models by learning their parameters on a corpus (Chen and Rosenfeld, 2000). Despite the considerable literature available with numerous models, the ease to integrate these models into a learning framework to derive high-level information from text corpora remains challenging.

Optimization-based methods are more generic and amenable to absorb information from multiple sources (Lau, 1994;[START_REF] Della Pietra | Inducing features of random variables[END_REF] than frequency-based methods. However, a naively designed model fit to a dataset does not generalize to unseen examples. This is due to a problem common to statistical models involving high dimensional spaces with sparse sampling (Hastie et al., 2009). The solution is to restrict the set of models so that the generalization error is controlled. This is called regularization or penalization (Vapnik, 1998). However, standard choices of penalization are not sufficient for problems with parameters involving specific patterns (Bach et al., 2012). Penalization needs to be designed in a such a manner that it is aware of the structure within the problem. We study such structure-aware penalization for modeling language or discrete structures in general to improve generalization performance.

The optimization of an objective designed to learn the parameters of a model from some observed data is called training. The process of testing involves evaluation of the trained model on data (not overlapping with the training set) to measure generalization performance. Both training and testing become increasingly expensive with a growing number of categories or classes involved in the problem. The number of classes for language models is the size of the vocabulary which is very large, typically of the order 10 4 or above. This makes the use of statistical models computationally demanding for practical use. A simple technique to overcome this problem is to group together classes (or words) into clusters and then apply the same model at two levels. Generalizing this idea, one can build a hierarchy of such clusters and apply the model successively along the hierarchy. An immediate advantage of such hierarchical organization of classes is the significant gain in speed when the resulting model is applied to test data. This technique to build taxonomic trees from samples is generic and has applications beyond language modeling. The first contribution of this work is a language model with a suitable structured penalty that offers better generalization performance than earlier methods. We also present a framework that is quicker to optimize and results in a more compact model than traditional approaches. Our second contribution is a framework to organize classes in a large-scale multi-class problem into a tree structure. We study different tree-building methods in this framework including both top-down and bottom-up procedures to grow such trees. We test these methods on datasets of images and language. In Section 1.1,w ei n t r o d u c et h e problem of language modeling. We present traditional approaches to modeling language, namely smoothing techniques and maximum entropy models in Section 1.2.I nS e c t i o n1.3 we present more recent approaches to this problem based on Bayesian framework and neural networks. We motivate the purpose of our work and describe our contributions in Section 1.5.

Problem of modeling language

Language modeling involves estimating probability distributions of sequences of words. Consider a vocabulary V from which words are drawn to make discrete sequences. Let s =( s 1 ,s 2 , ••• ,s |s| ) be a sequence with words s i 2 V and |s| being the length or the number of words in the sequence. We use s =(xy) to denote a split of the sequence where y 2 V is the word following the context x 2 V |s|-1 . The suffix of a sequence x of length m is denoted by x m which is the subsequence with the last m words of x. We wish to design an algorithm A that will learn the probability distribution P(s) over the sequences from ac o r p u s . Ac o r p u si sac o l l e c t i o no fs e q u e n c e so fw o r d sf r o mV . The input to A is a text corpus C that is used to learn the parameters of the model. Apart from the training set C, we will additionally need a validation set, also called held-out data, distinct from C to tune any necessary parameters. We distinguish the training set C from the test set C t that is used to compare performance of different models.

The corpus C is a sampling from the space of sequences, however, space of C is significantly smaller than the complete space of sequences. This is particularly true for language where numerous possibilities are either meaningless or grammatically incorrect and have zero probability. Further, the space of meaningful and grammatically correct sequences is so varied that this space cannot be sampled sufficiently. This makes the estimation of joint distribution of words in a sequence P(s) very hard. Hence, the focus is usually the much simpler problem of estimating the following conditional distribution P(y | x) of a word y following the context x. The joint distribution of a sequence is inferred by taking the product of the conditionals which is equivalent to predicting one word of the sentence at a time in that order. This makes sense for language modeling since the Markovian assumption applies naturally to data of discrete sequences. In practice, one prescribes the maximal length of dependence in the sequences that restricts the distance along the sequence that a word can influence. This is also called the order of the language model. Using sequences of length at most m leads to an m-gram language model which is also called the (m -1) order language model. A context of length (m -1) is used to predict the following word in such models. In the language models that we will consider in the next section, the order is useful to tabulate occurrences of sequences.

Consider the (m +1)-gram model with sequences |s| = m +1.As i m p l em o d e lt h a t counts the number of occurrences to assign a probability from frequency estimates is,

P ML (y|x m )= c(x m y) c(x m ) , (1.1
P ML (s)= Y (xy)2{(s 1 ,••• ,s i )} |s| i=1 P(y|x m ).
The product of the probabilities of predicting all the sequences in a corpus C gives the probability of generating C or the likelihood of C,

P ML (C)= Y s2C P(s).
The probability estimate from the distribution defined in (1.1)m a x i m i z e st h ep r o b a b i l i t y P ML (C) of generating the corpus C for a given language order m and hence has the name maximum likelihood estimate.

However, the goal is not to maximize the likelihood of generating a given training corpus C but to minimize the errors in predictions on test set C t . They are not equivalent since the test set typically has data not seen during training and the maximum likelihood estimator in (1.1)t y p i c a l l ya s s i g n st h e ms m a l lo rz e r op r o b a b i l i t i e sb e c a u s et h ee s t i m a t o rfi t st h e training set too well. This situation is called overfitting and the resulting error also referred to as generalization error. Overfitting is common in problems where the enough data cannot be collected to learn parameters by simply maximizing the likelihood like in equation (1.1). This is referred to as data sparsity and there is significant amount of work in statistics and machine learning communities to handle this issue for various models.

The distribution from the estimator in (1.1) varies with the value of m. Models with smaller m have fewer parameters to estimate from more data in comparison to those with larger m that will have more parameters. A more confident estimate can be made when a parameter sees more data, a property characterized by smaller variance (often referred to as estimation error), which is the case when m is small. However, a small m assumes short dependence along the sequence discarding information available from the data leading to high bias (also called approximation error) in the estimate.

The assumption of short dependence does not hold since randomly drawing words independent of their context will return meaningfuless sequences. On the contrary, a large m uses more information available from the training data resulting in smaller bias but since there are fewer observations with longer context lengths the variance of the estimate shoots up. Bias and variance are two competitive properties of an estimator both of which are directly proportional to the generalization error. Estimates from larger m will have higher variance and lower bias and vice versa. It is important to balance bias and variance so that the resulting generalization error is small. Generalization error can be improved for a fixed amount of data without costing us variance. This is achieved by an appropriately chosen modification of the estimator referred to as regularization or smoothing. The trick is to design models that trade some bias to significantly reduce the variance and eventually improve generalization. The trade-off between bias and variance is central to statistical models and will be dealt with in detail in Chapter 2 as approximation and estimation errors. In the following section, we will study such modifications to the estimator in (1.1)c a l l e ds m o o t h i n gm o d e l st h a ti m p r o v e generalization. We will also study parametric models called maximum entropy models that optimize the likelihood to learn the distributions P(y|x m ) from the data. These are approaches that have been traditionally investigated in the language processing literature. In Section 1.3 we will study some recently introduced models for the same problem.

Traditional approaches

We will see in this section that the statistical estimation process in language modeling suffers from the high dimensionality of the problem, often called the curse of dimensionality. It leads to the problem of data sparsity where the datasets are a sparse sampling of the space of sequences. This motivated the design of models that improve performance over the simple estimator in (1.1)f o rt h es a m ea m o u n to fd a t a . T r a d i t i o n a l l y ,t h i sh a sb e e n achieved through smoothing techniques that modify the distribution estimated by (1.1) and regularization in parametric maximum entropy models. We discuss data sparsity and these models in this section.

Data sparsity. In the ideal case of infinitely large number of samples or sufficiently large dataset, the estimator in (1.1) is sufficient to make an estimate with low variance and very good generalization. However, it not possible to acquire a sufficiently large dataset for high dimensional problems. This is because the space of all possible sequences is too large to be sampled sufficiently. Specifically in the case of language, the space of all possible sequences of length m with a vocaulary of size |V | is |V | m . Consider a modestly sized vocabulary of the order 10 4 with a relatively short dependence at m =3and we already have an unmanagably large space of 10 12 possible sequences. This is the problem of data sparsity where the feature space is too large to be finitely summarized in a statistically representative dataset. A theoretically sound way to handle data sparsity is to exploit the bias-variance trade-off discussed in the previous section. The idea is to design biased estimators that significantly reduce variance and hence improve generalization. We briefly discuss smoothing methods from the literature that achieve this for m-gram models by applying different variations of the estimator in (1.1)a bo v e .

Smoothing models

Consider estimating the probability of a sequence x m y that was never seen in training corpus C.W ea s s u m et h e r ea r en ow o r d so u to ft h ev o c a b u l a r yV . The estimator in (1.1) simply sets its probability to zero which is inappropriate since the training data has not seen all possible sequences. It often overestimates the probability for sequences observed in C and underestimates it for unseen sequences. This overfitting to training data degrades predictive performance of the model. Smoothing models adjust for this overfitting by modifying the predictive distributions. They achieve this in two different ways; redistribution of probability mass and mixing distributions of multiple orders. Methods that redistribute mass explicitly modify the counts by some chosen heuristic. Models that mix multiple orders rely on lower orders when higher orders are unobserved. We briefly mention some of these methods here that are detailed in the Appendix A.1 (see [START_REF] Chen | Performance prediction for exponential language models[END_REF]Goodman, 1996, 1998,f o rac o m p l e t es u r v e yc o m p a r i n gv a r i o u ss m oo t h i n gm od e l s ) .

Redistribute probability mass. Additive smoothing is the technique of adding some fake samples to original frequencies as if they were observed in C. This is the classical Laplace smoothing for categorical data which is a kind of shrinkage estimator (Lidstone, 1920;Jefreys, 1948) and has the following form:

P LP (y|x m )= c(x m y)+d c(x m )+|V |d , with 0 <d 1. (1.2)
where d is chosen arbitrarily. For d>0,a l lu n o b s e r v e ds e q u e n c e sa r ea s s i g n e ds o m em a s s but Gale and Church (1994)a r g u e dt h a tt h i si sp o o rc h o i c ef o rs m o o t h i n g . A l t e r n a t i v e l y , the Good-Turning estimator redistributes the probability mass of sequences that occurred exactly (k +1) times in C among the sequences with frequency k,

P GT ( y|x m ,c (x m y)=k ) / (k +1) C k+1 E[C k ] , (1.3)
where C k is the number of sequences with frequency k and E[ • ] denotes expectation. It redistributes the mass of unit frequency sequences to sequences that we might encounter at test but were never seen in C. This, however, requires us to make an estimate of the number of unseen sequences that we might encounter at testing phase. Good (1953[START_REF] Good | Turing's anticipation of empirical bayes in connection with the cryptanalysis of the naval enigma[END_REF] explains the details of this estimator.

Back-off smoothing. In estimating P(y|x m ),t h es i m p l e s tw a yt oa v o i dz e r oc o u n t si st o lower the order m and look for a smaller context in C. This is the back-off model proposed by [START_REF] Katz | Estimation of probabilities from sparse data for the language model component of a speech recognizer[END_REF]a n dt h eo r d e ri sl o w e r e du n t i lx m y is found in C.I nt h ee x t r e m ec a s e , m goes to zero and it uses the unigram probability of predicting y when no context is observed. This has to be done such that the resulting values sum to one over all y 2 V for any given context. This requires weighting the lower orders by ⌘(x m ). The resulting distribution takes the following recursive form,

P KZ (y|x m )= ( P(y|x m ) use highest order model if c(x m y) >⌧ ⌘(x m )P KZ (y|x m-1 ) otherwise, (1.4)
where ⌧ is a threshold chosen to avoid assigning mass to sequences that occur too few times. The value for ⌧ could be chosen by cross-validating performance on held-out data but it is not very critical and is often set to zero (Chen and Goodman, 1996)

P AD (y|x m )= max{c(x m ) -δ, 0} c(x m-1 ) +(1-γ(x m ))P AD (y|x m-1 ),
where δ is the discount parameter tuned on validation dataset. The weighting function for the lower orders takes the form

1 -γ(x m )= δC 1+ (x m •) c(x m ) ,
so that the mass of the resulting distribution adds to one. Performances of absolute discounting were comparable to that of linear interpolation with fewer parameters to tune (single parameter of δ) and it also agrees with intuition of [START_REF] Witten | The zero-frequency problem: Estimating the probabilities of novel events in adaptive text compression[END_REF]f o r weighting interpolated models. Kneser and Ney (1995)e x t e n d e da b s o l u t ed i s c o u n t i n gb y using modified counts for the lower order distribution so that it is optimized for situations where the higher order counts are small. This modification follows the idea that the lower order probability should be proportional to the number of unique words preceding the sequence. The resulting Kneser-Ney smoothing formulae are,

P KN (y|x m )= 8 > > > > > > > > < > > > > > > > > : abs. disc. z }| { max{c(x m y) -δ, 0} c(x m-1 ) + back-off term z }| { δC 1+ (x m •) c(x m ) P KN (y|x m-1 ) largest m s.t. c(x m y) > 0, max{C 1+ (•x m-1 y) -δ, 0} C 1+ (•x m-1 •) | {z }
modified lower order dist.

+ δC 1+ (x m-1 •) C 1+ (•x m-1 •) P KN (y|x m-1 ) | {z } interpolation term otherwise,
where On the positive side, smoothing models are very well engineered and thoroughly studied models that are used in numerous applications but they lack certain desirable properties. Chen and Goodman (1996)s t u d yv a r i o u ss m o o t h i n gm o d e l sa n do b s e r v et h a tt h efl e xibility offered by models with more parameters is one important aspect that improves performance. These models with parameters that are tuned on held-out data are observed to perform better than other ones. While this is the case with some conventional m-gram models, the flexibility they offer is very limited. The necessity of parametric models that can learn from data goes beyond improvements in predictive performance. They open possibilities to custom design models for specific tasks and fine tune them using data. We further discuss this in Section 1.5. This requirement motivates the modeling of language using parametric models. In the next section we describe such parametric modeling of language using the maximum entropy principle.

C 1+ (•x m y)=|{z | c(zx m y) ≥ 1}| counts the number of unique words preceding x m y and C 1+ (•x m-1 •)=|{(z 1 ,z 2 ) | c(z 1 x m-1 z 2 ) ≥ 1}|

Maximum entropy models

The task is to estimate a distribution explaining the given data using a parametric model. 'Explaining data' is used to imply that the distribution must be similar to the empirical distribution observed from the data but not equivalent to avoid overfitting. More precisely, the expectation of random variables under the distribution should equal their empirical observations from the data. There could be multiple such distributions with expectations matching empirical observations for any given dataset. The principle of maximum entropy states that from among various candidate distributions for a dataset, the one with highest entropy must be chosen. Entropy is the measure of uncertainty in a random process and a uniform distribution has the highest entropy. A distribution chosen by this criterion is closest to uniform distribution that satisfies the above said constraint for that dataset. Maximum entropy methods have been studied extensively in the statistical language processing literature (see Rosenfeld, 1998;Lau, 1994;[START_REF] Lau | Adaptive language modeling using the maximum entropy principle[END_REF]Rosenfeld, 1996;Ratnaparkhi, 1998;[START_REF] Berger | A maximum entropy approach to natural language processing[END_REF]. Maximum entropy models bear relation to Gibbs and Boltzmann distributions in statistical physics, log-linear models and Markov random fields in probability theory and Boltzmann machines in neural networks. They offer interesting properties as described by Della Pietra and Della Pietra (1993).

Let {δ i (s)} d i=1 be a set of binary random variables or features defined over sequences s. We use contextual features where δ i (s) indicates the occurrance of a certain suffix in the sequence s that we describe shortly. Alternatively, one could use a different feature set and build other models. For example, Lau (1994)u s e st h eo c c u r a n c eo fc e r t a i nw o r d sc a l l e d triggers in s to build a trigger-based language model. In a more generic setting, δ i could take any non-negative value that quantifies a certain property like, for example, a quantity proportional to the length of s.I fP ME is the maximum entropy distribution then the expectation of δ i (s) must satisfy,

X s2C P ME (s)δ i (s)= X s2C P ML (s)δ i (s), (1.5)
where P ML is the empirical distribution from equation (1.1). The maximum entropy distribution is one that satisfies all such constraints laid down by C and has the maximum entropy among them. Essentially, these methods choose a distribution that makes no assumptions beyond that of the data, in our case C,a n dt h ec h o i c eo fr e p r e s e n t a t i o n . W e now describe a model based on this maximum entropy principle.

Consider a model with one parameter ! i associated to each feature δ i .D e fi n ea ne v e n t T associated with a subset of the random variables S T ⇢{ δ i } d i=1 . The maximum entropy model assigns a probability to T that is proportional to the product of the exponentials of all parameters ! i corresponding to relevant features S T or,

P ME (T ) / Y i2S T e ! i .
(1.6)

The parameters of the model are estimated by maximizing the probability of observing the training data. We now look at the specific set of features and the estimation method for modeling language.

Maximum entropy language model. Consider a language model of order m that requires estimating P ME (y|x m ).L e te a c hs e q u e n c es of length at most (m+1) in the training corpus C be a feature, S = {s | s 2C^|s|m +1}.

Associate a parameter ! i to each feature in S resulting in a model with d = |S| number of parameters. The feature set gets richer upon increasing the amount of data but so do the number of parameters that need to be estimated. Given a sequence (x m y),ourfeatures{δ i (x m y)} are occurrences of S as suffixes of (x m y). This can be described by an indicator function I(x m y, i) that assigns one to δ i (x m y) if S i and x m y have a common non-null suffix, i.e., if x k y = S i for some 0  k  m. The indicator function I(x m y, i) takes the following form:

δ i (x m y)=I(x m y, i)= ⇢ 1 if x k y = S i for some 0  k  m, 0 otherwise.
Now, we need to write the probability P ME (y|x m ) as defined in equation (1.6). This requires us to sum all parameters of features relevant to the event of y following the context x m . The conditional probability is the exponential of this sum,

P ME (y|x m ; !) / e P d i=1 ! i I(xmy,i) .
Actual probabilities are computed by taking ratios with the normalization factor,a l s o called the partition function,t h a tc o m e sf r o mm a r g i n a l i z a t i o no fy over all V ,

Z(x m ; !)= X v2V e P d i=1 ! i I(xmv,i) . (1.7)
The corresponding probability of generating a corpus which is also the likelihood of the corpus L(C; !) would be,

L(C; !)=P ME (C; !)= Y {xmy}2C P ME (y|x m ; !)= Y {xmy}2C e P d i=1 ! i I(xmy,i) Z(x m ; !) . (1.8)
The optimal set of parameters is recovered by maximizing L(C; !) which is usually done by first taking the logarithm. The negative of the log of the likelihood takes the following form:

L(C; !)=- X {xmy}2C ln P ME (y|x m ; !), and
! ⇤ =a r g m i n !2R d L(C; !), (1.9)
where ! ⇤ is the set of optimal parameters in R d .W eb r i e fl yr e v i e wb e l o wt h em e t h o d st o solve the optimization in (1.9).

Iterative scaling methods. The optimization described in (1.9) is convex with a unique minimum and any suitable optimization method could be applied depending on the size of the problem. The earliest technique used is the iterative scaling introduced by Darroch and Ratcliff (1972). This method involves minimizing the difference in the likelihood at two different parameter estimates separated by ∆!, err = L(! +∆!) -L(!).

(1.10)

⌘ CD P C I(x m y, i)= P C E P(v|xm) [e ∆! i I(xmv,i) ∆! i I(xmv,i)] E P(v|xm) [e ∆! i I(xmv,i) ]
A3 for i = 1 to d A4 ∆! i = U (!, C,i) #8i as in Table 1.1 A5 ! ! +∆! B. Sequential update (SCIS and coordinate descent) B1 Input: C,! := 0 B2 repeat until termination B3 for i = 1 to d B4 ∆! i = U (!, C,i) #8C as in Table 1.1 B5 ! i ! i +∆! i
Typically, the error is not easy to minimize and is replaced by a surrogate function that bounds the error from above and is easier to minimize (see Lange et al., 2000,o nu s i n g surrogates for optomization). The derivative of the surrogate is then set to zero to derive the update equation. The update is applied iteratively until some termination condition is met. There are different variations of this approach depending how the surrogate is derived from the error function.

The original method proposed by Darroch and Ratcliff (1972)i sc a l l e dg e n e r a l i z e d iterative scaling (GIS). Della Pietra and Della Pietra (1993) proposed a different surrogate, they refer to as the improved iterative scaling (IIS). Both, GIS and IIS, lead to update equations that can be applied in parallel, meaning all parameters can be updated at each iteration of the optimization. Goodman (2002)d e r i v e da n o t h e rv a r i a t i o no ft h es u r r o g a t e that results in an algorithm called the sequential conditional generalized iterative scaling (SCIS). This algorithm updates only one parameter at each iteration and cycles over the list of the parameters it updates. Using the following definitions for I # , I # (x m v) and I M (i) as,

I # (x m v)= X i I(x m v, i), I # =max C I # (x m v) and I M (i)=max C I(x m v, i),
the resulting update equations are tabulated in Table 1.1. The derivations leading to the corresponding surrogates for these methods are described in Appendix A.2. Huang et al. (2010) propose using coordinate descent (CD) as an alternative which directly minimizes the error in (1.10). CD also leads to sequential updates like SCIS. They also show that all these methods (iterative scaling and coordinate descent) converge to the optimum at a linear rate.

These procedures for optimization with both parallel and sequential updates are summarized in Algorithm 1. The parallel algorithm estimates the update for each parameter in the vector ! and applies them together in step (A5) updating all entries at every iteration. On the contrary, the update step (B5) for sequential algorithms is inside the for-loop with only one parameter ! i updated at each iteration and the update value for the next parameter ! i+1 is estimated with the new estimate of !.

Generic optimization methods. Generic function optimization techniques available in the literature (see Nocedal and Wright, 2006)w e r el a t e rf o u n dt ob em o r es u i t a b l et h a n iterative scaling to minimize the negative loglikelihood in (1.9). First order techniques use gradients in the parameter space to minimize the objective. The steepest descent method descends along the negative of the gradient with an appropriately chosen step size. In contrast, conjugate gradient method finds directions that are orthogonal to previous steps. Second order methods use the dense Hessian matrix to estimate an appropriately sized descent step. They offer faster convergence at the expense of computational time and memory. The number of entries in the Hessian grows quadratically with the size of the feature set. Further, its inversion is required that is cubic in the number of features.

In quasi-Newton methods, the inverse of the Hessian is approximated efficiently to overcome the computational burden of the Hessian. A rank-one approximation of the inverse of the Hessian is computed by using the last few gradients, a method that is popular as the limited-memory Broyden-Fletcher-Goldfarb-Shanno (L-BFGS) algorithm. Malouf (2002)andMinka (2003)comparedv ariousnumericaloptimizersanddemonstrated faster convergence of conjugate gradient methods and quasi-Newton methods over iterative scaling methods. However, when the dataset has large number of samples estimating a single gradient itself can be very time consuming. But it is unnecessary to use all available samples to make a reliable estimate of the gradient. In such cases, the gradient at each step is estimated stochastically from a small random subset of the dataset (or just one sample at a time) making it significantly faster. Stochastic methods were found to be more suitable for such optimization involving large data (see, for e.g., Finkel et al., 2008).

Relation to smoothing models. Unlike the smoothing models above, maximum entropy models learn the distributions from the data by fitting an exponential model to it. Chen and Goodman (1996)a r g u et h a tt h i sp a r a m e t e r i z a t i o ng i v e st h e ms i g n i fi c a n ta d v a n t a g e over conventional m-gram models. Despite the difference, models resulting from maximum entropy estimation were shown by Chen and Rosenfeld (2000) to bear resemblance with interpolated and back-off smoothing models described above. Maximum entropy models also suffer from data sparsity and require smoothing of its estimates. Earliest works to smooth the estimates would modify the constraint set (1.5) which are later superseded by regularization of the parameters. We describe this in detail in the next section.

Predictive performance and computational efficiency

Maximum entropy models are simple and intuitive with flexibility to capture information of various types. For example, the model described above captures the information encoded in m-gram models and Lau et al. (1993)s h o wh o wt r i g g e r -b a s e dm od e l sa n dc a c h em od e l s can also be absorbed into this framework. These models have been used for various kinds of language applications like disambiguation, sentence boundary identification, part-of-speech tagging, and numerous others. However, there are two major issues with the framework that need to be addressed; one relating predictive performance of the resulting model and the other of its computational efficiency. We discuss these aspects in detail below.

1.

Overfitting. The parameters recovered by minimizing L very well fit the data in C but fitting it too well will cause it to degrade performance on any other sample C 0 that deviates from C. This phenomenon of a model fitting the training data too well is called overfitting. Smoothing of parameters, similar to conventional n-gram models is used to avoid overfitting.

Regularization by constraint modification. Smoothing in maximum entropy models involves modifying the marginal equivalence constraint in (1.5). It is important to note that if the modification leads to an inconsistent set of constraints, the problem becomes infeasible and the solution space will be empty. Different modifications lead to different changes in the feasibility set resulting in different solutions (Chen and Rosenfeld, 2000). The earliest choice studied for smoothing of parameter estimates was to drop some of the constraints from the set described by the corpus C in (1.5). This widely used method is called constraint exclusion and various variants of this idea have been studied by Della Pietra and Della Pietra (1993); Lau (1994); Rosenfeld (1996) and Della [START_REF] Della Pietra | Inducing features of random variables[END_REF]. Typically, constraints corresponding to sequences with very low frequencies are the ones that are excluded. The resulting model is observed to be very close to conventional n-gram models with a positive threshold on the frequency count (Lau, 1994;Rosenfeld, 1996). Replacing the empirical estimate on the right side of (1.5) with a discounted value is called Good-Turing smoothing of maximum entropy models as described by Lau (1994)a n dRosenfeld (1996). The resulting model is known to be similar to Jelinek-Mercer interpolation smoothing for conventional n-grams models described above (Lau, 1994). Alternatively, Newman (1977)andKhudanpur (1995)relaxtheequalityconditionsin(1.5)todefineanupper and a lower bound on the marginals under the resulting distribution P ME to smoothen the estimates. The resulting inequalities are called fat constraints. An alternative is to optimize the unconstrained objective in (1.9) with an additional penalty term that adjusts for parameter smoothing. Chen and Rosenfeld (1999) propose using a Gaussian prior on the parameters which is equivalent to imposing an `2-norm on the parameters (Della Pietra and Della Pietra, 1993;Chen and Rosenfeld, 2000). Penalties similar to the `1-norm have been also been attempted by Goodman (2004). A combination of the two penalties, `1 and `2 2 ,s i m i l a rt ot h ee l a s t i cn e th a sb e e nt r i e db yKazama and Tsujii (2003)a n dChen (2009). The `2 penalty and its combination with the `1-norm have shown improvements (Chen, 2009; Alumae and Kurimo, 2010) while the `1 penalty alone was less satisfactory (Goodman, 2004)i n d i c a t i n gt h a tu n i f o r ms p a r s i t yi sn o ta na p p r o p r i a t e prior for modeling language. These modifications lead to appropriate changes of the update equations in Table 1.1. We discuss the issue of overfitting in detail in Chapter 2 and then in Chapter 3,w ep r o p o s eu s i n gs t r u c t u r ei n c o r p o r a t i n gp e n a l t i e st o steer the optimization to a more appropriate model.

2.

Computation of the normalization factor. The update at every step of the optimization in Table 1.1,r e q u i r e se s t i m a t i n gt h ee x p e c t a t i o no fs o m eq u a n t i t yu n d e rt h e distribution P ME (•) which depends on the current estimate !. This means, we will need to recompute the expensive normalization factor Z at every iteration of the optimization. [START_REF] Wu | Efficient training methods for maximum entropy language modeling[END_REF]presen tatric kthatimpro v esthetimerequired for computing Z by storing calculations that are common in multiple terms of Z. The time complexity of Z is still linear in the vocabulary V . Goodman (2001)r e d u c e s this dependence on V by clustering words. This breaks into into a two-stage problem of choosing the best cluster followed by picking the best word from the chosen cluster. This idea can be generalized to multiple levels of hierarchy that in the ideal case bring the complexity down to logarithmic in V . The hierarchy, however, should be such that the resulting classifier has predictive performance close to the original one. The hierarchy is usually built ad-hoc (Mnih and Hinton, 2008)o rb u i l tu s i n g the standard Brown clustering [START_REF] Brown | Class-based n-gram models of natural language[END_REF]Goodman, 2001) . In Chapter 4, we propose an alternative to build this hierarchy that is very generic and applicable to build taxonomies for various problems.

Recent trends

In the recent years, language models have been developed based on Bayesian techniques and distributed representations (recurrent neural network, Boltzmann machine and others).

We review some of these methods below.

Bayesian models

Numerous smoothing methods described above have performed well but offer very little insight in terms of the properties of word distributions they generate. It is well known that the distribution of word frequencies in natural language follows a power law with the distribution decaying rather slowly, also called the heavy tail behavior (Zipf, 1932). This is because there are a small number of higher frequency words and a significant number of low frequency words occurring in every sampling of text. A generative model should be able to mimic this behavior of the distribution by putting considerable mass in its tail.

Hierarchical Dirichlet language model. The power-law makes Gaussian-like distributions inappropriate to model language since they decay too quickly. Mackay and Peto (1994)s t u d i e dt h es u i t a b i l i t yo fD i r i c h l e td i s t r i b u t i o nt og e n e r a t eh e a v yt a i l st h a tc o u l d match language's behavior. They imposed a Dirichlet prior on the words and hierarchically stacked multiple layers of Dirichlet to model the probability of a word following various lengths of the context. Figure 1.1 shows a hierarchical model with three letter vocabulary V ={a,b,c} where each node indicates a context. The distribution over the words in V following that particular context is given by G x with G x (y)=P(y|x) for y 2 V .F o re x a mple, G bc =[ P(y|bc)] y2V is the vector describing the probabilities of words in V following the context bc. Mackay and Peto (1994) proposed this distribution to be drawn from a Dirichlet process, G x ⇠ DP (↵ x ,B x ), with strength parameter ↵ x controlling the mass in the tail and B x being the mean or base distribution (Ghosal, 2010). The base distribution at any given node will be the conditional distribution at the parent node, for example, B bc = G c and G ? (y)=1/|V |, the uniform distribution. This was the first work to develop a Bayesian model with an appropriately chosen prior over the words for modeling language and they reported favorable results. It was used develop an input mechanism that relies on touchscreen gestures or eye-tracking [START_REF] Ward | Adaptive computer interfaces[END_REF].

Pitman-Yor's power law. However, the Dirichlet process, despite being an improvement over others, would not satisfactorily match the distribution of word frequencies. [START_REF] Goldwater | Interpolating between types and tokens by estimating power-law generators[END_REF]Goldwater et al. ( , 2011) ) showed that a Pittman-Yor process (Perman et al., 1992)isclosertothe empirical distribution of word frequencies. They build a two stage morphological model to learn linguistic structure. The first stage is a generic model following any distribution, a multinomial in their case. This is then followed by the second stage of processing that produces distributions that are closer to natural language. They show that a Pitman-Yor pro cess for the second stage results in b etter p ower-law distributions and improved performances. Pitman-Yor, unlike the Dirichlet, has no known closed form representation and the induced distribution is handled using an appropriate Chinese restaurant process or a stick-breaking process (Teh, 2006;Goldwater et al., 2011). x . The resulting model with a Hierarchical Pitman-Yor process (HPY process) prior was found to deliver results comparable to the Kneser-Ney and also reveals interesting relations between them. The resulting equation of the HPY process model describing the generative procedure for drawing words was observed to functionally match that of the interpolated Kneser-Ney. This offers a principled derivation and an understanding of the smoothing technique that was otherwise ad-hoc, though effective.

In the hierarchical structure of contexts as shown in Figure 1.1,t h e r ea r eo f t e np a t h s of non-branching nodes. The conditional distribution at each of these nodes follows a Pitman-Yor process. It is known that HPY processes are closed under marginalization and the resulting conditional remains a Pitman-Yor process. This property was used to marginalize out the non-branching nodes in the hierarchy to develop an infinite length Markovian model (or a non-Markovian model) by Wo o d et al. (2010,2011), which they refer to as the sequence memoizer.

Distributed representations

Representing words often requires a 1-of-|V | encoding with a long vector of zeros containing a single one indicating the occurrence of the word. This is because finding a continuous space feature representation for words is non-trivial. However, it is a sensible thing to do considering some words are semantically closer than others, something the 1-of-|V | encoding does not reflect. Methods like latent semantic analysis represent words in a vector space [START_REF] Deerwester | Indexing by latent semantic analysis[END_REF] and are widely used in information retrieval and other areas. However, language models learned on such word features were found to be underperforming (Bengio et al., 2003). Models were designed to learn both the feature representation and the probability function jointly. These are referred in the literature as distributed representation models and offer competitive performances to traditional approaches. They minimize a complex energy function of the data and are often implemented with a neural network architecture. We will review three such models below.

Neural probabilistic language model. Bengio et al. (2003)p r o p o s et h en e u r a lp r o b abilistic language model built on feed-forward neural networks. They represent words in afi n i t ed dimensional continuous feature space and express the joint probability of the sequences in the corpus in terms of these feature vectors. The log-likelihood of the training corpus under this model is maximized over the parameters of the feature representation and that of the probability function. Figure 1.2 illustrates the architecture of the network with the notation. It is a three layered network with input to hidden layer connections, hidden to output layer connections and also input to output layer connections.

Consider s =(x m y) with the context

x m =(s 1 , ••• ,s m ).
Each word in x m is mapped to a R d⇥1 as X i = C(s i ) which are concatenated into X 2 R md⇥1 vector. The X vector makes the input that is mapped with W 1 to the output layer and with W 2 to the hidden layer. Offsets defined by vectors b 1 and b 2 are used in the two mappings. The hidden layer has h units and applies a hyperbolic tangent ⌧ (•) to its values which are then mapped onto the output space with W 3 . The output layer has |V | nodes, one per word in the vocabulary and contains the unnormalized probabilities of the target words (/ P(y|x m )). These scores could be used straight away for some applications (Bengio and Senecal, 2003), but when probabilities are required a softmax δ(•) is applied to the vector.

C : V ! R d⇥1 ,X i = C(s i ) X =[X 1 X 2 •••X m ] 2 R md⇥1 W 2 2 R md⇥h ,b 2 2 R h⇥1 W 3 2 R h⇥|V | ,b 3 2 R |V |⇥1 W 1 2 R d⇥|V | ,b 1 2 R |V |⇥1 ⌧ (z) , z i tanh(z i ) δ(z) , z i e z i P j e z j ✓ =(C, W 1 ,b 1 ,W 2 ,b 2 ,W 3 )
The parameters of this model ✓ are estimated using updates from the back-propagation algorithm. This neural model offered competitive performance to smoothing techniques outperforming Kneser-Ney. Additionally, the model returns a vector space representation for words which is a deviation from standard frequency tables. Smooth representation for words has the advantage of compactness and semantic meaningfulness but becomes challenging with polysemous words. The neural model has significantly more parameters than the traditional methods and has longer training times. Techniques like word clustering or importance sampling could be used to improve training times (see Bengio and Senecal, 2003;Schwenk, 2004;Schwenk and Gauvain, 2005;Morin and Bengio, 2005).

Log-bilinear language model. Mnih and Hinton (2007)proposedamodelthatminimizes a bilinear energy function similar to that of a restricted Boltzmann machine. They consider continuous space feature representations for words like Bengio et al. (2003)a n dc a p t u r e the interactions between the words in their energy function. This function is a similarity score between a mapping of the context x m onto the feature space and the features of the target word y. It has the following form,

E(x m ,y)=- m X i=1 1 s i C > R i ! C1 > y ,
where,

x m =(s 1 , ••• ,s m ), 1 v 2{0, 1} 1⇥|V | is a 1-of-|V | encoding of the word v, C 2
R d⇥|V | is a matrix of d dimensional features for the words, and R i 2 R d⇥d captures the interaction of the i th word s i and the target y. The resulting predictive distribution will be, ,v) , and the log-likelihood of the corpus is maximized to estimate parameters C and R i . The optimization alternates between the maximization over the feature representations C and the context mappings R i . The resulting model outperformed back-off Kneser-Ney and also has the advantage of learning a smooth representation for words. This model is similar to that of Bengio et al. (2003) but for the bilinear interactions which helped improve performance over the latter. Learning was further made to work faster using a tree-structured embedding of words in the hierarchical log bilinear model of Mnih and Hinton (2008). Bilinear functions were also be used to model multiple relations in language by Jenatton et al. (2012b).

1 v 2{0, 1} 1⇥|V | X =[1 v X 2 ] 2 R |V |+h⇥1 W 1 2 R |V |+h⇥h W 2 2 R h⇥|V | ⌘(z) , z i 1 1+e -z i δ(z) , z i e z i P j e z j ✓ =(W 1 ,W 2 )
P(y | x m )= e E(xm,y) P v2V e E(xm
Recurrent neural network language model. The distributed model of Bengio et al. (2003) is a fixed length Markov models where information in a sequence is processed in chunks limited by its maximal order. However, the recursive nature of language input as opposed to the fixed length input is not sufficiently captured by such models. This motivated models that explicitly characterize the recursive nature. Mnih and Hinton (2007)p r o po s e atemporalfactoredrestrictedBoltzmannmac hinethatoutperformsthelog-bilinearmodel described above for short context lengths. But the temporal model has significantly higher number of parameters restricting its applicability to shorter contexts while the log-bilinear model would easily scale to moderately long lengths and outperform the temporal models. Bengio et al. (2003)suggestaccommodatinglongercon textsb yin troducingatime-dela y ed layer in their network. Mikolov et al. (2010)i n v e s t i g a t et h i si nt h e i rr e c u r r e n tn e u r a ln e twork language model which is considerably simpler than that of Bengio et al. (2003) with fewer parameters to specify and significantly faster training times. It uses a simple three layer network similar to that of Bengio et al. (2003) but with recurrence in the middle layer. Figure 1.3 illustrates the corresponding network architecture with the notation.

Input to the network is 1-of-|V | encoded words X 1 from the training sequence in that order. At any given iteration, the second layer is fed the input word along with its own output in the previous iteration X 2 . The sigmoid function ⌘(•) is applied at the second layer and the output is fed into the third layer with a mapping W 3 . The last layer has as many nodes as there are words and contains unnormalized probabilities of generating the corresponding words. A softmax function gives out actual word probabilities.

In contrast to the architecture of Bengio et al. (2003), the strong difference lies in that the recurrent hidden layer imposes a time-delayed feedback. This time-delayed feedback conveniently takes into account the recursive dependence in the input. This model has outperformed interpolated Kneser-Ney smoothing and was applied to meeting recognition (Stefan et al., 2011)a n dt oc a p t u r el i n g u i s t i cp a t t e r n s( l i k ew o r d sking and queen indicate to positions of similar stature but vary in gender (Mikolov et al., 2013)). The time to train the network was improved further by using techniques like word grouping and other optimizations (such as Mikolov et al., 2011).

Summary and motivation

In summary, numerous methods were developed following various techniques to model language. There are both advantages and disadvantages for each of these methods and some are more suitable than others for specific tasks. While all methods focus on generating the conditional probability distribution of a word given the preceding context, certain methods make modeling easier for specific problems. A typical language application requires multiple layers of processing. In such cases, numerous factors play role in determining the applicability of a particular model. Factors like ease of integration, or aspects of time and space complexity, or suitability to problem's domain like incorporating additional information and so on. We motivate the purpose of pursuing and improving various models with a particular focus on the class of discriminative models to which maximum entropy models (Section 1.2.2)b e l o n g . W eu s et e x tg e n e r a t i o ni nm u l t i m o d a lp r o b l e m sa sa ne x a m p l et o present our case. We then describe which aspects of discriminative models we address in this work and summarize our contributions.

Discriminative modeling of multi-modal data. In this broad view of model compatibility to applications, we see discriminative models as those that fit into scenarios that require flexibility to pool additional features to learn combined models easily. Take multi-modal applications with language being one of the modalities, more specifically the target modality. The other modality, being the source modality, could be an audio signal or image features or a video sequence involving both. Generating short descriptive summaries of images or other data is one simple application where this could arise.

Consider the problem of generating human-like captions for images that recently gained significant attention (see, for example, Gupta et However, these methods deal with the two modalities separately with a one-way information channel transferring the image signal summarized in a few words, mostly image annotations with some additional tags on spatial organization (Mitchell et al., 2012;Yang et al., 2011;Farhadi et al., 2010;Ordonez et al., 2011)sen tacrosstothelanguagemodelto make its sentence. The language part pools this oversimplified information together with as much textual data of its own to make a meaningful sentence that sometimes leads to completely incorrect sentences (Mitchell et al., 2012).

Making meaningful sentences that explain the source signals requires the model to leverage statistical strength (Li et al., 2011)o ft e x tc o r p o r a . S u c hm o d e l ss h o u l da l s ob e amenable to accommodate source signals in determining the final distributions without the above over-simplification causing information loss. In tasks like this, we see discriminative models as a natural fit where we build a language model on available text from various sources and reuse that to learn a conditional model for our multi-modal data. Further, discriminative models allow for flexibility over aesthetics of language like its variations in style and tone, characteristics that manifest as terms in the objective function.

Encoding large context for discriminative modeling. Generating complete sentences in adiscriminativeframeworkrequireshandlinglongcontexts,insomecasespossiblyinvolving multiple sentences. This could be necessary for various reasons. For example, we might want to suppress information covered in previous sentences to avoid repetitions, or prevent from reusing the same words in the same sentences to maintain good readability, or to control the order in which content is delivered and so on. In such situations, one would need a discriminative language model that can encode large sentences efficiently. This is one aspect that we target in our work.

Large multi-class log-linear models. The other is a much more generic problem involving log-linear models with a large number of classes. The bottleneck is always the estimation of the normalization factor in which the number of vector dot-products directly depends on the number of classes. This slows training since it requires to estimate the gradient and also slows the test time application of the model. A growing number of classes is a challenge in numerous fields especially with language models where the number of classes is the number of words in the vocabulary. Organizing classes into a hierarchy is one standard trick to alleviate this issue and significantly speeds up test time predictions. However, building such a hierarchy without loss of performance in comparison to the standard multi-class classifier is a challenge. We propose various methods to build such a hierarchy from samples and empirically study their behavior.

Contributions and outline

This work revisits traditional approaches in the light of recent advances in structured penalties and large-scale optimization. In particular, we focus on the two issues of discriminative language models concerning generalization performance and model complexity. Our contributions can be summarized as follows:

1. Discriminative language models are known to overfit for long context lengths even when regularized using standard penalty terms. This clearly reflects in the predictive performance plots of models involving unstructured regularization on the subsets of AP-news corpus that we considered (see Figure 3.5). We study this issue to understand why simple regularization would not contain overfitting appropriately. To this end, we rewrite this model as a categorical distribution of words leading to a similar likelihood function as in (1.8) but with an extra constraint. The sequential structure of sentences is then interpreted on a suffix tree data structure. Penalties are then designed to exploit this tree structure inducing a structure-aware bias into the optimization. The optimization itself is described as operations on the suffix tree.

Models with structured penalties are evaluated on the same data as the unstructured models above and improvements in generalization clearly show up in predictive performance plots against increasing context lengths (see Figure 3.6). We further analyze the predictions of these models by grouping together words using various criteria to understand performance gains. As the plots reveal (see, e.g., Figure 3.8), there is scope for significant improvements which is a topic for future work.

On the complexity side, increasing context length leads to significant growth in the number of parameters. We study the efficiency of different penalties and some of them can be used to build models that scale efficiently with increasing context length. We prop ose an algorithm that improves the iteration time complexity for optimizing with such penalties over currently available methods. This work was published in the Conference on Empirical Methods in Natural Language Processing 2013. However, the method used to cluster words in the above models is either random or ad-hoc with the exception of Brown's clustering [START_REF] Brown | Class-based n-gram models of natural language[END_REF]. We propose different methods to group words using their contexts. These methods are generic with applications beyond data of discrete sequences and can also be used with nonsequence data in continuous feature spaces. We study their behavior on image and text datasets and observe how tree-building methods must be chosen carefully to stem performance loss by switching from flat multi-class classifier to a tree-based classifier. Interestingly, in some cases, a suitable tree structure could also lead to improvements in predictive performance.

Outline of the thesis. The outline of the remaining chapters is as follows. Chapter 2 describes risk minimization framework and the necessity of regularization particularly focusing on structure incorporating penalties. It also considers algorithms for optimization with such penalties and studies various methods available. Chapter 3 details our contribution on log-linear models involving structured penalties built on top of the suffix tree data structure. It studies time and space efficiency of optimizing with different penalties. Chapter 4 describes the grouping methods that we propose for building hierarchies or taxonomies. We also present evaluation results on various datasets. We summarize and conclude in Chapter 5 with remarks and directions for future work.

Chapter 2

Learning with structured penalties

Statistical learning theory has been successfully used to develop algorithms for numerous applications including classification and regression tasks (see Vapnik, 1998Vapnik, , 1995[START_REF] Vapnik | Estimation of dependencies based on empirical data[END_REF] The theory puts together statistical principles into an algorithmic framework that can be used to process data on machines. One such principle, and probably the most used of them, is the principle of risk minimization (see Vapnik, 1998,fordetailsof the risk minimization framework). Consider a parametric model that is designed to achieve a certain task with parameters lying in a defined domain. Risk quantifies the closeness of am o d e lt ot h ed e fi n e dg o a li nt h es p a c eo fp a r a m e t e r s . I ti sm e a s u r e db ya ne m p i r i c a l estimate over a certain sample set and hence the name empirical risk. This empirical risk is minimized using a learning algorithm to build the necessary classifier or regressor.

However, the effectiveness of this method relies on generating an appropriate and sufficiently large sample set to estimate the parameters of the model. In most scenarios, especially those involving high-dimensional spaces, it is not possible to generate a proper sample set. Minimizing the empirical risk too well is detrimental in such cases. To handle this overfitting, the risk function is modified to sacrifice some empirical risk by biasing the estimates in an appropriately chosen manner. This modification to risk function with a penalty or regularization term that induces the bias is referred to as the structural risk. The design of this regularization term is specific to the problem domain. Numerous choices for regularization with different properties have been investigated for various problems. We study some that are more suitable for language modeling than those considered earlier. The other issue in fitting an appropriate model involves designing an algorithm that minimizes this risk. We study algorithms necessary for risk optimization involving our choice of penalties.

In this chapter we detail the theory to achieve the goal of language modeling using structural risk minimization framework. We describe the principles of empirical risk minimization and structural risk minimization. We present various choices for penalty functions and choose the ones appropriate for out model. We briefly survey different algorithms available for their optimization and choose an appropriate method.

Principle of empirical risk minimization

The principle of empirical risk minimization was developed a few decades ago and has since been used successfully in numerous applications. Consider the event space X⇥Y where X is the feature space and Y is the output space. We wish to recover the function that maps X to Y from a given set of observations. The idea is to design experiments and collect empirical data for testing multiple hypotheses, h : X!Yand pick the best fit. Hypothesis is also called the predictor that predicts y 2Yfrom x 2X.I nam o r e generic case, it could be a mapping to some transformation of the outputs as ⇣(y)=h(x), where ⇣ is called the link function. Each hypothesis has a certain amount of expressiveness or the kind of relations it can capture. Greater expressiveness comes from more complex hypotheses involving more parameters.

The misfit of a particular hypothesis at any point (x, y) 2 (X⇥Y ) is measured by a non-negative real valued loss function f (•, •):Y⇥Y![0, 1]. The loss function f takes two arguments and returns a real value representing how different they are. Since our objective is to score the fitness of a hypothesis h for an event (x, y),w ep a s st h ep r e d i c t e d value of the hypothesis h(x) and its actual value y to retrieve the score f (h(x),y).

Define a probability density function P(X , Y) over the space X⇥Y .T o c o m p a r e multiple hypotheses, we must quantify each one over the complete space. Risk, R f P [h],i s the expectation of loss from h under the probability distribution P(X , Y):

R f P [h]= Z X⇥Y f (h(x),y) dP(x, y). (2.1)
It is this risk that we seek to minimize over all possible mappings Y X to choose the hypothesis that best models the problem:

R ⇤ =i n f h2Y X R f P [h] (2.2)
where R ⇤ is the best achievable risk by the most suitable predictor, commonly referred to as the Bayes risk.W ed e fi n ea st h ee x c e s sr i s ke the difference between R ⇤ and the risk from a hypothesis h, R f P [h],at e r mq u a n t i f y i n gh o wf a rw ea r ef r o mt h ebe s tpo s s i b l e solution:

e = R f P [h] -R ⇤ . Consider a set of hypotheses H✓Y X of varying complexities. The complexity of functions h 2Hdefines the capacity of the class H.L e t t h e c o r r e s p o n d i n g m i n i m i z e r of (2.2)i nH be,

h H =argmin h2H R f P [h].
Now, for any h 2H,t h ee x c e s se r r o re could be split into two components as follows:

e = R f P [h] -R ⇤ (2.3) =  R f P [h] -inf i2H R f P [i] +  inf i2H R f P [i] -R ⇤ = h R f P [h] -R f P [h H ] i | {z } e est h + h R f P [h H ] -R ⇤ i | {z } e app H ,
of which e app H depends only on the choice of the class H and e est h depends only on h.

Error e app

H is called the approximation error and quantifies how much worse R f P [h H ] is in comparison to the Bayes risk R ⇤ . This is due to the possible mismatch of the hypothesis class H for the problem being considered.

2. The other part of e depends on how far the solution h is from the optimum within H.

This component, e est h is called the estimation error. Consider a feature space X and an output space Y with a joint population distribution of D = P(X , Y).H o w e v e r ,w ed on o th a v ea c c e s st ot h i st r u ed i s t r i b u t i o nt oe v a l u a t e quantities involving D.W ei n s t e a dd r a ws a m p l e sS n = {x i ,y i } n i=1 ⇢ (X⇥Y) and use the corresponding empirical distribution S n (⇠ D as n !1 ) to approximate the unknown distribution D.Q u a n t i t i e si n v o l v i n gD are approximated by an estimate from S n . Thus, we approximate the risk

R f D [h] in minimization (2.
2)b yt h ee m p i r i c a lr i s kd e fi n e da s :

R f Sn [h]= n X i=1 1 n f (h(x i ),y i ). (2.4)
Now, consider a learning algorithm A : S n !Hthat takes observations S n and returns a hypothesis from H:

h Sn = A(S n , H)=argmin h2H R f Sn [h]
and the corresponding estimation error as,

e est Sn = R f D [h Sn ] -R f D [h H ]. Then we say, A is 1. statistically consistent w.r.t. D,f if for any ✏>0 P(R f D [h Sn ] -R f D [h H ] >✏) ! 0 as n !1.
2. Bayes consistent w.r.t. D,f if for any ✏>0

P(R f D [h Sn ] -R ⇤ >✏) ! 0 as n !1.
The idea of consistency in both the above cases shows that for the particular D and f , the risk can be driven to arbitrary close to the optimal value (R f D [h H ] or R ⇤ respectively) with high probability by using more samples for S n .W h e n t h e a b o v e p r o p e r t i e s h o l d independent of the distribution D,t h e nt h e ya r ec a l l e duniversally consistent learning methods.

The split of error into approximation and estimation terms can be used to understand an important trade-off between them. The approximation term is solely dependent on the set H but independent of the specific sampling S n .I tl o w e rb o u n d st h eb e s ta c h i e v a b l e risk using H. The estimation term, on the other hand, depends on S n and A.I nt h ei d e a l case when S n ⇠ D, h Sn = h H ,b u tt h i sr e q u i r e s ,n !1.

Given a finite random sample set, it is fairly possible that S n only crudely approximates D. This is often the case in high dimensional space, where there is almost never enough data to make an accurate estimate. In this situation, the minimizer of e est Sn and that of e app H are not equivalent, h Sn 6 = h H .W h i l eh Sn optimizes for the current sample set S n and very well minimizes e est Sn it also leads to generalization error, also called overfitting since S n 6 = D.W ec o u l di n s t e a dt r a d es o m ee est Sn for significant reduction in e app H and, end up reducing the combined error e. This is the approximation-estimation trade-off or more classically, when using a square loss, the bias-variance trade-off.

The bias-variance split comes from considering the mean-squared error (MSE)o ft h e estimator in (2.1) ( Hastie et al., 2009):

MSE[h Sn -h H ]=E[(h Sn -h H ) 2 ] = Var[h Sn ] | {z } variance +(E[h Sn ] -h H ) 2 | {z } square of bias .
Approximation error e app H corresponds to squared bias term and cannot be improved without modifying the hypotheses H. Estimation error e est h corresponds to the variance of this estimator since it depends on the sample size n and the algorithm used for estimation. In this interpretation, we wish to trade a little bias and make a more confident estimate with large reduction in variance.

The trade-off is made by appropriately modifying the class H.I n c r e a s i n gt h ec o m p l e x i t y of the functions in H results in a lower e app H and a higher e est Sn and vice versa. Large capacity of H shoots up e est Sn leading to overfitting described above. On the contrary, H with small capacity will lead to underfitting due to high e app H . This trade-off is balanced by controlling the capacity of H such that the resulting error e is minimal. The balance is achieved using an additional term in the risk function in (2.4)t h a tp e n a l i z e sc o m p l e xh y p o t h e s e s . W e discuss specific details of this penalization in the next section.

Penalized loss and structural risk minimization

In order to ensure good predictive performance, we need to minimize the excess risk e in (2.3). Since, we only have access to a finite sample of the actual distribution, this generalization is achieved by controlling the capacity of H.D e fi n eap a r a m e t r i cf a m i l yo f hypotheses H(λ) with the parameter λ controlling the capacity of the resulting class. We modify the empirical estimate of the risk in (2.4)toappendthelossf with a penalty term Ω:H![0, 1] that depends only on h and not on the sample S n . The resulting function called the structural risk is,

R f +λΩ Sn [h]= n X i=1 1 n f (h(x i ),y i )+λΩ(h). (2.5)
Parameter λ controls the weighting of Ω in comparison to f and we recover the empirical estimate in (2.4)b ysettingλ =0. The penalty Ω maps the hypotheses to the real number line by order of their increasing complexities. Increasing λ will encourage functions with smaller complexities and lowers the capacity of H. The set of hypotheses that is included in H(λ) for a given λ is easier to understand in the following equivalent form of (2.5):

R f,Ωδ Sn [h]= ⇢ P n i=1 1 n f (h(x i ),y i ) if Ω(h)  δ, 1 otherwise. (2.6)
Clearly, H(λ) of (2.6)i st h es e to fa l lh y po t h e s e sh for which Ω(h) is smaller than some δ.

There is a one-to-one mapping from λ to δ,ho w ev er,itisnotob vioustocomputeonefrom the other for any given Ω. The term λΩ is also called the regularization term and plays ar o l es i m i l a rt ot h a to ft h eprior in methods involving maximum a posteriori estimation.

Since the penalty adds some bias in return of variance reduction, the estimator in (2.5)i s ab i a s e de s t i m a t o r .

The choice of loss function depends on the specific goal of the model, its suitability to data and ease of optimization. In some cases, the loss might directly describe the problem like square loss for regression or 0-1 loss for binary classification. One might even minimize a complex loss function that is more suitable for the problem (like area under ROC-curve or, MAP, NDCG measures1 (Chen et al., 2009; Ravikumar et al., 2011), or ⌧quantile (Boyd et al., 2012)). However, considering ease of optimization a non-convex loss is often replaced a convex surrogate that is more amenable to optimization like hinge loss, logistic loss (multinomial for multi-class), huber loss, absolute loss, perceptron loss (see Steinwart, 2002;Mannor et al., 2002;Zhang, 2003;Jiang, 2003;Lugosi and Vayatis, 2003;[START_REF] Bartlett | Large margin classifiers: convex loss, low noise, and convergence rates[END_REF],a n do t h e rr e f e r e n c e st h e r e i nf o rs t a t i s t i c a lc o n s e q u e n c e so fv a r i o u s loss functions). The other choice to be made for the risk minimization framework is that of the penalty that incorporates our belief into the learning algorithm of what the parameters should look like. We discuss various options for penalty functions and their effect in the following sections.

To simplify notation, let hyp othesis set b e parameterized by a vector w as H = {h w }. In the case of linear predictors this would be ⇣(y)=h w (x)=w > x. The dependence could be more complex with h w (x) being any function of w and x.H e r e a f t e r ,w er e f e rt ot h e penalty Ω(h w ) in terms of the parameter vector as Ω(w).

Unstructured penalties

Regularization has become a standard component in almost every model and until about a couple of decades ago it was almost always the `2-norm. It offers additional benefits in some cases like adding stability to ill-conditioned problems which was how it was first introduced by Tikhonov, popularized as Tikhonov regularization. Lasso that was introduced later has been shown to be helpful in practice for which some theoretical results have also been proven like consistency under certain conditions (see for example Zhao and Yu, 2006;Zou, 2006;Wainwright, 2006). Since these penalties treat all parameters equally and regularize them uniformly, we refer to them as unstructured penalties.W e d e s c r i b e b e l o w s o m e unstructured penalties from the literature.

Ridge regularization. The most commonly used penalty is the Euclidean `2-norm (Ω(w)= kwk 2 )o ri t ss q u a r e dv a l u e( Ω(w)=kwk 2 2 )t h a ti sc a l l e dt h eRidge regularization. It penalizes the magnitude of the weight vectors and encourages vectors closer to the origin. H(λ) in this case is all points lying inside the `2-ball of δ units as seen from the alternative interpretation in (2.6). Expectedly, the `2-norm shrinks the weight vectors towards the origin and does so uniformly in all directions. The `2 2 penalty behaves similarly and the choice among the two is made by convenience of optimization.

Lasso estimator. The `1-norm is the other common penalty that gained popularity for H(λ) that involves sparse vectors. `1 penalty encourages sparsity by setting small values to zero that an `2 penalty would leave with small magnitude. This made `1 particularly interesting for problems where the actual solution is sparse as is often the case in large feature spaces. The estimator in (2.6) with Ω(w)=kwk 1 constrains the hypothesis class to an `1-ball of δ units. This sparsity inducing penalty leads to solutions similar to that of the popular Lasso estimator in statistics (Tibshirani, 1996)a n dbasis pursuit (Chen et al., 1998b)insignalprocessingandisrelatedtocompressedsensing (Candes and Wakin, 2008).

`1-norm has been shown to perform particularly well when sparsity is a valid assumption. In some cases it offers more than just better performance. `1-norm provides interpretability which is important for some applications involving large feature spaces. It also allows for high-dimensional inference with the number of observations logarithmic in the size of these observations.

Elastic net and fused lasso. Mixed norms were introduced to pool together properties from different penalties. Elastic net (`E n(γ) ) proposed by Zou and Zhang (2009)u s e sbo t h `1 and `2-norms on the features:

Ω(w)=kwk En(γ) = kwk 1 + γkwk 2 2 .
Its advantage comes from both feature selection using `1-norm and shrinkage of selected features from `2-norm. Fused Lasso (`F l(γ 1 ,γ 2 ) ) was proposed by [START_REF] Tibshirani | Sparsity and smoothness via the fused lasso[END_REF] which further adds a term to the elastic net that encourages piece-wise constant behavior by smoothing out minor changes in consecutive entries of w and retaining sufficiently large ones as controlled by γ 2 :

Ω(w)=kwk Fl(γ 1 ,γ 2 ) = kwk 1 + γ 1 kwk 2 2 + γ 2 |w|-1 X i=1 |w i+1 -w i |.
Non-convex penalties. All penalties considered above are convex functions, however, non-convex penalties are used when more appropriate. The `0(w) penalty, for example, maps a vector to its support (the number of non-zero entries):

`0(w)=supp(w)= X i I(w i 6 =0).
`0 is not a proper norm (often called a pseudo-norm) since it is not positive homogeneous, ↵||w|| 0 6 = ||↵w|| 0 for ↵ ≥ 0 and is non-convex which complicates optimization with troublesome local minima in a combinatorially large space. The `1-norm which is the tightest convex approximation for the `0 penalty is used as a surrogate for `0 Building upon the simpler norms, more theoretically appealing variants have been developed (like adaptive Lasso (Zou, 2006), relaxed Lasso [START_REF] Meinshausen | Relaxed lasso[END_REF], thresholding (Lounici, 2008), Bolasso (Bach, 2008a), stability selection [START_REF] Meinshausen | Stability selection[END_REF].; Wasserman and Ro eder, 2009)). Mixed and hybrid penalties that lie between `1 and `2 have also been studied. Apart from the ones mentioned above, various other penalties like the garotte (Yuan and Lin, 2007), bridge (Fu, 1998)a n d" B e r h u "( r e v e r s eo fH u b e r function) (Owen, 2006)c a na l s obef o u n di nt h el i t e r a t u r e .

Improved generalization from a penalty depends on its suitability (of properties like sparsity) to the data at hand. When suitable, the penalty uses the additional information to reduce the capacity of A with a more educated estimate of the solution space. While sparsity is the only additional information we have seen with `1,`0 penalties, sometimes there is more information available than just sparsity. Information like which groups of features co-occur, or a specific pattern in which zeros occur, or an ordering of its values and so on. This information can be used to further shape-up the solution space by suitably improving the penalty's design. We look at some structured penalties in the next section that help incorporate such additional information by redesigning the penalty.

Structured penalties

Structured penalties carve the space of hypothesis by using additional information from the problem domain. The earliest structure was in the form of specific patterns in which zeros occur in the solutions and hence the name structured sparsity. This was later generalized to other structures involving trees and graphs. We look at some examples in this section that we will use in later chapters.

Group lasso. The simplest form of structure that could be imposed is grouping of variables into non-overlapping sets. This was introduced by Yuan and Lin (2006) which they call the group Lasso. It imposes an `1-norm on non-overlapping groups of variables and `2-norm on variables within each group. This was further modified to a norm that uses an `1-norm within each group. We define a grouping on the features as follows:

Definition 1. Let G P = {g i } |G P |
i=1 be a partition (mutual ly exclusive and col lectively exhaustive subsets) of the set of indices I = {1, ••• , |w|} i.e., S g2G P g = I and g i \ g j = ?. G P defines a grouping on the entries of w.

Let w g 2 R d be a vector with entries from w corresponding to g and zeros everywhere else, i.e., w g (i)=w i I [i 2 g] where I[ • ] is the indicator function. Now, Ω(w) takes the following form for group Lasso:

Ω(w)=`G P p (w)= X g2G P kw g k p .
(2.7) The superscript G P defines the partitioning of features and the subscript p indicates to the norm imposed on each partition of features w g . The penalty across various groups is always the `1-norm also with other group penalties defined below, hence, we do not indicate this with a separate subscript. Such a norm either selects or discards a group completely. This is easy to optimize with non-overlapping feature groups but complicates with overlapping groups. But some overlaps are easier to handle than others.

Overlapping group lasso. A natural generalization of the group Lasso is to have groupings with feature overlap, as studied by Zhao et al. (2008) (see also Jenatton et al., 2011a). We define the grouping with overlaps, G O as follows.

Definition 2. Define a grouping with overlaps

G O = {g i } |G O | i=1 such that g i ⇢ I = {1, ••• , |w|} and S g2G L g = I.
An index in I could belong to one or more groups making the intersection of groups possibly non-empty. But each index must belong to at least one group. The group Lassolike formulation defined on G O is the overlapping group Lasso:

Ω(w)=`G O p (w)= X g2G O kw g k p .
(2.8)

The grouping G O defines a set of overlapping groups that is not a distinct partitioning of features as in group Lasso defined in (2.7). Each group w g has an `p-norm imposed on its features. This formulation also tends to drive groups of variables to zeros together but with a difference due to the overlap. A feature could belong to multiple groups and the feature is excluded from the final solution unless all the groups containing this feature are selected. So, only those features that belong to none of the zeroed groups belong to the final solution. The support of the penalty is the complement of the union of all the discarded groups. If G 0 is the subset of groups with a zero norm, then the support is,

supp(ŵ)= [ g2G 0 g ! c for some G 0 ⇢ G O .
One special case of the overlapping group Lasso that is of particular interest, is where the overlap is a nested hierarchy, referred to as the tree-structured group Lasso.

Tree-structured group lasso. Tree-structured norms were intro duced by Zhao et al. (2008)a n df u r t h e rs t u d i e db yJenatton et al. (2011b)e n f o r c eat r e es t r u c t u r eo nt h e variables. This is similar to the group lasso penalty but with overlapping groups organized in a tree structure. Each subtree of the tree forms a feature group. Feature groups in this case have a nested hierarchical structure. Definition 3. Let w be a vector with a tree structure T = {V, E} with V vertices and E edges, where each entry w i belongs to a vertex v 2V.D e fi n eg r o u p i n gG T = {g v } v2V where g v ✓{1, ••• , |w|} is the set indices in the subtree rooted at v. Now, Ω(w) takes the following form for tree-structured penalty:

Ω(w)=`G T p (w)= X g2G T kw g k p .
(2.9)

Similar to the group lasso, the tree structured penalty is often used with p =2 , 1.F i gure 2.1 illustrates an eight dimensional tree-structured vector along with the corresponding groups. The support with this penalty is as defined with the overlapping group Lasso that translates to a property that drives all descendants of a zero valued node to zeros. It does this by penalizing parameters lower in the tree more than those above resulting in solutions that usually have smaller values below. The groups in G 0 are the subtrees lower in the tree all variables of which have been shrunk to zero. Hereafter, we refer to this penalty as the `T p -norm with the tree structure T replacing G T for convenience.

Latent group Lasso. Obozinski et al. (2009a) study a different kind of overlapping group Lasso formulation where the support is the union of a subset of groups rather then their complement. They call this the latent group Lasso since they define latent groups of feature variables, the sum of which gives the final weight vector. P g2G L v g . The feature grouping here is similar to that of the overlapping Group Lasso above. Additionally, we define vector v g which is the latent vector corresponding to the feature grouping g. The definition of the latent group Lasso penalty is as follows,

Ω(w)=`G L p (w)= X g2G L kv g k p .
(2.10)

Since a feature could belong to multiple latent vectors v g and its contribution from multiple selected groups is summed together to get its value in w,af e a t u r ei ss e l e c t e di fa tl e a s t one group containing it has a non-zero norm. This property is in contrast to that of the overlapping group Lasso above. As a consequence, the support is the union of a subset of groups G 1 that have a non-zero norm:

supp(ŵ)= [ g2G 1 g for some G 1 ⇢ G T .
This was then extended to graph Lasso, the case with a graph structure on the parameters by grouping those parameters that share an edge.

Tree-guided group lasso. In a regression model with multiple outputs, it is more appropriate to assume that each output variable depends on a subset of features specific to itself, that varies from feature groups of other output variables. This motivates considering sparsity in features across output variables unlike other penalties for multi-task problems that only consider sparsity among features but not specific to outputs.

Consider the case where we are given a hierarchy defined over the output variables such that each node in the hierarchy groups a subset of the output variables. The leaves of the hierarchy are output variables. Kim and Xing (2010, 2012)d e s c r i b eam e t h o dt h a t uses such a hierarchy to define a penalty that at each node considers only those features that are relevant to the output variables belonging to that node in the hierarchy. Let y k ,k 2 [1, ••• ,K] be the K output variables. We now have one vector w k for each of the output variables with

I features ⇥ w 1 k , ••• ,w i k , ••• ,w I k ⇤ . Definition 5. Let R = {G R ,E R } be a tree over output variables {y k } K 1 with nodes G R and edges E R such that • for g 2 G R , g ⇢ [1, ••• ,K] and g = S h2χ(g)
h ,w h e r eχ(g) are children of g in R,

• and leaves of R are output variables.

Define w i g as the feature set with index i 2 I corresponding to the output variables k 2 g. For each no de in the hierarchy, the p enalty defined by tree-guided group Lasso, `GR p imposes an `p-norm on all the features of a given index i that belong to output variables at that node and and `1 across feature indices:

Ω(w)=`G R p (w)= X i X g2G R λ g kw i g k p .
(

2.11)

There is an additional weight of λ g for each group to ensure that the penalization of various output variables is balanced when features overlap. This penalty induces sparsity in feature sets across output variables.

All the above mentioned structured penalties are convex functions that are good for optimization. However, they are theoretically harder to analyze and few such results are available (see Bach, 2008b;Nardi and Rinaldo, 2008;Chesneau and Hebiri, 2008;Nardi and Rinaldo, 2012;Percival, 2012).

An alternative approach is to directly solve the non-convex penalties involving `0 pseudo-norm with appropriate groupings. In this direction, the greedy approach of orthogonal matching pursuit has been extended to incorporate structural properties Huang (Nardi and Rinaldo, 2011). In the next section we give some definitions and discuss specific tree-structured norms that we will use in later chapters.

Optimizing penalized loss

We now fo cus on minimizing the risk in (2.5) with the penalized loss over the observations S n . The optimization is rewritten in terms of the parameters of the hypothesis space w and the average of loss over samples is replaced by

L = P n i=1 1 n f (h(x i ),y i ): b w =argmin w R f +λΩ Sn [w]=argmin w L(w, S n )+λΩ(w).
(2.12)

We briefly review different optimization methods for generic loss functions and detail the specific approach we use for our application. Bach et al. (2012)p r e s e n tad e t a i l e dr e v i e w of various optimization techniques for various sparsity-inducing penalties.

In the case of convex smooth f and Ω, any gradient or Newton based method is appropriate. However, most penalties we considered above are convex but non-smooth, ruling out a simple gradient based algorithm. Similar issues arise with non-smooth loss functions (like the 0-1 or hinge loss) that are not easily amenable for gradient based methods. Various techniques have been adapted to suit specific cases of loss and penalty combinations. Numerous methods are employed to solve the large-scale optimization problems like breaking it down into smaller subproblems or exploiting the problem's structure or using low-rank approximations and so on (see Sra et al., 2011). We restrict our discussion to variations in penalties that we considered above and assume the loss is convex and smooth.

Gradient and Newton methods. If f and Ω are both smooth, the simplest algorithm to use would be steepest descent (or gradient descent) that offers O(1/t) rate of convergence for general convex differentiable functions with Lipschitz continuous gradients (Bertsekas, 2004), with a potential acceleration to O(1/t 2 ) (Nesterov, 1983). Convergence can be improved further to linear rate, O(⇢ t ) for strongly convex objectives. In problems where the Hessian is computable (twice differentiability) and invertible (well-conditioned and computationally feasible), second-order Newton methods would lead up to quadratic rate of convergence of O(⇢ 2 t ) (Bertsekas, 2004). Quasi-Newton methods are used to avoid inverting the Hessian that approximates it from successive estimates of the gradient. In cases where storing the dense Hessian is also infeasible, the inverse is locally approximated like using rank-one updates, also called the L-BFGS algorithm (Nocedal and Wright, 2006).

However, these methods are no longer appropriate when the objective is non-smooth. The quasi-Newton method of orthant-wise limited-memory quasi-Newton (OWLQN) (Andrew and Gao, 2007)i sa ne x c e p t i o nt h a th a n d l e sn o n -s m o o t h`1-norm regularized models. It exploits the fact that origin is the only non-smooth point in the domain. Nondifferentiability at the origin is handled by estimating the signs of the variables (by choosing an appropriate orthant) and restricting them to remain unchanged through the current update (make an L-BFGS update and project it back to that orthant). In other nonsmooth cases one needs to switch to subgradient methods. However, subgradient methods can be very slow to converge with a convergence rate of O(1/ p t) (Shor, 1985).

Active set and path-following methods. Alternatively, dedicated algorithms have been proposed for specific penalties on the lines of active set algorithms used in linear programming literature (see Nocedal and Wright, 2006). These methods use the prior knowledge of the solution being sparse to design computationally efficient algorithms. They typically keep track of a set of features, called the working set or the active set, that is likely to be in the support of the solution. This working set is modified appropriately until the solution is obtained. These algorithms are tailored for specific loss function L and regularization Ω of the optimization in (2.12)a n ds o l v ei tf o ras p e c i fi cv a l u eo ft h er e g u l a r i z a t i o np a r a m e t e rλ. As o l u t i o nf o u n df o ras p e c i fi cv a l u eo fλ can then be used to find the solutions for other λ values close to it. This is done by exploiting the property that for certain penalties the entries in the solution are piecewise linear when plotted against the regularization parameter. These are called homotopy methods or path-following algorithms (Markowitz, 1952; Osborne et al., 1999)t h a ti n c l u d et h ep o p u l a rl e a s ta n g l er e g r e s s i o na l g o r i t h mb yEfron et al. (2004). These approaches are known to work well in practice but are restricted to specific penalties.

Coordinate descent. Coordinate descent is another method that is known to perform well for some penalties (Fu, 1998;Friedman et al., 2007). This method minimizes along one coordinate at a time while iterating through the list of free variables of the optimization. In the case of `1-norm, for example, it results in iteratively soft-thresholding across each coordinate. It leads to similar rules for other penalties where applicable. But for coordinate descent to be applicable, it is necessary that the optimality conditions are separable across different coordinates (Tseng, 2001;Bertsekas, 2004). Fused lasso is one example where such separability is not possible leading to non-optimal points in the domain at which the UpdateConstants()

Procedure: w := GeneralizedGradient(S # n , w, λ, ⇢) #f o rs o m eS # n ✓ S n a. w 0 = w -1 ⇢ rL(S # n , w)# gradient step b.
w = Prox λΩ (w)# proximal step (see Table 2.1)

coordinate descent iterations are stuck (Friedman et al., 2007).

Reparameterizing the norm. Another method that applies generically is the weighted squared norm regularization formulation (Rakotomamonjy et al., 2008). Any norm can be rewritten as a maximum of quadratic functions which can be minimized using iterative least squares alternating between w and the parameter (Bach et al., 2012). This method has a caveat that might generate a term with zero in the denominator, cases like which need to be handled carefully.

Proximal methods. These are methods that are designed to optimize composite functions that involve sum of a smooth convex term (in our case L) with a convex but possibly non-smooth term (λΩ). There are a few algorithms that tackle such composite functions; Nesterov's method (Nesterov, 2007) with both batch and stochastic optimization algorithms, Forward Looking Subgradient by Duchi and Singer (2009) which is a kind of forward-backward splitting for both batch and stochastic and Regularized Dual Averaging for stochastic by Xiao (2010). We consider Nesterov's method that delivers the best convergence rate among these algorithms. Nesterov's proximal algorithm is an iterative process that makes a generalized gradient update at each step with gradient update depending only on L followed by the proximal step depending on λΩ. The proximal step is a projection involving a small optimization that can be solved efficiently for numerous penalties (analytically in few cases). We will consider this method in greater detail in the next section.

Proximal minimization algorithms

We cho ose proximal metho ds as they exhibit an optimal convergence rate among first-order techniques combined with the ability to reuse specialized algorithms for different penalties by simply changing the proximal step (see Nesterov (2007) Proximal methods iteratively update the current estimate by making a generalized gradient update at each iteration. Formally, they are based on a linearization of the

w = Z =0, ⌧ = δ =1, ⇢ = L + µ 2 repeat until maximum iterations 3 w =(1-⌧ )w + ⌧Z #estimate point for gradient update 4 w = GeneralizedGradient(S # n , w, λ, ⇢)# use mini-batch S # n ⇢ S n for update 5a Z = 1 ⇢⌧ +µ ((1 -µ)Z +(µ -⇢)w + ⇢w)# weighted combination of estimates 5b ⇢ = L + µ/δ, ⌧ = p 4δ+δ 2 -δ 2 , δ =(1-⌧ )δ #update constants
objective function f about the parameter estimate w,a d d i n gaq u a d r a t i cpe n a l t yt e r mt o keep the updated estimate in the neighborhood of the current estimate. At iteration t, the update of the parameter w is given by the following equation called the generalized gradient update,

w t+1 =a r g m i n w2K ⇢ f (w)+(w -w) > rf (w)+λΩ(w)+ L 2 kw -wk 2 2 , (2.13)
where L>0 is an upper bound on the Lipschitz constant of the gradient rf and w is the point at which the gradient is estimated. Equation (2.13) can be rewritten to be solved in two independent steps: a gradient update from the smooth part followed by a projection depending only on the non-smooth penalty:

w 0 = w - 1 L rf (w), (2.14)
w t+1 =a r g m i n W 2K 1 2 kw -w 0 k 2 2 + λΩ(W ) L .
(2.15) Update (2.15)iscalledtheproximaloperatorProx λΩ L (w 0 ). Efficiently computing the proximal step is crucial to maintain the fast convergence rate of these methods.

Proximal minimization procedure. The basic steps of a proximal minimization procedure are described in Algorithm 2. These methods iterate over three operations in a loop until termination. The termination usually involves a threshold on the amount of relative progress made in consecutive iterations ⇣

|L(w t+1 )-L(w t )| L(w t )
⌘ unless the duality gap is easily computable. The first operation involves finding the point at which the gradient needs to be estimated (Step 3). The second operation in Step 4 solves the update equation in (2.13) for a new estimate of the parameters. This is carried out in two steps with a gradient update for f (equation (2.14)i nS t e pa)f o l l o w e db yt h ep r o x i m a lp r oj e c t i o nf o rΩ (equation (2.15)i nS t e pb). The third operation updates any necessary constants necessary for the next iteration.

Accelerated batch minimization. The simplest proximal minimization scheme sets w = w t , the current estimate of the parameters. This is the iterative soft-thresholding algorithm (ISTA) that is known by other names in signal processing literature (see, e.g., Chambolle et al., 1998;Daubechies et al., 2004) and is known to converge at a rate of O(1/t). However, the rate of convergence can be improved by using a more appropriate choice of w. These methods are popularly known as accelerated gradient methods originally proposed by Nesterov (1983)(see also Tseng, 2008). One such algorithm is called the Fast Iterative Shrinkage Thresholding algorithm by Beck and Teboulle (2009). It involves computing the gradient at a point between the current parameter estimate and its estimate at the previous iteration. A fixed step-size could be used for the gradient update but it is common to choose a more appropriate step by backtracking. In backtracking, the size of the step is L⌘ K for some ⌘>1 with k being the smallest integer satisfying:

f (w) <f(w)+rf (w -w)+0.5L⌘ k ||w -w|| 2
2 . This algorithm is summarized as the batch method in Algorithm 3 with the three operations within the main loop matching Algorithm 2.S t e p3 computes the point (w) about which gradient is estimated. Step 4 makes the generalized gradient update with a loop for backtracking until an appropriate step is found. Step 5 updates the constants for the next iteration. This technique is shown to improve the rate of convergence to O(1/t 2 ) that is faster than the O(1/t) rate of the simple algorithm above.

Accelerated stochastic minimization. On the downside, Algorithm 3 requires multiple calls to function evaluation and the full gradient at each iteration. In most applications with large amounts of data it is extremely time consuming to compute the full gradient. As t o c h a s t i ca l t e r n a t i v ei st oe s t i m a t et h eg r a d i e n to ns u ffi c i e n t l ys i z e ds u b s e tc a l l e da mini-batch. The size of the mini-batch controls the variance in the gradient estimate that is traded against the computational time. Hence, we use an accelerated stochastic version of the proximal methods by Hu et al. (2009) with mini-batches to process large datasets. At every update, the stochastic algorithm estimates the gradient on a minibatch. This version of the optimization is summarized as stochastic proximal minimization in Algorithm 4.S t e p s3 and 5 are similar to the batch processing algorithm except with a different set of constants. But step 4 only uses a subset S # n ⇢ S n of the complete set of observations to estimate the gradient. This algorithm converges at a O(1/t) rate for strongly convex objectives but degrades to O(1/ p t) for general convex objectives.

Proximal operators for penalties

The proximal projection step in equation (2.15)liesatthecoreoftheproximalminimization algorithms. It can be rewritten as follows,

Prox λΩ (v) def == a r g m i n u 1 2 ||u -v|| 2 + λΩ(u).
(2.16)

Proximal step can be interpreted in numerous ways and related to existing methods (see Parikh and Boyd, 2013,f o rd e t a i l s ) . O n ep a r t i c u l a ri n t e r p r e t a t i o ni st ov i e wi ta st h e conjugate of the `2 2 smoothed conjugate of Ω. This operation is referred to as the Yoshida-Moreau regularization or infimum convolution. This helps us understand how it handles non-smooth functions in optimization. We present proximal projections for unstructured and structured norms and look at specific improvements later.

It is common to iteratively maximize the Fenchel dual of the minimization in (2.15) to solve for u (Jenatton et al., 2011b). However, the minimization can be solved very quickly in closed form for specific choices of Ω.I nt h ec a s eo f`2 2 ,o n ec a ns e tt h ed e r i v a t i v e of proximal objective in (2.16)t oz e r ot or e c o v e rProx λ`2 2 (v) ⌘ v/(1 + λ).B u t i t g e t s tricky with non-differentiable Ω like `1. Prox λ`1 can be rewritten in terms of projection on the dual norm ball using the following property of proximal operators called Moreau decomposition:

v = Prox λΩ (v)+Prox g (v), (2.17)
where g(y)=s u p x {y > x -λΩ(x)} is the Frenchel-conjugate of λΩ.W h e nΩ(v)=||v|| p is the `p-norm, then the Frenchel-conjugate is the indicator of the dual norm ball B q of radius λ. The dual norm ball for the `p-norm is B q = {x, ||x|| q  λ} where 1/p +1/q =1. This makes the corresponding proximal step for a projection onto B q ,a n ds u b s e q u e n t l y Prox `p would be the residual v -Π Bq (v).

Essentially, if we can project onto the dual norm ball efficiently, we make a quick proximal update. The proximal for `1-norm reduces to residual of projection on `1-norm ball; Prox λ`1 (v) is element-wise soft-thresholding v at λ.

In the case of group Lasso, the proximal step is separable over the groups leading to individual projection of variables in each of the groups. It can be solved similarly for the elastic net as well. It gets a bit trickier with fused lasso and involves making the projection in a series of two steps following the work of 1. Proximal step is made assuming only the fused part of the regularization exists and that of the elastic net is zero by setting Ω(w)=γ 2 P |w|-1 i=1 |w i+1w i |. This is performed by a modification of the LARS algorithm.

2. The above projection is then followed by a projection for the elastic net alone corresponding to the other two terms of the penalty.

These are reported in Table 2.1.H o w e v e r ,i ti sm u c hm o r ei n v o l v e df o ro t h e rs t r u c t u r e d penalties. We consider the particular case of tree structured penalty in detail.

The Prox λΩ (v) for tree-structured norms with Ω defined in (2.9)i sc o m p l i c a t e dd u et o overlap of groups. This overlap can be untangled by taking the dual and then coordinate ascent could be used to maximize the dual. However, for specific choices of p the maximization of the dual can be performed in closed form. Jenatton et al. (2011b)sho w edthat Prox `T p reduces to applying the Prox `p to the subvectors in a specific order defined by G below.

Algorithm 5 Proximal update for tree-structured norms following (Jenatton et al., 2011b). The set G defines an order on the grouping described in G T (from Definition 3)s u c h that before a group is encountered, all its subsets that are included in G T are visited. This is equivalent to visiting the nodes of T is a pre-order depth-first search. Given the ordering G, Prox `T p takes the following form:

u ⇤ = Prox λ`T p (v) def = = argmin u 1 2 ||u -v|| 2 + λ||u|| `T p Input: Vector u, parameter λ, tree structure T , ordered groups G. 1. for i 2{1, ••• , |G|} 2. w g i w g i -Π ||•||qλ (w g i ) 3. Return w a. `q is the dual norm of `p ( 1 p + 1 q =1)andΠ ||•
Prox λΩ (v)=Prox g |G| λΩ •••••Prox g 2 λΩ • Prox g 1 λΩ (v) (2.18)
where

g i 2Gand Prox g i λΩ (v) def == Prox λΩ (g v i )
. This is to say that the proximal update for the tree-structured norm is equivalent to applying an ordered sequence of projections for its groups with ordering defined by G. The order G of projections is such that for every g r ( g s , (g r ,g s ) 2G, g r is projected before projecting g s .I n o t h e r w o r d s ,a s u b t r e e i s projected only after all its subsets in the tree are projected. This order over the groups is generated by a bottom-up sweep of the tree.

Each Prox g i λΩ in the sequence of proximal operators can itself be rewritten as residuals of projections on dual norm ball (projection-residuals) using the decomposition in equation (2.17). This makes Prox `T p as e q u e n c eo fp r o j e c t i o n so nt h e`q-norm ball. The resulting procedure is described in Algorithm 5.

The second step of the procedure described in Algorithm 5 performs projection on the dual norm ball. This needs to be done in an iterative fashion and is not guaranteed to converge in finite number of steps. However, for specific norms, namely p =2and 1,i t can be performed in closed form. `2-norm being self dual Prox λ`2 (v)=v -Π `2λ (v) which is a block soft thresholding operator. Similarly, Prox λ`1 (v)=v -Π `1λ (v) requires an element-wise soft thresholding operator.

The projection on the `2-ball results in scaling operation and has complexity linear in the length of the vector. The resulting Prox λ`T 2 when applied naively as described above has quadratic complexity. A clever trick due to Jenatton et al. (2011b)i st oc o m p u t ea l l necessary scale factors and project the complete vector in one pass rather than projecting each of its subvectors individually. This reduces the complexity of Prox λ`T 2 to linear in the

`GT p Prox G |G| `p •••••Prox G 1 `p (w)
ordered sequence of proximal steps Table 2.1: Definitions of the penalties and their corresponding proximal operators.

number of dimensions. An adaption of this algorithm to our case is detailed in the next chapter.

Projection on `1-ball results in soft-thresholding operation and estimating the threshold value has an amortized linear time complexity in number of dimensions due to Bruckner (1984); Maculan and Galdino de Paula (1989); Pardalos and Kovoor (1990)l e a d i n gt o quadratic complexity similar to the case of Prox λ`T 2 .B u tt h ea b o v et r i c ku s e di nProx λ`T 2 does not apply here since a subvector should have been projected for the next threshold to be estimated2 .S o ,t h es e q u e n t i a ls t r u c t u r ei np r o j e c t i n gt h es u b v e c t o r sm u s tn e c e s s a r i l y be followed. However, under certain assumption on the distribution of values in the vector, the time complexity can be reduced to deterministic linear in the number of features. We discuss this algorithm with improved complexity for Prox λ`T 1 in the next chapter.

Conclusion

In this chapter we reviewed the necessary material for the risk minimization framework. We discussed different penalties available from basic unstructured functions to those that depend on specific grouping of its features. We motivate the choice for incorporating structure specific to the problem's domain into the penalty. Various algorithms available for their minimization were surveyed and the suitable choice of proximal gradient minimization was studied in detail. In the next chapter we will consider the log-linear language model that we propose with suitable penalty functions and their optimization.

Chapter 3

Log-linear language model

We now consider the sp ecific mo del that we prop ose for language. We describ e the problem discussed in Chapter 1 as a generalized linear model and explain the contextual features used in the model. Then, the suffix-tree representation is described which is necessary for tractable computation of the model. We distinguish between the two representations; at r i ea n dt h ec o r r e s p o n d i n gt r e et h a ti sm a d eb yc o l l a p s i n gn o n -b r a n c h i n gp a t h si nt h e trie. However, we will see that the tree representation is not suitable for our model and we introduce a partially collapsed trie. We then discuss penalties that are structurally suitable for language sequences and map their proximal projections from Chapter 2 to operations on suffix-trees. We show how specific proximal operators with some nice properties can be computed efficiently on the suffix-tree. We conclude the chapter with an efficient algorithm to optimize the penalized risk with large contexts.

Introduction to Generalized Linear Models

The hypothesis set we considered earlier in Section 2.1 is restricted to a linear mapping of the form y = h wy (x)=w > y x.H o w e v e r ,i ti se a s yt os e et h a tn u m e r o u sa p p l i c a t i o n s in real world follow more complex relations that cannot be explained by linear mappings. This has thus been extended to more general class of mappings where some function of the response or dependent variable varies linearly with the predictor, or ⇣(y)=w > y x. The link function ⇣ can be chosen arbitrarily with its domain matching the range of the expectation of y.I no u rc a s e ,t h el o g -o d d s( l o go ft h er a t i oo fp r o b a b i l i t i e so ft w oc l a s s e s )b e a r sal i n e a r relationship with the input variables. This relation is captured by a multinomial logit link function (Hastie et al., 2009).

This generalization offers multiple benefits over the simple linear model. For example, it allows for modeling count data, ordered data, categorical data (multi-way choices), and ordinal data (ratings). It does this by allowing for modeling response variables using skewed distributions (like Poisson, Gamma and others) beyond the standard Normal distribution of linear regression. These models have been dealt in detail by [START_REF] Mccullagh | Generalized Linear Models, Second Edition[END_REF]. We consider the case where ⇣ is the multinomial logit giving ln y = w > y xln Z(x, [w v ] 8v ) where [w v ] 8v is the matrix of all parameters and hence the name log-linear model. Loglinear models leave us with an exponential prediction of the form y / e w > y x .W es t u d ya log-linear formulation for modeling language in the next section.

Log-linear language model

Let V be the set of words or more generally symbols, which we call vocabulary. We are given samples in the form of a text corpus S n ⇠C with words from V and are required to assign probabilities to sequences of words of length m+1.S i m i l a rt ot h em a x i m u me n t r o p y methods considered in Chapter 1,w ed i s c r i m i n a t i v e l ym o d e lt h ep r o b a b i l i t yo fp r e d i c t i n g aw o r dy from its context x m , P(y|x m ). The joint distribution of a sequence s comes from predicting each of its words from the corresponding context. This is the case of |V |-way choice problem where we must choose one word from a list of |V | choices. Such situations are explained using the "categorical" distribution 1 over the vector of probability mass for different words. Probability for each word itself comes from the log-linear model described above as ⇡ v (x) / e w > v φm(x) leading to the following:

y|x ⇠ Categorical (⇡(x)) = Y v2V ⇡ v (x) I[y=v] ,⇡ v (x)= e w > v φm(x) P u2V e w > u φm(x) , (3.1)
where W =[w v ] v2V is the set of parameters and φ m (x) is the vector of features extracted from x, which we will describe shortly. Parameters are estimated by minimizing the penalized log-loss over the training corpus C = {(x m y) i } n i=1 :

W ⇤ 2 argmin W 2K L(W, C)+λΩ(W ), L(W, C):=- 1 n X (xmy)2C ln P(y|x m ; W ), (3.2)
where W ⇤ is the optimal set of parameters and K is a convex set representing the constraints applied on the parameters (it will be the positive orthant). The convex loss function L is called the log-loss and the penalty Ω can be non-smooth.

Next, we describe how to map a sequence x to its feature vector φ m (x).O u rf e a t u r e sa r e scaled indicator vectors that describe the sequence of words. These are the simplest features with no information of syntax or semantics of the language. They merely encode the sequential structure of sentences in vectors. Each non-zero value indicates the occurrence of a particular suffix with a magnitude that could vary with the length of the suffix.

We recall that x k denotes the suffix of length k of the sequence x,t h a ti s ,x k is the sequence of the last k symbols in x.I fx is followed by y,t h e nt h es e to fs u ffi x e s{x k } n k=1 defines the contexts in which y is observed. Further, let ⇠ k denote the lexicographically ordered set of all length k sequences formed with the elements of V .F o re x a m p l e ,t h es e t ⇠2 for V = {a, c, o} is the ordered set {aa, ac, ao, ca, cc, co, oa, oc, oo}.W ed e fi n ea mapping from sequences x to binary vectors k (x) indicating the location of the suffix x k in the set ⇠ k :

k (x)= ⇥ I(⇠ k (1) = x k ) I(⇠ k (2) = x k ) ... I(⇠ k (|V | k )=x k ) ⇤ > , (3.3
φ m (x)= ⇥ β(0) 0 (x) > β(1) 1 (x) > ... β(m) m (x) > ⇤ > , (3.4)
where the function β(k) weighs suffixes depending on their length k.I fw ec h o o s eβ(k)=1 for all k, then the suffixes of all lengths are equally weighted. The first entry 0 is a non-zero value indicating the null context. Moreover, φ m (x) discards all suffixes longer than m, restricting the maximal length of the context. This is equivalent to the Markov assumption used in m-gram language models. Indeed, φ m (x) encodes occurrences of various suffixes, while the parameters W provide a weighting of contexts of different lengths. The main difficulty comes from the fact that the dimension of the feature space is P m k=0 |V | k , meaning that the number of entries in W becomes rapidly unmanageable using standard data structures when the context length increases (as |V | is typically in the order of 10 4 or larger). This causes storage and computational issues, at training and test time. However, in practice φ m (xy) has only m non-zeros elements due to the sequential dependencies between successive symbols. In this context we describe the use of suffix trie and tree structures to handle this data efficiently.

Suffix encoding in tries and trees

Suffix trees provide an efficient way to store and manipulate discrete sequences as they can be constructed in linear time due to Ukkonen (1995) when the vocabulary is fixed (also see Giegerich and Kurtz, 1997). They are extensively used in natural language processing and bioinformatics. Recent examples include language models based on a variable-length Markovian assumption (Kennington et al., 2012)

andthesequencememoizer(Wo o d et al., 2010).

The data structure encodes all the unique suffixes observed in a sequence up to a maximum given length. It is organized as a tree with nodes lower in the tree holding longer suffixes. We distinguish a suffix trie from a suffix tree here. A trie stores the suffixes with one suffix per node. A tree,h o w e v e r ,c o l l a p s e sp a t h si nt h et r i et h a td on o t branch. A suffix tree could have multiple suffixes per node while the hierarchy still exists. Figure 3.1(a) illustrates the suffix trie on a sequence coacac and the corresponding suffix tree is shown in Figure 3.1 (b).W es p e c i fi c a l l yr e f e rt ot r i eb yt h es y m b o lS(X) built on sequence X and the corresponding tree by T (X).

This collapsing of such paths into nodes saves memory required to encode the sequence. Each internal node in a suffix tree has at least two children while those in a suffix trie have one or more children. The number of nodes in the tree scales by a significantly lower order than that of the trie with increasing length of the sequence. The exact relation between the sequence length and the node count varies from one application to another. In language, this has been observed to be linear by Wo o d et al. (2010).

Suffix trie structured vectors

The feature vector φ m (x) encodes suffixes (or contexts) of increasing length and it corresponds to one path of length m starting at the root of S(X). Thus, when building a log-linear language model, it is sufficient to consider weight vectors of size |S(X)|.I no t h e r words, there is one weight parameter per suffix per symbol and the matrix of parameters W is of size |S(X)||V |.A si l l u s t r a t e di nF i g u r e3. Making use of the suffix trie encoding additionally offers the computational benefit of efficient matrix-vector (or vector-vector multiplication), which lies at the core of optimization in (3.2). Indeed, each inner product w > v φ m (x) reduces to the following three steps: a. finding the longest suffix of x of maximal length m max in S(X), b. extracting the corresponding entries of w v and c. summing them after proper scaling with β(•).

Again, this is a substantial gain as the longest suffix of x is much smaller than |S(x)| and we avoid summing over weights that are irrelevant in a specific context. This technique of using an efficient data structure to fetch the few non-zero values of a very sparse large vector has been used earlier in numerous ways (most commonly as feature hashing [START_REF] Stolcke | Srilm-an extensible language modeling toolkit[END_REF]Weinb erger et al., 2009)a n ds o m e t i m e su s i n go t h e rs t r u c t u r e sl i k ew e i g h t e da u t o m a t o n by Roark et al. (2004)). We refer to these vectors as the trie structured vectors.

Word-sp ecific suffix trie structured vectors

While suffix tree encoding leads to a substantial storage and computational gain it might still cause problems in practice as the number of nodes is large for most real data sequences.

We can make further storage and computational gains by building one context tree for every symbol in the vocabulary and constraining the parameters to be non-negative.

We denote the resulting suffix tries by {S v (x)} v2V with one trie per word in V . The number of free parameters in W is now (b) shows the word-specific suffix trees for X = oacac and V = {a,c,o} and Figure 3.3 (b) the corresponding matrix of parameters W .A l lo t h e rp a r a m e t e r sv a l u e sa r e fixed to zeros. Note that the number of free variables varies from one vector to another in W .

P v |S v (x)|, which is substantially smaller than |S(x)||V |. Figure 3.2

Constraining to positive orthant

There are two issues that arise from plugging in the above described trie structured vectors into the optimization in (3.2).

1. The gradients of the log-linear model in equation (3.1)a r ed e n s ea n dr e q u i r ea n update of all entries of W for every single observation making the gradient update very expensive. Both these issues are due to the fact that for each positive sample (x, y),all(x, y 0 ),y 0 6 = y are considered negative examples. This leads to numerous negative entries for parameters in trees of labeled by y 0 .A s i m p l e w a y t o fi x t h i s i s t o e x p l o i t t h e r e d u n d a n c y i n t h e parameterization of the model to add additional constraint that removes the negative entries in the gradient.

The log-linear model described in equation (3.1) with |V | columns in W (one per word) is over-parameterized. Since it only requires parameters from |V |-1 columns to be estimated with the left out residual probability mass assigned to remaining |V | th class. A nonnegativity constraint is imposed to handle this over-parameterization which is similar to applying a large positive translation to all parameters. The ratio of number of positive entries to the total number of parameters being very small per each sample, this makes the gradient very sparse. This also makes it possible to replace the trie structured vectors (in Figure 3.3(a)) by the word-specific trie structured vectors (shown in Figure 3.3(b)), since the zero entries will remain untouched due to projection into positive orthant.

Fortunately, this constraint can b e handled very efficiently by pro jecting the gradient itself into the non-negative orthant before updating the parameter vector (Appendix B.6 of Jenatton et al., 2011b;Bertsekas, 2004). The constraint effectively reverts parameters corresponding to unobserved suffixes to zeros, which otherwise have small negative values. We solve the optimization problem using the suffix tree representation with this additional constraint of non-negativity of parameters.

Word-sp ecific suffix tree-structured vectors

Model complexity can be reduced further by ensuring that all parameters at a node share a single value. This would impose tree structure on the vectors instead of the trie structure leading to significant saving in memory. It is not straightforward to see why these parameters should share a single value. But with some modification to the standard suffix tree one can observe that this property will always hold. Then, we can collapse non-branching paths sharing a single value to reduce the number of parameters. We formally define this property as follows.

Definition 7. Constant value non-branching paths, P(S, w), are distinct subsets of nodes P ⇢V of a trie structure S = {V, E} w.r.t. S-structured vector w such that P has |P | nodes with |P |-1 edges between them and each node has at most one child and al l nodes (i, j) 2 P have the same value in vector w as w i = w j .

Figure 3.11(a) shows an example of a trie with constant value paths before collapsing them and Figure 3.11 (b) shows the tree structure for the same example after collapsing them. Rewriting the problem with a single parameter per node requires that along the iterations to solve for the optimization in (3.2), we preserve this property. Assume all values to be initialized with zeros for the optimization. There are two steps in the optimization that update parameters: gradient update and proximal projection. We should collapse nodes from trie S(X) such that the above property is closed under both the gradient and the proximal updates. Considering gradient updates, we wish to have the same gradient values for all parameters at any collapsed node. This is violated by nodes in word-specific trees that have overlapping suffixes with other word-specific suffix trees.

Consider the nodes of coaca and co in Figure 3.2 (b). The suffix cy is common to both trees indicated by y = o, a.A f t e rag r a d i e n tu p d a t ef o ro b s e r v a t i o nco,t h ep a r a m e t e r sa t node coaca will no longer share a common value. Since the corresponding gradient will have negative values at & 1,9 and zeros for & 10,15,16 . This can be avoided by splitting nodes that share suffixes with other trees as shown in Figure 3. is split into two each with a single parameter. The vectors as shown in Figure 3.3(c) now has 10 parameters against trie structured vectors that uses 17 parameters. We refer to this as suffix tree-structured vectors with tree structure M (X).H o w e v e r , strictly speaking this is not a proper suffix tree owing to the aspect that some intermediate nodes have a single child. We generically use suffix tree to mean either of the two trees in Figures 3.2(b) and 3.2(c) and distinguish between them by specifying if the vectors are trie-structured S v (X) or tree-structured M v (X). In the following section, we look at the effect switching from the trie structure to tree structure has on the number of parameters.

2(c).A c c o r d i n g l y ,t h en o d ecoaca

& 17-18 & 1 & 2-8 0 & 1 0 & 9 0 (b) W with Sy(X) shaped columns. w a w c w o $ 1 0 $ 5 $ 6 $ 7 $ 1 $ 2 $ 3 $ 4 0 $ 1 0 $ 5 0 (

Complexity improvements from trees

The complexity of the model measured by the number of parameters would vary from one task to another and depends on the patterns within the sequences of that data. We measure this for English language to compare the number of nodes in trie structures against that of the tree structures. We consider four distinct subsets of the Associated Press News (AP-news) text corpus with train-test sizes of 100K-20K for evaluation. The corpus was preprocessed as described in Bengio et al. (2003)b yr e p l a c i n gp r o pe rn o u n s ,n u m be r sa n d rare words (occurring fewer than three times) with special symbols "hproper_nouni", "#n" and "hunknowni"r e s p e c t i v e l y . S e n t e n c eb o u n d a r i e sa r ei n d i c a t e db ym a n u a l l ya p p e n d i n g each sentence with a start and end tag at the beginning and the end respectively. Punctuation marks are retained which are treated like other normal words. Vocabulary size for each of the training subsets was around 8,500 words.

Figure (3.4)p l o t st h ei n c r e a s ei nt h en u m b e ro fp a r a m e t e r sa g a i n s ti n c r e a s i n gc o n t e x t lengths for tries S y (X) and trees M y (X) for a sequence of hundred thousand words. Models using the uncollapsed trie structured vectors S y (X) show a linear increase in the number of parameters as we account for longer contexts to predict the following word. This dependence is only logarithmic when we collapse non-branching paths along the tree that share av a l u ea si nM y (X). Fewer parameters will require fewer updates at each iteration of the optimization over the model and eventually results in a more compact model. This shows how sequences can be encoded efficiently to build models that capture longer dependencies within sequence data.

Next, we consider different models involving structured and unstructured penalties. We could have used different optimization algorithms depending on the choice of the penalty like simple gradient descent with `2 2 , orthant-wise limited memory quasi-Newton for `1 (Andrew and Gao, 2007)a n dp r o x i m a lm e t h od sd e s c r i be di nS e c t i o n2.4 for structured penalties. But we consistently use a proximal algorithm for all penalties including unstructured penalties since it is convenient considering that we only need to change the proximal update to match the penalty. In the following sections, we describe algorithms for proximal updates on suffix trees for different unstructured and structured penalties we consider. These models are then fitted and evaluated on the train and test splits of the dataset described in Section 3.3.5.

Models with unstructured penalties

In this section and the following one, we fit models with unstructured penalties and evaluate their predictive performance on data. We repeat this evaluation with models of structured penalties in the next section showing how choice of the regularization effects predictive performance.

Evaluation criterion. There are multiple measures to evaluate language models depending on their application. Information theoretic measure of perplexity is one such quantity used in the literature. It is the average of the negative log-likelihood (also referred as the logloss) of the test corpus raised to the power of ten. It upper bounds the number of bits required per word to compress the text using that model. It serves as a generic measure to compare language models but often, evaluation methods are custom designed for specific tasks. For example, word-error rate (WER (Hunt, 1990)) is used to evaluate speech recognizers, bilingual evaluation understudy (BLEU score (Papineni and Roukos, 2002)o r its variants like metric for evaluation of translation with explicit ordering (Banerjee and Lavie, 2005)) is used for translation systems, recall-oriented understudy for gisting evaluation (ROUGE score (Lin, 2004) and it variants) for summarization and so on. These measures are tailored to quantify application-specific properties and are sometimes hard to compute (see Chen et al., 1998a, for WER). There is further work discussing how accurately these measures capture their actual objectives (see, e.g., Wang et al., 2003).

We use the standard perplexity measure that is generic and compares how different methods fare at predicting the test corpus. The perplexity measure is computed as follows:

P(C t ,W)=10 n -1 n V P (xy)2C t I(y2V )logP(y|x;W ) o , (3.5)
where n V = P (xy)2Ct I(y 2 V ) counts the number of in-vocabulary words and (xy) are sequences from the test set C t .T a g si d e n t i f y i n gs e n t e n c eb o u n d a r i e sa r en o tu s e di nc o mputing perplexity scores. Performance is measured for varying depth of the suffix trie with different norms of regularization suggested in Table 2.1.P e r p l e x i t yv a l u e sf o ru n m o d i fi e d interpolated Kneser-Ney are computed using the openly available SRILM toolkit [START_REF] Stolcke | Srilm-an extensible language modeling toolkit[END_REF]a n dm a r k e db yt h eKN curve in the plots.

We also evaluate space and time complexity of these mo dels. We use the numb er of free parameters in the resulting model to measure space complexity. A comparison of training time complexities for different models comes out to be a direct comparison of their proximal updates, since the gradient updates are all equivalent. Hence, we use the per iteration cost of making a proximal update to measure the time complexity for each model. In the following section, we describe proximal operations for unstructured penalties on suffix tries and study their behavior on language sequences.

Proximal projection with unstructured penalties

Proximal projections for unstructured penalties are straightforward and independent of the underlying tree structure of the vectors. They give the following update equations for proximal projections:

Prox `2 2 ⌘ w i w i 1+ Prox `1 ⌘ w i sgn(w i )[|w i |-] +
Evidently, these operations can be distributed across the entries of the vector and all parameters with the same value will continue to share a single value after the proximal update. `2 2 and `1 penalties preserve constant value non-branching paths P(S(X),w) making it possible to use M v (X) tree structure. This gives an O(M (X)) complexity for the proximal step.

Performance evaluation with unstructured penalties

We evaluate the mo dels by averaging p erplexity measure on four distinct subsets 100K words of the AP-news data processed as described in Section 3.3.5. The model is reset at the start of each sentence, meaning that a word in any given sentence does not depend on any word in the previous sentence. The regularization parameter λ of (3.2)i sc h o s e n for each model by cross-validation on a smaller subset of data. Models are fitted to a sequence of 30K words for 20 different logarithmically spaced values of λ from 10 -8 to 10 -3 and validated against a sequence of 10K words to choose the best fit. The optimal λ was further fine tuned to find the best performing values of 5.3 ⇥ 10 -6 and 8.5 ⇥ 10 -6 for `2 2 and `1 penalties respectively. Interestingly, the same regularization parameter was found to work for models with different tree depths for a given penalty. Figure (3.5) plots the average perplexity values from four subsets for different penalized models involving unstructured norms. It can be observed that the performance of `2 2 and `1 improves until a relatively low order of 3 and then degrades. This is because all features are treated uniformly by these penalties without proper consideration of the space of features. The space of sequences encoded by these features is not uniformly sampled. Features corresp onding to longer sequences is sampled much sparsely in comparison to smaller sequences. `1 and `2 2 penalties are completely agnostic to this difference in sampling causing them to overfit with features corresponding to longer contexts.

Models with structured penalties

We next consider models with structured penalties discussed in the earlier chapter. In particular, we choose the tree-structured penalty with hierarchical grouping of features as described in equation (2.9). This penalty naturally fits our data with the suffix trie or tree defining the grouping of features. It perfectly explains the proposition that data observed for features lower in the tree is sparser than that above and hence requires higher amount of regularization.

We restrict our choices of p enalty `T p to p =2 , 1 owing to the efficient closed form proximal updates as described in Section 2.4.1.I nt h i ss e c t i o n ,w ep r e s e n ta l g o r i t h m sf o r proximal updates for tree-structured penalties on suffix trees. We then use them to build Algorithm 6 w := Prox `T 2 (w) Proximal projection step for `T 2 on grouping G.

1 Input: T tree structure , w vector to project,  threshold 2 Initialize: {γ i } =0 ,{⌘ i } =1 3 ⌘ =U p w a r d P a s s ( ⌘, γ, , w) 4 w = DownwardPass(⌘, w)

Procedure: ⌘ := UpwardPass(⌘, γ, , w) 1 for x 2 DepthFirstTraversal(T, PostOrder ) 2 γ x = w 2 x + P h2children(x) γ h 3 ⌘ x =[1-/ p γ x ] + 4 γ x = ⌘ 2 x γ x Procedure: w := DownwardPass(⌘, w) 1 for x 2 DepthFirstTraversal(T, PreOrder ) 2 w x = ⌘ x w x 3 for h 2 children(x) 4 ⌘ h = ⌘ x ⌘ h
a. DepthFirstTraversal(T,Order ) returns observed suffixes from the suffix tree T by depth-first traversal in the order prescribed by Order. b. w x is the weights corresponding to the suffix x from the weight vector w and children(x) returns all the immediate children to suffix x in the tree.

models and compare them against those from unstructured penalties.

Proximal projection with `T 2 -norm

The proximal step for `T 2 -norm following the decomposition in (2.18)leadstoasequence of `2 proximal steps on subvectors. `2-norm being self-dual, `2 proximal step comes out to be residual of projection on the `2-norm ball from the equation in (2.17). Projection of vector w on the `2-ball of size  is equivalent to thresholding the magnitude of w by  units while retaining its direction:

w [||w|| 2 -] + w ||w|| 2 . (3.6)
This can be performed in time linear in size of w, O(|w|).

In our case the groups for subvectors are defined by the subtrees of the suffix trie S(X). The ordering defined in Definition 6 is an upward pass of the trie. This results in |S(X)| number of Prox g i λ`2 projections. Each Prox g i λ`2 scaling being linear in the number of entries in g i making the overall Prox λ`T 2 quadratic, O(|S| 2 ).

This can be made efficient by computing scale factors for each subtree g i as we make an upward pass and later apply them in one single downward pass of S(X). This is possible because the necessary values for computing scale factor for Prox g i λ`2 can be computed from the scaled `2-norms of child-subtrees if g i without actually applying the scaling on the children. This technique due to Jenatton et al. (2011b)l e a d st oa na l g o r i t h ml i n e a ri nt h e number of features |S(X)|. This algorithm for performing linear Prox λ`T 2 in two passes of the suffix trie is presented in Algorithm 6.

Feature weighting to avoid overfitting

Next, to avoid overfitting at larger depths we consider the simpler alternative of weighting features appropriately. By down-weighting a feature we reduce its contribution to performance which is similar to applying regularization on the feature. This method can be used to incorporate structure into unstructured penalties. We apply feature weighting with unstructured penalties `1, `2 2 by choosing an exponential decrease of weights varying as β(k)=↵ k .

Parameter ↵ was tuned on a smaller validation set. The best performing values for `2 2 and `1 were respectively 0.5 and 0.7. Thus, features deeper in the tree are scaled down. We refer to these weighted mo dels as w`2 2 and w`1.P e r f o r m a n c ep l o t sf o rt h e s em o d e l sa r e shown in Figure 3.7.

Further, we applied the scaling with `T 2 ,`T 1 -norm and performance improved for ↵ =1.1 and 0.8.W h i l et h em o d e lb a s e do nw`1 performs worse than interpolated Kneser-Ney, we see that the models based on w`2 2 and w`T 2 peform better. Interestingly, there is observable improvement up to about 9-grams with w`T 2 for the data set we considered, indicating that there is more to gain from longer dependencies in natural language sentences than what most standard models extract.

Interestingly, best performing ↵ for w`T 2 is greater than one, indicating that the unweighted model based on the `T 2 -norm was overpenalizing features at larger depths. For depths greater than 9,e v e n`T 2 starts to overfit slightly. It is important to note that while feature weighting could be used to verify for improvements in performance by manually fitting different laws of decay for β(k),i ti sn o taa na p p r o p r i a t em e t h o dt oh a n d l eo v e rfitting for the following reason. On changing the amount of data fed into the algorithm, the amount of regularization must also be varied appropriately. With feature weighting method, this requires retuning of the ↵ appropriately to account for this change in data and hence is not a convenient method to use. However, the same effect of fine tuning the amount of regularization across various depths can be achieved in structured penalties by using group specific weights in the penalty (Jenatton et al., 2011b). This is more conve- nient with varying amounts of data since the same regularization parameter can be reused by simply scaling it without having to retune it for new data.

The model of exponential decay performed better than a shifted logarithm and linear laws of varying weights from among which it was chosen. However, intuitively speaking, an exponential decay is not the most suitable since, it either starts to discard features completely (for ↵<1)o rg i v e st o om u c hi m p o r t a n c ef u r t h e rb e l o w( ↵>1)i nt h et r e e . Hence, weighing model can be used to verify for possible improvements over the simple structured models but is not a convenient model for practical use. This makes unstructured penalties with feature weighting less useful, further stressing the necessity of structured penalties in handling such problems.

Analysis of perplexity improvements

We now analyze performance of different methods split by various groupings of words. We try to segregate words into groups that would help understand sp ecific cases that are suitable for each of the models.

Figure 3.8 plots how different 7-gram models perform in comparison to Kneser-Ney with the words split by their context length at test time, m max . The value indicated by m max is the length of the longest suffix of a given test sample that was observed in the training corpus (or the suffix tree). All models predict a token (particular occurrence of a word) with the same number of context tokens m max .H e n c ea te a c hm max value, all models compare average logloss for the same set of words occurring in the same contexts. Points lying above zero are those methods that outperformed Kneser-Ney. The dashed line plotted to the right shows the number of words for a given m max value showing that more words tend to occur in newer or unseen contexts.

Evidently, all penalization methods fare similarly and better than Kneser-Ney when the context length is small. The performance of the models based on w`1 and w`2 2 degrades significantly with growing context length due to their shortcoming in encoding longer dependencies, while w`T 2 maintains performance comparable to that of Kneser-Ney. It can be observed that log-linear models are able to learn more accurate weights for the shorter contexts, for which more data is available. The model with w`T 2 penalty particularly stems this loss of performance with a gain over Kneser-Ney on average. This plot explains how structural information helps penalties improve performance. Further, it shows that there is more to gain with a more suitable structural penalty where we perform better than Kneser-Ney for shorter context and at least as well as Kneser-Ney for larger ones. A simple mixed model, for example, where we choose probability from w`T 2 for shorter contexts and Kneser-Ney everywhere else will give us a perplexity of 204.1 against 213.6 with only w`T 2 model and 217.4 with only Kneser-Ney. This is a significant boost for a simple heuristic from observing the curves in Figure 3.8.H o w e v e r ,s u c ham o d e l deviates from our goal to build a principled learning framework for larger tasks. It does not serve the purpose of learning weights through a model that has the various desirable characteristics as described in Section 1.5.

We make a point cloud of the words to visualize how different different methods perform. The average log-loss for each word predicted by the weighted log-linear models of order 6 is plotted against that of Kneser-Ney in Figure 3.9. The color code represents the frequency of the words. There is a large number of low frequency words concentrated on the top-right corner of the plot and fewer high frequencies along the left-bottom of the level set y = x. Words lying below the level set are those for which the corresponding log-linear model outperformed Kneser-Ney. The dense blue cloud of words on top-right tilts well below the level set indicating that the log-linear methods gain significantly with less frequent words that occur in large numbers. We can also observe the increasing dispersion of words away from the level set line from w`T 2 to w`2 2 and w`1. These are the fewer high frequency words where performance comparable to Kneser-Ney becomes harder.

Figure 3.10 plots difference in logloss for different models and Kneser-Ney for words in the order of their frequency at train. Each dot represents a word and the mean difference of logloss at a given frequency value is shown in a thick circle. Points to the left in the plots are concentrated above the zero line. These correspond to words with smaller frequency where learning methods fare better because there is more data for these parameters. Moving rightwards, models with w`T 2 and w`T 1 are packed close to the zero line while that of w`2 2 and w`1 are scattered with a few points lying well below the zero line. Finally, in Table 3.1 we report a few predictions randomly chosen from the test set that are representative of the different methods. We show predictions for different words with different context lengths m max in the first group. The values reported are logloss values with the best performing model marked in bold-face. We also show logloss of predicting the same word (police)underdifferen tcon texts. W enotethatthebestperformingmethodiseitherw`T 2 or Kneser-Ney.

Time complexity of proximal operators

Proximal updates Prox Ω of unstructured penalties (Ω=`1,`2 2 )arelinearinthen um berof nodes in the suffix trees M v (X) built for each symbol v in the vocabulary V .I nt h ec a s e of structured `T 2 ,t h et i m ec o m p l e x i t yo fProx `T 2 is linear in the number of nodes in S v (X) for v 2 V due to Algorithm 6.H o w e v e r ,Prox `T 1 has quadratic complexity in the number of nodes in S v (X) for v 2 V .

Prox Ω Complexity Naive algorithm Improved algorithm Ω=`1,`2 2 O(|M |) Ω=`T 2 O(|S| 2 ) O(|S|) Ω=`T 1 O(|S| 2 ) O(|M | ln M )
Table 3.2: Complexity of proximal operators for different penalties in terms of the nodes in the corresponding suffix tree (M ) and the trie (S).

It can be observed that the complexity of proximal updates for unstructured norms depend on the tree rather than the trie. This is because the corresponding models preserve constant value non-branching paths defined in Definition 7.I f t h i s p r o p e r t y h o l d s f o r structured penalties, we could reduce the number of parameters and consequently the number of operations by devising a more appropriate algorithm for proximal projection.

It is easy to verify that this property does not hold for Prox `T 2 .F i g u r e 3.11(c) shows an example of an eight-dimensional vector that violates this property. However, Prox `T 1 on the same example shows how these paths are preserved in Figure 3.11(d). This can be proven for the general case that constant value non-branching paths are indeed closed under Prox `T 1 operations.

In the next section we present two properties specific to the `T 1 -norm. The first among them shows that the suffix tree structure can be used instead of the trie structure reducing the space complexity from |S| to |M |. The second property uses this to derive an efficient proximal operation that involves fewer projections on to the `1-ball. This will then be used to derive an algorithm for Prox `T 1 with reduced time complexity in Section 3.6.2. Time complexities for proximal operations with naive projection algorithms and the corresponding improved algorithms are summarized in Table 3.2.

Properties of `T 1 -norm.

We present two prop erties of the `T 1 -norm on trees that will be particularly useful with thin and tall structures. The following proposition shows that paths P(S(X),w) are preserved under Prox `T 1 operations. Proposition 1. Constant value non-branching paths P(T,w) of T -structured vector w are preserved under the proximal projection step Prox `T 1 (w, ).

Proof. Let T be a tree with constant value non-branching paths P(w, T ) and P 2P ac o n s t a n tv a l u en o n -b r a n c h i n gp a t ho ft w on od e sv i ,i =1, 2 with v 1 being the child of v 2 . Node v 1 could further have a subtree below it. Let the subtree rooted at v i be denoted g i . Following the decomposition in (2.18), the proximal operator Prox `T 1 (w) will require applying the following operations

Prox `T 1 (w) ⌘ Prox gt `1 ••••• Prox g 2 `1 • Prox g 1 `1 •••••Prox gs `1 (w)
. Consider the operators applied on subtrees g 1 and g 2 of vector v obtained after applying all preceding operators on w,

δ(v) ⌘ Prox g 2 `1 • Prox g 1 `1 (v). (3.9)
Each of the two Prox(•) operations above is a residual of projection on the `1-ball of  units which is a thresholding operation as mentioned in (3.7). We can equivalently rewrite the same operations as shown below by replacing the thresholding [•] + with a min(•, •) operation:

g v 1 sgn(g v 1 )min(|g v 1 |,⌧ 1 ) (3.10) g v 2 sgn(g v 2 )min(|g v 2 |,⌧ 2 ) (3.11)
These two operations are applied in that order and the g v 2 in (3.11)involvestheg v 1 modified by (3.10). ⌧ 1 and ⌧ 2 are computed from vectors g v 1 and g v 2 respectively such that the condition in (3.8) is satisfied. We now look at different possibilities of ordering the pair (⌧ 1 ,⌧ 2 ) and check if the constant value non-branching path P is closed under (3.9). We us h i to denote the value at the root variable of g v i and h c to denote the `1-norm of the subtree below g v 1 (not including its root h 1 ).

1. ⌧ 2 >⌧ 1 . By using the condition on the pivot for projection in (3.8)o nt h es e c o n dp r o x i m a l step in (3.11)w eg e t , h 2 - = ⌧ 2 . Using the same condition on the first proximal step in (3.10), we have,

h 1 + h c -⌧ 1 =  =) h 1 -<⌧ 1 .
Since, h 1 = h 2 because P is a constant value non-branching path,

h 1 -<⌧ 1 =) h 2 -<⌧ 1 =) ⌧ 2 <⌧ 1 .
This contradicts with our initial assumption of ⌧ 2 >⌧ 1 ruling this option out.

2. ⌧ 1 ≥ ⌧ 2 .
The smaller of ⌧ 1 and ⌧ 2 dominates the entries of g v 1 in min(•, •) operations when applied in (3.10)a n d( 3.11). The entry h 2 is only affected by ⌧ 2 . This makes (3.10) redundant if we knew ⌧ 2 and the final solution of (3.7)c a nb eo b t a i n e db ys i m p l y applying g 2 v min(g 2 v ,⌧ 2 ). This retains the inclusion of P 2Pand the closure property holds in this case. However, note that using (3.7), ⌧ 2 can be computed only after applying ⌧ 1 in (3.10). This proves that constant value non-branching paths are closed under Prox `T 1 for two node paths. This can be extended to paths of arbitrary length using induction proving the closure property of P under Prox `T 1 operator. ⌅

The next proposition shows how composition of Prox `1 operations over constant value non-branching paths in P(S(X),w) can be simplified. Let Prox P `T 1 be composition of the following sequence of operations on non-branching path P 2P(S(X),w):

Prox P `T 1 ⌘ Prox g w |P | `1 •••••Prox g w 1 `1 , such that g w i 2G 8i 2 P.
It is those sequence of Prox `1 operations necessary for Prox `T 1 for which the root node of the corresponding subtree lies in the subset of node P with grouping g w 1 through g w

|P |

following the bottom-up ordering defined in G. We now have the following simplification of the above proximal sequence over P .

Proposition 2. Prox P `T 1 ⌘ Prox g w |P | `T 1 with  = |P |.
Proof. Consider the proximal operator applied on the two node non-branching path P in equation (3.7). It is clear from the proof of Proposition 1 that if we could directly estimate ⌧ 2 ,w ec a nm a k eas i n g l ep r oj e c t i o ni np l a c eo ft h et w oi n( 3.7).

The case of ||g v 2 || 1 <leads to a zero vector on projection with ⌧ 2 =0 .I ti se a s yt o see that this case holds to for this proposition. Consider the other case of ⌧ 2 > 0.L e t z = Prox g 1 `1 (v) and u = Prox Since sgn(v)=sgn(z)=sgn(u), we can write the following using the above two relations:

||g v 2 -g z 2 || 1 =  (3.12) ||g z 2 -g u 2 || 1 =  (3.13)
||g v 2 -g u 2 || 1 = ||(g v 2 -g z 2 )+(g z 2 -g u 2 )|| 1 = ||g v 2 -g z 2 || 1 + ||g z 2 -g u 2 || 1 =2
This can be extended to P of arbitrary length by induction principle and we recover

Prox P `T 1 ⌘ Prox g w |P |
|P |`T 1 proving the proposition. ⌅

The above propositions show that M v (X) structure is preserved under the proximal operation for `T 1 -norm and that it can be performed more efficiently. An immediate consequence of this is that the number of Prox `1 projections required reduces from the number of unique suffixes |S(X)| to the number of nodes in the tree-structured vectors |M (X)|. However, the proximal projection from Algorithm 7 will still be quadratic O(|M (X)| 2 ) due to the linear time complexity of the pivoting method. In the next section we will present a heap-based pivoting method that will improve the complexity of the proximal step to O(|M (X)| ln |M (X)|).

3.6.2 Fast proximal pro jection with `T 1 -norm.

Linear time complexity of computing the threshold value in Prox `1 is the reason for the quadratic complexity of the resulting Prox `T 1 operator. The amortized linear time due to Bruckner (1984)i sf o rp r o j e c t i n gg e n e r i cv e c t o r sb u ti ft h ev a l u e sw e r es o r t e di n descending order it would be O(k) where k is the number of entries larger than the pivot. Now if we have an upper bound on the number of largest few values we need to look at, we can bound the time it takes to compute the threshold in a sorted vector.

We verified empirically that in our case of language mo deling, the numb er of largest entries required to compute the threshold is about 3 on average in vectors with as many as 10 5 entries. Depending on the regularization, the maximum number of values it needs to compute the threshold is between 20 and 30. This leads to significantly faster computation of the threshold. However, we need an efficient way to keep the values sorted to exploit this fact.

Algorithm 8 w := Prox `T 1 (w) Proximal step for `T 1 on G using heap data structure.

Input: T suffix tree, w=[vc ] tree-structured vector v with corresponding number of suffixes collapsed at each node in c,  threshold Initialize: H ={ }# empty set of heaps 1 for x 2 DepthFirstNodeTraversal(T, PostOrder ) g(v, x):=⇡ `T 1 (w, x, c x , H )

Procedure: q := ⇡ `1 (w, x, , H ) 1 H x = NewHeap(v x ,c x ,v x ) 2 for j 2 children(x)# merge with child heaps ⌧ x = ⌧ x + ⌧ j # update `1-norm H x = Merge(H x , H j ), H = H\H j 3 H = H[H x ,S =0,C =0,J = {} 4 if H x (⌧ ) <, set H x =0return 5 for j 2 OrderedIterator(H x )# get max values if v j > S+(v j •c j )- C+c j S = S +(v j •c j ),C = C + c j ,J = J [{j} else break 6 r = S- C ,δ =0 #compute threshold 7 for j 2 J # apply threshold ⌫ =min(v j ,r),δ = δ +(v j -⌫) H j (v)=⌫ 8 H x (⌧ )=H j (⌧ ) -δ # update `1-norm
a. Heap structure on vector w holds three values (v, c, ⌧) at each node. v, c being value and its count, ⌧ is the `1-norm of the sub-vector below. Tuples are ordered by decreasing value of v and H j refers to heap with values in sub-tree rooted at j. Merge operation merges the heaps passed. OrderedIterator returns values from the heap in decreasing order of v.

We use a max-heap data structure to have access to values in the vector in a sorted order. A new heap is initialized at each leaf of M (X) with the node's value pushed on the heap. At each intermediate node g i ,am a x -h e a pi sm a d eb ym e r g i n gt h em a x -h e a p so fi t s children and adding the value at the node itself. Then one can use an ordered iterator to fetch values in the heap in decreasing order.

The exact time complexities of merging and ordered iteration depend on the kind of heap used. We use a Fibonacci heap that allows for constant time merging of heaps (Cormen et al., 2009) Figure 3.12 shows the time taken for `T 1 proximal step under different settings in one of the iterations of our experiments. Plot in Figure 3.12(a) compares the time in seconds for Prox `T 1 on suffix-tree and suffix-trie with increasing tree depth. The Prox `T 1 operation is computed using the random pivoting method of Bruckner (1984). The curve marked as random-tree makes only one projection operation per node in the tree using Proposition 2 as opposed to the random-trie method with one projection per node in the trie. We see how the per-iteration time difference between the two methods shows up with increasing depth of the tree.

In Figure 3.12(b) the random pivoting of Bruckner (1984)(curvemarkedrandom-tree) is compared against the pivoting method based on the Fibonacci heap described in Algorithm 8 (indicated by heap-tree). Time of the proximal step is plotted for increasing lengths of the training sequence. These plots show how suffix-tree can be used with the heap-based method to improve the time required for Prox `T 1 projection. This allows for efficient use of longer contexts with a structure incorporating penalty.

Conclusion

In this chapter, we describe log-linear models for language with structured penalties. We show how the suffix tree structure can be used to penalize features at different depths in the tree with varying amount of regularization. Then, we show how `T 1 penalty allows using the suffix tree instead of the trie leading to a space efficient model. We present an algorithm for optimizing with `T 1 -norm on trees in a time efficient manner using heap data structure. Properties of different penalties involving their generalization characteristics, time efficiency of proximal updates and space complexity of resulting models are summarized in Table 3.3. In the next chapter we will consider the problem of building a taxonomy of words (or any generic classes) from a text corpus (or samples). Chapter 4

Efficient taxonomy learning

In this chapter we will consider the problem of building a hierarchy of classes from their observations. This is a problem of generic interest to understand the hierarchical structure within a set of classes but also specifically useful in various learning models involving large number of classes. Large multi-class problems using log-linear problems are slow to train and apply at test time because of the expensive normalization factor involved. Hierarchical grouping can be used to divide and conquer the computation of this expensive factor. The test time complexity per sample of the flat classifier is O(K) where K is the number of classes. In the most optimal hierarchical setting of a complete binary tree, the test time complexity reduces to O(ln K) which is a significant gain in prediction time complexity.

We describ e this problem and prop ose a framework to build such hierarchies to overcome the issue. We particularly focus on the predictive performance of the tree-classifier for various depths of the tree.

Normalization in multi-class log-linear models

The formulation considered in the language model (3.1)isthatofalog-linearmodelapplied to a multi-class problem, that we recall here as,

P(y | x)= e w > y x P K k=1 e w > k x , (4.1)
where w k is the weight vector of category k and x is the feature vector. There are K categories which in the case of language would be the |V | words. An issue to common to such models is the computation of expensive normalization factor which is the computational bottleneck for large multi-class problems. The normalization factor in the above log-linear model is,

Z = K X k=1 e w > k x
During training log-linear models require estimating the expectation of some quantity that requires computing Z with the current estimates of w k at each iteration. This is also the case with maximum entropy updates in Table 1.1.F o rd i s c r e t es e q u e n c e s ,t h e speed of computing this quantity can be improved by ensuring some calculations common to multiple terms are not repeated as described by [START_REF] Wu | Efficient training methods for maximum entropy language modeling[END_REF]. However, there is more to gain by using hierarchical organization of classes, a method that is generic and not restricted to discrete sequential data.

The complexity of computing the factor depends directly on the number of classes involved. A simple workaround is to group classes or categories into fewer meta-classes. The problem is then a two-step process of choosing the right cluster followed by picking the best word from the chosen cluster. Each of these two steps have smaller Z factors to compute that are together cheaper than that of the original problem. The grouping process can be repeated to multiple levels to generate a hierarchy of classes (also called a taxonomy) where each non-leaf node in the hierarchy is a meta-class. A classifier is trained at each node for the meta-classes and a sample traverses the hierarchy from its root to a leaf during classification. This hierarchy directly reduces the time required for the normalization factor by reducing the number of choices at each level of the classifier. The use of such a taxonomy for classification is referred to as the hierarchical classification problem and sometimes also called the Pachinko machine.

Hierarchical classification and its extensions have been thoroughly studied in the literature. Extensions include problems with multi-label classification, hierarchies where internal nodes could assign labels, and directed acyclic graphs of classes instead of simple hierarchies (see Silla Jr. and Freitas, 2011,f o ras u r v e yo fh i e r a r c h i c a lc l a s s i fi c a t i o nm e t h o d s ) . However, the focus of these methods is usually on how best to train the hierarchical classifier given the taxonomy. We rather study the problem of building the taxonomy from sample distributions.

The problem of building a taxonomy given data samples has also been studied in the literature. In the particular case of reducing multi-class problems to binary classification, decision trees like CART are the earliest known (see Hastie et al., 2009). CART models use naive decision stumps like thresholds on predictors that are simple for moderately complex data distributions. Vural Goodman (2001)u s e st h ea g g l o m e r a t i v ec l u s t e r i n g method called Brown clustering proposed by [START_REF] Brown | Class-based n-gram models of natural language[END_REF]t ob u i l dat w ol e v e lh i e rarchical language model of picking the most probable cluster and then the most probable word from the chosen cluster. Brown clustering initializes one cluster per word and greedily merges a pair of clusters while maximizing the average mutual information of adjacent clusters (clusters with words belonging to them appearing next to each other in the corpus). Mikolov et al. (2011)useasimilarhierarc hicalorganizationforneuralnet w orks. Mnih and Hinton (2008), on the other hand, use a bootstrap method to build a hierarchy over the words.

In most classification tasks, taxonomies are either built manually as in Wordnet (2010) or borrowed from a related ontology (see Deng et al., 2009). In either case the hierarchy might be unsuitable for the task at hand. For example, Mnih and Hinton (2008)p r e f e rt o build the tree by bootstrap rather than using the existing hierarchy from Wordnet (2010).

This problem bears relation to parsimony studied in statistics and mathematical biology (Dunn and Everitt, 2004). In phylogenetics one seeks the most likely tree that explains the given data referred to as maximum parsimony (Kolaczkowski and Thornton, 2004;Steel, 2002). Approaches for maximum parsimony include maximum likelihood inference, distance matrix methods and Bayesian inference. While Bayesian inference resorts to sampling, frequentist algorithms often employ greedy methods returning suboptimal trees.

The crux of the problem lies in the fact that despite all samples being labeled with appropriate classes, the grouping of classes is inherently unsupervised. The steps that lead us from observations to a tree-classifier can be split into two parts either of which could effect the overall predictive performance:

1. Tree construction : Each leaf of a binary tree can be uniquely encoded by a binary string of 1s and 0s (for left and right edges). Each such string is a series of classifier decisions at the nodes. A classifier makes similar decisions for similar feature vectors and hence classes closer in feature space should have similar codes. This motivates grouping of classes by similarity of features making tree construction dependent on the measure of the proximity of the categories. These details are discussed in Section 4.2.

2.

Classifier training:L e a r n i n gp a r a m e t e r sf o rn o d e -s p e c i fi cc l a s s i fi e r so ft h et r e ec a nb e formulated in different ways. The choice of the formulation could determine the size of the optimization problem. A simple option is to train one classifier per node independently. This can be any kind of classifier including those that return probabilities like the nested logit [START_REF] Train | Discrete Choice Methods with simulation[END_REF]. Alternatively, one can use a classifier where each gradient update depends on a multiple nodes in the tree (Weston et al., 2010). We independently learn multinomial regression coefficient at each of the nodes. Section 4.3 discusses these details Our goal is to build a hierarchy that speeds computation while trying to retain performance of a simple flat model. We study empirically the performance of five different tree-building approaches by measuring predictive log-likelihoods.

Tree embedding of classes

A label tree is a tree T =( V, E, Z), where V is the set of nodes or vertices and E the set of directed edges and Z = {z v } |V| v=1 is the set of label-sets z v . Each label-set z v indicates a subset of the complete list of classes V that are relevant to the vertex v. V Algorithm 9 Hierarchical organization of categories.

Top-down approach 1 Input:

X 2 R n⇥d ,Y 2 R n⇥K Output: T =(V, E, Z) Initialize: V = {v}, E = ?, Z = {z v } with z v =[1, ••• ,K] 2 repeat until required depth 3 for v 2V, v is leaf and |z v | > 1 4
find optimal partition (s, t) such that would the vocabulary list for language modeling. Let K v = |z v | denote the number of labels at vertex v.

z v = z s [ z t #update tree 5a V V+ {s, t} 5b E E+ {e v!s ,e v!t } 5c Z Z+ {z s ,z t } 6 return T Bottom-up approach 1 Input: X 2 R n⇥d ,Y 2 R n⇥K Output: T =(V, E, Z) Initialize: V = {v 1 , ••• ,v K }, E = ?, Z = {z 1 , ••• ,z K } with z k = k 2 A = V #A
Each vertex except the root has a single parent, but can have multiple children. We are interested in a balanced label tree on top of the K classes based on local optimal decisions. Given a data point, vertex-specific classifiers will then successively decide which branch of the tree to follow (see Figure 4.1). We derive top-down and bottom-up approximations of flat multi-class classifiers by a tree of given depth.

In the top-down approach, the multi-class classifier is greedily approximated by recursively partitioning label-sets. At every level of the tree, each vertex partitions a subset of the classes into two (approximately) balanced meta-classes, meaning that each metaclass contains roughly half the classes originating from the parent vertex. The labeling of the classes at vertex v,d e n o t e dz v ,i sav e c t o ro fs i z eK v indicating the child to which the label is pushed. Trees generated by the top-down approaches here are binary with z v = {-1, +1} Kv . This process is repeated down to the required depth. Each leaf node then, either corresponds to a single class, or a small number of classes, in which case it contains a multi-class classifier. Hence, in this setting the choice of tree-depth will realize at r a d e -o ffbe t w e e nc l a s s i fi c a t i o na c c u r a c ya n dc l a s s i fi c a t i o ns pe e d .

In the bottom-up approach, classes are successively aggregated up to required level. This procedure creates a tree that could be non-binary at the top. Again, the tree depth determines the trade-off between classification accuracy and classification speed. Given the tree, we learn node-specific classifiers in the same way.

Algorithm 9 summarizes the procedures to build the hierarchy from observations in topdown and bottom-up approaches. Step 4 of both top-down and bottom-up approaches in the algorithm indicates to the grouping of categories. In the top-down case it is the optimal partitioning and in the bottom-up it is the optimal merging. We need a measure of closeness of categories for either of the operations (split or merge). We use the residuals under the square loss for this measure, that we describe in Section 4.2.1.A te a c hs t e po f the iteration, we need to recompute this measure for a particular subset of the categories that we wish to split or merge. This update of the residuals is described in Section 4.2.2. Then, we need an algorithm to carry out the split or merge given the subset of categories. We discuss different methods for this grouping in Sections 4.2.3 and 4.2.4.F i n a l l y ,w el e a r n the classifiers at each node of the recovered label tree which we describe in Section 4.3.W e evaluate these models in Section 4.4 and conclude in Section 4.5.

Measuring the class proximity

Let X 2 R n⇥d and Y 2 R n⇥K be respectively the d dimensional feature vectors and the corresponding class label indicator vectors. Columns of Y correspond to class labels and rows to observations. Each row of Y contains a single entry equal to 1,a l lo t h e r sb e i n g equal to zero; if observation i belongs to class j,t h e nY ij =1.W em e a s u r ec l a s ss i m i l a r i t y through the residuals under a ridge regression model. Consider minimization of the `2-regularized square loss:

W ⇤ =argmin W kY -XWk 2 + δkW k 2 , (4.2)
where W 2 R d⇥K with columns [w 1 , ••• ,w k ] corresponding to the K categories. Setting the gradient of the above equation (4.2)t oz e r og i v e su s ,

2X > (Y -XW) -2δW =0,
or equivalently,

W ⇤ =(X > X + δI d ) -1 X > Y, (4.3)
where I d is a (d ⇥ d) identity matrix.

Residual matrix. Substituting this closed-form solution for W ⇤ from (4.3)b a c ki n t ot h e objective in (4.2) leads to the following matrix of squared residuals:

Q = Y > (I K -X(X > X + δI d ) -1 X > )Y. (4.4)
The Q matrix contains values that measure how close the corresponding category pairs are under the square loss. The goal for bottom-up or top-down tree building approaches will be to make partitions of the label-sets with a small product of residuals.

The process of partitioning (or merging for bottom-up) will be repeated iteratively until the required depth as described in Algorithm 9. This will require us to recompute the residual matrix for different label-sets. Consider a node v 2V with

K v = |z v | categories, z v ⇢ [1, ••• ,K].
The square residuals Q v for categories within node v will follow (4.4),

Q v = Y > v (I Kv -X v (X > v X v + δI d ) -1 X > v )Y v , (4.5)
where X v is the subset of observations belonging to categories in z v and Y v is the corresponding class indicator matrix. 1. In large feature spaces with few observations (large d, small n), we use,

Q = Y > (I K -XX > (XX > + δI d ) -1 )Y,
where the complexity is reduced to O(n 3 ) by using the matrix inversion lemma.

2. In large feature spaces with many observations (large d, large n), we use,

Q = Y > (I K -R(R > R + δI d ) -1 R > )Y, XX > = RR > ,R 2 R n⇥m , zl zr Q v ! Q l Q r
(a) Split operation. Q l ,Qr can be approximated with submatrices from rows and columns corresponding to labels zl , zr respectively. Such a split operation is only an approximation.

p q p q Q v ! t t Qv (b
) Merge operation. Rows (columns) p, q removed from Qv and added to make row (column) t which is appended to make the new residual matrix Qv. The idea it use matrix inversion lemma and write Q as an inversion of XX > . The XX > is then approximated by a low-rank decomposition such that XX > = RR > where R has dimensions m ⌧ d. Then we again use the matrix inversion lemma to write it as an inversion of R > R.

There are various algorithms to achieve this low-rank decomposition like sparse greedy approximations (Smola and Scholkopf, 2000), incomplete Cholesky decompositions (Fine and Scheinberg, 2001), or Nystorm's method (Williams and Seeger., 2000). They approximate XX > by exploiting the fact that X can be represented in a lower dimensional subspace and that the rank of the resulting matrix m is small in practice. We use the incomplete Cholesky decomposition in our algorithm (also see Bach and Jordan, 2005;[START_REF] Golub | Matrix computations[END_REF]. The decomposition is O(m 2 n),i . e . ,l i n e a ri nn and the resulting matrix can be inverted in O(m 3 ) as opposed to O(d 3 ) or O(n 3 ).

Split and merge operations

At an given iteration of the tree building process, we need to choose the best split of the classes into two groups for top-down approach and correspondingly the best merge for bottom-up approach. We show below that the update for residual matrix Q v can be performed efficiently for merge operations but it needs to be recomputed for split operations at every iteration.

Merge operations on residual matrix Consider the situation in Figure 4.2(b) where vertices p, q of matrix Q v are merged to make vertex t. Merging here implies, labels from sets z p ,z q both receive the same labeling in vertex t.W es h o wt h a tt h i sc a nb ea c h i e v e db y merging the columns corresponding to vertices p, q in the indicator matrix Y v while keeping X v unchanged. Let Y v be (n v ⇥ k) indicator matrix, then the updated indicator matrix Ȳv is as follows

Ȳv = Y v U where, U k⇥(k-1) = ⇥ u i k⇥1 ⇤ ,i 2{1, ••• ,k}[{p + q}\{p, q} u i k⇥1 (j)= ⇢ 01  j  k, j 6 = i 1 j = i u i k⇥1 is a k-dimensional unit vector with 1 in the i th position. U is a (k ⇥ (k - 1
)) binary matrix made by removing two columns u p ,u q from I k and appending the column (u p + u q ) to it. The residual matrix after merge Qv takes the following form,

Qv = Ȳ > v [I -X v (X > v X v ) -1 X > v ] Ȳv = U > Y > v [I -X v (X > v X v ) -1 X > v ]Y v U Qv = U > Q v U
where Q v is the residual matrix before merge operation. The update U neatly factors out of the residual matrix making it simple to compute the new residuals.

Hence, we can exactly compute the residuals Qv after a merge operation from Q v by simply summing the appropriate row (or columns) of Q v .H o w e v e r ,i nt h ec a s eo fs p l i t operation there is no convenient trick to derive the modified residuals which must be recomputed using the new label sets.

Split operations on residual matrix Consider the case where label set z with residual Q is split into z l and z r as in Figure 4.2(a).W i t h o u tl o s so fg e n e r a l i t yw ec a na s s u m et h a t X and Y can be ordered by labels z l followed by z r :

Y =  Y l 0 0 Y r ,X =  X l X r . (4.6) Recall that Q v = Y > v (I Kv -X v (X > v X v + δI d ) -1 X > v )Y v . Rewriting Q v in terms of X l ,X r ,Y l ,Y r from (4.6), we get the following, Q v =  Y > l Y l 0 0 Y > r Y r -  Y > l X l B -1 X > l Y l Y > l X l B -1 X > r Y r Y > r X r B -1 X > l Y l Y > r X r B -1 X > r Y r
, where B = X > X + δI.

If we were to extract the submatrix of Q v corresponding to the labels in z l ,w ew o u l d have,

Q l = Y > l I -X l (X > X + δI) -1 X > l Y l .
But the correct matrix Ql would be Ql

= Y > l I -X l (X > l X l + δI) -1 X > l Y l .
N o t et h a t they are not equivalent and since the matrix inversion makes it impossible to recover Ql that we need by simply modifying Q l .H e n c e ,w er e q u i r et or e c o m p u t et h er e s i d u a la f t e r every split operation in the top-down approach.

Top-down pro cedure

Consider a vertex v with K v classes and let {X v ,Y v } be the set of observations belonging to one of these K v classes, where X v 2 R nv⇥d and Y y 2{0, 1} nv⇥Kv .A tv e r t e xv,w ep a r t i t i o n the K v classes into two disjoint subsets corresponding to the two subtrees. This can be done by picking a label vector z v 2 {-1, +1} Kv , each entry of which entry describe which of the two subtrees the corresponding label belongs. Under a multiple regression model, we obtain the following optimization problem:

min zv min wv kY v z v -X v w v k 2 + δkw v k 2 . ( 4.7)
Substituting back β v from (4.3)i n t ot h ea b o v ee q u a t i o ns i m p l i fi e si ti n t oaf o r mt h a tc a n be rewritten as the following trace minimization problem: Low-rank approximation: Here, we will take a different route by noting that (4.8)i s closely related to the clustering formulation DIFFRAC (Bach and Harchaoui, 2007). 1 First, note that A v = z v z > v has constant diagonal, is positive definite and has rank-one. As in (Bach and Harchaoui, 2007;[START_REF] Goemans | Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming[END_REF], we relax the rank constraint to obtain a semidefinite program. Second, we add 11 > to the objective to avoid the trivial solution of a constant vector (Joulin et al., 2010). This leaves us with the following relaxed optimization problem:

minimize zv tr z v z > v Q v . ( 4
minimize Av tr A v Q v + 11 > (4.9) subject to diag(A v )=1,A v < 0.
The value of the parameter  is reasonably set to 1 Joulin et al., 2010). We used the solver proposed by Journee et al. ( 2010), which returns a matrix A v of rank at least two. This matrix is then projected to the space of rank one matrices by taking the eigenvector corresponding to the largest eigenvalue of A v . This vector is then thresholded at zero to recover cluster assignments. This problem is referred to as DIFF hereafter.

K 2 v (
Spectral relaxation: As imple rre laxationtotheproble mistoimpos ez >

v z v = K v , which corresponds to relaxing the constraints diag(A v )=1to tr{A v } = K v . This leads to minimize zv tr z v z > v Q v (4.10) subject to z > v z v = K v .
The solution to this problem is the eigenvector associated with the smallest eigenvalue of Q v , which is then thresholded at zero to recover cluster assignments. This method is referred to as SPEC.

Bottom-up procedure

The above two methods, SPEC and DIFF, build the tree in a top-down fashion by partitioning the matrix of squared residuals. They could alternatively be built in a bottom-up fashion by merging vertices agglomeratively. A baseline would be merging vertices one-by-one greedily by picking the pair corresponding to the smallest off-diagonal entry in the residual matrix. We refer to this as OBYO which is similar to the bottom-up method in (Griffin and Perona, 2008). Note that trees learned by this method have no reason to be balanced.

Hungarian algorithm: An attractive alternative is to consider it as an optimal assignment problem and use the Hungarian algorithm (Frank, 2004) to pair nodes . The algorithm optimally assigns nodes in polynomial time and every vertex is paired with another. However, the compulsory pairing of nodes causes unwanted merges among them. The residual matrix is modified to avoid such unwanted merges by adding dummy nodes which is classically done in assignment problems:

Qv =[Q v + ⌘I Kv γ1 Kv⇥φKv ] , (4.11)
where ⌘ is a large constant added to the diagonal to avoid self-assignments, φ is the fraction of real vertices added as dummy vertices and γ is the weights on the edges between real and dummy vertices. The optimization problem for this method, which we refer to as HUNG,i s defined as

minimize Bv tr B > v Qv (4.12) subject to B v 1 (1+φ)Kv =1 Kv ,B > v 1 Kv  1 (1+φ)Kv , where B v 2{0, 1} Kv⇥(1+φ)Kv .

Node-specific classifiers

Once we build a tree T = {V, E, Z} using any of the above methods, we need to learn node-specific classifiers. Each of these classifiers is a probabilistic multinomial classifier with independent parameterization. Thus, we are faced with a learning problem in a tree-structured directed graphical model with independent parameterizations and fully observed data. Regularized maximum likelihood thus decouples and we can learn each classifier independently. At test time, we can simply take the product of the individual output probabilities to obtain the joint probabilities (Bishop, 2006).

We consider `2-regularized linear classifiers, and one important practical issue is the selection of hyper-parameters, i.e., the regularization parameter at each node. We have experimented with different policies in order to choose them at different nodes of the tree:

1. using a single value at all nodes, referred as single below, 2. picking the regularization parameter independently for each node referred as indep below,

3. using a hierarchical Gamma prior on them, referred as gamma below.

Regularization parameters in the first two cases are chosen by cross-validation over a list of candidate values. In the case of Gamma prior, if λ v denotes the parameters for node v and L v (w v ),t h en e g a t i v el o g -l i k e l i h oodo ft h el i n e a rc l a s s i fi e rr e p r e s e n t e db yw v at node v, then we assume that λ v is sampled from the gamma distribution P(λ)= β ↵ Γ(α) λ α-1 e -βλ , with ↵ controlling the shape and β the rate of decay (these parameters are common to all nodes). The global penalized log conditional-likelihood is given by (up to constants)

L(w, λ)= X v L v (w v )+λ v kw v k 2 -↵ log β -(↵ -1) log λ v + βλ v .
L(w, λ) is then optimized by alternating between w and λ (Do et al., 2007). This amounts to alternating between regular independent multinomial regression and the update λ v = α-1 β+kwvk 2 . Cross-validation is done over a grid of values for ↵>1 and β>0. This prepares the necessary hierarchy along with the classifier training at each of its nodes.

Evaluation of taxonomy methods

Detailed experiments are run on a smaller synthetic dataset while only efficient methods are tried on larger real datasets to verify their use in practice. PO50 and WS50 are synthetic datasets with 50 classes of 200 dimensional features with about 200 samples per class. There is partial overlap among samples from different classes in PO50 while classes are well separated in the WS50 dataset. Specific details on how the synthetic data were generated are provided in the Appendix B.

We measure efficiency of a tree by the average numb er of dot pro ducts required on a test dataset. Predictive performance is evaluated in terms of prediction accuracy and negative log-likelihood. The ranking of methods varies with the measure used for performance. The best performing method when considering accuracy might not be as good with logloss. Performance plots show accuracy and loglikelihood of models trained with varying tree depths and also the number of dot-product operations required on average on the test dataset.

Ad e p t ho f1 indicates tree after one split or merge operation. More merge operations are performed in OBYO at each level since a single merge in this method does have the same effect on the tree depth as with the other methods. Flat always has a depth of zero and is plotted with a horizontal line for ease of comparison.

We compare top-down approaches (DIFF and SPEC), bottom-up approaches (HUNG and OBYO)a n dr a n d o mt r e eb u i l d i n gRAND,a sw e l la st h em e t h o dCONF proposed by Griffin and Perona (2008)a n dBengio et al. (2010). CONF runs a surrogate classifier and makes a confusion matrix from its predictions on a validation dataset. This confusion matrix is then symmetrized by taking the average with its transpose and used as a measure of the proximity of classes. This is followed by a standard spectral method to cluster classes. Confusion matrix often has zeros when classes are well separated. We observed that this turns out to be detrimental to spectral methods that compute the eigenvectors of this matrix. In cases where the eigenvector cannot be stably estimated, we use a random split of the classes. As expected RAND performs worse in terms of accuracy and negative log-likelihood on the test. When all classes are well separated, the classification problem is relatively easy. All principled tree building heuristics are able to group similar classes together, eventually leading to performances very close to the flat multi-class classifier.

When there is some overlap, it is more challenging to identify similar classes. The problem becomes more troublesome when the tree is deeper, as the subset of classes are more alike. Despite the overlap, all methods (apart from RAND)s h o wp e r f o r m a n c e sc l o s e to the flat multi-class classifier, with a slight advantage for bottom-up approaches.

It is interesting to note that on both synthetic examples, the method of Bengio et al. arated. This is because the confusion matrix has too many zeros and almost always a random split is performed to resolve for a clustering. Evidently, in such cases a confusion matrix is not an appropriate measure of proximity of classes. Also, a random grouping should certainly be avoided to organize hierarchies.

Effect of various regularization strategies discussed in the paper are examined in Figure 4.4. The simplest strategy of a single regularization parameter for all nodes worked as well as the other more expensive methods. This single parameter was chosen by crossvalidation.

We investigate the performance of different tree building techniques on the following datasets:

1. CIFAR: 100 classes of images in a 384 dimensional space. There are 1000 samples per class which are equally split into for train, cross-validation and test. SPEC performs best among the tree-based methods all of which usually perform better than RAND.However, in this case the flat multi-class classifier has a considerable advantage over the approximate methods by accuracy measure. The log-loss plot also reveals a similar trend where SPEC outperforms other methods. Strangely, in the log-loss plot , after some initial degradation performance improves slightly with deeper trees. This happens because the most loss performance from simple flat multi-class of happens at the lowest level in the tree that involves the multi-class classifier of that lead node. So, it mostly depends on the grouping at the lowest level of the tree which were not very suitable clusterings for a flat multiclass. With larger trees, the clusters got smaller with classifiers being more confident of the correct label improving the log-loss. This, however, does not apply to accuracy as can be seen in the plot because once a sample is misclassified along its true path in the tree it has no recovery from misclassification by this measure. Hence, it might not always be true that smaller trees are closer to flat multi-class than deeper ones. Contrastingly, plots from Figure 4.6 showing results on the Vehicle dataset has a different trend. Performance of all top-down methods degrades including SPEC that performed very well on the CIFAR dataset. Accuracy of bottom-up approaches improves over that of the flat classifier. Logloss values of all methods except for that of SPEC are slightly better than that of the flat classifier.

Finally, we consider a bigram language model dataset (AP-news) where we use a CCAbased dimensionality reduction (Dhillon et al., 2011)t or e d u c et h ei n p u td i m e n s i o nt o 100. We then apply different tree construction methods to the task of predicting a word given the feature representation of the preceding word, a multi-category problem with 2114 classes. These results are reported in Figure 4.7.I nt h i sc a s ew eu s em e d i a no fl o g -l o s sa s opposed to average since there were few words that had a very high log-probability leading to a considerably biased depiction of the methods. And also the backward jump in diffrac on second plot. On this dataset, we obtain both improved prediction performance, i.e., improved accuracy and median log-loss and improved prediction efficiency. In this case the bottom-up methods degrade significantly after about depth 7 while the top-down methods continue to perform very well.

Overall, we can conclude from these results that the tree-based methods can improve the performance in some applications when the hierarchy suits the data distribution, but in general the performances are close to optimal at a much smaller computational cost. However, there are two major concerns that remain to be addressed.

1. Af u n d a m e n t a lq u e s t i o ni st ou n d e r s t a n dt h ee x p r e s s i v epo w e ro ft r e er e p r e s e n t a t i o n of classification or regression or rather, what distributions can be approximated by tree representations?

2. The best performing tree-based methods varied from one dataset to another. It is not straightforward to determine which method to use for a given dataset for which it is necessary to understand what tree structures are generated by each of these methods?

The above two questions remain to be addressed to make this framework useful in practice. Given a dataset, one can then determine if a tree representation is appropriate and choose a suitable method to build the hierarchy.

An additional concern in dealing with large structured feature spaces like the long and sparse contextual features of language modeling is suitability of regularization. Our regularization scheme must reflect the effect of word groupings on the feature space to maintain predictive performance. This needs to be studied to integrate the language model from the previous chapter with the hierarchical framework presented here.

Conclusion

We presented a simple framework to learn hierarchical structure within the classes from their samples. This framework involves using a square loss function to rewrite the interclass residuals in a matrix and using this matrix to group classes appropriately. This could be used with numerous strategies to organize the classes into a hierarchical structure. We follow two kinds of approaches; top-down approach of building the tree from root to leaves and bottom-up approach where classes put in leaves are combined to make meta-classes. Each tree built from the data is an approximation of the conditional-likelihood P (y | x) resulting in reduced-classifier complexity for a variety of tasks. The top-down approach involves finding an appropriate partition of the classes repeatedly until the required depth is reached. This reduces to a max-cut problem that is NP-hard of which we consider two different relaxations. In the bottom-up approach, it involves grouping classes agglomeratively to generate the hierarchy. The two approaches generate different kinds of tree structures that have different properties. We study their performance empirically on different kinds of data.

Chapter 5

Concluding remarks

We conclude the work with a summary and some remarks on certain shortcomings that need to be addressed. We also point to directions worthy of investigation to design more useful models building upon the material presented here to gain a clearer understanding of the methods.

Conclusion and discussion

. In this work we address two crucial aspects pertaining to the use of discriminative language models. Maximum entropy and perceptron based discriminative models have only used unstructured penalties in their objective functions. They were agnostic to the structure within the model that led to overfitting at longer context lengths affecting generalization performance. This restricted these models to short context lengths. Our first contribution studies the usefulness of structured penalties to correct for varying levels of sparsity in different contextual features. We observe that overfitting happens due to structural differences in sampling for various features, the solution of which lies in utilizing the same structure to vary the amount of regularization appropriately.

We achieve this using a log-linear mo del built on suffix tries and using the tree structure to design a suitable penalty. We study performance and complexity with different treestructured penalties. We further show that in specific cases one could use the suffixtree structure instead of the suffix-trie structure. This work further adds to the evidence drawn from other fields that structured feature spaces benefit from structure incorporating penalties.

Our second contribution proposes different methods to build taxonomy of classes using as q u a r e -l o s st om e a s u r ec l a s sp r o x i m i t yi nf e a t u r es p a c e . N u m e r o u sa l g o r i t h m sl e a d i n g to both top-down and bottom-up procedures for growing the tree were studied. Empirical results from these experiments show that building an appropriate tree is important to minimize any loss of performance by switching from flat to tree based classification. Furthermore, in some cases there could b e improvements of p erformance from a well built tree that matches the actual distribution of classes in the feature space. The experiments in Chapter 4 indicate that a top-down approach to build a taxonomy is more suitable for words than bottom-up approaches. The applicability of hierarchical organization of words goes beyond computational gains to tackle problems like out-of-vocabulary words by using other words from the most suitable cluster. Some additional work is required before using the taxonomy algorithms proposed here to build a hierarchical language model. It must Further study of taxonomy learning. In Chapter 4 we proposed different algorithms to hierarchically organize classes. There are two important features these algorithms lack that are desirable for various applications; 1. Some classes might appear at multiple leaves in the tree. For language modeling, these would be polysemous words that have different meanings, and each leaf it appears at would be one concept indicated by that word. The word bank is one such example that could either mean a river bank or a financial bank and this problem has been studied extensively in the literature as word sense disambiguation and discovery (see, e.g., Linden, 2005;[START_REF] Navigli | Word sense disambiguation: A survey[END_REF]. This replication of classes at multiple leaves was reported to be beneficial by Mnih and Hinton (2008)a n dw a su s e db yDeng et al.

(2011) for images with multiple objects but with pre-defined number of clusters at each level of the hierarchy. One could accommodate this within the clustering framework by allowing a class to belong to multiple clusters that the presented framework does not address. Also, it would be interesting to study how one could incorporate information from existing word sense discovery algorithms to improve their hierarchical organization.

2. The space of possible tree structures for a given set of categories is combinatorially large. In some cases, an ontology available from a related task could be used in choosing a suitable tree structure from this large set of choices. For example, Rabani et al. Additional study is required to address the above issues for more suitable tree structures. Apart from improving proposed algorithms, their relation to other methods developed in the literature also needs to be understood. It would be useful to study how various methods behave in different scenarios. Empirical results suggest that different algorithms tend to perform better with different kinds of class distributions. However, it is unclear what algorithms are suitable for which kinds of distributions. This is necessary to know which algorithm to use given the prior class distribution. The other way round, if we could measure the fitness of a tree to data, it could throw light on what the class distribution of data looks like.

The other issue is that of how many samples do we need to reliably recover the underlying hierarchy, in what cases can it be recovered exactly and how well the corresponding hierarchical classifier performs in comparison to flat classifiers. Some of these questions have been addressed in phylogenetics where certain sample bounds and complexity results on the recovery of hierarchy were derived (Roch, 2007). In discrete choice models distributions that can be recovered under specific assumptions on noise in samples were studied (Ben-Akiva and [START_REF] Ben-Akiva | Discrete Choice Analysis: Theory and Application to Travel Demand[END_REF]. Recently, Babbar et al. ( 2013)d e r i v e dab o u n d on the generalization error of hierarchical classifiers that reveals a trade-off between hierarchical and flat classifiers. A more complete study could explain the relation between classes of trees and the various distributions they generate to develop algorithms that return taxonomies with theoretical guarantees.

2. Good-Turing. The method proposed by Good (1953[START_REF] Good | Turing's anticipation of empirical bayes in connection with the cryptanalysis of the naval enigma[END_REF]u s e sc o u n to fc o u n t s( C k , the number of distinct sequences with frequency k)tomakeanestimateofthepossible amount of unseen data and decide the correction factor. It reallocates the mass of sequences in the C k+1 list that occur (k +1) times to sequences with frequency k (the list of C k sequences):

P GT ( y|x m ,c (x m y)=k )= c ⇤ k C , (A.3)
where c ⇤ k =(k +1)

E [C k+1 ] E [C k ] and C = m X k=1 c ⇤ k E [C k ] , (A.4)
where E [C k ] is the expectation of the quantity C k . The simplest is to use the maximum likelihood estimate of frequency estimates from C, E [C k ]=C k (C). This simply reassigns the probability of unigrams to unseen contexts avoiding the case zero probabilities. However, a caveat of this method is that the values C k (C) could be zeros, particularly for larger values of k. This requires some modification to appropriately estimate the expectation, the simplest being to use the unmodified counts.

A.1.2 Avo i d ove r fi t t i n g u s i n g l owe r o r d e r d i s t r i b u t i o n s .

Given that contexts of a given length m are not found the most reasonable way to make an estimate is to look for orders lower than m. There are two ways this idea is introduced into the literature, one of which simply reduces order by one at a time until the sequence is found or it backs off until unigram and this method is called the Katz back-off smoothing. The other method extends this to a case where probabilities of higher order distributions are interpolated with lower order to make the final estimate. This method is called Jelenick-Mercer interpolated models. Jelinek-Mercer has then been improved to better performing methods by appropriately modifying the lower order distributions in the interpolation, namely, Witten-Bell, Absolute Discounting and Kneser-Ney that we describe below. 2. Jelinek-Mercer interpolated smoothing. Jelinek and Mercer (1980)proposedamethod that interpolates higher order prediction probabilities with that of the lower orders. While avoiding the zero probabilities for unseen sequences, it additionally offers a flexibility in controlling bias by parameters 0 <γ (x m ) < 1 that determines the mixing proportions. The simplest version linearly interpolates the ML estimates of the highest order with its immediate predecessor following:

P JM (y|x m )=γ(x m )P ML (y|x m )+(1-γ(x m ))P ML (y|x m-1 ).

An improved version uses a recursive formulation that interpolates probabilities from highest order down to unigram:

P JM (y|x m )=γ(x m )P ML (y|x m )+(1-γ(x m ))P JM (y|x m-1 ).

In both the above versions, a uniform distribution is used for unigrams:

P(y)= 1 |V | .
Parameters γ(x m ) are learned by optimizing predictive performance on validation data. If a single validation dataset is used to estimate the parameters it is called held-out interpolation. If distinct subsets of the training and validation are drawn from the corpus multiple times with replacement to make different estimates of the parameters that are averaged, it is called deleted interpolation. But since there are too many γ values to tune, some of them grouped together into a single bucket and constrained to take the same value. Note that the • above maps to unit length sequences |z| =1. The weighting scheme for Witten-Bell takes the following form:

1 -γ(x m-1 )= C 1+ (x m •) C 1+ (x m •)+c(x m-1 )
.

This weighting scheme leads to Witten-Bell probability distribution of the form:

P WB (y|x m )=γ(x m )P ML (y|x m )+(1-γ(x m ))P WB (y|x m ). Discount parameter δ is tuned using held-out data. Appropriate value of 1γ that comes from the probability constraint is,

1 -γ(x m )= δC 1+ (x m •) c(x m ) ,
where C 1+ (x m •) is count of distinct sequences following x m as defined above.

5. Kneser-Ney smoothing. The method proposed by Kneser and Ney (1995)extendsAbsolute Discounting and is the best performing smoothing technique. It improves the back-off weighting of Absolute Discounting in a very intuitive and effective manner. Lower order distributions, which are significant only when higher order contributions are small, are optimized to perform very well for these cases. This is achieved by modifying the lower order distribution P KN (x m-1 ) that scales proportional to the number of single word contexts in which it occurs. Similar to the unique succeeding contexts above, we define the number of distinct words preceding a context x m as,

C 1+ (•x m )=|{z | c(zx m ) ≥ 1}|
and the unique pair of words that sandwich the sequence x m-1 in the middle, This model is more specifically called the interpolated Kneser-Ney and there is a backoff version of Kneser-Ney that skips the interpolation term (second term of the second part of the equation above) by setting the corresponding δ to zero. The parameter δ is either chosen by held-out data or set using some heuristics. There is a variant of this where δ is set to different values depending on the length of the sequence |x m y| it is applied on which is called the modified interpolated Kneser-Ney.

It is important to note that while models have been developed separately in the literature as back-off and interpolated, a model of one kind can be rewritten appropriately in the other format (Chen and Goodman, 1998).

A.2 Iterative scaling methods

We derive the surrogate functions for the error defined in (1.10)a n dt h er e s u l t i n gu p d a t e equations for different iterative scaling methods described in Section 1.2.2. The update equations involved in minimizing L come from finding a possible ∆! that minimizes the error in (1.10) which, we recall, is:

err = L(! +∆!) -L(!).
It measures the difference in L at two distinct points in the domain that are separated by ∆!.A r r i v i n ga ta p p r o p r i a t eu p d a t ee q u a t i o n sc o m e sf r o mt h ed e c o u p l i n go f! i . This is achieved by using an appropriate surrogate function that upper bounds err. The steps below briefly derive iterative scaling algorithm for the minimization of err.

Upon expansion err takes the following form: Three different iterative scaling algorithms were developed in the literature; the generalized iterative scaling (GIS) proposed by Darroch and Ratcliff (1972), the improved iterative scaling (IIS) due to Della Pietra and Della Pietra (1993)a n dt h es e q u e n t i a lc o n d i t i o n a l generalized iterative scaling (SCIS) by Goodman (2002). They follow from the three different surrogate functions that we will derive below. We will make use of the following definitions:

I # (x m v)= X i I(x m v, i), I # =max C I # (x m v) I M (i) = max C I(x m v, i)
A.2.1 Generalized Iterative Scaling.

We will derive an upper bound of T e that splits across the features i using Jensen's inequality. An additional (d +1) th feature I # -I # (x m v) with a weight value ∆! d+1 =0 . This makes the inner fractions involving indicator functions a proper probability mass where

  Considérons le modèle d'ordre m pour des séquences d'ordre |s| = m +1.L em o d è l e simple considère les fréquences d'apparition empiriques P ML (y|x m )= c(x m y) c(x m ) ,

  On obtient alors la probabilité L(C; !) du corpus : L(C; !)=P ME (C; !)= Y {xmy}2C P ME (y|x m ; !)= X {xmy}2C e P s2S ! i I(xmy,s) Z(x m ; !) .

3. 1

 1 Diagrams of suffix trie and tree for X=coacac. ............... 3.2 Diagrams of suffix trees on X=coacac.S u b fi g u r e(a) shows the complete suffix tree with 18 different contexts & i .S u ffi xt r e e si ns u b fi g u r e(b) are built for each symbol separately with contexts preceding the specific symbols. & 9 is example of a context that appears in multiple suffix trees and requires to be identified to make M y (X).S u b fi g u r e(c) only collapses constant value non-branching paths of suffix trees in (b). The node corresponding to & 9 is split to make M a (X).A l lc o n t e x t si nan o d ea r er e p r e s e n t e db yas i n g l e parameter. ................................... 3.3 Diagrams showing parameter matrices W with different tree structures of Fig. 3.2 for its column vectors. Free variables are shown in grey with the corresponding contexts they represent from Fig. 3.2.S u b fi g u r e(a) shows W with S(X) shaped column vectors (from Fig. 3.2(a)). Each column has as many parameters as there are contexts making it 54 parameters. Subfigure (b) shows columns w y of W with S y (X) shape (from Fig. 3.2(b)). Each vector only has parameters for relevant contexts making it 17 parameters. No parameters are learned for unobserved suffixes unlike in (a).S u b fi g u r e(c) with columns from M y (X) has 10 parameters with only one parameter per node. ...................................... 3.4 Number of parameters for tree and trie structured vectors plotted for increasing orders of the language model.

  ) where c(s) is the number of times s was observed in C.T a k i n gt h ep r o d u c to ft h ep r o b abilities for predicting each of the words in a sequence s,w eg e tt h ej o i n tp r o b a b i l i t y ,

  Regularization by penalization. Smoothing by adding a regularization term (also called penalty) to the maximum likelihood formulation was considered as a simpler and efficient alternative to modifying the constraint set. Various regularizers have been tried in the context of maximum entropy models and a survey by Chen and Rosenfeld (2000)r e p o r t e dt h a tt h e yp e r f o r mb e t t e rt h a nm o d e l ss m o o t h e db yc o nstraint modifications.

Figure 1 . 1 :

 11 Figure 1.1: Hierarchical Bayesian models for language.

Figure 1 . 2 :

 12 Figure 1.2: Network architecture of the neural probabilistic language model and the corresponding notation.

Figure 1 . 3 :

 13 Figure 1.3: Network architecture of recurrent neural network language model and the corresponding notation.

2 .

 2 The idea of grouping together words into clusters to make training and prediction time efficient has been used with different models (see(Goodman, 2001)formaximum entropy models, (Morin and Bengio, 2005)forfeed-forw ardnet w orks,(Mikolov et al., 2011)f o rr e c u r r e n tn e t w o r k sa n d( Mnih and Hinton, 2008)f o rl o g -b i l i n e a rm o d e l s ) .

wg 8 =

 8 [ 34665777 ] w g 7 =[ 4665777 ] wg 5 = [7] ,w g 6 = [7 7] wg 3 = [6 5 7] ,w g 4 =[ 6657 ] w g 1 = [5] ,w g 2 = [7]

Figure 2 . 1 :

 21 Figure 2.1: An eight-dimensional vector with a tree structure and the corresponding groupings w g i corresponding to subtree g i with root r i . The numbers 3, 4, 5, 6, 7 shown are examples of values those components of w can take.

Definition 4 .

 4 Define groups with overlaps G L = {g i } |G O | i=1 such that g i ⇢ I = {1, ••• , |w|} and S g2G L g = I.F o re a c hg r o u pg 2 G L ,d e fi n eav e c t o rv g 2 R |w| such that supp(v g ) ⇢ g and w =

  et al.(2011);Koltchinskii and Yuan (2008);[START_REF] Huang | The benefit of group sparsity[END_REF]. Sparsity (both structured and unstructured) has also been considered in the Bayesian framework byWipf and Rao (2005, 2007); Argyriou et al. (2008); Ji et al. (2009)a n dHe and Carin (2009).Application of structured penalties. Structured penalties have found application in numerous problems like dimensionality reduction (sparse PCA[START_REF] Zhang | Sparse pca: Convex relaxations, algorithms and applications[END_REF][START_REF] Zhang | Sparse pca: Convex relaxations, algorithms and applications[END_REF], CCA(Witten et al., 2009), matrix factorization(Bach et al., 2008)), dictionary learning (sparse decompositions(Olshausen and Field, 1997; Elad and Aharon, 2006; Lee et al., 2007), with online learning (Mairal et al., 2009a), simultaneous sparse approximation (Mairal et al., 2009b; Tropp et al., 2006a,b)), multi-task learning (joint variable selection with group lasso (Obozinski et al., 2009b), joint feature selection with trace-norm (Argyriou et al., 2007), with fewer observations than tasks Obozinski et al. (2008); Lounici et al. (2009), shared dictionary learning with `1-norm (Mairal et al., 2009c); learning shared structures in multi-class classification with trace-norm (Amit et al., 2007; Harchaoui et al., 2012)), computer vision (image denoising (Elad and Aharon, 2006; Mairal et al., 2009b), image classification with learned code books (Boureau et al., 2010; Yang et al., 2009, 2010; Mairal et al., 2008; Leordeanu et al., 2007)in v ersehalf-toning(Mairal et al., 2012), digital zooming (Couzinie-Devy et al., 2011)), speech processing (source separation Benaroya et al. (2006)), neuroimaging (resting state activity (Varo quaux et al., 2010), M/EEG source localization (Gramfort et al., 2012), multi-scale mining fMRI (Jenatton et al., 2012a)), language processing (chunking, entity recognition, and dependency parsing (Martins et al., 2011)), sociolinguistics (Eisenstein et al., 2011)), bioinformatics (Rapaport et al., 2008; Kim and Xing, 2012), semi-supervised learning (Raina et al., 2007), structure learning (Lee et al., 2007), graphical model selection with `1-norm (Ravikumar et al., 2010)a n dt i m e -s e r i e s prediction

Algorithm 2

 2 Generic proximal minimization algorithm (see Parikh and Boyd, 2013) w ⇤ := argmin w {L(w, S n )+λΩ(w)} 1 Input: λ regularization parameter , L Lipschitz constant of rf , µ coefficient of strong-convexity of f + λΩ, X design matrix, Y label set 2

  ; Beck and Teboulle (2009); Parikh and Boyd (2013)forpro ximalminimizationandBach et al. (2012)foroptimization with sparsity inducing penalties).

Algorithm 3 1+4⌧ 2 2 Algorithm 4

 324 Batch proximal minimization following Beck and Teboulle (2009) w ⇤ := argmin w {L(w, S n )+λΩ(w)} 1 Initialize: w = Z =0, ⌧ = δ =1 2 repeat until termination 3 w := δ+⌧ -1 δ w -⌧ -1 δ Z; Z := w 4a repeat: w = GeneralizedGradient(S n , w, λ, 1/L)# full batch update 4b if L(w) < L(w)+rL(ww)+0.5L||w -w|| 2 2 break else L: =⌘L 5 ⌧ = δ; δ =1+ 1+ p Stochastic proximal minimization following Hu et al. (2009) w ⇤ := argmin w {L(w, S n )+λΩ(w)} 1 Initialize:

  Friedman et al. (2007)(seealso Mairal, 2010; Liu et al., 2010).

Definition 6 .

 6 ||qλ is projection on the dual norm ball of λ units size. Let G = {g i } |G| i=1 denote the ordered tree structured grouping of indices I = {1, ••• , |w|} of a vector w with tree structure T such that • S g2G g = I (grouping as in Definition 3) • for r, s 2 I, r<s, G r \G s = ; or G r ⇢G s .( d e fi n e s o r d e r i n g o n g r o u p s )

  )where I(•) is the indicator function. For example, for x = oacac and x 2 = ac,w eh a v e Suffix trie S(X).

  Suffix tree T (X).

Figure 3 . 1 :

 31 Figure 3.1: Diagrams of suffix trie and tree for X=coacac.

  3(a),e a c hc o l u m no fW contains the weight vector w v associated with symbol v 2 V and |S(X)| =1 3 . The dimension of the weight vectors is bounded by the length of the training sequence. Hence, like the sequence memoizer (Wo o d et al., 2010), the model can be used as an infinite length language model, though in practice it makes sense to restrict dependency to the sentence length (or the document length).

2 .

 2 The trie structured vectors set values of non-occuring suffixes to zeros (see Figure 3.3(b)). However, a gradient with the multinomial loss for optimization in (3.2) requires us to update these variables ruling out possibility of trie structured vectors {S v (X)} v2V .

  Complete suffix tree T (X) corresponding to trie S(X).

9 ( b )

 9b Trees Ty(X) for different symbols for tries Sy(X).

5 (

 5 c) Trees My(X) with only constant value non-branching paths collapsed.

Figure 3 . 2 :

 32 Figure 3.2: Diagrams of suffix trees on X=coacac.S u b fi g u r e(a) shows the complete suffix tree with 18 different contexts & i . Suffix trees in subfigure(b) are built for each symbol separately with contexts preceding the specific symbols. & 9 is example of a context that appears in multiple suffix trees and requires to be identified to make M y (X).S u b fi g u r e(c) only collapses constant value non-branching paths of suffix trees in(b). The node corresponding to & 9 is split to make M a (X). All contexts in a node are represented by a single parameter.

w a w c w o & 1 -

 1 18 & 1-18 & 1-18 (a) W with S(X) shaped columns.

  c) W with My(X) shaped columns.

Figure 3 . 3 :

 33 Figure 3.3: Diagrams showing parameter matrices W with different tree structures of Fig. 3.2 for its column vectors. Free variables are shown in grey with the corresponding contexts they represent from Fig. 3.2.S u b fi g u r e(a) shows W with S(X) shaped column vectors (from Fig. 3.2(a)). Each column has as many parameters as there are contexts making it 54 parameters. Subfigure(b) shows columns w y of W with S y (X) shape (from Fig.3.2(b)). Each vector only has parameters for relevant contexts making it 17 parameters. No parameters are learned for unobserved suffixes unlike in (a).S u b fi g u r e(c) with columns from M y (X) has 10 parameters with only one parameter per node.

Figure 3 . 4 :

 34 Figure 3.4: Number of parameters for tree and trie structured vectors plotted for increasing orders of the language model. Tree structured vectors have fewer parameters to learn and lead to more compact models.

1 Figure 3 . 5 :

 135 Figure 3.5: Comparison of average perplexity values for unweighted models involving unstructured penalties learned for 2-gram through 12-gram.

Figure 3 . 6 :

 36 Figure 3.6: Comparison of average perplexity values from models with structured penalties for 2-gram through 12-gram.

Figure 3 . 7 :

 37 Figure 3.7: Average perplexity values for different penalized models with feature weighting following an exponential decay.

Figure 3 . 8 :

 38 Figure 3.8: Average log-loss is plotted against words grouped by maximal context length used in predicting them at test time. The green dashed line shows the number of words encountered with that m max value plotted on the axis to the right.

  Log-loss of different words on the test set.

Figure 3 . 9 :

 39 Figure 3.9: Average log-loss for different words plotted against that of Kneser-Ney (KN). Each dot in the plot is a word. Points are color coded to indicate their frequency with blue being least frequent. Points above the level set y=x are better predicted by KN.

  wℓ T 2 ) at test (c) w`T 2 penalty.

  w`T 1 penalty.

Figure 3 .

 3 Figure 3.10: Plots showing logloss difference of tree-based methods and Kneser-Ney for different words grouped by their frequency at train. The larger circles show the mean value. Points lying above the constant zero line correspond to words for which Kneser-Ney was outperformed.

Figure 3 .

 3 Figure 3.11: An eight-dimensional trie shaped vector in subfigure (a) and the corresponding tree in (b). Values in the vector after Prox 0.8`T 2 are shown in (c) and that after Prox 0.8`T 1 in (d).

g 2 ` 1

 21 (z).F r o mt h ec o n d i t i o nf o rp r o j e c t i o no n`1-ball in (3.7) we have the following:

  Time comparison of Prox `T ∞ with random pivoting on suffix-tree against suffix-trie .

  Time comparison of random pivoting against heap-based pivoting on suffix-tree.

Figure 3 .

 3 Figure 3.12: Comparison of time taken for Prox `T 1 projection under various settings.

  . The time required to access the top k entries of a Fibonacci heap containing d entries is O(k log d). This new pivoting method improves the time complexity of Prox `T 1 to O(k|M (X)| log |M (X)|). The details of the heap-based Prox `T 1 procedure are summarized in Algorithm 8.

  and Dy (2004)a n dTibshirani and Hastie (2007)g e n e r a l i z et h i s idea to more generic cases. More recent works in this line are that of Griffin and Perona (2008),Weston et al. (2010)a n dGao and Koller (2011). Griffin and Perona (2008)a n dWeston et al. (2010) use a surrogate classifier to build a confusion matrix that is used with spectral clustering methods to build the tree in a top-down manner. Griffin and Perona (2008)a l s op r o p o s e simply merging two most confusing categories at each step by looking for the largest entry in the confusion matrix. Alternatively, Gao and Koller (2011)u s eam a x -m a r g i na p p r o a c h extending the idea of Tibshirani and Hastie (2007)t oap r i n c i p l e do p t i m i z a t i o np r o b l e m . However, their formulation is non-convex and sensitive to initialization. Bart et al. (2011) consider the same in a Bayesian framework using nested Chinese restaurant process and study the usefulness of taxonomic structures of image collections for human browsing and navigation. Particularly for modeling language, it was tried by Goodman (2001), Mikolov et al. (2011)a n dMnih and Hinton (2008).

4 Figure 4 . 1 :

 441 Figure 4.1: Binary classification tree. Leaf nodes are shown in blue and the rest in brown. The path to the leaf y is marked by vertices P(y)={v 1 ,v 2 ,v 3 ,v 4 ,v y } and edges {e y 1 ,e y 2 ,e y 3 ,e y 4 }. The edges {ē y 1 , ēy 2 , ēy 3 , ēy 4 } are the alternative branches on the path.

  Efficient computation of residual matrix. The computation of Q (or any Q v )c a nb e expensive as it requires the inversion of d ⇥ d matrix, which is O(d 3 ).D e p e n d i n go nt h e number of data points n and the number of features d,w ec a nc o m p u t et h er e s i d u a l sm o r e efficiently as follows:

Figure 4 . 2 :

 42 Figure 4.2: Residual matrix estimation in split and merge operations.

Figure 4 .

 4 Figure 4.3 shows the performance efficiency trade-off for all methods on synthetic dataset.As expected RAND performs worse in terms of accuracy and negative log-likelihood on the test. When all classes are well separated, the classification problem is relatively easy. All principled tree building heuristics are able to group similar classes together, eventually leading to performances very close to the flat multi-class classifier.When there is some overlap, it is more challenging to identify similar classes. The problem becomes more troublesome when the tree is deeper, as the subset of classes are more alike. Despite the overlap, all methods (apart from RAND)s h o wp e r f o r m a n c e sc l o s e to the flat multi-class classifier, with a slight advantage for bottom-up approaches.It is interesting to note that on both synthetic examples, the method of Bengio et al. (2010) performs similar to the random tree-based classifier when the classes are well sep-

  Figure 4.3 shows the performance efficiency trade-off for all methods on synthetic dataset.As expected RAND performs worse in terms of accuracy and negative log-likelihood on the test. When all classes are well separated, the classification problem is relatively easy. All principled tree building heuristics are able to group similar classes together, eventually leading to performances very close to the flat multi-class classifier.When there is some overlap, it is more challenging to identify similar classes. The problem becomes more troublesome when the tree is deeper, as the subset of classes are more alike. Despite the overlap, all methods (apart from RAND)s h o wp e r f o r m a n c e sc l o s e to the flat multi-class classifier, with a slight advantage for bottom-up approaches.It is interesting to note that on both synthetic examples, the method of Bengio et al. (2010) performs similar to the random tree-based classifier when the classes are well sep-

  Classes with partial overlap (PO50).

Figure 4 . 3 :

 43 Figure 4.3: Performance plots for varying tree depth for various methods on WS50 dataset on the left and on PO50 dataset on the right.

2 . 3 .

 23 Vehicle: 263 classes of 262K images. 500 dimensional pro jections of 4096 dimensional Fisher vectors of the images are used. APnews subset: 2114 classes of 100 dimensional features. Each word is a class from the subset of the original APnews corpus. Features were derived by CCA on bigram co-occurances (Dhillon et al., 2011).

Figure 4 .

 4 Figure 4.5 shows the results on the CIFAR image classification dataset. SPEC performs best among the tree-based methods all of which usually perform better than RAND.However, in this case the flat multi-class classifier has a considerable advantage over the approximate methods by accuracy measure. The log-loss plot also reveals a similar trend where SPEC outperforms other methods. Strangely, in the log-loss plot , after some initial degradation performance improves slightly with deeper trees. This happens because the most loss performance from simple flat multi-class of happens at the lowest level in the tree that

  Predictive performance on PO50 data with overlap of categories.

  Predictive performance on WS50 data with separated categories.

Figure 4 . 4 :

 44 Figure 4.4: Performance variation with regularization policy.

  Performance against tree depth.

  Performance against average number of dot-products on test.

Figure 4 . 5 :

 45 Figure 4.5: Performance variation with depth and performance efficiency trade-off on CIFAR dataset.

  Performance against number of dot-products required at test.

Figure 4 . 6 :

 46 Figure 4.6: Performance variation with depth and performance efficiency trade-off on Vehicle dataset.

Figure 4 . 7 :

 47 Figure 4.7: Performance variation with depth and performance efficiency trade-off on subset of AP-news dataset.

  (2008)a n dBabbar et al. (2013)m o d i f ye x i s t i n gt a x o n o m i e st om a k eh i e r a r c h i e sf o r specific tasks. A framework that can exploit side information like existing ontologies is a desirable characteristic that the approaches proposed in Chapter 4 lack.

1 .

 1 Katz back-off smoothing.[START_REF] Katz | Estimation of probabilities from sparse data for the language model component of a speech recognizer[END_REF]p r o p o s e dav a r i a n to ft h eG o o d -T u r i n ge stimator that uses back-off distribution to redistribute the subtracted mass among unobserved sequences using the following rule:P KZ (y|x m )= 8 < : P(y|x m ) c(x m )=k>⌧, ⌘(x m )P KZ (y|x m-1 ) otherwise,where P(y|x m ) is any estimator. Katz (1987)chooseGood-T uringestimatordescribed above for P(y|x m ). The parameter ⌧ is used as a threshold for backing off to lower distribution is found not be critical for its performance(Chen and Goodman, 1998).The function ⌘(x m ) is chosen so that the resulting distribution is a valid probability and sums to one,⌘(x m )= β(x m ) P {z|c(xmz)τ } P(y|x m-1 ) | {z } redistributed as per lower-order dist. ,β (x m )=1-X {z|c(xmz)>τ } P(y|x m ) | {z } subtracted mass

3 .

 3 Witten-Bell smoothing. The smoothing model of Witten-Bell was published by(Bell et al., 1990;[START_REF] Witten | The zero-frequency problem: Estimating the probabilities of novel events in adaptive text compression[END_REF]f o rt e x tc o m p r e s s i o na n di sas p e c i a lc a s eo f Jelinek-Mercer interpolation where mixing proportion is chosen cleverly. The weight of the lower order distribution (1γ(x m-1 )) indicates the probability of a word following the sequence x m-1 and is chosen to be proportional to the number of unique words following x m-1 . We define the number of distinct words following the context as, x m-1 as C 1+ (x m •)=|{z | c(x m z) ≥ 1}|.

4 .

 4 Absolute discounting smoothing. The method of Absolute Discounting byNey et al. (1994) is another variant of the Jelinek-Mercer interpolation where a fixed amount of mass (controlled by 0 <δ<1)i ss u b t r a c t e df r o mt h eh i g h e s to r d e rt e r mi n s t e a do f the multiplicative factor γ. The interpolation weight for the lower order distribution, (1γ) is solved for by ensuring that the resulting values sum to one so that its a valid probability. The formula for the distribution is,P AD (y|x m )= max{c(x m )δ, 0} c(x m-1 )+(1-γ(x m ))P AD (y|x m-1 ).

C

  1+ (•x m-1 •)=|{(z 1 ,z 2 ) | c(z 1 x m-1 z 2 ) ≥ 1}|. Note that |z i | =1and C 1+ (••) is the bigram count in C.The formulae for Kneser-Ney smoothing can now be put down as follows:P KN (y|x m )= 8 > > > > > > > > < > > > > > > > > : abs. disc. z }| { max{c(x m y)δ, 0} c(x m-1 ) + back-off term z }| { δC 1+ (x m •) c(x m ) P KN (y|x m-1 ) largest m s.t. c(x m y) > 0, max{C 1+ (•x m-1 y)δ, 0} C 1+ (•x m-1 •) | {z } modified lower order dist. + δC 1+ (x m-1 •) C 1+ (•x m-1 •) P KN (y|x m-1 )

5 ) 4 P

 54 i ω i I(xmv,i)P z2V e P i ω i I(xmz,i) e P i ∆ω i I(xmv,i)The inequality of ln(x) <x-1 is used to bound err from above: ME (v|x m ) e P i ∆ω i I(xmv,i)

Figure C. 1 :

 1 Figure C.1: Performance variation with tree regularization parameter δ in equation (4.8). Three plots on the left are on PO50 dataset and the ones on the right are on WS50. Values of δ vary as 0.001, 1 and 1000 from top to bottom.

Figure C. 2 :

 2 Figure C.2: Effect of residual matrix approximation on top-down methods. Results on dataset PO50 on the left and that on WS50 on the right.

  Modélisation de la langue naturelle ...................... vi 0.2 Méthodes existantes .............................. vii 0.2.1 Méthodes par lissage .......................... vii 0.2.2 Entropie maximale et maximum de vraisemblance .......... ix 0.2.3 Méthodes récentes. ........................... x 0.3 Motivations ................................... Problem of modeling language ......................... 2 1.2 Traditional approaches ............................. 4 1.2.1 Smoothing models ........................... 4 1.2.2 Maximum entropy models ....................... 7 1.2.3 Predictive performance and computational efficiency ........ 1.3 Recent trends .................................. Summary and motivation ............................ 1.5 Contributions and outline ........................... Principle of empirical risk minimization .................... 2.2 Penalized loss and structural risk minimization ................ 2.2.1 Unstructured penalties ......................... 2.2.2 Structured penalties .......................... 2.3 Optimizing penalized loss ........................... 2.4 Proximal minimization algorithms ....................... Introduction to Generalized Linear Models .................. 3.2 Log-linear language model ........................... 3.3 Suffix encoding in tries and trees ....................... 3.3.1 Suffix trie structured vectors ...................... 3.3.2 Word-specific suffix trie structured vectors .............. 3.3.3 Constraining to positive orthant .................... 3.3.4 Word-specific suffix tree-structured vectors .............. 3.3.5 Complexity improvements from trees ................. 3.4 Models with unstructured penalties ...................... 3.4.1 Proximal projection with unstructured penalties ........... 3.4.2 Performance evaluation with unstructured penalties ......... 3.5 Models with structured penalties ....................... Node-specific classifiers ............................. 4.4 Evaluation of taxonomy methods ....................... 4.5 Conclusion .................................... Smoothing models ............................... A.1.1 Redistribute mass to handle unseen sequences. ............ A.1.2 Avoid overfitting using lower order distributions. ........... A.2 Iterative scaling methods ............................

	xviii	CONTENTS
	3L o g -l i n e a r l a n g u a g e m o d e l
	Détail des contributions 3.1 5C o n c l u d i n g r e m a r k s 0.1 2L e a r n i n g w i t h s t r u c t u r e d p e n a l t i e s Appendices	v 21
	AS m o o t h i n ga n dm a x i m u me n t r o p ym o d e l s 2.1 xvii A.1

x 0.4 Contributions et plan de la thèse ....................... xii 0.4.1 Pénalités structurées pour la modélisation du langage ........ xii 0.4.2 Apprentissage de la taxonomie ..................... xiii 0.4.3 Plan de la thèse. ............................ xiv 1I n t r o d u c t i o n 1 1.1 1.3.1 Bayesian models ............................ 1.3.2 Distributed representations ....................... 1.4 2.4.1 Proximal operators for penalties .................... 2.5 Conclusion .................................... 3.5.1 Proximal projection with `T 2 -norm ................... 3.5.2 Proximal projection with `T 1 -norm .................. 3.5.3 Performance evaluation with structured norms ............ 3.5.4 Feature weighting to avoid overfitting ................. 3.5.5 Analysis of perplexity improvements ................. 3.6 Time complexity of proximal operators .................... 3.6.1 Properties of `T 1 -norm. ......................... 3.6.2 Fast proximal projection with `T 1 -norm. ............... 3.7 Conclusion .................................... 4E ffi c i e n t t a x o n o m y l e a r n i n g 4.1 Normalization in multi-class log-linear models ................ 4.2 Tree embedding of classes ........................... 4.2.1 Measuring the class proximity ..................... 4.2.2 Split and merge operations ....................... 4.2.3 Top-down procedure .......................... 4.2.4 Bottom-up procedure .......................... 4.3 A.2.1 Generalized Iterative Scaling. ..................... A.2.2 Improved Iterative Scaling. ....................... A.2.3 Sequential Conditional Generalized Iterative Scaling. ........

  1.1 Hierarchical Bayesian models for language. .................. 1.2 Network architecture of the neural probabilistic language model and the corresponding notation. ............................. 1.3 Network architecture of recurrent neural network language model and the corresponding notation. .

............................ 2.1 An eight-dimensional vector with a tree structure and the corresponding groupings w g i corresponding to subtree g i with root r i . The numbers 3, 4, 5, 6, 7 shown are examples of values those components of w can take. .......

  Tree structured vectors have fewer parameters to learn and lead to more compact models. ........... 3.5 Comparison of average perplexity values for unweighted models involving unstructured penalties learned for 2-gram through 12-gram. ........ Average perplexity values for different penalized models with feature weighting following an exponential decay. ...................... 53 3.8 Average log-loss is plotted against words grouped by maximal context length used in predicting them at test time. The green dashed line shows the number of words encountered with that m max value plotted on the axis to the right. ..................................... 54 3.9 Average log-loss for different words plotted against that of Kneser-Ney (KN). Each dot in the plot is a word. Points are color coded to indicate their frequency with blue being least frequent. Points above the level set y=x are better predicted by KN. ............................ 55 3.10 Plots showing logloss difference of tree-based methods and Kneser-Ney for different words grouped by their frequency at train. The larger circles show the mean value. Points lying above the constant zero line correspond to words for which Kneser-Ney was outperformed. ............... 56 3.11 An eight-dimensional trie shaped vector in subfigure (a) and the correspond-Three plots on the left are on PO50 dataset and the ones on the right are on WS50. Values of δ vary as 0.001, 1 and 1000 from top to bottom. .... 94 C.2 Effect of residual matrix approximation on top-down methods. Results on dataset PO50 on the left and that on WS50 on the right. .......... 95

	1.1 Update equations for three different iterative scaling algorithms; generalized
	iterative scaling (GIS), improved iterative scaling (IIS), sequential condi-
	tional generalized iterative scaling (SCIS) and coordinate descent (CD) (see
	Huang et al.

3.6 Comparison of average perplexity values from models with structured penalties for 2-gram through 12-gram. ....................... xxi 3.7 ing tree in (b).V a l u e si nt h ev e c t o ra f t e rProx 0.8`T 2 are shown in (c) and that after Prox 0.8`T 1 in (d). .......................... 57 3.12 Comparison of time taken for Prox `T 1 projection under various settings. .. 59 4.1 Binary classification tree. Leaf nodes are shown in blue and the rest in brown. The path to the leaf y is marked by vertices P(y)={v 1 ,v 2 ,v 3 ,v 4 ,v y } and edges {e y 1 ,e y 2 ,e y 3 ,e y 4 }. The edges {ē y 1 , ēy 2 , ēy 3 , ēy 4 } are the alternative branches on the path. .................................. 67 4.2 Residual matrix estimation in split and merge operations. ......... 69 4.3 Performance plots for varying tree depth for various methods on WS50 dataset on the left and on PO50 dataset on the right. ............ 74 4.4 Performance variation with regularization policy. ............... 75 4.5 Performance variation with depth and performance efficiency trade-off on CIFAR dataset. ................................. 75 4.6 Performance variation with depth and performance efficiency trade-off on Vehicle dataset. ................................. 76 4.7 Performance variation with depth and performance efficiency trade-off on subset of AP-news dataset. ........................... 76 C.1 Performance variation with tree regularization parameter δ in equation (4.8). , 2010). ............................... 2.1 Definitions of the penalties and their corresponding proximal operators. .. 3.2 Complexity of proximal operators for different penalties in terms of the nodes in the corresponding suffix tree (M ) and the trie (S). ............ 3.3 Table showing the generalization and efficiency achievable using different penalties. .................................... 3.1 Predictions from the test set illustrating behaviour of various 7-gram methods. The word in bold face is predicted using a context of m max words preceding it. Values reported are negative of log-probabilities. The lower the value, the better is its performance. .................... xxiii Chapter 1

Table 1 .

 1 1: Update equations for three different iterative scaling algorithms; generalized iterative scaling (GIS), improved iterative scaling (IIS), sequential conditional generalized iterative scaling (SCIS) and coordinate descent (CD) (seeHuang et al., 2010).

Algorithm 1 Minimization in maximum entropy models (see Huang et al., 2010). A. Parallel update (GIS and IIS) A1 Input: C,! := 0 A2 repeat until termination

  Hierarchical Pitman-Yor language model.Teh (2006)e x t e n d e dt h ew o r ko fGoldwater et al. (2006)toalanguagemodelbyreplacingtheDirichletprocessinthehierarchicalmodel of Mackay and Peto (1994) by a Pitman-Yor process. The distributions are now drawn from a Pitman-Yor process G x ⇠ PY(δ x ,↵ x ,B x ) with discount parameter δ x ,strengthparameter ↵ x and mean distribution B

  [START_REF] Navigli | Word sense disambiguation: A survey[END_REF] Farhadi et al., 2010; Kulkarni et al., 2011; Yang et al., 2011; Mitchell et al., 2012). The first few models that were proposed used template-based construction of sentences from image tags returned by visual classifiers(Kulkarni et al., 2011). Template models are known to be suboptimal when textual variations are necessary(Reiter and Dale, 1997). Template filling has been replaced by models that generate syntactic trees that resulted in varied and well formed text(Mitchell et al., 2012; Yang et al., 2011).

  Matrix penalties. In cases where the hypotheses are matrices, matrix norms are used. The nuclear norm or trace-norm (sum singular values)[START_REF] Fazel | A rank minimization heuristic with application to minimum order system approximation[END_REF]i su s e da sa convex surrogate to the NP-hard rank minimization problem. Such penalties have been applied to numerous problems like multi-class categorization(Crammer and Singer, 2002), multi-task learning(Agarwal et al., 2008), and matrix completion(Srebro et al., 2005).

.H o w e v e r ,n o n -c o n v e x `0 based methods are sometimes preferred and used with approximate greedy algorithms like orthogonal matching pursuit (Tropp and Gilb ert, 2007)andcompressedsensing(Haupt and Nowak, 2006; Baraniuk et al., 2008; Huang et al., 2009)i ns i g n a lp r oc e s s i n g .

Table 3 .

 3 3: Table showing the generalization and efficiency achievable using different penalties.

Table 3 .

 3 1: Predictions from the test set illustrating behaviour of various 7-gram methods. The word in bold face is predicted using a context of m max words preceding it. Values reported are negative of log-probabilities. The lower the value, the better is its performance.

  is active set of nodes that can be merged 3 repeat until required depth 4 find optimal pairing P 2{0, 1} |A|⇥|A| and P = P > 5 for unordered (s, t) 2 A such that P (s, t)=1

	#update tree
	6a 6b 6c 7 #add root variable with active nodes as children V V+ {v} E E+ {e v!s ,e v!t } Z Z+ {z v }, where z v = z s [ z t A A -{s, t} + v
	8a V 8b E 8c Z 9 return T V+ {r} E+ {e r!A i } Z+ {z r }, where z r =[1, ••• ,K] |A| i=1

  .8) where Q v is given by (4.5)a n dX v is centered. Equation (4.8)c a nb er e c o g n i z e da st h e standard maximum cut problem(Cormen et al., 2009)(alsoreferredintheliteratureasthe Chinese postman problem or the route inspection problem (see also Part VII of[START_REF] Schijver | Combinatorial optimization[END_REF]). While maximum cut is non-convex and NP-hard, there exist efficient approximation schemes with guaranteed bounds, such as the classical semidefinite programming relaxation known as the 0.878-approximation algorithm by[START_REF] Goemans | Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming[END_REF].

ROC is receiver operating characteristic, MAP is min-average precision and NDCG stands for normalized discounted cumulative gain

When the trees are balanced and short, the amortized complexity is much lower than quadratic at about O(pD) where D is the depth of the tree(Jenatton et al., 2011b).

(x)=[ 010000000 ] > . The feature vector φ m (x) encodes all suffixes observed in x1 Categorical distribution (a generalization of Bernoulli)i se q u i v a l e n tt ot h eMultinomial distribution for single observation in discrete space and is sometimes called the Discrete distribution. For our purposes, they can be used interchangeably but are not equivalent in general with subtle differences.

Instead of clustering data points like in DIFFRAC, we cluster classes of data points.

Acknowledgments

I am very thankful to my advisers Cedric, Francis and Guillaume for their guidance and support. They were very patient with me to say the least. I would also like to thank Julien, Rodholphe and Armand for their help with my work. I also wish to express my gratitude to my masters adviser Edmond who offered me an opportunity to move to Grenoble. I am grateful to Xerox Research and the French ANRT for the CIFRE grant that funded me for the whole duration. Group members both in the MLS team at Xerox and in the SIERRA team at Inria have been very helpful to me. I have greatly benefited from the support of my friends and well-wishers who made things a lot easier over these three years. There is a long list of people I must thank by name but I wish not to regret missing someone, something bound to happen with long lists. So, I skip listing them but I am truly thankful to all of them for all their help and support. I use the privileged last line to thank my parents for all their sacrifices.

Algorithm 7 w := Prox `T 1 (w) Proximal projection step for `T 1 on grouping G.

Input: T suffix tree, w=[vc ] tree-structured vector v with corresponding number of suffixes collapsed at each node in c,  threshold 1 for x 2 DepthFirstNodeTraversal(T, PostOrder ) 2 g(v, x):=⇡ `T 1 ( g(v, x),c x  )

Procedure: q := ⇡ `1 (q, )

S := (S + δS),C:= (C + δC),I:= L 8 else I := U \{⇢} 9 r = S- C , v i := v imax(0,v ir)# take residuals a. DepthFirstNodeTraversal(T,Order ) returns nodes x from the suffix tree T by depth-first traversal in the order prescribed by Order.

It is easy to see by example that the Prox `T 2 operator does not preserve the paths P(S(X),w) required for efficient tree structure M v (X).Ac o u n t e re x a m p l ep r o v i n gt h i s point is provided in Figure 3.11(c) on an eight-dimensional vector. This makes the method less efficient with increasing contexts eliminating long range dependencies from consideration. We next consider the proximal projection step for `T 1 -norm.

Proximal projection with `T 1 -norm

The proximal step for `T 1 -norm follows a similar decomposition where a sequence of Prox g i λ`1 projections are applied in an upward pass of the trie S(X).A g a i n ,u s i n gt h e conjugate decomposition in equation (2.17), Prox λ`T 1 can be performed by taking residuals of projection on to the `1-norm ball.

Projection of a vector w on the `1-ball of size  is more involved and requires thresholding by a value such that the entries in the resulting vector add up to , otherwise w remains the same:

⌧ =0is the case where w lies inside the `1-ball of size  with ||w|| 1 <,leavingw intact. In the other case, the threshold ⌧ is to be computed such that after thresholding, the resulting vector has an `1-norm of . The simplest way to achieve this is to sort in descending order the entries w = sort(w) and pick the k largest values such that the (k +1) th largest entry is smaller than ⌧ :

We refer to w k as the pivot and are only interested in entries larger than the pivot. Given as o r t e dv e c t o r ,i tr e q u i r e sl o o k i n gu pt oe x a c t l yk entries, however, sorting itself take O(|w| log |w|). Ar a n d o m i z e da l g o r i t h mt ofi n dt h ep i v o tt h a th a sa m o r t i z e dl i n e a rt i m ec o m p l e x i t y was proposed by Bruckner (1984)andPardalos and [START_REF] Pardalos | An algorithm for a singly constrained class of quadratic programs subject to upper and lower bounds[END_REF]. This method randomly chooses a candidate for the pivot and checks for it correctness using the condition in (3.7). This method is repeated until the right pivot is found. However, a linear time complexity for `1-ball projection leaves us with an O(|S| 2 ) quadratic time algorithm for Prox λ`T 1 . The resulting algorithm is summarized in Algorithm 7.

Unfortunately, Prox λ`T 1 does not simplify into a linear two pass algorithm like Prox λ`T 2 because the threshold value depends on the distribution of values unlike the scaling parameter of `T 2 that only depends on the norm of the vector. At each subvector g i ,t h r e s h o l d i n g needs to be applied and the `1-norm of the subvector recomputed before moving to its parent node.

We discuss later in Section 3.6.1 two specific aspects of the `T 1 penalty that lead to significant computational and memory gains over the naive algorithm presented in Algorithm 7.O n eo ft h e mi st h a tt h ep a t h sP(S(X),w) required for tree structure M v (X) are preserved under Prox `T 1 operation. The other involves a single projection at each collapsed node of M v (X) replacing the series of projections. This comes from an observation that composition of Prox `1 operators over constant value non-branching paths can be replaced by a single Prox `1 with  appropriately modified to .W et h e ng i v ean e w algorithm for Prox `1 using Fibonacci heaps (Cormen et al., 2009)thathasde te rminis tic linear time in the number of entries when some specific condition is true that holds in our case.

Performance evaluation with structured norms

We evaluate models with structured penalties on the same splits of data as described in Section 3.4.2. Structured penalties nicely employ the hierarchy within features that unstructured penalties discussed in Section 3.4.1 fail to capture. This reflects in their proximal steps where features lower in the suffix trie are either scaled or thresholded (depending on the choice of the penalty) more than those higher above in the tree. This property varies the amount of regularization with the depth of the tree. We compare performance of models using structured penalties to that of unstructured models.

Figure 3.6 plots the average perplexity values from the four subsets used in Section 3.4.2 for models involving structured penalties. Regularization parameters of 7.1 ⇥ 10 -6 and 5.6 ⇥ 10 -6 were chosen for `T 2 and `T 1 penalties by cross-validation as in the case of unstructured models. Performance curves for unstructured penalties are also plotted for comparison. It can be observed that unlike `2 2 and `1,the`T 2 penalty does not show performance degradation by avoiding overfitting for features of longer contexts. Moreover, the log-linear language model with `T 2 penalty performs quite similar to interpolated Kneser-Ney. Model involving `T 1 penalty has perplexity values close to Kneser-Ney and performs better at lower depths but starts to overfit for higher ones. allow for assigning a single word into multiple clusters that was found to be important for deeper trees (Mnih and Hinton, 2008).

A hierarchical language model with classifiers based on suffix-trees at each node that can learn from large data is of huge interest in language processing. As described in Section 1.4, structured penalization in such models can be helpful to discriminatively model task specific requirements (like constraints for good readability) that are hard to handle with other techniques. Beyond applications in language, this model is of interest to various areas handling discrete sequences like molecular biology. Protein sequence alignment, for example, is one problem where large contexts have been found necessary for good performance (see, e.g., Edgar and Sjolander, 2003;Koonin and Galperin, 2003). These algorithms could also be extended to such problems to improve performance by exploiting the structure within their feature spaces. However, there are issues that need to be studied in detail for a more complete understanding that is necessary to tackle some known shortcomings. We describe these with possible directions worthy of exploration for further study.

Further investigation of language mo deling. The strength of a model is largely dependent on the amount of data it can crunch, i.e., assuming it is suitably biased with a term tending to zero with growing amount of data fed into the model. One could imagine building an online model for language where nodes are added into the suffix tree with appropriately chosen initial weights as they are observed. Upon observing a new sample, an o d ei sa d d e di fn e c e s s a r ya n da ni t e r a t i o no ft h eo p t i m i z a t i o ni sp e r f o r m e d . At r e estructured regularization is most appropriate in such situations. Since adding a new node is equivalent to setting a weight corresponding to a subtree to non-zero that earlier had a zero weight because corresponding samples were observed. Such a model can be used to learn as and when data arrives and can accommodate as much data as we can feed without having to worry about overfitting.

A model with such statistical strength could serve as a backbone to numerous applications and could be used for domain adaptation and transfer learning. Domain adaptation is the problem where the target distribution is known to be different from that of the training observations and transfer learning is where different related tasks are learned from the same set of observations. Under-resourced domains would significantly benefit by borrowing from data available for other domains. The adaptation could be achieved by learning ap a r a m e t r i cl a y e ro nt o po ft h ea b o v em o d e lt os u i td o m a i ns p e c i fi cd i s t r i b u t i o n s( l i k e the two-stage model of Goldwater et al. ( 2011)). Similarly, various tasks can be modeled by parameters specific to the tasks that can be learned jointly to exploit task relatedness. This borrows the statistical strength from the large amounts of text while retaining the flexibility to fine tune it to specific domains and tasks.

An online statistical model that can be customized to address specific tasks is of particular interest to fields like language processing where no amount of data could be considered as u ffi c i e n t l ye n o u g hs a m p l i n go ft h ef e a t u r es p a c e . F u r t h e r ,i na p p l i c a t i o n sl i k el a n g u a g e generation where annotations are harder to gather borrowing strength from available data could give a significant boost. Consider for example, generating descriptive summaries of medical images or, short explanations to weather plots. We could have easy access to bare images and plots but we cannot expect sufficient annotation to guide a learning algorithm to translate them into meaningful sentences.

Appendix A

Smoothing and maximum entropy models

A.1 Smoothing models

We detail various metho ds briefed in Section 1.2.1 relating smoothing techniques for mgram models. The two aspects of smoothing models relate to redistribution of probability mass to unseen sequences and mixing models of multiple orders using back-off or interpolation. We recall the maximum likelihood estimator as,

A.1.1 Redistribute mass to handle unseen sequences.

Given that C only sparsely samples the space of all sequences, it is possible that with more words and larger vocabulary, sequence s will have a smaller probability of being seen at training phase. This motivates setting aside a part of the mass allocated to the sequences in C for unseen contexts. We briefly describe two methods that tackle this; the Laplace smoothing that uses additive values and the Good-Turing smoothing the uses multiplicative factors to achieve this behavior.

1. Laplace smoothing. Laplace smoothing, also called additive smoothing is a generic smoothing technique for models of categorical data (Lidstone, 1920;Jefreys, 1948).

It is also called a shrinkage estimator because it brings the distribution closer to uniform distribution. It works by adding some fake samples to original frequencies from data C. This is equivalent to incrementing values of both the numerator and the denominator of P ML resulting in an estimate of the form:

where 0 <d 1 is a parameter that is tuned using held-out data. The case of d =1 is called add-one smoothing. Gale andChurch (1994, 1990)h a v ea r g u e da g a i n s tt h i s choice of smoothing asserting that is performs rather poorly in general.

Jensen's inequality is applied to rewrite T e as a sum over i.

T e =e x p

Substituting the upper bound from (A.7)i n t o( A.6) we get the following as the surrogate for GIS,

A.2.2 Improved Iterative Scaling.

This method straight away applies Jensen's inequality on the T e by using I # (x m v):

T e =e x p

Putting (A.9)i n t o( A.6), we get the surrogate for IIS,

This method follows a derivation similar to that of GIS above except that I # is replaced by I M gives us the following surrogate:

While the above two methods, GIS and IIS, update all parameters at every iteration, SCIS only updates one parameter at each iteration. It sequentially iterates through the list of parameters until termination. It was shown by Goodman (2002)t h a tt h i sm o d i fi c a t i o n could be used to gain about an order of magnitude in computational time over GIS.

The derivatives of surrogate functions for err in (A.8), (A.10)a n d( A.11)a r es e tt oz e r o to get the update equations for each of these methods. These equations are summarized in Table 1.1. Note that the update for IIS unlike the other two is not straightforward with ∆! being implicit and requires solving the equation iteratively to fetch the ∆! .

An alternative to above methods is to use coordinate descent to minimize (A.5)directly . Coordinate descent updates variables sequentially as in SCIS but the update step is similar to that of IIS where ∆! is implicit and must be solved for using iterative techniques. The three iterative scaling algorithms above and coordinate descent are all known to converge linearly (Huang et al., 2010).

Appendix B

Synthetic Data Generation

A specified number of clusters are distributed in different orthants. Each cluster has a specified number of data points. dim: dimensionality of features pntspc: points per class nclust: number of clusters disperse: distance of mean of cluster from origin variance: variance within cluster An orthant is chosen by a binary encoding of decimal number i varying from zero to number of clusters. Disperse is the amount by which is moves in the orthant. It is further moved by a small random vector (vec below) in this orthant. Uniformly distributed points are generated with this as the mean. Such clusters are piled to make the data matrix.

Effect of parameters

We empirically study the significance of the δ parameter used in estimating the residuals and the effect of approximating residuals in top-down approaches.

Ridge in square loss. There is one free parameter in the measure of proximity of classes, namely the ridge parameter δ. This effects the entries in the residual matrix which is used to determine the shape of the tree. The ridge value showed no significant variations on the final performances of the tree classifiers. They are compared on the synthetic datasets in Figure C.1. The tree structure remained considerably unchanged for a large range of δ which we can safely fix to a value.

Approximatrion of residuals at deeper nodes. Top-down methods, unlike bottom-up, cannot exactly update residuals after a split operation using those before the split. The effect of such approximations is shown in Figure C.2. The difference shows up in the wellseparated classes and this was observed to become critical for top-down methods as the number of classes grow.