Requêtes et Grammaires d'Interrogation

• Le document traite des requêtes et des grammaires d'interrogation dans le cadre de l'indexation et de la recherche d'information.

Introduction

• Une requête est un ensemble de mots liés par des opérateurs Booléens.
• L'objectif est de transformer une requête en langage naturel en un format compatible avec le modèle d'indexation des documents.
• L'objectif est de trouver un modèle qui représente au mieux le besoin en information exprimé par la requête.

Requêtes sous forme de phrases

• Les utilisateurs peuvent utiliser des phrases dans leurs requêtes lors de la recherche d'information.
• Par exemple: "Stanford University".
• Un document contenant "The inventor Stanford Ovshinsky never went to university" ne devrait pas être retourné pour cette requête.
• Les index inversés ne conservent pas l'ordre relatif des termes, ce qui peut entraîner le retour de documents non pertinents.

Index Bimots

• On indexe chaque paire de termes consécutifs du document comme un "bimot".
• Chaque bimot devient un terme du vocabulaire.
• Par exemple, "compiègne, oise, france" génère deux bimots : "compiègne oise" et "oise france".
• Facilite la réponse à des requêtes de phrases exactes.

Bimots étendus

• Un anti-dictionnaire (stop words) est utilisé.
• Les termes reçoivent une étiquette (N) et les mots de l'anti-dictionnaire reçoivent une étiquette (X).
• Toute expression du type NX*N est définie comme un bimot étendu.
• Les bimots étendus sont ajoutés à la liste des index en supprimant les mots de l'anti-dictionnaire.
• Exemple: "université de compiègne" (N X N) ou "président de la république" (N X X N).

Limites des index bimots

• Une requête plus longue, comme "université de technologie de compiègne en france," peut poser des problèmes.
• La requête booléenne devient: "université technologie" AND "technologie compiègne" AND "compiègne france".
• Un document comme "l'université de technologie de compiègne fait partie du même réseau que l'utt et l'utbm. Elle est située à compiègne en france" pourrait être retourné.
• Risque de faux positifs.
• Un post-filtrage est nécessaire pour identifier le sous-ensemble de documents contenant la phrase exacte.
• L'explosion de la taille des index est une autre limite associée aux faux positifs.

Index de position

• Les index de position représentent une alternative plus efficace aux index bimots.
• Un index non positionnel contient uniquement un ID de document dans chaque entrée des listes d'affectations.
• Un index de position contient un ID de document et une liste de positions dans chaque entrée des listes d'affectations.

Exemple d'Index de Position

• Exemple de la requête "indexation₁ etx recherche₂ d'ₓ information₃"
• À partir des listes qui font référence à des documents dans lesquels les trois mots ont des positions successives, on effectue une recherche.
• La réponse est dans le document 4 pour : indexation, recherche et information.

Recherche de proximité

• La recherche est étendue en spécifiant un nombre maximal possible de termes entre deux termes de la requête.
• "indexation /3 recherche" où /k signifie "dans l'intervalle de k mots avant ou après".
• Indexation et information à une distance de 1 à 3 termes dans les documents.
• Exemple valide: "l'indexation et la recherche d'information".
• Exemple invalide: "l'indexation de documents dans un grand corpus contenant l'information".

Limites de l'index de position

• La taille de l'index de position augmente considérablement.
• La complexité de l'opération d'intersection change de façon importante (Θ(T) au lieu de Θ(N) où N = nombre de documents et T = nombre de tokens).

Association des deux types d'index

• L'association des index bimots et position peut donner des résultats appréciables.
• L'augmentation de la vitesse de recherche par rapport aux index de position est significative pour les bimots très fréquents.
• Billie Eilish, Céline Dion en sont des exemples.
• L'association consiste à inclure les bimots fréquents comme termes du vocabulaire dans l'index, et à gérer les autres phrases par intersection d'index de position.

Utilisation des grammaires formelles

• L'utilisation des grammaires formelles soutient un modèle de la syntaxe du langage pour réaliser l'analyse et la reconnaissance syntaxique des requêtes.
• L'analyse syntaxique donne un sens à la juxtaposition des termes de la requête.
• Plus besoin de se limiter aux opérations booléennes.
• La théorie des grammaires formelles comprend les grammaires syntaxiques, les grammaires transformationelles, les grammaires sémantiques, les grammaires logiques et les automates.

Grammaires formelles : généralités

• Chomsky a fait deux observations dans "Syntactic Structures" (1957) : le nombre de phrases d'une langue est infini, un locuteur reconnaît une phrase qu'il n'a jamais entendue auparavant.
• Une structure profonde permet de reconnaître un nombre infini de phrases.

