No description available.

Current information retrieval models are optimized for retrieval with short keyword queries. In contrast, in this dissertation we focus on longer, verbose queries with more complex structure that are becoming more common in both mobile and web search. To this end, we propose an expressive query representation formalism based on query hypergraphs. Unlike the existing query representations, query hypergraphs model the dependencies between arbitrary concepts in the query, rather than dependencies between single query terms. Query hypergraphs are parameterized by importance weights, which are assigned to concepts and concept dependencies in the query hypergraph, based on their contribution to the overall retrieval effectiveness. Query hypergraphs are not limited to modeling the explicit query structure. Accordingly, we develop two methods for query expansion using query hypergraphs. In these methods, the expansion concepts in the query hypergraph may come either from the retrieval corpus alone or from a combination of multiple information sources such as Wikipedia or the anchor text extracted from a large-scale web corpus. We empirically demonstrate that query hypergraphs are consistently and significantly more effective than many of the current state-of-the-art retrieval methods, as demonstrated by the experiments on newswire and web corpora. Query hypergraphs improve the retrieval performance for all query types, and, in particular, they exhibit the highest effectiveness gains for verbose queries.

No description available.

Cette thèse s'inscrit dans le domaine de la théorie des hypergraphes et s'intéresse aux traverses minimales des hypergraphes. L'intérêt pour l'extraction des traverses minimales est en nette croissance, depuis plusieurs années, et ceci est principalement dû aux solutions qu'offrent les traverses minimales dans divers domaines d'application comme les bases de données, l'intelligence artificielle, l'e-commerce, le web sémantique, etc. Compte tenu donc du large éventail des domaines d'application des traverses minimales et de l'intérêt qu'elles suscitent, l'objectif de cette thèse est donc d'explorer de nouvelles pistes d'application des traverses minimales tout en proposant des méthodes pour optimiser leur extraction. Ceci a donné lieu à trois contributions proposées dans cette thèse. La première approche tend à tirer profit de l'émergence du Web 2.0 et, par conséquent, des réseaux sociaux en utilisant les traverses minimales pour la détection des acteurs importants au sein de ces réseaux. La deuxième partie de recherche au cours de cette thèse s'est intéressé à la réduction du nombre de traverses minimales d'un hypergraphe. Ce nombre étant très élevé, une représentation concise et exacte des traverses minimales a été proposée et est basée sur la construction d'un hypergraphe irrédondant, d'où sont calculées les traverses minimales irrédondantes de l'hypergraphe initial. Une application de cette représentation au problème de l'inférence des dépendances fonctionnelles a été présentée pour illustrer l’intérêt de cette approche. La dernière approche s'est intéressée à la décomposition des hypergraphes en des hypergraphes partiels. Les traverses minimales de ces derniers sont calculées et leur produit cartésien permet de générer l'ensemble des traverses de l'hypergraphe. Les différentes études expérimentales menées ont montré l’intérêt de ces approches proposées / This work is part of the field of the hypergraph theory and focuses on hypergraph minimal transversal. The problem of extracting the minimal transversals from a hypergraph received the interest of many researchers as shown the number of algorithms proposed in the literature, and this is mainly due to the solutions offered by the minimal transversal in various application areas such as databases, artificial intelligence, e-commerce, semantic web, etc. In view of the wide range of fields of minimal transversal application and the interest they generate, the objective of this thesis is to explore new application paths of minimal transversal by proposing methods to optimize the extraction. This has led to three proposed contributions in this thesis. The first approach takes advantage of the emergence of Web 2.0 and, therefore, social networks using minimal transversal for the detection of important actors within these networks. The second part of research in this thesis has focused on reducing the number of hypergraph minimal transversal. A concise and accurate representation of minimal transversal was proposed and is based on the construction of an irredundant hypergraph, hence are calculated the irredundant minimal transversal of the initial hypergraph. An application of this representation to the dependency inference problem is presented to illustrate the usefulness of this approach. The last approach includes the hypergraph decomposition into partial hypergraph the “local” minimal transversal are calculated and their Cartesian product can generate all the hypergraph transversal sets. Different experimental studies have shown the value of these proposed approaches

