Two decades of statistical language modelling

Well, I think I began reading this in the lastweek of may. With lots of breaks, I completed it towards mid-june. With a second round of breaks, I am finally writing about it now

The title of the paper is: “Two decades of statistical modelling: Where do we go from here”
Author: Ronald Rosenfeld

Though I have been moving around with this phrase “statistical modelling” for almost three years now, it never appealed to me until some 3 months back. I don’t know why..perhaps, I dont want machines to “grow” I dunno. Coming to the paper, I felt it serves its purpose. It basically summarizes different statistical language modelling approaches and also points to future directions of research. Let me summarize the paper, the way I see it:

1. It started with an introduction to statistical language modelling – what does it mean etc. Well, to say in simple words, “Statistical language modelling” refers to “capturing the regularities in language for the purpose of improving the performance of various Natural Language applications.

2. Then, it gave examples of how statistical modelling is used in various natural language processing applications.

3. It was commenting on how “language models dont actually realize that they are modelling a language” and on how to “put language back in modelling”.

4. It gave a brief overview of various Statistical language modelling techniques, principles, measures to evaluate, common weaknesses etc.

5. It then pointed towards future models of language processing and then, discussed about the challenges of statistical language modelling for future

More than anything else, this paper is a wealth of references. At around the same time I began reading this, I was struggling with something, for which one of these references provided the answer.
Well, to conclude, I’d suggest that people MUST read it, if they are interested in statistical language modelling – Who am i to suggest, anyways? those who are interested might have read this already

And finally, some baatcheet : I was sitting in a hall 2 years back, listening to the same Roni Rosenfeld talking on “from natural language to language of life”, @Indian Institute of Science – wondering what the hell is all this? I don’t understand a bit!! I doubt if my peanut brain can understand that discussion even now, though

The paper can be accessed here.

పుస్తక భాండాగారాల వేటలో..

పుస్తకం.నెట్ కోసమని జూన్ నెలలో పుస్తకాల షాపులకు బానే తిరిగాము. ఆ తరువాత ఆన్లైన్ లో కూడా జల్లెడ పట్టడం మొదలుపెట్టాము. ఒక విధంగా, ఈ నెలలో చేసిన ఈ ఇంటర్వ్యూలు నాకు పూర్తి కొత్త అనుభవం. అసలు ఇవి ఎందుకు చేయాలనిపించింది? అంటే ఏం చెప్పేది? నాకు కథలు వినడం అంటే ఇష్టం. చదవడం అంటే కూడా ఇష్టమే కానీ, మనుషుల్ని కదిలించి, వారి నోటి నుండి వారి కథలు వినడం – నథింగ్ బీట్స్ ఇట్. 1997 లో మన స్వాతంత్ర్యం వచ్చి యాభై ఏళ్ళైనప్పుడు నాకు తెలిసిన అరవైల్లో ఉన్నవారినందరినీ ఇలాగే బగ్ చేసిన విషయం ఇంకా గుర్తుంది. సరే, మనం విన్న కథలే ఇంకా చాలా మందికి కూడా ఆసక్తికరంగా అనిపించవచ్చు అనిపించి – అలా ఈ ఇంటర్వ్యూలు చేయడం, మాటామంతీ కార్యక్రమంలో నేనూ భాగం పంచుకున్నాను.

హైదరాబాద్ నగరంలో చాలా ఏళ్ళుగా ఉన్న కదంబి, ఏ.ఏ.హుస్సేన్, విశాలాంధ్ర, అబిడ్స్ మార్కెట్ వారితో మాట్లాడటం చాలా మంచి అనుభవం అనే చెప్పాలి. ఎప్పుడూ షాపులకి వెళ్ళడం, పుస్తకాలు తీస్కోడం రావడమే కానీ, వాళ్ళ తరపు కథ వినలేదు. పుస్తకం.నెట్ నాకు ఆ అవకాశం కలిగించిందన్నమాట ఇన్నేళ్ళకి ఆమధ్య ఆఫీసు లో ఒక సంస్థ పిల్లల పుస్తకాల ప్రదర్శన పెట్టగానే, వాళ్ళతో కూడా మాట్లాడుతున్నప్పుడు పిల్లల పుస్తకాల ముద్రణ గురించి ఎన్నో సంగతులు తెలిసాయి. అలాగే, యూఎస్ లోని కాంటన్ పబ్లిక్ లైబ్రరీ గురించి రచ్చబండ గుంపులో అనుకుంటా, ఓ వేగు చదివి, దాని ద్వారా వారిని ఈమెయిల్ ఇంటర్వ్యూ చేయడం కూడా నాకు కొత్త అనుభవం. మళ్ళీ వాళ్ళ నుంచి వాళ్ళకి భారతీయ భాషల పుస్తకాలను పంపే డీకేఏజన్సీస్ వివరాలు కనుక్కుని వారితో కూడా సంభాషించడం – అక్కడ్నుంచి మళ్ళీ కొత్త సంస్థల గురించి తెలుసుకోడం – కొత్త ప్రపంచం కనిపించింది నాకు. నా చదువు, పని- ఇవి కాకుండా బయటి ప్రపంచంలో ఇంత మందితో ఇలా సంభాషించిన దాఖలాలు లేవు నాకు గత నాలుగైదేళ్ళలో.

