Comparison of Greedy and Optimal Assessment of Natural Language using word-to-word Similarity Metrics

Introduction:

This article covers the comparison of optimal approach and greedy approach for assessing of natural language student input in dialogue based tutoring systems.  
Consider a instance below from experiments with AutoTutor (a dialogue based tutoring system):

Expert Answer : Expectation
Student Input : Contribution

To check contribution is similar to expectation or not.If yes, system should return positive feedback else system should return negative feedback.

Optimal Approach:

Well known combinatorial optimization problem , known as Sailor Assignment Problem or simply known as Assignment Problem.

In Assignment problem, we are given n jobs/tasks and k employees and experience(maximization problem) or salary(minimization problem) of ith employee for performing jth task  where i = 1,2,......,k and j  =1,2,.......,n

(weight matrix).

Two variants of problem:

We have to assign employees to jobs such that:

1) Maximization Problem

When we are given experience of each employee and we want to assign most experienced employee among the qualified employees for a particular task.

2) Minimization Problem

When we are given salary of each employee and we want to assign employee with least salary among qualified employees for a particular task.

Solution of Assignment problem: The Hungarian Algorithm

For reference:

Same variant of maximization problem of Hungarian algorithm could be applied

on word-to-word similarity metrics. Here, employees and tasks are replaced by words from two sentences to be compared and the element of weight matrix wxy is the similarity between word x and word y.

Greedy Approach:

Principle of Compositionality:
In mathematics and semantics, the principle of compositionality states that the meaning of a complex expression is determined by the meanings of of its constituent expressions and the rules used to combine them.Simply stating, the meaning of longer texts can be composed from the meaning of their individual words.

Based on compositionality principle, the similarity between two texts is composed in a simple additive manner from individual similarities between pair of words.

The greedy approach can be summarized in steps:

1) After pairing of each word of text T1 with every word of text T2, similarity scores are computed. Then, exclusive pairs of similar words(i.e. having max similarity score) are added to set S.
2)  The similarity of text T1 and T2 is simply additive or weighted sum of similarity scores of pairs present in set S.
3) Normalize computed sum with weighted length of original texts. Ways of normalizing: Dividing to the longest text, or dividing to the average length of two texts.

Drawback:
Greedy approach does not aim to get global maximum  similarity score.

Example to see difference between greedy and optimal approach:

Here, we have two sentence fragments and word-to-word similarity scores of word pairs across sentences (Bold lines show optimal pairing)
Greedy method would pair motion with motion(max similarity score 1.00),then pair speed with acceleration (similarity score 0.69)
So total similarity score before normalization by greedy approach: 1.69
Whereas optimal matching would yield a score of 0.75(pair motion with speed)+ 0.95(pair acceleration with motion) = 1.70    

Explanation: How Hungarian algorithm would give optimal pairing:  

Conclusion:

Optimal assessment obviously provide better performance in terms of accuracy as compared to greedy approach and other baseline methods.  

References:

1)  https://aclweb.org/anthology/W/W12/W12-2018.pdf
2)  https://www.topcoder.com/community/data-science/data-science-tutorials/assignment-problem-and-hungarian-algorithm/
3)  https://www.aaai.org/ocs/index.php/FLAIRS/FLAIRS12/paper/viewFile/4421/4801