在這篇論文中，我們利用分離－收縮法(splitting-contraction algorithm)獲得一個擁有完全C邊以及循環D邊特性的圖之著色多項式。 假如一個混合超圖在點集合上有主要的循環， 使得所有的C邊和D邊包含一個主循環(host cycle)的連接子圖， 則稱此圖為循環的(circular)。 對於每個l≧2， 所有連續l個點會形成一個D邊時， 我們把D記作D_l。 如此一來， 超圖(X,Φ,D_2)就是圖論中n個點的普通循環。 我們先觀察擁有完全C邊和循環D邊的超圖， 利用分離－收縮法的第一步， 找到遞迴關係式並且解它。 然後我們就推廣到一般完全C邊及循環D邊的超圖。 / In this thesis, we obtain the chromatic polynomial of a mixed hypergraph with complete C-edges and circular D-edges by using splitting-contraction algorithm. A mixed hypergraph H=(X,C,D) is called circular if there exists a host cycle on the vertex set X such that every C-edge and every D-edge induces a connected subgraph of the host cycle. For each l≧2, we denote D by D_l if and only if every l consecutive vertices of X form a D-edge. Thus the mixed hypergraph (X,Φ,D_2) is a simple classical cycle on n vertices. We observe first a mixed hypergraph with complete C-edges and D_2. By the first step of the splitting-contraction algorithm, we can find out the recurrence relation and solve it. Then we generalize the mixed hypergraph with complete C-edges and circular D-edges.

A wide range of problems can be modelled as constraint satisfaction problems (CSPs), that is, a set of constraints that must be satisfied simultaneously. Constraints can either be represented extensionally, by explicitly listing allowed combinations of values, or intensionally, whether by an equation, propositional logic formula, or other means. Intensionally represented constraints, known as global constraints, are a powerful modelling technique, and many modern CSP solvers provide them. We give examples to show how problems that deal with product configuration can be modelled with such constraints, and how this approach relates to other modelling formalisms. The complexity of CSPs with extensionally represented constraints is well understood, and there are several known techniques that can be used to identify tractable classes of such problems. For CSPs with global constraints, however, many of these techniques fail, and far fewer tractable classes are known. In order to remedy this state of affairs, we undertake a systematic review of research into the tractability of CSPs. In particular, we look at CSPs with extensionally represented constraints in order to understand why many of the techniques that give tractable classes for this case fail for CSPs with global constraints. The above investigation leads to two discoveries. First, many restrictions on how the constraints of a CSP interact implicitly rely on a property of extensionally represented constraints to guarantee tractability. We identify this property as being a bound on the number of solutions in key parts of the instance, and find classes of global constraints that also possess this property. For such classes, we show that many known tractability results apply. Furthermore, global constraints allow us to treat entire CSP instances as constraints. We combine this observation with the above result, and obtain new tractable classes of CSPs by dividing a CSP into smaller CSPs drawn from known tractable classes. Second, for CSPs that simply do not possess the above property, we look at how the constraints of an instance overlap, and how assignments to the overlapping parts extend to the rest of the problem. We show that assignments that extend in the same way can be identified. Combined with a new structural restriction, this observation leads to a second set of tractable classes. We conclude with a summary, as well as some observations about potential for future work in this area.

Cette thèse s’intéresse à un problème de bin-packing en deux dimensions avec des défauts sur les bins rencontré dans l’industrie verrière. Les plans de découpe sont guillotine 4-stage exact, les objets à couper sans défauts.Une possible résolution utilise la décomposition de Dantzig-Wolfe puis une génération de colonnes et un branch-and-price. Cela est impossible dans notre cas du fait d’instances de trop grande taille. Nous résolvons d’abord le problème de pricing sans défauts par un algorithme incrémental de labelling basé sur un programme dynamique (DP), représenté par un problème de flot dans un hypergraphe. Notre méthode est générique pour les problèmes de sac-à-dos guillotine mais ne résout pas de larges instances en un temps de calcul raisonnable. Nous résolvons alors le problème de bin-packing sans défauts grâce à un DP et une heuristique de diving. Le DP génère des colonnes “non propres”,ne pouvant pas participer à une solution entière. Nous adaptons le diving pour ce cas sans perte d’efficacité. Nous l’étendons alors au cas avec défauts. Nous réparons d’abord heuristiquement une solution du problème sans défauts. La fixation des colonnes dans le diving sans-défaut est ensuite modifiée pour gérer les défauts. Les résultats industriels valident nos méthodes. / This thesis deals with a two-dimensional bin-packing problem with defects on bins from the glass industry. Cutting patterns have to be exact 4-stage guillotine and items defect-free. A standard way to solve it isto use Dantzig-Wolfe reformulation with column generation and branch-and price.This is impossible in our case due to large instance size. We first study and solve the defect-free pricing problem with an incremental labelling algorithm based on a dynamic program (DP), represented as a flow problem in a hypergraph. Our method is generic for guillotine knapsack problems but fails to solve large instance in a short amount of time. Instead we solve the defect freebin-packing problem with a DP and a diving heuristic. This DP generatesnon-proper columns, cutting patterns that cannot be in an integer solution.We adapt standard diving heuristic to this “non-proper” case while keeping itseffectiveness. We then extend the diving heuristic to deal with defects. Ourfirst proposal heuristically repairs a given defect-free solution. Secondly the defect-free diving heuristic is adjusted to handle defects during column fixing.Our industrial results outline the effectiveness of our methods.