పుస్తకం.నెట్ లో నేను పైన చెప్పినవి, మరికొన్నీ – ఇక్కడ చదవొచ్చు, నాలాగా మీకు జ్ఞాపకాల కబుర్లపై ఆసక్తి ఉంటే.

Automatic generation of Tamil lyrics for melodies

Paper details: “Automatic Generation of Tamil Lyrics for Melodies.”
Authors: Ananth Ramakrishnan A., Sankar Kuppan and Sobha Lalitha Devi

I was browsing through the schedule page of a workshop on: “Computational Approaches to Linguistic Creativity”, 2009. I came across this title – “Automatic generation of Tamil lyrics for melodies” and was quite fascinated by it. I am perennially suspicious about works on such sci-fi topics and their efficiency levels. Nevertheless, I was eager to read it. Back then, the workshop did not happen and the paper was not accessible for download. Now, it is, and I finally got a chance to have a look at it (Interested? download-here)

So, as the name indicates, this explains a system which generates lyrics for a given melody, automatically. They did this for Tamil. There was a kind of general overview of the process and a mention about related work. There was this reference to a work about a “poetry generation system” !! I was shocked to a considerable extent. Most of human poetry itself is unreadable and sometimes crappy. We think about Poetry generation! Man’s imagination indeed roams freely in thin air There was even this reference to some work on “lyric generation strategies” and I thought – “Oh! this is not sci-fi then, if so many are working in this direction!”

Coming to the paper, the process of lyric generation involves 2 steps:
1. Syllabic pattern generation
2. Identifying a phrase matching this pattern, as well as satisfying other word/sentence/rhyming requirements.

For the first part, they used a notation called KNM. K stands for Kuril-Short vowel, N for Nedil- Long vowel and M for Mei-Consonants. Taking their own example, the word thAmarai will be broken as “thA-ma-rai” and will be labelled as NKN. To generate such patterns for a given melody, they have used Machine Learning (specifically the Conditional Random Fields aka CRFs) to train a system to learn these patterns. The system was trained with sample film songs and their lyrics as input (and… I got doubts about the size of data they trained with..). This trained model is used to then label a given melody with a syllabic pattern. This pattern is then given to a sentence generation module which generates a sentence that satisfies the following conditions:
1. Words should match the syllabic pattern
2. Sequence of words should have a meaning.

This is like a baseline level work and they mention about the ways they plan to improve their system in future. They also plan to experiment more with different strategies as well as different domain data sets. Finally, they mention my “sci-fi” idea of poetry generation again
This is an extra brief summary about it. For more details, go on and visit it online.

సువ్వీ సువ్వీ సువ్వీ!

ఎందుకో గానీ, ఇవాళ పొద్దున్న ఆఫీసు చేరే దారి పొడుగుతా ఇదే పాట … ఇందులోని వాక్యాలూ పదే పదే గుర్తొచ్చాయి. మధ్య మధ్య -“నువ్వక్కడుండీ నేనిక్కడుంటే…ప్రాణం విలవిలా…నువ్వెక్కడుంటే నేనక్కడుంటే..మౌనం గలగలా…” అని గోపీ గోపిక గోదావరి పాట గుర్తొచ్చింది కానీ, వెంటనే… “ఆగక పొంగే కన్నీళ్ళే నీ ఆకలి దప్పులు తీర్చేనమ్మ” అన్న లైను క్షణానికోమాటు గుర్తొచ్చి మనసు పాడుచేస్తూ ఉండింది. “చి! పాడు పాట… ఇలా వెంటాడుతూ ఉందేంటి” అని విసుక్కున్నా కూడా, మళ్ళీ ఈ పాట వినడం మొదలుపెట్టాను. ఓ పక్క మనసు పిండేసింది కానీ, దీని గురించి రాయకుండా ఉండలేకపోతున్నా.

పాట యూట్యూబ్ వీడియో ఇక్కడ.

“గువ్వ మువ్వ సవ్వాడల్లె నవ్వాలమ్మ”
- అలా నవ్వడమెలాగో…నాకు తెలీలేదు కానీ, వాక్యం వినగానే పెదాలపై చిన్న చిర్నవ్వు. ఈ పార్టంతా ఇలా సాగిందా, ఇక అసలు కథ మొదలు…

