XKCD and simplification.

I have been an avid reader of the webcomic xkcd since my days as an undergrad.  If you've never heard of it, I would recommend you check it out, some of them are laugh-out-loud funny.  There are several comics that stick out as having a simplification theme.  I'm going to use this post to look at those comics through the lens of automatic simplification.  I'll try to explain what we can do with the current technology and what we just plain can't.

Simple

Particle accelerators are complex beasts.  I can empathise with the character who read so much simple Wikipedia that he can only talk in that way now.  One of the techniques we use in simplification is language modelling.  A mathematical model of sentences is trained which can be used to score new sentences to say how likely they are to have been produced by a language.  So for example:  "I went to the bank" might recieve a higher score than "I to the banking place did go".  As the latter sentence is poorly written.  An interesting factor of language models is that the scores they give rely heavily on the sentences which are used to train them.  So if you train a model using the text of the English Wikipedia you are likely to get very difficult to understand language.  If you train a model using the text of Simple Wikipedia, you are likely to get very simple sounding language, just like the second character in this comic.  A great paper which explains this further (without the xkcd references) is Kauchak (2013) (see the lexical simplification list).

Up Goer Five

This next one is too long to put in this post - but it's worth a read.  The full comic is here: Up Goer Five (Or, right click on the image and open it in a new tab to view).

The comic presents a simplified blueprint of the Saturn V rocket.  The translator has been restricted to only the thousand most common words in the English language.  There is some question as to where the statistics for the 'thousand most common words' came from.  If it were taken from NASA technical rocket manuals then there may have needed to be little change!  We'll assume that it was taken from some comprehensive resource.  The best way of determining this with currently available resources would be to use the top ranked words in the Google Web1T corpus (Google counted a trillion words and recorded how often each one occurred.)

The style of translation in this comic is phenomenally difficult to achieve, even for humans.  You can try it for yourself at The Up-Goer Five text editor.  Most words have been substituted for simpler phrases, or explanations.  Some technical terms rely on outside knowledge - which actually has the effect of making the sentence more difficult to understand.  For example, one label reads: "This is full of that stuff they burned in lights before houses had power".  This is referring to kerosene, which is highly understandable if you know of kerosene but inapproachable if not.

It would be an interesting experiment to determine the lowest number of words required to be able to produce this kind of simplification without having to draw on inferred knowledge (such as the type of fuel lights once burned).  My guess is that you would need 10 - 20,000 before this became a reality.  It would be difficult to automatically produce text at this level of simplicity.  Explaining a concept requires a really deep understanding and background knowledge, which is difficult to emulate with a machine.

Winter

The above comic touches on an excellent point.  If the words we use are understandable, does it matter if they're not the correct words? Previously, I have written about lexical complexity noting that many factors affect how difficult we find a word.  The big factor that is played on here is context.  For example the term 'handcoats' in the second panel is understandable (as gloves) because we know from the first panel that 'the sky is cold'.  Handcoats is a word that you've probably never seen before, and out of context it would be difficult to get the meaning.  This highlights the importance of selecting words which fit the context of a sentence. If the correct context is chosen and a simple word fitting that context is used, then the understandability of a sentence will be dramatically increased.

Word Sense Disambiguation

Some words have more than one meaning.  The brain seems to have an innate ability to work out what a sentence means.  Take the following two sentences:

"I tied my boat to the bank"

"I put my money in the bank"

In the first sentence the you probably imagine somebody tying their boat to the side of a river, yet in the second sentence you imagine somebody investing their money with a financial institution.  That string of four characters: 'b a n k' has completely changed meaning.

Word sense disambiguation (WSD) is a well researched task in computational linguistics with an important application to lexical simplification.  The majority of previous research splits roughly into three categories:

• Supervised: Using labelled data, a system builds a classifier which can recognise the different senses of a word, from a variety of features in the words surrounding it.
• Unsupervised: With unlabelled data, a system learns the different senses of a word.  Classification of new data makes use of the previously learned senses.
• Knowledge Based: A large knowledge resource such as WordNet provides information about the words which can be used during disambiguation.

 WSD is vital to the task of lexical simplification.  Consider simplifying a sentence from the previous example. If you look up the word 'bank' in a thesaurus you will have a list of synonyms that looks something like the following:

