Sujet de these: PhD position in Text Mining / Fouille de Textes, Loria, Nancy

[Thierry Hamon]

[version française en deuxième partie du message]

Date: Tue, 12 Apr 2011 10:56:29 +0200
From: Yannick Toussaint <yannick.toussaint at loria.fr>
Message-Id: <DD517DE2-5BAF-4751-9679-0B74B7E988AC at loria.fr>
X-url: http://www.loria.fr/accueil_loria


Graph mining for text analysis : using graph pattern structures and
subgraph mining

One major problem in knowledge discovery is posed by the very large
number of patterns (itemsets, association rules) that is returned by
pattern mining algorithms. This is particularly true for texts or
graphs. It is then quite impossible for an expert to analyse the
results of the mining process. There are some ways of lowering the
complexity of the mining task. One is to set up a high frequency
support but this is usually not appropriate as very frequent patterns
are not the most interesting ones and many interesting less frequent
patterns are missed. Another idea is to use appropriate constraints or
measures for filtering the extracted patterns. Among these measures,
we would like to consider and to extend the notion of “most
informative pattern” resulting from a previous work on the mining of
molecular structures.

The interesting patterns are those which are “discriminant” in the
sense that they are able to represent a large family of patterns
(factorization, internal cohesion) and this family is well separated
from other families (discrimination, external separation). The notion
of most informative pattern is well adapted to this discrimination
task. The search for most informative pattern can be considered as an
optimisation problem where the patterns showing the best compromise
between frequency and information rate in their description. A measure
of this compromise can be estimated by a score function. In the
present case, given a collection of texts, the problem is to search
for the graph patterns which show the highest measure.

The most informative patterns were introduced for guiding subgraph
mining. In this thesis subject, an idea is to extend this previous
work to natural language processing and text analysis based on
subgraph mining techniques. Graphs are powerfull tools for
representing texts both on structural aspects and on semantic
ones. The problem of extracting most informative patterns consists
in searching for the patterns whose score is maximal. One example of
score function is given by the area function involving frequency and
length of the patterns. A property of a score function is to be
increasing w.r.t. all its variables (following the pattern order). In
the present project, there is a need to design an adapted score
function that in addition takes into account domain knowledge and as
well linguistic relevant elements.

Based on the collection of subgraph patterns that can be extracted
from a collection of text using the most informative pattern approach,
the next idea is to extend the pattern structure approach in FCA to
subgraph. In this way, a classification of texts w.r.t. the graph
representation of their content, will be available as a concept
lattice. This concept lattice can be used for a number of tasks, such
as information retrieval, but also for ontology engineering. For
achieving the classification task, it is necessary to adapt and extend
previous work on pattern structures.
Finally, this thesis subject tries to bridge two mining approaches,
sub- graph mining in the one hand and FCA in the other hand. Each of
these approach has powerful characteristics and it is worth trying to
take advantage of the strength of both methods for completing and
enriching each of the methods.


Applications are opened now and should include the following:
- Cover letter outlining interest in the position and academic goals
- Complete CV
- Copies of certificates and marks sheets
- Copy of the MA thesis and other publications.
- Name  (and status) of 2 referees for a letter of recommandation

For further questions, please send an email to
Yannick.Toussaint at loria.fr

The position is available in the Orpailleur Team at LORIA Lab, Nancy,
France (http://www.loria.fr/accueil_loria)

------------------------------------------------------------------------


Fouille de graphes pour l’extraction de connaissances à partir de textes 

La découverte de connaissances se heurte à un problème récurrent : le
très grand nombre de motifs ou de règles d’association extraits par
les algorithmes d’extraction de motifs. Cela est d’autant plus vrai
lorsque les données sont des textes ou des graphes. Il est alors
quasi-impossible pour un expert d’analyser les résultats du processus
de fouille. Il existe cependant plusieurs méthodes pour diminuer ce
nombre. L’une d’entre elles est d’augmenter le seuil de fréquence pour
l’extraction de motifs fréquents mais les motifs très fréquents ne
sont pas nécessairement les plus intéressants et les motifs un peu
moins fréquents ne seront plus extraits. Une autre approche consiste à
spécifier des contraintes ou à utiliser des mesures pour filtrer les
motifs extraits. Parmi ces mesures, nous reprendrons puis affinerons
la notion de “motifs les plus informatif” proposée dans le cadre de la
fouille de structures moléculaires.

Les motifs intéressants sont les motifs qui sont discriminants
c’est-à-dire (1) des motifs capables de représenter une famille
importante de motifs (par rapport à la factorisation ou à la cohésion
interne) et (2) des motifs distincts des autres familles
(discrimination). La notion de motifs les plus informatifs répond bien
au besoin de discrimination. La recherche des motifs les plus
informatifs peut donc être vue comme un compromis entre la fréquence
des motifs et leur valeur informative. Une mesure de ce compromis peut
être réalisée par une fonction de score. Dans le cas d’une collection
de textes, le problème est de chercher les motifs de graphes ayant un
score élevé.La notion de motifs les plus informatifs a été introduite
pour guider la fouille de sous-graphes. L’idée ici est d’étendre ces
travaux à l’analyse de textes et au traitement automatique de la
langue en s’appuyant sur des tech- nique de fouille de graphes. Les
graphes sont en effet bien appropriés à la représentation d’un texte
que ce soit pour rendre compte d’aspects structurels ou
sémantiques. Il faut donc définir une fonction de score qui prend en
compte des connaissances du domaine et des connaissances de nature
linguistique.

À partir d’un ensemble de motifs de sous-graphes extraits d’un corpus
de textes en utilisant les motifs les plus informatifs, l’idée est
d’étendre la notion de structure de motifs en Analyse Formelle de
Concepts à des sous-graphes. La classification de textes relativement
aux graphes qui les décrivent sera ainsi organisée en un
treillis. Différentes applications peuvent alors être envisagées,
comme la recherche d’information ou encore la construction
d’ontologie. Cette classification suppose cependant d’adapter les
travaux réalisés jusqu’à présent sur les structures de motifs.

Cette thèse va donc établir un pont entre deux approches de fouille,
la fouille de sous-graphes d’une part, et l’analyse formelle de
concepts d’autre part et les appliquer à l’extraction de connaissances
à partir de textes. Ce sont deux approches très puissantes, leur
association permettra l’enrichissement de chacune d’entre elles et au
final, les connaissances extraites seront plus complètes et précises.

Les candidatures sont à envoyer maintenant et doivent contenir :
- une lettre de motivation
- un CV détaillé
- les copies des diplômes et relevés de notes
- la version électronique du mémoire de master ou de publications (si
  disponibles)
- le nom et le statut de 2 personnes pouvant faire une lettre de
  recommandation

Pour plus de détails sur le sujet ou tout autre information:
Yannick.Toussaint at loria.fr

La thèse se déroulera dans l'équipe Orpailleur au LORIA, Nancy, France
(http://www.loria.fr/accueil_loria)

-------------------------------------------------------------------------
Message diffuse par la liste Langage Naturel <LN at cines.fr>
Informations, abonnement : http://www.atala.org/article.php3?id_article=48
English version       : 
Archives                 : http://listserv.linguistlist.org/archives/ln.html
                                http://liste.cines.fr/info/ln

La liste LN est parrainee par l'ATALA (Association pour le Traitement
Automatique des Langues)
Information et adhesion  : http://www.atala.org/
-------------------------------------------------------------------------