“అండ దండ ఉండాలని కోదండరాముని నమ్ముకుంటే
గుండెలేని మనిషల్లే నిన్ను కొండ కోనల కొదిలేసాడా”
- ఈ వాక్యం విన్నప్పుడు మాత్రం, చాలా చలనం కలిగింది నాలో. అందులోనూ…రెండోసారి జానకి గారు పాడుతున్నప్పుడు – “గుండేలేని మనిషల్లే…” అని ఓ క్షణం ఆగినప్పుడైతే… మరీనూ. ఆ వాక్యాల్లోనే బాధ తెలుస్తోంది. ఇక అలా సగం చెప్పి ఆగడంలో … ఆ బాధ intensity ఇంకా బాగా చెప్పినట్లు అనిపించింది. అలా అలా ఈ పాటలో నన్ను వెంటాడిన మూడు లైన్లలో ఇదొకటి. అంటే, అక్కడి సందర్భంలో అతనేదో ఆలోచించక అది అనేస్తే, ఆ మాట ఆమెనెంత లోతుగా తాకిందో, అక్కడ ఆ బాధ చాలా బాగా తెలుస్తుంది ఆ దృశ్యంలో.

“అగ్గిలోన దూకి పువ్వు మొగ్గలాగా తేలిన నువ్వు
నెగ్గేవమ్మ ఒక నాడు నింగి నేల నీ తోడూ”
- “నెగ్గేవమ్మా ఒకనాడు..” అని జానకి గారు పలికిన తీరు ఆ పాత్ర అనుభవిస్తున్న బాధను ఎంత బాగా చెప్పిందో అనిపిస్తుంది నాకు. అంటే, రాధిక మొహంలోని దీనత్వం కూడాననుకోండి… “నింగీనేలా నీ తోడు”…. ఒంటరితనాన్ని ఎంత బాగా వర్ణించారో!

“చుట్టూ వున్న చెట్టు చేమ తోబుట్టువులింక నీకమ్మా”
- ఒంటరితనాన్ని చూపుతూనే, ప్రపంచంలో ఏ ఒక్కరూ ఒంటరి కారు అని చెప్పడమేమిటో! అసలీ వాక్యం మొదటిసారి పలికినప్పుడేమో ఒంటరి తనం నీది…అని జాలి చూపుతున్నట్లూ, రెండోసారి పలికినప్పుడు ధైర్యం చెబుతున్నట్లూ అనిపించింది..ఎందుకోగానీ.
“ఆగక పొంగే కన్నీళ్ళే నీ ఆకలి దప్పులు తీర్చేనమ్మ”
అబ్బా! ఆగక పొంగే కన్నీళ్ళే! – పాడిన పాత్ర మానసిక స్థితి వేరే రకానిదే కానీ, ఎంతైనా, అలా మొహం మీదే నీదో దురదృష్టపు బ్రతుకు… అంటూ ఉంటే, ఎలా ఉంటుందో వినడానికి నిజంగా కష్టాన్ని అనుభవించేవారికి!!

“పట్టిన గ్రహణం విడిచి
నీ బ్రతుకున పున్నమి పండే గడియ
వస్తుందమ్మా ఒకనాడు
చూస్తున్నాడు పైవాడు”
- లాస్ట్ కి మళ్ళీ ఓ ఓదార్పు! అతని లాంటి తెలిసీ తెలియని మనిషి మాట్లాడితే, ఇలాంటి వాక్యాల్లో ఎంత అమాయకత్వం కనిపిస్తుందో,
“వస్తుందా ఆ నాడు
చూస్తాడా ఆ పైవాడు”
- అని ఆమె నిరాశగా అన్నప్పుడు ఆమె నిస్సహాయతా, ఆమె పడుతున్న వేదనా అంత స్పష్టంగా తెలుస్తోంది…

అమ్మో! ఈ పాట నా గుండే పిండేస్తోంది ఇవాళ. అవే వాక్యాలు మళ్ళీ మళ్ళీ ఆ గొంతుకల్లో మ్రోగుతూనే ఉన్నాయి… నా చెవులకి ఎక్కడికెళ్ళినా వినిపిస్తూనే ఉన్నాయి…

పాట వివరాలు:
స్వాతి ముత్యం లో SPB, S.Janaki పాడిన పాట.
రచన: సినారె.
సంగీతం: ఇళయరాజా.

నిశ్యాలోచనాపథం-9

