In this month’s col­umn, we re­turn to our dis­cus­sion on nat­u­ral lan­guage pro­cess­ing.

OpenSource For You - - CODE SPORT - Sandya Man­nar­swamy

In the last two col­umns, we have been dis­cussing com­puter sci­ence in­ter­view ques­tions. This month, let’s con­tinue our on­go­ing dis­cus­sion on nat­u­ral lan­guage pro­cess­ing (NLP) by look­ing at one of its emerg­ing ap­pli­ca­tions.

Au­toma­tion is one of the ar­eas likely to ben­e­fit from NLP tech­niques and tools. Many of us have in­ter­acted with cus­tomer ser­vice agents from dif­fer­ent sec­tors such as e-com­merce, bank­ing, hos­pi­tal­ity, etc, over the phone, via email or chat, at all hours of the day, 24x7. Some of these com­mu­ni­ca­tion chan­nels are in real-time, such as the phone or chat, while oth­ers are off­line, such as email.

To­day, while these ser­vices are pro­vided by hu­man agents, there is an in­creas­ing push to­wards au­toma­tion. The chat typ­i­cally starts off with the agents greet­ing the cus­tomer and ask­ing what they can do for the lat­ter. The cus­tomers then state their prob­lem or put forth their query, which is then fol­lowed by the agents ask­ing for more de­tails from the cus­tomers to au­then­ti­cate their iden­tity, ob­tain the or­der in­for­ma­tion, and then pro­vide steps to an­swer the query or solve the prob­lem. This is an in­ter­ac­tive con­ver­sa­tion which has a typ­i­cal struc­ture and fol­lows a well-de­fined pat­tern of di­a­logue between the cus­tomer and agent. The agents are typ­i­cally pro­vided with a ‘FAQ’ or ‘prob­lem­so­lu­tion’ man­ual in which in­for­ma­tion on re­solv­ing cus­tomer queries is sys­tem­at­i­cally doc­u­mented, with de­tails on each step the agent needs to fol­low. The con­ver­sa­tions are au­dited to en­sure that the agents were cour­te­ous in their com­mu­ni­ca­tion with cus­tomers, that they fol­low the ap­pro­pri­ate prob­lem-res­o­lu­tion script, and that they use the ap­pro­pri­ate greet­ings at the start and end of com­mu­ni­ca­tion.

Let us con­sider a sim­ple sce­nario. You have or­dered an item on an e-com­merce web­site and have not yet re­ceived it. So you are us­ing the Web chat in­ter­face to speak to the cus­tomer ser­vice agent. Af­ter the cus­tom­ary greet­ing, you tell the agent that you have or­dered item XYZ one week back but it has not yet been de­liv­ered. The agent then asks you for the or­der de­tails. He then apol­o­gises to you for putting you on hold while he looks up the back­end data­base. Once he has the de­tails, he ei­ther men­tions that, “The item has al­ready been shipped and you can ex­pect to re­ceive it on date XX-YY-ZZ,” or he tells you that the de­liv­ery has been de­layed and gives you the rea­son for the de­lay, etc. Now, if you an­a­lyse the many thou­sands of such con­ver­sa­tions that take place ev­ery day, you can find that they fol­low a typ­i­cal pat­tern. From that, the cru­cial next ques­tion that springs to mind is, “Can these queries be an­swered by an au­to­mated agent in­stead of a hu­man agent?”

Well, the an­swer is yes, and NLP comes to our res­cue in au­tomat­ing these com­mu­ni­ca­tion ser­vices. While at first glance it seems quite dif­fi­cult to re­place the hu­man-to-hu­man com­mu­ni­ca­tion with hu­man-to-vir­tual agent com­mu­ni­ca­tion, it is in­deed pos­si­ble. In many cases, vir­tual agents pro­vide ini­tial com­mu­ni­ca­tion sup­port for sim­ple queries. How­ever, hu­man agents can take over in case the con­ver­sa­tion be­comes com­plex and de­vi­ates a lot from the nor­mal script.

