This paper presents a report on Detecting Paraphrases in Indian Languages (DPIL), in particular the Tamil language, by the team NLP@KEC of Kongu Engineering College. Automatic paraphrase detection is an intellectual task which has immense applications like plagiarism detection, new event detection, etc. Paraphrase is defined as the expression of a given fact in more than one way by means of different phrases. Paraphrase identification is a classic natural language processing task which is of classification type. Though there are several algorithms for paraphrase identification, reflecting the semantic relations between the constituent parts of a sentence plays a very important role. In this paper we utilize sixteen different features to best represent the similarity between sentences. The proposed approach utilizes machine learning algorithms like Support Vector Machine and Maximum Entropy for classification of given sentence pair. They have been classified into Paraphrase and Not-a-Paraphrase for task1 and Paraphrase, Not-a-Paraphrase and Semi-Paraphrase for task2. The accuracy and performance of these methods are measured on the basis of evaluation parameters like accuracy, precision, recall, f-measure and macro f-measure. Our methodology got 2nd place in DPIL evaluation track.
Variability of semantic expression is a fundamental phenomenon of natural language where in the same meaning can be expressed by, or inferred from, different texts. Paraphrases are alternative ways to express or convey the same information. One can express a single event in many different ways in natural language sentences which depends on the command of the language the writer or speaker has on the language in consideration. A properly written paraphrase expresses the ideas of a fact or event in words and sentence structure inherent to the writer or speaker. It is similar to summarization but the key difference is that paraphrases include both key points and sub-points. Because a paraphrase includes detailed information it can sometimes be as long as the original source. A paraphrase typically explains or clarifies the text that is being paraphrased. This greatly adds to the difficulty of detecting paraphrases Paraphrase detection is the task of determining whether two or more sentences represent the same meaning or not [1]. Paraphrase detection systems progress the performance of a paraphrase generation by choosing the best sentence from the list of paraphrase sentences. Plagiarism detection is another task which needs the paraphrase identification technique to detect the sentences which are paraphrases of others. Identifying paraphrases is an important task that is used in information retrieval, question answering, text summarization and plagiarism detection. This work mainly focuses on the detection of paraphrases in Tamil language. For example, the sentences in Table 1 express the same meaning therefore, they are paraphrases.
Table 1 Sample Sentence in Tamil Language கேரளமாநில ்திு ்ூி்ூட்மாணி்ே் கோயி்திுவிழாுவ ்.ேியு ூட்மாணி்ே்
கோயி்திுவிழாகோலாே லமாேுவ
்ேிய.ு Our proposed system utilizes two supervised machine learning approaches using a Support Vector Machine (SVM), Maximum Entropy (ME) and learns classifiers based on sixteen features like lexical and POS tagging features in order to detect the paraphrase sentences. The structure of the report is defined as follows: Section-2 describes literature review. Section-3 gives the task description Section-4 represents the overview of the proposed system. Section-5 presents the performance evaluation results and Section-6 concludes the work.
In this section, recent research work carried in the field of
paraphrase identification in general, and paraphrase identification
in Tamil language in particular is discussed. Many researchers on
paraphrase identification make use of existing Natural Language
Processing (NLP) tools to identify paraphrases. [2] exploits the
NLP tools of a QA system to identify paraphrases. [3-6] have
employed lexical semantic similarity information based on
resources such as WordNet [7]. Tamil paraphrase detection is
tried with deep learning method [
The ability to identify paraphrase, in which a sentence express the same meaning of another one but with different words, has proven useful for a wide variety of Many different natural language processing applications are there for detecting paraphrases. The different approaches can be categorized into supervised methods, i.e. [8-9], which are the most promising methods.
Most of the existing system utilizes thresholds to determine whether two sentences are similar and represents the same meaning. But the specification of exact threshold will depends up on the training data. Machine Learning (ML)techniques have been applied in order to overcome the problems in setting the threshold. The benefit of applying the ML approach resides based on the morphologic, syntactic, semantic features of a sentence. In general, supervised and unsupervised machine learning techniques are quite useful in paraphrase detection. In supervised learning technique, the dataset is labeled and trained to obtain a reasonable output which help in proper decision making. Unlike supervised learning, unsupervised learning process does not need any label data; therefore they cannot be processed easily. This report work presents the impact of two supervised learning methods on given dataset.
One of the most commonly used corpora for paraphrase detection
is the Micro Soft Research in Paraphrase (MSRP) corpus [
The training data set given to us is the News Corpus, which
contains 2,500 Tamil sentence pairs for subtask1 and 3,500 Tamil
sentence pairs for subtask2. The test set given to us consisted of
900 Tamil sentence pairs for subtask1 and 1,400 Tamil sentence
pairs for subtask2. Both the training and test corpus are available
at the link specified in [
Subtask1 and subtask2 datasets are processed using Tamil shallow
parser. The processed results are in text format; but for
classification of sentences using the machine learning algorithms,
the text values are converted into numerical matrix, which is then
given as input into SVM and ME for further classification.
SVM: Given data are analyzed and decision boundaries are
defined by having hyper planes. In two category case, the hyper
plane separates the document vector of one class from other
classes, where the separation is maintained to be large as possible
[
ME: The training data are used to set constraint on conditional
distribution [
Shallow parsing also called as chunking or light parsing is an
analysis of a sentence which first identifies basic parts of
sentences such as nouns, verbs, adjectives, etc., and then links
them to higher order units that have discrete grammatical
meanings. While the most elementary chunking algorithms simply
link constituent parts on the basis of elementary search patterns,
approaches that use ML techniques can take contextual
information into account and thus compose chunks in such a way
that they better reflect the semantic relations between the basic
constituents. That is, these more advanced methods get around the
problem that combinations of elementary constituents can have
different higher level meanings depending on the context of the
sentence. The proposed system utilizes Tamil Shallow parser
developed by IIIT [
poslcat="NM" head="இ்ு"
case_name="nom" name="இ்ு"
case_name="nom" head="இ்கரா"
case_name="nom" name="இ்கரா" case_name="nom" <fsaf='ொதகை,n,any,sg,any,d,0,' paradigm="n2"> <fsaf='ுதி,யadj,any,any,any,,,' paradigm="adj"> <fsaf='ொதகை,n,any,sg,any,d,0,' paradigm="n2"> head="ொதகை"
case_name="nom" name="ொதகை" case_name="nom" <fsaf='பகட,v,n,sg,3,,்ு_உ்_்,wwu_ulY_lY_awu' head="பகட்ு்ள"ுtense="PRESENT" paradigm="v11" finite="Y"> <fsaf='பகட,v,n,sg,3,,்ு_உ்_்,wwu_ulY_lY_awu' name="பகட்ு்ள"ுtense="PRESENT" paradigm="v11" finite="Y"> vbp="Y" vbp="Y" SYM <fsaf='˙ ,punc,,,,,,'>
From the output of shallow parsing process, feature file is constructed both for training and test datasets for subtask1 and subtask2. Sample feature file is presented in Table 3
When supervised machine learning algorithms are considered for
classification purpose, the input dataset is desired to be a labeled
one. In this study, two different supervised learning techniques are
applied for classification purpose such as SVM and ME.
Classification of sentences may be categorized into two types, i.e.,
binary sentence classification and multi-class sentence
classification [
SVM is based on the structural risk minimization principle from computational learning theory. This method analyzes data and defines decision boundaries by having hyper-planes. In binary classification problem, the hyper-plane separates the given vector in one class from other class, where the separation between hyperplanes is desired to be kept as large as possible. One property of SVM is that their ability to learn can be independent of the classified as not paraphrase by the classifier, whereas False Negative are not paraphrase sentences but classifier classify it as paraphrase. Table 5 and Table 6 represents confusion matrix for sub task 1 sentences and sub task 2 sentences.
Table 5 Confusion Matrix for Subtask1 Sentences
SP NP 420 106 NP 514 44 87
P 43 131 99 NP 409 117 NP 499 51 95
P
47
113
113
dimensionality of the feature space. SVM measure the complexity
of hypotheses based on the margin with which they separate the
data, not the number of features [
ME is a general technique for estimating probability distributions from data. The over-riding principle in maximum entropy is that when nothing is known, the distribution should be as uniform as possible, that is, have maximal entropy. Labeled training data is used to derive a set of constraints for the model that characterize the class-specific expectations for the distribution. Constraints are represented as expected values of “features” any real-valued function of an example. The improved iterative scaling algorithm finds the maximum entropy distribution that is consistent with the given constraints.
Due to the minimum assumptions that the ME classifier makes, we regularly use it when we don’t know anything about the prior distributions and when it is unsafe to make any such assumptions. Moreover ME classifier is used when we can’t assume the conditional independence of the features. This is particularly true in text classification problems where our features are usually words which obviously are not independent. The ME method requires more time to train comparing to Naive Bayes, primarily due to the optimization problem that needs to be solved in order to estimate the parameters of the model. Nevertheless, after computing these parameters, the method provides robust results and it is competitive in terms of CPU and memory consumption. In our text classification scenario, maximum entropy estimates the conditional distribution of the class label given pair of sentences. Entire document is represented by a feature file. The labeled training data is used to estimate the expected value on a class-byclass basis.
The parameters which are helpful to evaluate performance of supervised machine learning algorithm is based on the element from a matrix known as confusion matrix or contingency table. It is used in supervised machine learning algorithm to help in assessing performance of any algorithm. From classification point of view, terms such as “True Positive”(TP), “False Positive” (FP), “True Negative” (TN), “False Negative” (FP) are used to compare label of classes in this matrix as shown in Table 4. In Table 4, True Positive represents the number of sentences those are paraphrase and also classified as paraphrase by the classifier, where as False Positive indicates paraphrase sentences, but classifier does not classify it as paraphrase. Similarly, True Negative represents the sentences which are not paraphrase also In SVM method, out of 900 sentence pairs, 409 NP sentences are correctly classified as NP sentences and 129 NP sentences are misclassified as P sentences. Similarly, 245 sentences are correctly classified as P sentences and 117 P sentences are misclassified as NP sentences. We believe that this misclassification is mainly due to higher lexical similarity in false paraphrase pairs, which makes them hard to be differentiated from true paraphrase pairs. In ME method, out of 900 sentence pairs, 420 NP sentences are correctly classified as NP sentences and 120 NP sentences are misclassified as P sentences. Similarly, 254 sentences are correctly classified as P sentences and 106 P sentences are misclassified as NP sentences. The ME system performs fairly well compared to SVM method at identifying true paraphrase pairs, as given in Table 5for sub task 1 and Table 6 for sub task2.
Based on the values obtained from confusion matrix, other parameters such as “precision”, “recall”, “f-measure”, and “accuracy” are found out for evaluating performance of any classifier. •Precision:
It measures the exactness of the classifier result. It is the ratio of number of examples correctly labeled as paraphrase to total number of paraphrase sentences in sub task1 dataset. It can be calculated using the equation 1.
=
TP
TP+FP
It measures the completeness of the classifier result. It is the ratio of total number of paraphrase sentences to total sentences which are truly paraphrase. It can be calculated using the equation 2.
=
It is the harmonic mean of precision and recall. It is required to optimize the system towards either precision or recall, which have more influence on final result. It can be calculated using the equation 3.
− = 2 ∗
Pecii∗Recall Pecii+Recall (3) The tables 7 and 8 represent Precision, Recall and F-Measure summary for sub task 1 and sub task2 in identifying paraphrase and not a paraphrase sentences. In Table 7 SVM-NP stands for SVM used for identifying Not Paraphrase (NP) sentences and SVM-P stands for SVM used for identifying Paraphrase (P) sentences. Similarly ME-NP stands for ME used for identifying Not Paraphrase (NP) sentences and ME-P stands for SVM used for identifying Paraphrase (P) sentences. The results show that precision, recall and F-Measure values are high for Non Paraphrase identification by both SVM and ME systems. In Table 8, SVM-SP stands for SVM used for identifying Semi Paraphrase (SP) sentences and ME-SP stands for ME used for identifying Semi Paraphrase (SP) sentences. The results show that both the systems identify sentences in the order NP, SP and P.
It is the most common measure of classification process. It can be calculated as the ratio of correctly classified sentences to total number of sentences. It can be calculated using the equation 4. The comparative analysis based on results obtained using proposed approaches are shown in Table 9. It can be analyzed that the accuracy obtained using ME method is better than that of SVM because of dependent feature and also high dimensionality and sparseness of text data.
This work makes an attempt to classify given sentence pairs into paraphrases or not using two supervised machine learning algorithms, such as SVM and ME. In this paper we utilize sixteen different semantic features to best represent the similarity between sentences. Two machine learning algorithms such as Support Vector Machine and Maximum Entropy have been considered for classification of given sentence pair into Paraphrase (P)and Not-aParaphrase(NP) for task1 and Paraphrase(P), Not-aParaphrase(NP) and Semi-Paraphrase (SP) for task2. The accuracy and performance of these methods are measured on the basis of parameters such as accuracy, precision, recall, f-measure and macro F-measure. The results show that ME method outperforms than SVM to identify paraphrases.
[1] Qayyum, Z., and Altaf, W. 2012. Paraphrase Identification using Semantic Heuristic Features, Research Journal of Applied Sciences, Engineering and Technology, 4(22) (pp.4894-4904). [2] Duclaye, F., Yvon F., Collin O., and Cedex L. 2002. Using the Web as a Linguistic Resource for Learning Reformulations Automatically. In proceedings of the Third International Conference on Language Resources and Evaluation (pp.390-396). [3] Finch, A., Hwang, Y., and Sumitha, E. 2005. Using Machine Translation Evaluation Techniques to determine Sentencelevel semantic Equivalence. In proceedings of the Third International Workshop on paraphrasing (pp.17-24). [4] Mihalcea, R., Corley and Strapparava C.2006. Corpus-based and Knowledge-based Measures of Text Semantic Similarity. In proceedings of 21st National Conference on Artificial Intelligence, Vol:1 (pp:775-780). [5] Fernando, S., and Stevenson, M.2008. A semantic similarity approach to paraphrase detection. In proceedings of 11th Annual research colloquium of the UK special interest group for computational linguistics (pp.45-52). [6] Malakasiotis, P. 2009. Paraphrase recognition using machine learning to combine similarity measures. In proceedings of