రాయకుండా ఉంటే నిద్రపోతున్నట్లు కాదు. ఆ మధ్య నాకు నాలాంటి ఓ నిశాచరితో పరిచయమైంది. సూర్యుడి మొహం కూడా చూడదట! ఎండకన్నెరుగని సుకుమారి అనుకునేరు! వెలుగు అన్నదొకటుందని కూడా ఒప్పుకోడం ఇష్టం లేనంత పెసిమిస్టు. అందుకే, చీకట్లోనే తిరుగుతుందంట ఎప్పుడూ. ఇంతకీ, మాకు పరిచయం ఎలా ఐందంటే, ఆ మధ్యోరోజు పంచరైన సైకిల్ని కూడా తొక్కుకుంటూ తిరిగే వెర్రిమొహంలాగా తిరుగుతున్నా చీకట్లలో. ఇంతలో ఎందుకో అనుమానమొచ్చింది ఎవరో వెంబడిస్తున్నారని. డిటెక్టివ్ బుర్ర ఉపయోగించలేదు కానీ, చెవులు కాస్త రిక్కించాను. అంతే.

సరే, కాసేపు అలా గమనిస్తూ ముందుకెళ్ళాక కొంత వీథి దీపం వెలుగు కనబడ్డది. వెలుగుంటే దయ్యాలు పారిపోతాయన్న సూత్రం ప్రకారం అది మనకి సేఫ్ ప్లేస్ అని, వెనక్కి తిరిగా (అయినా, యముణ్ణే భయపెట్టాం మనం! ఇవెంత?) చూస్తే ఏముందీ, నాలాగే ఇంకో అమ్మాయి. దాదాపు నా వయసే ఉండొచ్చేమో. కాకుంటే, నాలా కాక, కాస్త పద్ధతిగా ఉంది. నా కళ్ళు నిద్ర లేక ఎర్రగా ఉంటే, ఆమె ఇప్పుడే లేచినట్లు ఉంది. నా దారుల్లో నాకు మనుషులు ఇప్పటివరకూ తారసపళ్ళా. మీకూ తెలుసుకదా ఆ సంగతి.. (కాళ్ళు చూస్కున్నా లెండి. మనిషే ఇక్కడున్నది.)

“హలో, అయాం సో అండ్ సో” అని పరిచయం చేస్కున్నా.
“హలో, అయాం నిశీనిశ్” అని జవాబిచ్చి ఊరుకూందామే. అదేం పేరు? అనుకున్నాగానీ,
“ఏమిటండీ, మీరు ఈ సమయంలో…ఇలా… మీరూ ఇన్సోమ్నియా బాధితులా?” మరియాదగా అడిగాను.
“పీడకలలతో స్నేహం చేసి వాటి వెంటే నడుస్తూ పిచ్చిగా నవ్వాలనిపించింది. అందుకే ఇలా వచ్చాను” అంది.
“కెవ్వ్!” అనబోయి, ఆగాను. “ఏంటీ? ఏమైందీ? మనసు బాలేదా?” – ఈసారి ఏకవచనంలోకి దిగబోతున్నా అన్న హింట్ ఇస్తూ, కాస్త అనునయంగా అడిగాను.
“నా మెదడు తీసి ఎదుట పెట్టుకుని దానిలోని అలజడంతా కళ్ళారా చూసి, చెవులారా మనసు ఆర్తనాదాలు వినేసి, నోరార నవ్వుకుని – తరువాత పడుకోవాలనుంది.” అంది.
ఎర్రగడ్డ బాపతో ఏంటో! అనుకున్నా. వైజాగన్నా కావొచ్చేమో, రాత్రి కదా, సాధారణంగా ఏ దారన్నది నేను పట్టించుకోను. అయినా, ఏదో, సాటి మనిషి ఇలా మాట్లాడుతూ ఉంటే, మన మూడెలా ఉన్నా, కొంచెం ధైర్యం చెప్పాలని –

“అమ్మాయ్! కష్టాలు, నష్టాలు ఇవన్నీ వస్తూ ఉంటాయి, పోతూ ఉంటాయి. మనం కూడా శ్రీశ్రీ లాగా రానీ రానీ అని ముందూ, పోనీ పోనీ అని తరువాతా – అనుకుని వదిలేయాలి. అలా ఉంటేనే అవి మనముందు ఓడిపోతాయి” అన్నా – మనసులో నేనేవో కష్టాలనుకుని ఏడ్చుకున్న రోజులు జ్ఞాపకాలై నన్ను వెక్కిరిస్తున్నా కూడా. దానికి ఆమె -
“మనుష్యుల్ని, మనసుల్నీ, కష్టాల్నీ, కోపాల్నీ కాదు. జీవితాన్ని జయించాలనుంది నాకు.” అంది.
ఓహో… అలా కూడా అనిపించేసిందా? మనల్ని మించినట్లుంది, అనుకున్నా. ఎందుకోగానీ, అలా వదిలేసి పోబుద్ధి కాలేదు. అంటే, నేను మనుషుల్ని చంపేసే ఆలోచనలు మానేసా లెండి ఆ మధ్య. మామూలుగా మానవజాతికి శాంతియుతంగా మరమ్మత్తు చేద్దాం అనుకుంటున్నా.