Mise en évidence de la structure profonde

• La structure profonde est une représentation interne de la phrase et construite à partir de l'analyse de la syntaxe.
• Deux phrases de structure grammaticale identique peuvent donner lieu à deux interprétations différentes.
• Exemple: "Jean est facile à convaincre" (Jean est l'objet) vs "Jean est habile à convaincre" (Jean est le sujet).
• La structure grammaticale (forme externe) est "Jean est ADJECTIF à convaincre"
• La structure syntaxique (forme profonde) est: (1) Jean OBJET; (2) Jean SUJET.
• Deux phrases de structures grammaticales différentes peuvent correspondre à une même structure profonde (Forme active = forme passive).
• Une phrase constituée de mots non ambigus peut avoir un sens ambigu ("La critique de Chomsky est injustifiée").

Théorie des grammaires formelles

• Une grammaire comprend un vocabulaire, des règles de ré-écriture, et un symbole origine (symbole distingué).
• Le vocabulaire est V = VT ∪ VN avec VT ∩ VN = ∅, où VT sont les terminaux (constituants de la phrase) et VN sont les non-terminaux (symboles de description).
• Les catégories syntaxiques peuvent être définies (Groupe nominal = NOM | NOM ADJECTIF | ...).
• Un langage est un ensemble ∞ le chaînes de longueur finies.

Théorie des grammaires formelles (suite)

• Règles de réécriture : ensemble de règles de production qui spécifient le comportement des catégories dans une phrase(P → GN + GV).
• Deux types de règles : relations entre catégories syntaxiques(GV → VERBE + GN) et lexicalisation (NOM → Garçon).
• Le symbole origine indique où commence l'analyse.
• Une grammaire formelle est un quadruplet: G = (VT, VN, R, P).

Exemple 1 : Construction d'une phrase

• Vocabulaire : VT = {le, une, chat, souris, dort, mange} et VN = {P, GN, GV, Det, N, V}.
• Règles : P → GN + GV, GN → Det + N, GV → V, GV → V + GN, Det → le | une, N → chat | souris, V → dort | mange.
• Symbole origine : P.
• Exemple : "Le chat mange une souris" peut être construit à partir de l'ensemble des règles et symboles.

Exemple 2 : Opérations arithmétiques

• VT = {+, −, nombre} et VN = {E, O}.
• Règles: E→O, O→O+O|O−O et O → nombre.
• Symbole origine : E.
• Exemple : 14 + 7 − 2 peut être construit à partir de l'ensemble des règles et symboles.

Les types de grammaire

• Il y a 4 types de grammaires formelles (de 0 à 3).
• Le langage engendré va du plus général au plus particulier.
• Les grammaires de type 3 sont les plus simples.
• Les langages de programmation sont de type 3 ou 2.
• Les grammaires de type 0 sont les plus générales (machine de Turing).
• Les grammaires de type 2 seront seulement utilisées.

Grammaires de type 2

• Le membre gauche ne peut être qu'un non-terminal (NT) et un seul, sans contrainte sur le membre droit.
• Le membre gauche peut être réécrit indépendamment du contexte (grammaires à "contexte libre").
• Exemple: P → a + P + b; P→ a + b, engendre aⁿbⁿ.

Exemple de grammaire de type 2

• R1: P → GN + GV
• R2: GN → det + nom
• R3 : GV → aux + verbe + GN | verbe + GN
• R4: aux → "va"
• R5 : verbe → "lire" | "bat" | "mange" | ...
• R6 : det → "le" | "la" | "des" | "un" | "une" | ...
• R7 : nom → "garçon" | "livres" | "pomme" | ...
• "pomme le garçon bat" ou "livres lit pomme la" sont refusés par cette grammaire.

Caractéristiques des grammaires de type 2

• Elles permettent les imbrications strictes.
• Elle peut construire un arbre qui représente la structure profonde de la phrase.

Utilisations des grammaires de type 2

• Ces grammaires peuvent répondre à des questions telles que:
  • Qui va lire un livre? Rép. : le GN → le garçon
  • Que fait le garçon? Rép.: le GV → va lire un livre
  • Que lit le garçon? Rép.: le GN du GV → un livre
• L'implémentation informatique se fait par automates à pile.
• Ces grammaires ne peuvent pas gérer les constituants discontinus.
• Les structures profondes peuvent être utilisées diversement, par exemple l'expression "time flies like an arrow "

Inconvénients des grammaires de type 2

• Ces grammaires ne formalisent pas la langue naturelle.
• Elles peuvent générer des phrases qui n'ont pas de sens ou qui sont incorrectes.
• Elles ne permettent pas non plus de gérer les accords adjectifs, noms et les accords sujets/verbes.
• Elles ne permettent pas de formaliser les langues naturelles.
• Elles peuvent générer des phrases qui n'ont pas de sens ou incorrectes, les accords adjectifs, noms et les accords sujets/ verbes.
• les références croisées.
• Toutefois, ces grammaires peuvent prendre en compte des phénomènes enchâssement.

Introduction des catégories "sémantiques"

• Approche pragmatique pour réaliser des programmes efficaces.
• Application à des domaines restreints, donc bien définis (commande de robots, systèmes experts, etc.).
• Les catégories sémantiques apparaissent sous forme de NT d'une grammaire syntaxique et sont définies par le concepteur.
• Permet une meilleure interprétation des textes, mais a une analyse syntaxique plus faible.

Grammaires syntaxiques avec catégories sémantiques

• L'intérêt est porté aux structures sémantiques de la phrase, limitant les structures syntaxiques (GN, GV, etc.).
• Les catégories sémantiques sont fortement orientées par le domaine.
• L'analyse est pratiquement déterministe, réduisant les ambiguïtés.
• Les catégories qui apparaissent dans les parties droites des règles désignent des classes sémantiques.
• Ces catégories peuvent également désigner des concepts plus généraux.
• L'analyse se fait en une passe syntaxico-sémantique.

Conséquences de l'approche syntaxico-sémantique

Restriction sur le vocabulaire - Améliore la compréhension du texte. - Diminue la portabilité. - Permet de lever des ambiguïtés syntaxiques (Jean aime Julie et Corinne et Sylvie déteste Paul). Restrictions sur la représentation syntaxique - Analyse simple et efficace. - Faiblesse de l'analyse.

• Les paraphrasages doivent explicitement construits.

Application à une syntaxe SQL

• L'objectif est de trouver la grammaire syntaxique SQL pour les requêtes en langage naturel.
• Exemple : je veux les articles de Focus qui parlent de nanotechnologies.
• La représentation formelle SQL : SELECT id_article FROM table_article WHERE mot LIKE 'nanotechnologies' and rubrique = 'focus' avec les catégories syntaxiques et sémantiques pertinentes.

Syntaxe SQL (suite)

• La règle syntaxique est : requete → SELECT ARTICLE FROM TABLE_TEXT WHERE MOT LIKE 'VAR' AND RUBRIQUE = 'RUBRIQUE_VAR'.
• Des exemples de règles de lexicalisation sont fournis pour SELECT, ARTICLE, TABLE_TEXT, etc.

Méthodologie pour la construction de la grammaire

• Cinq points importants : concision, introduction de la sémantique, catégories lexicales et sémantiques, récursivité et clauses relatives.
• Étapes en analysant des exemples de phrases du corpus, comme "Je veux les articles de Focus qui parlent de nanotechnologies".

1 - Recherche de concision

Les généralités regroupées donnent lieu à :P → Trouver DET NOM, DET → le | la, NOM → département | ville | région

2 - Introduction de la sémantique

On reconnaît des phrases du type : - Trouver le nom des villes - Trouver le nom des départements Qui est être réalisé par la grammaire suivante : - P → Trouver le NOM des NOM - NOM → nom | villes | départements Cette grammaire reconnaît également des phrases telles que : - Trouver le nom des nom - Trouver le villes des villes...

3 - Catégories lexicales et sémantiques

• Généralisation de la grammaire pour éviter un surplus de phrases inutiles.
• Les catégories syntaxiques sont P, GN. Les catégories sémantiques sont ATTRIBUT-LIEU, NOM-LIEU.

4 - Récursivité

• Application des phrases à remailler :
  • Trouver le numéro du département
  • Trouver la prefecture et le numéro du département

ATTRIBUT-DEPT-REF → ATTRIBUT-DEPT + [ATTRIBUT-DEPT-REF] Attention : ne pas oublier de donner une condition d’arrêt.

5 - Clauses relatives

• On écrit alors des règles du type -P → Trouver le NOM-LIEU dont le NOM-NO est PREDICAT-COMPARAISON <NUMERO-DEPT> • P → Trouver le NOM-NO du NOM-LIEU dont le nom est PREDICAT-COMPARAISON <NOM-DEPT> NOM-LIEU → département NOM-NO → numéro •PREDICAT-COMPARAISON → égal à | supérieur à \