Bank:
Financial Institution; Treasury; Safe;
Edge; Beach; Riverside;

If a system does not employ WSD, then there is no method of telling which of the synonyms are correct for the context.  We do not wish to say "I tied my boat to the treasury", or "I put my money in the riverside".  These examples are at best farcical and at worst nonsensical.  WSD is paramount to selecting the correct set of synonyms.

I will not venture to a full explanation of WSD as applied to lexical simplification.  Suffice to say that there are four papers which I have so far identified as addressing the matter.  These can be found in the lexical simplification list.

• Can Spanish be simpler? LexSiS: Lexical simplification for Spanish. Bott et al. 2012
• Wordnet-based lexical simplification of a document. Thomas and Anderson 2012
• Putting it simply: a context-aware approach to lexical simplification. Biran et al. 2011
• Lexical simplification. De Belder et al. 2010

3rd Year

On Wednesday (4/9/2013) I successfully completed my end of second year interview.  This means that I am now officially a third year PhD student.  I am now at the dead halfway point of my PhD, having completed 24 months with 24 more remaining.  It has been a long road getting here and there is still a long way to go.  Below is a brief analysis of the achievements in my PhD so far and the goals yet to come.

Completed So Far:

• Literature Review:  This was the first thing I did as a PhD student.  Reading took up most of the first six months of my research.  I consumed, refined and categorised as much of the relevant literature as I could find.  I am attempting to publish this as a survey paper currently, since the only available text simplification survey is a technical report from 2008
• Lexical Simplification Errors: I recently undertook a pilot study looking at the errors thrown up by the lexical simplification pipeline.  I'm looking to publish this in an upcoming conference, so won't say too much about the results here and now.
• Complex Word Identification: This was the first element of the lexical simplification pipeline that I studied.  I built a corpus of sentences, each with one word marked as complex for the purpose of evaluating current methods of identification.  This work was published in 2 separate workshop papers at ACL 2013.
• Substitution Generation: Once we have identified a complex word, we must generate a set of substitutions for it.  However, those words which are complex are also those which are least likely to be found in a thesaurus, complicating the task.  To address this I spent considerable efforts learning simplifications from massive corpora with some success.  This work is also currently being written up for publication.

Still to come:

• Word Sense Disambiguation: The next step in the pipeline is to apply some word sense disambiguation.  This has been done before, so I will be looking at the best ways to apply it and hopefully making a novel contribution here.  I am just starting out on this phase of research and am currently immersed in the WSD literature, trying to get my head round the myriad techniques that already exist there.
• Synonym Ranking: I have looked into the best way to rank synonyms according to their complexity before at the start of my project.  The small amounts of work that I did back then did not discover anything radical, but did help me to better understand the structure of a lexical simplification system.  When I revisit this area it will be with the hope of making some significant contribution.  I was really interested in the work David Kauchak presented at ACL 2013 and will be interested to explore what more can be done in this area.
• User Evaluation: Finally, I will spend some time exploring the effects of each of the modules I have developed on individual users.  It is of paramount importance to evaluate text simplification in the context of the users it is aimed at and to this end I will be focussing my research on a specific user group.  Although which group is as yet undecided.
• Thesis: This will undoubtedly take a significant portion of my final year.  The chapter titles will hopefully be the bullet points you see listed above.

So there you have it.  Although it appears that I have done a lot so far, it still feels like I have a real mountain to climb.  There are significant hurdles and vast amounts of reading, researching and writing ahead.  I look forward to the challenges that the next two years of my PhD will bring.

Lexical Simplification: Background

My PhD work is concerned with a process called lexical simplification.  I'm interested in how natural language processing can be applied to make documents easier to read for everyday users.  Lexical simplification specifically addresses the barriers to understandability provided by the difficult words in a text.

For example, take the following sentence:

The workers acquiesced to their boss' request.

