<!-- Slide number: 1 -->
Ministry of Higher Education and Scientific Research
University of Carthage
Faculty of Economics and Management of Nabeul
Research Master’s Thesis
SPECIALTY
Computer Decision Support
An Ant Colony Algorithm for Arabic
Dependency Parsing
Prepared by
Younes RBIA
| Dr. Slim BECHIKH | | Associate Professor | | | Chair |
| --- | --- | --- | --- | --- | --- |
| Dr. Sabeur ELKOSANTINI | | Assistant Professor | | | Examiner |
| Dr. Fériel BEN FRAJ | | Assistant Professor | | | Supervisor |
2019 - 2020
Notes:
<!-- Slide number: 2 -->
Presentation Plan
2
Notes:
<!-- Slide number: 3 -->
Introduction
An Ant Colony Algorithm for Arabic Dependency Parsing
Notes:
The problem of Natural Language Processing (NLP) has become unavoidable, due to the explosion in the number of electronic documents produced and available every day.
Therefore, it has become necessary to develop new applications that make it possible to automatically and efficiently process these large quantities of textual data.
Publicité
n particular, parsing takes an important place in the NLP field, since it constitutes an essential stage in the process of linguistic processing.
As a result, the automation of dependencies parsing has always benefited from special attention since the first applications of NLP. The problem of parsing is getting worse for the Arabic language because of its specificities.
Indeed, this language has a set of characteristics that make it more ambiguous than other natural languages and make its processing a difficult task.
<!-- Slide number: 4 -->
Objective
An Ant Colony Algorithm for Arabic Dependency Parsing
Notes:
The main objective of the research project is to deal with the dependency parsing problem of the Arabic texts.
The approach we have adopted is based on ant colony algorithm.
<!-- Slide number: 5 -->
Parsing
Parsing : *rich and confusing field of linguistics
*attempts to associate an input sentence with its representative syntactic structure.
A syntactic structure describes the way the syntactic rules are combined to form that sentence.
The computer program that performs this task is called a syntactic parser.
Knowing the syntactic structure of a sentence leads up to discern the dependency relationships between its different words and helps to predict the meaning of that sentence.
5
An Ant Colony Algorithm for Arabic Dependency Parsing
Notes:
Point 3 : The input of such a program is a sequence of lexical units. Its output is generally a syntactic tree.
<!-- Slide number: 6 -->
Dependency Parsing
An Ant Colony Algorithm for Arabic Dependency Parsing
<!-- Slide number: 7 -->
Dependency Tree
Example of a dependency tree
7
An Ant Colony Algorithm for Arabic Dependency Parsing
Notes:
This figure illustrates the dependency tree of the example sentence “This time around, they’re moving even faster ”.
Publicité
In this figure, the dependencies between the words are the oriented edges.
<!-- Slide number: 8 -->
Arabic Language
Specific problems of the Arabic language
8
An Ant Colony Algorithm for Arabic Dependency Parsing
Notes:
The Arabic language has particularities that make it more ambiguous than other languages.
Besides the classic phenomena like coordination, anaphora, and ellipsis, there are other specific problems of the Arabic language, namely :
<!-- Slide number: 9 -->
Related Works
9
An Ant Colony Algorithm for Arabic Dependency Parsing
<!-- Slide number: 10 -->
Related Works
10
An Ant Colony Algorithm for Arabic Dependency Parsing
<!-- Slide number: 11 -->
Ant Colony Optimization (ACO)
Ant colony optimization (ACO) is an evolution simulation algorithm proposed by Marco Dorigo (Italy) in 1992 in his PhD thesis.
It is inspired by the behavior of ant colonies. It belongs to the family of stochastic meta-heuristic methodologies.
11
An Ant Colony Algorithm for Arabic Dependency Parsing
Notes:
This figure illustrates the concept of an ant colony
<!-- Slide number: 12 -->
Ant Colony Optimization (ACO)
The colony has access to a food source linked by two paths to the colony’s nest.
During their trips, a chemical trail (pheromone) is left on the ground.
The role of this trail is to guide the other ants towards the target point.
Publicité
For a given ant, the path is chosen according to the smelt quantity of pheromone.
Furthermore, this chemical substance has a decreasing action over time (evaporation process) and the quantity left by one ant depends on the amount of food (reinforcement).
12
An Ant Colony Algorithm for Arabic Dependency Parsing
Notes:
The approach of the ant colony can be presented based on the five following points:
Point 3 : The larger the amount of pheromone on a particular path is, the larger the probability that the ants will select the path.
<!-- Slide number: 13 -->
Ant Colony Optimization (ACO)
Characteristics
13
An Ant Colony Algorithm for Arabic Dependency Parsing
Notes:
Ants have many collective and individual characteristics that can help us solve complex problems.
<!-- Slide number: 14 -->
Approach Description
10
An Ant Colony Algorithm for Arabic Dependency Parsing
<!-- Slide number: 15 -->
Approach Description
11
An Ant Colony Algorithm for Arabic Dependency Parsing
<!-- Slide number: 16 -->
Approach Description
12
An Ant Colony Algorithm for Arabic Dependency Parsing
<!-- Slide number: 17 -->
Experimental Study
13
An Ant Colony Algorithm for Arabic Dependency Parsing
<!-- Slide number: 18 -->
Publicité
Experimental Study
14
An Ant Colony Algorithm for Arabic Dependency Parsing
<!-- Slide number: 19 -->
Experimental Study
15
An Ant Colony Algorithm for Arabic Dependency Parsing
<!-- Slide number: 20 -->
Experimental Study
16
An Ant Colony Algorithm for Arabic Dependency Parsing
<!-- Slide number: 21 -->
Experimental Study
17
An Ant Colony Algorithm for Arabic Dependency Parsing
<!-- Slide number: 22 -->
Experimental Study
18
An Ant Colony Algorithm for Arabic Dependency Parsing
<!-- Slide number: 23 -->
Experimental Study
19
An Ant Colony Algorithm for Arabic Dependency Parsing
<!-- Slide number: 24 -->
Conclusion and Future Improvements
20
An Ant Colony Algorithm for Arabic Dependency Parsing
<!-- Slide number: 25 -->
21
An Ant Colony Algorithm for Arabic Dependency Parsing