ఏమో, ఏవో విషాదగాథలున్నాయేమో, అవి గుర్తొచ్చి నిద్రపట్టక ఇలా తిరుగుతోందేమో అని అనుమానమొచ్చింది. అంటే, ఉన్నా లేకున్నా నేను తిరుగుతూనే ఉంటాననుకోండి. కానీ, నేను స్పెషలన్నమాట. నాబోటి డేంజరస్ మనిషి ఇంకోళ్ళు ఉండరు అని నా ప్రగాఢ నమ్మకం.
“ఏదన్నా… గుర్తుకొస్తోందా?” అడిగాను.
“దిక్కులన్నిటా ఊడలు పెంచిన నా జ్ఞాపకాల ఉచ్చుల్లో బిగిసి ఊపిరాడక గిలగిలలాడాలనిపించింది. అడుతున్నాను.” అంది.
ఎంతైనా కూడా, ఇంత ఫిలోని భరించడం కష్టంగా ఉండింది నాకు. టాపిక్ మారుద్దామని… “ఏవమ్మా నిశీనిశ్, ఎవరు నువ్వసలు? ఈ తిరుగుళ్ళేంటి? ఆ మాటలేంటి?” అనేశా, ఉండబట్టలేక.

“నాకు చీకటంటే ఇష్టం. చిక్కగా, నల్లగా, ఎంత చక్కగా ఉంటుందో… ఎదురుచూపులు టాళలేక కరిగినీరౌతున్న నా కలల చిరునామా చీకటి. నిట్టూర్పుల నిరాశల నిశ్శహాయతల నిస్పృహల చితిని పేర్చి మండిస్తే మిగిలిన బూడిద నా చీకటి. ఈ బూడిదని పేర్చుకుని ఆడుకోడం, ఆ కన్నీరైన కలల్లో మునిగిపోడం -నిరంతరం చేయాలంటే, చీకట్లను వెదుక్కుంటూ తిరుగుతూనే ఉండాలి కదా…”
-ఆమె చెప్పుకుంటూ పోతోంది. పైన ఓ విమానం పోతూ ఉండింది. ఇక్కడంతా కూడా నా తలపైన్నుంచే వెళ్తోంది. వామ్మో టాపిక్ మారిస్తే ఇదో హింసా! అనుకున్నా. ఏం మాట్లాడాలో తోచక భయం భయంగా చూస్తూ ఉన్నా – దయ్యమే మనిషి రూపంలో వచ్చే పాజిబులిటీలు ఎంతున్నాయో రేప్పొద్దున్న గూగుల్ (సారీ, బింగ్) చేయాలి అని.

ఇంతలో, ఆమె ఏమిటో హడావుడిగా వాచి చూస్కుని, ఆకాశాన్ని చూస్తూ కంగారు పడడం మొదలెట్టింది. మనకా అలాంటోళ్ళని చూస్తే మహాసరదాకదా – “పద, అలా నడుస్తూ మాట్లాడుకుందాం” అంటూ, ఇహిహి అని ఓ సాడిస్టు నవ్వు నవ్వాను. “నేను వెళ్ళాలి” అంది మళ్ళీ ఆకాశం వంక చూస్తూ. “వెళుదువు గానీ. ఇప్పుడేగా పరిచయమైంది. కాసేపు కబుర్లు చెప్పుకుందాం” అన్నా…అప్పటిదాకా కలిగిన భయమంతా సాడిజం ఐంది ఇప్పుడు.

“ఉండవమ్మా! నువ్వూ నీ కబుర్లూ, నడకానూ… గుండు పాండురంగాన్ని మించేలా ఉన్నావ్!” విసుక్కుందామె.
“ఎందుకూ ఇంతకోపం? ఇంతసేపు ప్రవాహంగా చెప్పావ్ గా మాతలు?” అన్నా.
“చూడూ, నాకు వెలుగంటే అలర్జీ. నాకు వెలుగులన్నా, ఆశన్నా పరమ పరమ చిరాకు. అందుకే రెంటికీ దూరంగా ఉంటాను.” అంది. “అయితే?” అన్నా. “టైమైంది. వెళ్ళాలి.” అనేసి, జవాబు కోసమన్నా చూడకుండా వెళ్ళిపోయింది. కాసేపటికే మా ఇంట్లో శ్రీముఖాలతో నన్ను లేపడంతో నాకు అర్థమైంది ఆమె ఎందుకు వెళ్ళిపోయిందో.

అలా పరిచయమైందా… తర్వాత ఈ మధ్య నాలుగైదుసార్లు తగిలింది. ఫ్రెండ్సైపోయాం లెండి. ఆమె ఇంకా వెలుతురు చూడదు. అందుకే, నేనూ చీకటికి అలవాటుపడ్డా, తన స్నేహం కోసం. ఇదంతా రాయాలంటే వెలుతుర్లలో మెలుకువగా ఉండాలి కదా. అందుకని ఇంత టైం పట్టిందన్నమాట. మొత్తానికి interesting personality లెండి.