There are two key com­po­nents to a so­lu­tion to vir­tu­alise the com­mu­ni­ca­tion between hu­man cus­tomer and vir­tual agent. First, the hu­man cus­tomer’s part of the con­ver­sa­tion needs to be an­a­lysed and then the ap­pro­pri­ate re­sponse and fol­low-up ques­tion, if any, needs to be gen­er­ated in nat­u­ral lan­guage for­mat and fed to the vir­tual agent. So both nat­u­ral lan­guage pro­cess­ing and nat­u­ral lan­guage gen­er­a­tion need to be done. The key chal­lenge is to en­sure that the con­ver­sa­tional ex­pe­ri­ence does not de­te­ri­o­rate by au­tomat­ing the process and the hu­man cus­tomer does not feel dis­sat­is­fied (of course, the ideal ex­pe­ri­ence would be when the hu­man cus­tomer can­not de­tect whether he is talk­ing to a vir­tual agent or a hu­man agent).

Let us an­a­lyse the prob­lem in a little more de­tail, fo­cus­ing first on the nat­u­ral lan­guage pro­cess­ing part. Let us as­sume that we are given a data­base of thou­sands of chats that have hap­pened between hu­man agents and

hu­man cus­tomers. We are now asked to build a sys­tem where it is pos­si­ble to train vir­tual agents that can take the place of hu­man cus­tomer ser­vice agents in an­swer­ing cus­tomer queries. As we men­tioned be­fore, the com­mu­ni­ca­tion can take place over ei­ther the phone, chat, or email. The voice com­mu­ni­ca­tion is fur­ther com­pli­cated by the fact that speech-to-text con­ver­sion ac­cu­ra­cies are still lim­ited when it oc­curs in real-time. Voice com­mu­ni­ca­tion also re­quires that the speaker’s con­ver­sa­tional cues such as emo­tion, pitch and tone should be de­tected, and the ap­pro­pri­ate re­sponse cues should be used by the vir­tual agent. This is a dif­fi­culty we will set aside for now and fo­cus on text based com­mu­ni­ca­tion only, namely chat/email.

Vir­tual agent email replies to cus­tomer queries are sim­pli­fied by the fact that these can be driven by an off­line process, and the replies gen­er­ated by the vir­tual agent can be sub­jected to ran­dom hu­man re­views and var­i­ous other checks be­fore they are shared with hu­man cus­tomers, since this is not done in real-time. On the other hand, chat com­mu­ni­ca­tion needs to be done in real-time and hence re­quires a shorter re­sponse time, which doesn’t al­low any off­line re­view of the vir­tual agent’s com­mu­ni­ca­tion and thereby re­quires greater pre­ci­sion and ac­cu­racy.

What are the key prob­lems that need to be ad­dressed in analysing the on­line chat? Let us make some sim­pli­fy­ing as­sump­tions. We will as­sume that the agent starts the di­a­logue with the stan­dard greet­ing, which is im­me­di­ately fol­lowed by the cus­tomer ex­plain­ing what the prob­lem is. The first step is to iden­tify the cat­e­gory of the prob­lem/query as­so­ci­ated with a spe­cific cus­tomer. There can be dif­fer­ent prob­lem/query cat­e­gories for an e-com­merce web­site, such as queries to track an item, can­cel­la­tion of a pur­chase, de­lay in re­funds, an ad­dress change for a cus­tomer, etc.

We will as­sume that there are a fixed set of prob­lem cat­e­gories. So this step gets re­duced to the fol­low­ing prob­lem: Given a small piece of text, the prob­lem is to clas­sify it into one of the N known prob­lem cat­e­gories. This is a well-known doc­u­ment clas­si­fi­ca­tion prob­lem. Given a short doc­u­ment, can you clas­sify it into a known cat­e­gory? If we as­sume that there are al­ready an­no­tated con­ver­sa­tions where the prob­lem cat­e­gory has been iden­ti­fied, we can build a su­per­vised train­ing based clas­si­fier to clas­sify a new in­com­ing doc­u­ment into one of the known cat­e­gories.

Here is a ques­tion for our read­ers: If you are asked to come up with a su­per­vised clas­si­fi­ca­tion scheme for this prob­lem, given an­no­tated data of con­ver­sa­tions and their prob­lem cat­e­gories, (a) What would be the fea­tures you will use? (b) Which su­per­vised clas­si­fier will you use? Re­mem­ber that this is a multi-class clas­si­fi­ca­tion prob­lem, since there are many prob­lem cat­e­gories. Now let us make the as­sump­tion that we have ac­cess to the cor­pus of a bunch of con­ver­sa­tions, but the con­ver­sa­tions are not an­no­tated with the prob­lem cat­e­gory. Can you de­scribe an un­su­per­vised tech­nique with which you can still de­ter­mine the prob­lem cat­e­gory of an in­com­ing chat, given the cor­pus?

