The paper reports the approaches utilized and results achieved for our system in the shared task (in FIRE-2016) for paraphrase identification in Indian languages (DPIL). Since Indian languages have a complex inherent nature, paraphrase identification in these languages becomes a challenging task. In the DPIL task, the challenge is to detect and identify whether a given sentence pairs paraphrased or not. In the proposed work, natural language processing with semantic concept extractions is explored for paraphrase detection in Hindi. Stop word removal, stemming and part of speech tagging are employed. Further similarity computations between the sentence pairs are done by extracting semantic concepts using WordNet lexical database. Initially, the proposed approach is evaluated over the given training sets using different machine learning classifiers. Then testing phase is used to predict the classes using the proposed features. The results are found to be promising, which shows the potency of natural language processing techniques and semantic concept extractions in detecting paraphrases.
Paraphrasing is the process of restating the meaning of a text
using other words or adopting the idea and completely rewriting
the text information. Paraphrase detection is widely explored in
English language. The Microsoft Research Paraphrase corpus
(MSRP) is most commonly used benchmark database in English
paraphrase detections [
Task -1: Given a pair of sentences from news paper domain in the specific language, the task is to classify them as paraphrases (P) or not paraphrases (NP).
Task-2: Given two sentences from news paper domainin the specific language, the task is to identify whether they are completely equivalent (E) or roughly equivalent (RE) or not equivalent (NE). It is defined with three classes, viz., paraphrases (P), semi-paraphrase (SP) or not paraphrases (NP) respectively.
Task-1 is a binary classification problem, while Task-2 is a multiclass problem. The proposed work is carried out for identification of paraphrases in Hindi language. An approach that utilizes natural language processing (NLP) techniques with semantic similarity computations is adopted. The main focus is given to Task-1 and the same model is applied for evaluating Task-2. The paper is organized as follows. Section 2 describes the proposed approach in detail. In Section 3, data statistics and evaluation measures are discussed. Section 4 discuss and analyze the results obtained. Section 4 concludes the paper with some insights to future work.
Fig.1 depicts the general work-flow of proposed approach. The three main modules and the sub modules are described in the following subsections.
Initially feature extraction is applied for extracting the traits from given sentence pairs. These features are given as the input to the classifier. For extracting the feature, sentences are processed using various pre-processing procedures with the incorporation of NLP techniques.
Initially the input sentence pairs are tokenized. Then part of speech tagging is carried out.
POS Tagging &POS based Pruning: The word tokens are
tagged with their respective classes using NLTK1 POS tagger
[
Stop Word Removal: Stop words are the frequent and irrelevant words appearing within the document. The Hindi stop word list used in reported work is given in Table 1.Prior to stemming, punctuation removal is done. As punctuations play an important role in structural composition of documents, their removal can alter the results of NLP applications. The scenario becomes more affected with NLP techniques that operate at document level such as parsing, chunking, semantic role labeling (SRL) etc. Considering the dependence of NLP techniques on these structures of a document, punctuation removal is applied after POS tagging in our approach.
Stemming: Stemming is the process of removal of affixes from the given word. Stemming of the words is done using the suffix list given in Table 2. An example illustration for all these processing’s is done using a sample sentence S.
S:
Once the basic pre-processing and NLP techniques based
processing is done, the semantic similarity between the processed
sentences pairs are computed. The metric used extracts the
semantic concepts in the form of synonyms of given word. Instead
of considering just surface-level word matching, synonym–level
matching is also done. This facilitates paraphrase detection, since
in many cases paraphrasing is done by replacing the words with
their synonyms. The synonyms are extracted using Word Net2
lexical database [
If w is in S2, then Count = Count +1, else go to step 5. Extract synonyms of the word from WordNet.
For each synonym syn for word w, do step 7.
If syn is in S2, then Count = Count +1 and goto step 6, else go to step 3.
Compute similarity, sim using Equation (1). sim
Count max S1, S 2
(1) Equation (1) computes similarity between the processed sentences (S1, S2) as the ratio of Count value, to the maximum among the lengths of given sentence pair. For illustration consider two sentences S1 and S2.
S1:43 कह ुएसचिनतंद िुकरज्मददनम ुबारकहो ,द िजएबधाई| S2:किकटकभगवानसचिनकोज्मददवसम ुबारकहो , द िजएबधाई| The sentences after doing tokenization, POS tagging, pruning, stop word removal and stemming are given below. The procedure is same as explained in subsection 2.1.1.
[43(CD),सचिन (NNP),तंदिुकर (NNP),ज्मददन ( NNP),मुबारक (NNP),द
ज(VP), बधाई(NN)] [किकट (NN),भगवान(NNP),सचिन (NNP),ज्मदद व स(NNP),मुबारक (NNP), द (जVP), बधाई(NN)] In these sentences, each word in S1 in checked for its presence in S2. If word is not present, then synonym checking is done. In the given example, 4 exact matches are found, viz., सचिन ,मुबारक ,द
जand बधाई. One word is identified as synonym; viz. ज्मददवस is a synonym of ज्मददन . Thus the count value 1http://www.nltk.org/ 2http://wordnet.princeton.edu/ will be, Count =5. The similarity is computed using Equation (1) which will be:=5/(max(7,7)=0.7142.
The similarity output obtained is considered as the feature input from a sentence pair. This is the input to machine learning classifier.
Machine learning (ML) based classifiers are used for the paraphrase identification task. The similarity score which is the feature input is fed to the classifier and classification task is done. In the proposed work, different classifiers are tested and the best among them is selected based on accuracy.
Using the training data, initially training phase is implemented. This is followed by testing, where decision making is done. Decision is made on whether a given sentence pair is paraphrased or not in Task-1. In Task-2,multi-class classification is done to decide whether the sentence pair is paraphrased, semi-paraphrased or non-paraphrased.
Section 3 describes the data statistics used in evaluation (training and test data) and the evaluation measures.
In DPIL,Task-1 provides 2500 sentence pairs for training. The sentences are labeled as either paraphrased (P) or NonParaphrased (NP). The set include 1000 instances for P class and 1500 instances for NP class.Task-2 provides 3500 sentence pairs out of which 1000 are paraphrased (P), 1000 semi paraphrased (SP) and 1500 non-paraphrased (NP). Our main focus was Task-1 while we implemented the same model for Task-2 as well. The feature input is the semantic similarity computed, i.e., sim , using Equation (1). Result evaluation is carried out using the classification measures, viz., recall, precision, F-measure and % accuracy.
P P
Confusion matrix is mainly used to evaluate classification problems. The true positives (TP), false negatives (FN), true negatives (TN) and false positives (FP) are obtained from this matrix. General confusion matrix for binary class problem is shown in Equation (2). In the proposed work, TP indicates the number of paraphrased documents correctly classified as paraphrased. FN indicates the number of paraphrased documents misclassified as non-paraphrased. TN is the number of nonparaphrased documents correctly classified as non-paraphrased and FP indicates the number of non-paraphrased documents misclassified as paraphrased. The total population is computed using Equation (3). Accuracy is measured using Equation (4) which is the fraction of number of correctly classified instances to the total number of instances in the population. Precision, Recall, and F-measure are computed using Equation (5), (6) and (7) respectively. Recall is defined as the number of correctly classified documents to the actual number of correct documents to be identified with respect to a particular class. Precision is defined as the number of correctly classified documents to the total number of documents identified as belonging to that class by the system. F-measure defines the harmonic mean of precision and recall.
Receiver Operating Characteristic Curve (ROC) is also plotted for better understanding. ROC curve plots sensitivity Vs 1-specificity. Sensitivity is same as recall or true positive rate (TPR) while specificity is the true negative rate (TNR) which is defined by the fraction of documents correctly rejected to the total number of documents to be rejected. 1-specificity is termed fall-out, which is the false positive rate (FPR) defined as the fraction of documents misclassified or incorrectly rejected to the total number of documents to be rejected.ROC curves help us to understand the discriminative power of the classifier. Using these measures, the performance of proposed approach is evaluated over Task-1 and Task-2.
Initially the proposed approach is evaluated using different classifiers in Weka. Weka3 is an open source machine learning suite. The accuracy obtained using 10 fold cross-validations over Task-1 ad Task-2 by the tested classifiers is reported in Table 3.It is observed that decision tree exhibits the maximum accuracy in both tasks. Thus for further evaluations decision tree is considered. The Weka implementation of C4.5 decision tree, viz., J48 is used in proposed work.
For better understanding, the ROC curves obtained using J48 onTask-1 and Task-2 is also plotted.Figure.2 and 3 plots the ROC curve for class P in Task-1 and Task-2 respectively. From Figure 2 and 3, it is observed that area under ROC curve (AUC) is 0.9 and 0.799 respectively for Task-1 and 2. The values show that the J48 classifier is able to discriminate the classes significantly in Task-1 and it is not so low in Task-2. 3http://www.cs.waikato.ac.nz/ml/weka/
NP
Compared to the training results, during the testing phase, our results exhibited significant variation. Figure 4 plots the test results obtained using the proposed approach. Test results presented a considerable drop. In contrast to the 90.52% accuracy (Task-1) on training set, test set presented only 35.88% accuracy. Similar drop is noted in Task-2 also (Run-1 in Figure 4). On rechecking the submission, we found that the results were submitted wrongly. In Run-1 submission, the first sentence pair was not written to the final output file and hence making the second pair as first, third as second etc. and thus completely altering our results.
On request to DPIL, our results were reevaluated. The results of Run 2 are the final results of proposed approach. It is observed from Figure 4, that an accuracy of 89% in Task-1 and 66.6% in Task-2 is obtained on test sets for Run-2. This matches the training results also.
The proposed approach was originally developed for plagiarism identification and classification in English language. The results obtained in Task-1 reflect the potency of our model to be extended to other languages also. Task-2 can be further improved by extracting significant features and using advanced NLP techniques.
In the proposed approach natural language processing techniques and semantic similarity computations are used to classify a Hindi sentence pair as paraphrased or not. Part of speech tagging is used for comparing only relevant tags within each sentence pair. A semantic similarity metric is employed which extracts the word synonyms from WordNet to check whether the compared words are synonyms or not. This facilitates in detailed analysis and comparisons and helps in unmasking paraphrasing imposed by synonym replacements. The metric as a whole helps in detecting and classifying paraphrased and non-paraphrased sentence pairs effectively. In future, deeper natural language processing techniques and intelligent computing techniques can be explored. These advanced techniques are very less explored in Indian language paraphrase detections.