The objectives of this thesis are focused on research in machine learning for coreference resolution. Coreference resolution is a natural language processing task that consists of determining the expressions in a discourse that mention or refer to the same entity. The main contributions of this thesis are (i) a new approach to coreference resolution based on constraint satisfaction, using a hypergraph to represent the problem and solving it by relaxation labeling; and (ii) research towards improving coreference resolution performance using world knowledge extracted from Wikipedia. The developed approach is able to use entity-mention classi cation model with more expressiveness than the pair-based ones, and overcome the weaknesses of previous approaches in the state of the art such as linking contradictions, classi cations without context and lack of information evaluating pairs. Furthermore, the approach allows the incorporation of new information by adding constraints, and a research has been done in order to use world knowledge to improve performances. RelaxCor, the implementation of the approach, achieved results in the state of the art, and participated in international competitions: SemEval-2010 and CoNLL-2011. RelaxCor achieved second position in CoNLL-2011. / La resolució de correferències és una tasca de processament del llenguatge natural que consisteix en determinar les expressions d'un discurs que es refereixen a la mateixa entitat del mon real. La tasca té un efecte directe en la minería de textos així com en moltes tasques de llenguatge natural que requereixin interpretació del discurs com resumidors, responedors de preguntes o traducció automàtica. Resoldre les correferències és essencial si es vol poder “entendre” un text o un discurs. Els objectius d'aquesta tesi es centren en la recerca en resolució de correferències amb aprenentatge automàtic. Concretament, els objectius de la recerca es centren en els següents camps: + Models de classificació: Els models de classificació més comuns a l'estat de l'art estan basats en la classificació independent de parelles de mencions. Més recentment han aparegut models que classifiquen grups de mencions. Un dels objectius de la tesi és incorporar el model entity-mention a l'aproximació desenvolupada. + Representació del problema: Encara no hi ha una representació definitiva del problema. En aquesta tesi es presenta una representació en hypergraf. + Algorismes de resolució. Depenent de la representació del problema i del model de classificació, els algorismes de ressolució poden ser molt diversos. Un dels objectius d'aquesta tesi és trobar un algorisme de resolució capaç d'utilitzar els models de classificació en la representació d'hypergraf. + Representació del coneixement: Per poder administrar coneixement de diverses fonts, cal una representació simbòlica i expressiva d'aquest coneixement. En aquesta tesi es proposa l'ús de restriccions. + Incorporació de coneixement del mon: Algunes correferències no es poden resoldre només amb informació lingüística. Sovint cal sentit comú i coneixement del mon per poder resoldre coreferències. En aquesta tesi es proposa un mètode per extreure coneixement del mon de Wikipedia i incorporar-lo al sistem de resolució. Les contribucions principals d'aquesta tesi son (i) una nova aproximació al problema de resolució de correferències basada en satisfacció de restriccions, fent servir un hypergraf per representar el problema, i resolent-ho amb l'algorisme relaxation labeling; i (ii) una recerca per millorar els resultats afegint informació del mon extreta de la Wikipedia. L'aproximació presentada pot fer servir els models mention-pair i entity-mention de forma combinada evitant així els problemes que es troben moltes altres aproximacions de l'estat de l'art com per exemple: contradiccions de classificacions independents, falta de context i falta d'informació. A més a més, l'aproximació presentada permet incorporar informació afegint restriccions i s'ha fet recerca per aconseguir afegir informació del mon que millori els resultats. RelaxCor, el sistema que ha estat implementat durant la tesi per experimentar amb l'aproximació proposada, ha aconseguit uns resultats comparables als millors que hi ha a l'estat de l'art. S'ha participat a les competicions internacionals SemEval-2010 i CoNLL-2011. RelaxCor va obtenir la segona posició al CoNLL-2010.