On Smoothing Techniques

I know, I am going beyond the scope of the way I wanted my blog to be when I began it. But, three years is a long time and thoughts run wild. I know, perhaps I am going beyond the scope of my readers’ expectations too. But, this is my only mouthpiece

I heard this name called: “Kneser-Ney Smoothing” the other day and got curious to know what it is. (To understand what Smoothing means, go to the wiki page here). When I did my introductory course in Natural language processing, I came to know about smoothing for statistical language modelling (in late 2006). Back then, as far as I remember, we read about only three things:
1. Add one smoothing
2. Turing estimation
3. Witten-Bell smoothing
- I ofcourse dont remember anything but the names, though :p

Okay, in my over-curiosity to know more about Kneser-Ney smoothing, I found this presentation on smoothing techniques in NLP by Bill MacCartney. Again, since I don’t need anything from this specifically, at the moment, I just browsed through the PPT to understand the gist of it. Heres what I learnt on different smoothing mechanisms:

1. Add-one smoothing is the simplest possible and least effective one – as the textbooks say.
2. There is something called Additive smoothing, which, from my understanding is similar to Add-one smoothing, except that here, its not add-1 but add-some number between 0 and 1.
3. Good Turing estimation – which aims at re-allocating the probabilities of those n-grams that occur (r+1) times in training data to the mass of n-grams that occur r-times. [If you are more curious, and need an example, see the PPT slides. If you extra curious, go ahead and visit the wiki page]
4. Jelinek-Mercer smoothing – is a kind of interpolative method. Quoting from the ppt: “nth-order smoothed model is defined recursively as a linear interpolation between the nth-order ML model and the (n − 1)th-order smoothed model.” Did not realize that theres a name for this I used a similar idea sometime back, without realizing that theres a name for it!
5. Katz Smoothing – This can best be explained by using the words from the PPT again:
“Count mass subtracted from nonzero counts is redistributed among the zero-count bigrams according to next lower-order distribution”
6. Witten Bell Smoothing – A kind of Jelinek Mercer smoothing.
7. Absolute Discounting – From what I understood, this is a kind of hybrid between interpolation kind of smoothing like Witten bell and discounting kind of smoothing like Katz.
8. Kneser-Ney Smoothing – the one for which this search began! this was described as an extension of absolute discounting. Anyways, after reading all these, I actually forgot that my search began with this name!

There were some comments on interpolation kind of smoothing vs discounting kind of smoothing – compare and contrast stuff.

On the whole, educative. Would have been interesting if I were actually a student of this course now, and was asked to implement all these programatically and write a report with performance analysis

Data Measures that characterize classification problems

Somehow, in random surfing, I came across this Master’s dissertation dated Feb 2008, from University of Pretoria, by Christiaan Maarten Van Dar Walt. It is titled – “Data Measures that characterize classification problems“. Well, I am a total dumbo as far as the mathematics of classification is concerned. Once or twice, I tried to decipher the myth, but each time, i have been too intelligent to realize that its pointless to write with a broken pencil. (Now, if you don’t have enough math foundation, do you really expect to understand internals of these stuff?)

Reading through this thesis, I felt its a very clearly written thesis, which was educative, at least for me and informative too. I am not going to write an elaborate description of this thesis. Let me mention in brief, what each chapter contains. To read it or not is left to the enthusiasts. I just read it in parts randomly and found that lot of investigation went in to it. Here you go :

Essentially, this thesis aims at understanding the relationship between the nature of data and the choice of a particular classifier. It goes in to performing this “to do” in the following steps:

1. Identifying the properties of data, which will affect a classifier performance
2. Proposing measures to quantify these properties
3. Validating the efficiency of these measures
4. Use these measures, build a meta classifier and explain the predictions regarding classification using them.
5. Explain the results of their experiments, interpretation, contributions to research, short comings of this work and future directions.

There is a great deal of background work material provided for the enthusiasts, which I personally liked – for the depth of bibliography

I haven’t read the thesis top to bottom, but I can be sure that it gives a fair idea of the choice of a classifier for a specific kind of data set and issues involved in the process of choosing. However, I wondered that they should have at least mentioned about the impact of domain of the data set on classifier choice. Or, the relation between the statistical nature of the data set and its domain put together on classifier choice.

Anyways, the thesis can be accessed here. I liked it for its clarity. I’d go back to this when I really do some work which needs this background, quite confident about the content.

May all your wishes come true!!