Now let us as­sume that we have cor­rectly iden­ti­fied the prob­lem cat­e­gory. As we said be­fore, hu­man agents are typ­i­cally given ac­cess to the so­lu­tions data­base or FAQs, which they con­sult to find the an­swers for each prob­lem cat­e­gory. They use these an­swer tem­plates and pro­vide the re­sponse to the user. If we don’t have ac­cess to this so­lu­tions data­base, is it pos­si­ble for us to an­a­lyse the con­ver­sa­tions cor­pus and au­to­mat­i­cally iden­tify the an­swer tem­plate for each prob­lem cat­e­gory? First, we clus­ter the chats as per their prob­lem cat­e­gory. Now, we have a sub­set of chats be­long­ing to each prob­lem cat­e­gory. Given this sub­set S for prob­lem cat­e­gory P, how do we find out what is the pos­si­ble an­swer tem­plate script for this prob­lem cat­e­gory? Note that the hu­man agent ver­balises the an­swer tem­plate in a suit­able form for a spe­cific cus­tomer, per­son­al­is­ing it for each cus­tomer. Also, given that it is an in­ter­ac­tive di­a­logue, there can be con­sid­er­able noise in­tro­duced for each cus­tomer, based on the spe­cific query for­mu­la­tion. One pos­si­bil­ity is to an­a­lyse the con­ver­sa­tional snip­pets ut­tered by the agent as part of the chat, and find out the common se­quence of ac­tions sug­gested by the agent across these con­ver­sa­tions.

Here is a ques­tion for our read­ers: Given a cor­pus of con­ver­sa­tional chats cor­re­spond­ing to a spe­cific prob­lem cat­e­gory, marked with agent ut­ter­ance and cus­tomer ut­ter­ance in the di­a­logue, you are asked to find out the un­der­ly­ing common ac­tion se­quence, if any, sug­gested by the agent. Let us make some sim­pli­fy­ing as­sump­tions. Let us as­sume that such an ac­tion se­quence def­i­nitely ex­ists in all the con­ver­sa­tions. We will also as­sume that the verb phrases used in the agent con­ver­sa­tion de­note the steps of the ac­tion se­quence. Let us as­sume that each unique verb in our vo­cab­u­lary can be rep­re­sented by a unique char­ac­ter. Given that, we can rep­re­sent this as a sim­pler prob­lem: You are given N se­quences of char­ac­ter strings (each string rep­re­sents the ac­tion se­quence of verbs in one chat each). You are then asked to find the long­est common sub-se­quence of all these se­quences. Can you come up with an al­go­rithm? Please note that we are look­ing for the long­est common sub-se­quence across N mul­ti­ple se­quences where N can be greater than two. Can you come with a so­lu­tion which runs in poly­no­mial time? Please send me your re­sponses over email, on how you would solve this prob­lem.

If you have any favourite pro­gram­ming ques­tions/soft­ware top­ics that you would like to dis­cuss on this fo­rum, please send them to me, along with your so­lu­tions and feed­back, at sandyas­m_AT_ya­hoo_DOT_­com. Till we meet again next month, happy pro­gram­ming!

The au­thor is an ex­pert in sys­tems soft­ware and is cur­rently work­ing as a re­search sci­en­tist at Xerox India Re­search Centre. Her in­ter­ests in­clude com­pil­ers, pro­gram­ming lan­guages, file sys­tems and nat­u­ral lan­guage pro­cess­ing. If you are pre­par­ing for sys­tems soft­ware in­ter­views, you may find it use­ful to visit Sandya’s LinkedIn group Com­puter ScienceIn­ter­viewTrain­ingIn­dia at groups?home=HYPERLINK“ s?home=&gid=2339182”&HYPERLINK“http://www.linkedin. com/groups?home=&gid=2339182”gid=2339182

Newspapers in English

Newspapers from India

© PressReader. All rights reserved.