In this thesis, we investigate graphs and hypergraphs that have (relaxed) product structures. In the class of graphs, we discuss in detail \\emph{RSP-relations}, a relaxation of relations fulfilling the square property and therefore of the product relation $\\sigma$, that identifies the copies of the prime factors of a graph w.r.t. the Cartesian product. For $K_{2,3}$-free graphs finest RSP-relations can be computed in polynomial-time. In general, however, they are not unique and their number may even grow exponentially. Explicit constructions of such relations in complete and complete bipartite graphs are given. Furthermore, we establish the close connection of (\\emph{well-behaved}) RSP-relations to \\mbox{(quasi-)covers} of graphs and equitable partitions. Thereby, we characterize the existence of non-trivial RSP-relations by means of the existence of spanning subgraphs that yield quasi-covers of the graph under investigation. We show, how equitable partitions on the vertex set of a graph $G$ arise in a natural way from well-behaved RSP-relations on $E(G)$. These partitions in turn give rise to quotient graphs that have rich product structure even if $G$ itself is prime. This product structure of the quotient graph is still retained even for RSP-relations that are not well-behaved. Furthermore, we will see that a (finest) RSP-relation of a product graph can be obtained easily from (finest) RSP-relations on the prime factors w.r.t. certain products and in what manner the quotient graphs of the product w.r.t. such an RSP-relation result from the quotient graphs of the factors and the respective product. In addition, we examine relations on the edge sets of \\emph{hyper}graphs that satisfy the grid property, the hypergraph analog of the square property. We introduce the \\emph{strong} and the \\emph{relaxed} grid property as variations of the grid property, the latter generalizing the relaxed square property. We thereby show, that many, although not all results for graphs and the (relaxed) square property can be transferred to hypergraphs. Similar to the graph case, any equivalence relation $R$ on the edge set of a hypergraph $H$ that satisfies the relaxed grid property induces a partition of the vertex set of $H$ which in turn determines quotient hypergraphs that have non-trivial product structures. Besides, we introduce the notion of \\emph{(Cartesian) hypergraph bundles}, the analog of (Cartesian) graph bundles and point out the connection between the grid property and hypergraph bundles. Finally, we show that every connected thin hypergraph $H$ has a unique prime factorization with respect to the normal and strong (hypergraph) product. Both products coincide with the usual strong \\emph{graph} product whenever $H$ is a graph. We introduce the notion of the Cartesian skeleton of hypergraphs as a natural generalization of the Cartesian skeleton of graphs and prove that it is uniquely defined for thin hypergraphs. Moreover, we show that the Cartesian skeleton of thin hypergraphs and its PFD w.r.t. the strong and the normal product can be computed in polynomial time.

This thesis is divided into two parts. The first part is concerned with the commutative algebra of certain combinatorial structures arising from uniform hypergraphs. The main focus lies on two particular classes of hypergraphs called chordal hypergraphs and complete hypergraphs, respectively. Both these classes arise naturally as generalizations of the corresponding well known classes of simple graphs. The classes of chordal and complete hypergraphs are introduced and studied in Chapter 2 and Chapter 3 respectively. Chapter 4, that is the content of \cite{E5}, answers a question posed at the P.R.A.G.MAT.I.C. summer school held in Catania, Italy, in 2008. In Chapter 5 we study hypergraph analogues of line graphs and cycle graphs. Chapter 6 is concerned with a connectedness notion for hypergraphs and in Chapter 7 we study a weak version of shellability.The second part is concerned with affine monoids and their monoid rings. Chapter 8 provide a combinatorial study of a class of positive affine monoids that behaves in some sense like numerical monoids. Chapter 9 is devoted to the class of numerical monoids of maximal embedding dimension. A combinatorial description of the graded Betti numbers of the corresponding monoid rings in terms of the minimal generators of the monoids is provided. Chapter 10 is concerned with monomial subrings generated by edge sets of complete hypergraphs.