It is fairly clear that the rarely used verb 'acquiesce' is going to cause understandability issues here.  Do you know what it means?  Maybe in a wider context you could guess the meaning, however here it is fairly difficult to work out.  Lexical simplification deals with sentences such as the above and attempts to process them into more understandable forms.  There are several stages to the lexical simplification pipeline.  I intend to devote an entire post to each one of these as I continue, however for now, it should be sufficient to give an overview of each one.

The first stage in any lexical simplification system is complex word identification.  There are 2 main approaches to this.  Firstly, systems will attempt to simplify every word and those for which simplifications can be found are transformed, those which cannot be transformed are left.  Secondly, some form of thresholding is applied.  There are various measures of lexical complexity - which often reside heavily in word frequency.  Some threshold may be applied to one of these measures to determine between complex and simple words.  One of the major issues in this field is the lack of evaluation resources.  I have a paper on this topic accepted at the ACL student session 2013,  so will write more at that time.

If we assume that we can get lexical complexity values of:

worker:	300
acquiesce:	5
boss:	250
request:	450

If we also assume that our threshold (which is set on some training data) is somewhere between 5 and 250 then we have an indicator that 'acquiesce' is a difficult word.

The next step, once we have identified this complex word is to generate a set of synonyms which could replace it.  This is typically done with a thesaurus such as WordNet.  This could give us some of the following replacements for acquiesce.

Acquiesce: accept, accommodate, adapt, agree, allow, cave in, comply, concur, conform, consent, give in, okay, submit, yield

We must then process these to discover which will be valid replacements in the given context.  This third step is called word sense disambiguation.  This is necessary as a word will have typically have several senses, so some replacements will only be valid in certain contexts.  In the above example a word sense disambiguation step may look something like the following:

Acquiesce: accept, accommodate, adapt, agree, allow, cave in, comply, concur, conform, consent, give in, okay, submit, yield

Where words in green are those that would be valid replacements and words struck-through and in red are non-valid replacements.   This is somewhat subjective and remains an unsolved task in NLP.

The final step is to rank the resulting replacements in order of their simplicity.  The simplest will then replace the original word.  To do this we revisit our measure of lexical complexity from before.  For example if we have the following values for the remaining candidates:

accept:		550
agree:		450
cave in:		250
comply		35
conform		50
give in		350
submit		40
yield		20

 Then we would choose 'accept' as our replacement.  Giving the simplified sentence as:

The workers accepted their boss' request.

Which is a much more understandable sentence.

There are of course some nuances of the original meaning that are lost in this simplification, however this has to be accepted.  The understandability of the sentence is obviously dramatically increased.

My project is currently focusing on each of these stages individually.  The hypothesis is that by examining and optimising each stage in turn, it will be possible to improve the final simplification.  Work has already taken place in the first stages mentioned above and work will continue on the rest.

There is much more to lexical simplification than the basic outline presented above and readers wishing to know more should look to read the following publications:

Siobhan Devlin and John Tait. 1998. The use of a psycholinguistic database in the simplification of text for aphasic readers. Linguistic Databases, pages 161–173.

Or Biran, Samuel Brody, and No ́emie Elhadad. 2011. Putting it simply: a context-aware approach to lexical simplification. In Proceedings of the 49th Annual Meeting of the Asso- ciation for Computational Linguistics: Human Language Technologies: short papers - Volume 2, HLT ’11, pages 496–501, Stroudsburg, PA, USA. Association for Computational Linguistics.

Stefan Bott, Luz Rello, Biljana Drndarevic, and Horacio Saggion. 2012. Can spanish be simpler? lexsis: Lexical simplification for spanish. In COLING, pages 357–374. 

S. M. Alu ́ısio and C. Gasperin. Fostering digital inclusion and accessibility: the PorSimples project for simplification of Portuguese texts. In Proceedings of the NAACL HLT 2010 Young Investigators Workshop on Computational Ap- proaches to Languages of the Americas, YIWCALA ’10, pages 46–53, Strouds- burg, PA, USA, 2010. Association for Computational Linguistics. 

L. Feng. Text simplification: A survey, 2008.

L. Specia, S. K. Jauhar, and R. Mihalcea. Semeval-2012 task 1: English lex- ical simplification. In First Joint Conference on Lexical and Computational Semantics, 2012.