Wondering if I am praying for you? Not at all! I came across this paper:
May All YourWishes Come True: A Study of Wishes and How to Recognize Them
- Funny name for a computer science paper, eh? I was browsing through the Conference schedule of NAACL-HLT 2009 (North American Chapter of the Association for Computational Linguistics – Human Language Technologies) and found this paper over there. The conference is scheduled to be held from May 31st to June 5th 2009.

So, whats it about?: As the name indicates, this paper aims at developing a wish detector, which will enable extraction of information about “wishes” by people. This can be understood as a branch of sentiment analysis, in the sense that – if you consider a product review, this kind of a tool will let the manufacturers know about the user expectations and desires, which can be kept in mind while developing next versions.

WISH corpus?: Well, it seems, every year, theres something called “balldrop” at Newyork city Times Square, during the new years eve. “In December 2007, the Times Square Alliance, coproducer of the Times Square New Year’s Eve Celebration, launched a Web site called the Virtual Wishing Wall that allowed people around the world to submit their New Year’s wishes. These wishes were then printed on confetti and dropped from the sky at midnight on December 31, 2007 in sync with the ball drop” – says this paper. And, the authors gained access to this Wish corpus, and used this for their work. Ok, to give you an example of a wish: “I want to be the master of the world” is a wish. “Let everybody be happy and prosperous” is a wish…

Analysis of the WISH corpus: They have analyzed this Corpus according to the Topic and Scope of the wishes, using a pre-formed categorization of Topics (Eg: Love, Happiness, Health, Peace, Money etc..11 categories in all) and Scope (Self, World, family etc… 6 in all). Further, they analyzed these wishes according to geographical location (US and Non-US) and concluded that wishes differ in topic and scope with geographical location (Their results were statistically significant) .

Building Wish Detectors: And, here comes the actual part. Here, for the purpose of a baseline, two simple wish detectors are built first:
1. Manually looking for sentences containing : “I wish…” or “I hope..” etc can give you enough number of wishes from a domain. So, some wish-templates were obtained by analyzing the text patterns in sentences, which can indicate a wish, to make a simple rule based wish classifier. If a sentence matches some rule or pattern to some extent, it is a wish. Else,it is not. The authors say that this method might have a good precision but less recall.
2. “Another simple method for detecting wishes is to train a standard word-based text classifier using the labeled training set in the target domain.” – This might have a better recall, but lower precision.

Now, enter the dragon: The authors a method of automatically discovering the wish templates and a learning mechanism to learn the wish template features. They have tested this classifier on various domains. This training was done using WISH corpus and the testing was done on product reviews and politics!

Pretty interesting paper, though i did not get a “Wow!” feeling. The concept of domain independent wish template generation interested me, though.

For enthusiasts, the paper can be read here.

Breaking Audio Captchas

Details: Jennifer Tam, Jiri Simsa, Sean Hyde, and Luis von Ahn. Breaking Audio CAPTCHAs. In Advances in Neural Information Processing Systems (NIPS).

Firstly, the idea of audio captcha itself intimidates me, imagining the whole process that an automated device should go through, if it wants to decipher it. When I chanced across this paper, I was so sure that I can’t make the head or tail out of it. Hence, I did not touch it for the past 1 month. It was left open on my browser, for I was reluctant to close it. Finally, I read it to some extent today. Now, I can only identify the head or tail and still don’t know anything in depth, since all the speech processing stuff went above my head. Yet, I try to summarize what I understood.

Audio Captchas can be understood as those in which the user will be asked to listen to an audio which consists of words to be identified, combined with enough noise. I understand the target users most of the times were the visually impaired, since they can’t access the image based Captchas. This paper analyzed different audio captchas (From google site, digg and reCaptcha site) and estimated which one of them is more robust, using different Machine Learning algorithms (AdaBoost, SVM and k-Nearest Neighbour algorithms). In this process, they also understood the strengths and weaknesses of these algorithms as such too.

So, basically, in this paper, the focus was on understanding how much can a machine learn, in its attempt to break audio captchas. The experiment was done in two stages, like the image captchas: Speech segmentation and recognition. Machine Learning has been used on the captcha segments to perform automatic speech recognition (ASR). The features for this were generated using popular speech feature extraction techniques like – MFCC (Mel Frequency Cepstral Co-efficients), PLP (Perceptual Linear Prediction) and RASTA-PLP(relative spectral transform-PLP). These names appeared scary enough and I did not beyond them to find out more details

O my God, the creation of training data for these machine learning algorithms was a big exercise in itself. I began wondering about all the speech processing related experiments, involving huge amounts of training data. Patience man! patience! Finally, all their speech samples are transformed in to a set of segments of fixed size. They are all labelled either noise, digit or alphabet. These were used for training the classifiers, one type of captcha at a time.

So, I’ve blah-ed enough and hence, I’ll jump to conclusions:
1. An audio captcha that consists of a finite vocabulary and background noise should have multiple speakers and noise similar to the speakers.
2. Captchas that have longer solutions and multiple speakers tend to be difficult to solve.
3. Having a large vocabulary will make it difficult to collect enough training data for those who aim to break these captchas.
4. To develop an audio captcha with an improved human pass rate, we plan to take advantage of the human mind’s ability to understand distorted audio through context clues.

And finally, it made an interesting read. Some cool work.

The paper can be read here.

Confusion …Confusion!

ఇవాళ ఈనాడు పేపర్లో ఒక చిన్న వార్త ఉండింది. హైదరాబాద్ లోకల్ ఎడిషన్లో చూసినట్లు గుర్తు. ఈనాడు సైటులో నుండి ఈ వ్యాసానికి లంకె ఇద్దామని చూసాను కానీ, వ్యాసం పేరు గుర్తు లేక..వెదకలేకపోయాను. ఈపేపర్ నుండి దిగుమతి చేసిన పీడీఎఫ్ ఇక్కడ. ఇంతకీ విషయం ఏమిటంటే :

పాత కాలం నాటి తెలుగు పత్రికలన్నీ (ఆంధ్రపత్రిక పేరైతే గుర్తుంది. మిగితావి గుర్తు లేవు. నేను ఆ వ్యాసాం చాలా క్యాజువల్ గా చూసి వదిలేశా నిజానికి) డిజిటైజ్ చేస్తున్నామనీ, త్వరలో ప్రెస్ అకాడెమీ వారి వెబ్సైటులో అవన్నీ పెడతామనీ ఆ వార్తలో అన్నారు. అక్కడ ఇది ప్రారంభిస్తున్న దృశ్యం కూడా ఉంది. చదివి, ఓ…మంచి ఆలోచనే..అనుకున్నా. ఇప్పుడు ప్రెస్ అకాడెమీ వెబ్సైటు కోసం వెదుకుతూ ఉంటే, నాకు 2004 నాటి మరో వార్త – హిందూ పత్రిక పేజీల్లో కనబడ్డది. (అది ఇక్కడ.)

అంటే…ఐదేళ్ళ బట్టీ వీళ్ళు… చేద్దాం అనుకుంటూనే ఉన్నారనా? లేక…మధ్యలో ఏమన్నా ఐందా? పైగా, అప్పటి న్యూసైటెం లో “The academy had already taken up digitisation of old newspapers on a small scale and so far about 16 lakh pages had been digitised. A sum of Rs. 18 lakhs had been spent so far and the academy intended to take up a massive digitisation project covering all major newspapers and weeklies published from the State. A grant of Rs. 30 lakhs had been made to the academy, he said. ” అన్నారు. “He said all newspapers which would be digitised would be preserved and compact discs would be made. This would involve about Rs. 1 crore, he said adding the academy was serious about going ahead with the project.” అని కూడా అన్నారు.

ఇప్పుడేమో మళ్ళీ అరవై లక్షల నిధులు మంజూరు చేసారంట! వీళ్ళ పనే బాగుందే! అనుకున్నా.

ఇంతకీ, నాది ఇంకో సందేహం…ఇవన్నీ చేసి, నిజంగానే ఈ బాలారిష్టాలన్నీ దాటుకుని, ఆ కోట్లన్నీ తగలేసి దానిలో ఎంతో కొంత నిజంగా దీనిపై ఖర్చుపెట్టి మన వాళ్ళు దాన్ని ఆ ప్రెస్ అకాడెమీ వెబ్సైటేదో (నాకు కనబళ్ళేదు ఇంకా)..అందులో పెట్టారనుకుందాం…మనమెలా చదువుకోవాలన్నట్లు? ఏదో 1940 మార్చి ఐదున ఏం జరిగిందో మనకి అవసరమంటారా? లేక, ఫలానా సభలో ఫలానా వారేమన్నారో? అన్న విషయం కోసం వెదుకుతామా? – అంటే, నా ఉద్దేశ్యం – Search సౌలభ్యం ఉండాలి కదా అని. వీటన్నింటికీ సర్చి సౌకర్యం ఎప్పటికొస్తుందో లెండి, అది వేరే విషయం. కౌముది వారు ఇదివరలో వాళ్ళ పీడీఎఫ్ ఫైళ్ళలో keywords index చేయడం ద్వారా శోధన కొంతవరకూ పెట్టారు. (ఇది సెప్టెంబర్ 2007 ప్రాంతంలో వారి సైటులో ఉన్న ప్రకటన. అప్పట్లో వారిని ఏం చేస్తున్నారని సంప్రదిస్తే, yuyam వెబ్సైటు వారి ద్వారా ఇది చేస్తున్నామని చెప్పారు.

ఏమిటో… ముందు 2004 లో లక్షలు పోసిన వాటికి కాళ్ళొచ్చి ఎటుపోయాయి? అని అడిగితే చెబుతారంటారా?