德勤荷兰数据分析人工智能白皮书

ArtificialIntelligence

March2018

WhatisAI?WhatisMachineLearning?WhatisCognitiveAnalytics?Howdothesetermsrelate,ordiffer,fromoneanother?Ingeneralterms,AIreferstoabroadfieldofscienceencompassingnotonlycomputersciencebutalsopsychology,philosophy,linguisticsandotherareas.

ArtificialIntelligence|Contents

Contents

ArtificialIntelligenceDefined 04

ArtificialIntelligenceTechniquesExplained 10

ApplicationsofAI 16

Fivetechnologytrendsthatleap-frog

ArtificialIntelligence 22

AIopportunitiesforthefuture 26

Authors 31

Sources 32

03

04

ArtificialIntelligence|ArtificialIntelligencedefined

ArtificialIntelligence|ArtificialIntelligencedefined

ArtificialIntelligence|ArtificialIntelligencedefined

05

06

ArtificialIntelligencedefined

ThetopicofArtificialIntelligenceisatthetopofitsHypecurve1.Andtherearemanygoodreasonsforthat;itisexciting,promisingandabitscaryatthesametime.VariouspublicationsareclaimingthatAIknowswhatwewanttobuy,itcancreateNetflixseries,itcouldcurecanceranditmayeventuallytakeourjobsorevendestroymankind.2

TheproblemandatthesametimeopportunitywithAIisthatit’snotverywelldefined.Ifwewouldshowthenavigationsystemofourcartosomeonelivingin1980,heorshewouldprobablyconsideritasaformofArtificialIntelligence,whereaswenowadayswouldprobablynot.Weareseeingthesamewithspeechandimagerecognition,naturallanguagerecognition,gameenginesandothertechnologiesthatarebecomingmoreandmorecommonandembeddedinevery-daytechnology.

Ontheotherhand,varioustechnologysolutionprovidersaretakingtheopportunitytorebrandtheirexistingsolutionstoAI,totakeadvantageofthehugehypeandthatthemarketisexperiencingandtheresultingpresscoverage.Ifwehaveabuiltamachinelearningmodelthatpredictscustomer

demand,asolutionthathasbeenexistingforyears,wewouldhavecalledit“datamining”inthepastandwenowseeitrebrandedas“artificialintelligence”.Thisisaddingtotheconfusionandmayverywellleadtoinflatedexpectations.

Nevertheless,recentdevelopmentsinAIareimpressiveandexciting.Butalsooverestimatedandmisunderstood.Inordertosplithypefromrealityandhelpformingaviewonthismarket,wewillpublishaseriesofarticlesexplainingthe

worldofAI,zoomingintothetechniquesthatareassociatedwithAI,themostappealingbusinessapplicationsandpotentialissueswecanexpect.

Inthisfirstarticlewewillstartwiththebeginning,byexplainingAIandassociatedtermsinfivedefinitions.WhatisAI?WhatisMachineLearning?WhatisCognitiveAnalytics?Howdothesetermsrelate,ordiffer,fromoneanother?.

ArtificialIntelligence(AI)

Ingeneralterms,AIreferstoabroadfieldofscienceencompassingnotonlycomputersciencebutalsopsychology,philosophy,linguisticsandotherareas.AIisconcernedwithgettingcomputerstodotasksthatwouldnormallyrequire

humanintelligence.Havingsaidthat,therearemanypointofviewsonAIandmanydefinitionsexist.BelowsomeAIdefinitionswhichhighlightkeycharacteristicsofAI.

“AIreferstoabroadfieldofscienceencompassingnotonlycomputersciencebutalsopsychology,philosophy,linguisticsandotherareas”

1

/document/3380751/

2

/news/technology-37713629

/ai-open-letter/

BIGDATA

Capableofprocessingmassiveamountsofstructuredandunstructureddatawhichcanchangeconstantly

REASONING

Abilitytoreason(deductiveorinductive)andtodrawinferencebasedtothesituation.Contextdrivenawarenessofthesystem.

Abilitytolearnbasedonhistoricalpatterns,expertinputandfeedbackloop

LEARNING

Capableofanalyzingandsolvingcomplexproblemsinspecial-purposeandgeneral-purposedomain

PROBLEMSOLVING

Figure1:KeycharacteristicsofanAIsystem

Somegeneraldefinitions:

“Artificialintelligenceisacomputerizedsystemthatexhibitsbehaviorthat

iscommonlythoughtofasrequiringintelligence.”3

“ArtificialIntelligenceisthescienceofmakingmachinesdothingsthatwouldrequireintelligenceifdonebyman.”4

ThefoundingfatherofAIAlanTuringdefinesthisdisciplineas:

“AIisthescienceandengineeringofmakingintelligentmachines,especiallyintelligentcomputerprograms”.5

Inallthesedefinitions,theconceptofintelligencereferstotheabilitytoplan,reasonandlearn,sensingandbuildingsomekindofperceptionofknowledgeandcommunicateinnaturallanguage.

NarrowAIvsGeneralAI

Achesscomputercouldbeatahumaninplayingchess,butitcouldn’tsolvea

complexmathproblem.VirtuallyallcurrentAIis“narrow”,meaningitcanonlydowhatitisdesignedfor.Thismeansforeveryproblem,aspecificalgorithmneedstobedesignedtosolveit.NarrowAIaremostlymuchbetteratthetasktheyweremadeforthanhumans,likefacerecognition,chesscomputers,calculus,translation.TheholygrailofAIisaGeneralAI,asinglesystemthatcanlearnaboutanyproblemandthensolveit.Thisisexactlywhathumansdo:

wecanspecializeinaspecifictopic,fromabstractmathstopsychologyandfromsportstoart,wecanbecomeexpertsatallofthem.

AnAIsystemcombinesandutilizesmainlymachinelearningandothertypesofdataanalyticsmethodstoachieveartificialintelligencecapabilities.

3PreparingfortheFutureofArtificialIntelligence,NSTC,2016

46.Raphael,B.1976.Thethinkingcomputer.SanFrancisco,CA:W.H.Freeman

5

/jmc/whatisai/node1.html

ArtificialIntelligence|ArtificialIntelligencedefined

ArtificialIntelligence|ArtificialIntelligencedefined

07

08

ArtificialIntelligence

Abilitytosense,reason,engageandlearn

Computervision Robotics&motion

Naturallanguage

processing MachineLearning

Abilitytolearn

Voice

Planning&optimization

Knowledge

recognitionSupervised

learning

Unsupervisedlearning

Reinforcementcapture

MethodsAbilitytoreasonRegressionDecisiontreesetc.

learning

TechnologiesPhysicalenablementPlatform

UXAPIs

Sensorsetc.

Figure2:relationbetweenAI,MachineLearningandunderlyingmethodsandinfrastructure

MachineLearning

Machinelearningistheprocesswherebyacomputerdistillsmeaningbyexposuretotrainingdata6.Ifforexampleyouwantanalgorithmtoidentifyspamine-mails,youwillhavetotrainthealgorithmbyexposingittomanyexamplesofe-mails

thataremanuallylabeledasbeingspamornot-spam.Thealgorithm“learns”toidentifypatterns,likeoccurrenceofcertainwordsorcombinationofwords,thatdeterminesthechanceofane-mailbeingspam.

Machinelearningcanbeappliedtomanydifferentproblemsanddatasets.Youcantrainanalgorithmtoidentifypicturesofcatsinphoto-collections,potentialfraudcasesininsuranceclaims,transformhandwritingintostructuredtext,transformspeechintotextetc.Alltheseexampleswouldrequirelabeledtrainingsets.

Dependingonthetechniqueused,analgorithmcanimproveitselfbyaddingafeedbackloopthattellsitinwhichcasesitmademistakes.

ThedifferencewithAIhoweveristhatamachinelearningalgorithmwillnever

“understand”whatitwastrainedtodo.Itmaybeabletoidentifyspam,butitwillnotknowwhatspamisorunderstandwhywewantittobeidentified.Andifthereisanewsortofspamemerging,itwillprobablynotbeabletoidentifyitunlesssomeone(human)re-trainsthealgorithm.

MachinelearningisatthebasisofmostAIsystems.Butwhileamachinelearningsystemmaylook“smart”,inourdefinitionofAIitisinfactnot.

CognitiveAnalytics

CognitiveAnalyticsisasubsetofA.I.thatdealswithcognitivebehaviorweassociatewith‘thinking’asopposedtoperceptionandmotorcontrol.Thinking

allowsanentitytoobtaininformationfromobservations,learnandcommunicate.

Acognitivesystemiscapableofextractinginformationfromunstructureddatabyextractingconceptsandrelationshipsintoaknowledgebase.Forexample,fromatextaboutBarackObama,therelationsfromFigure3canbeextractedusingNaturalLanguageProcessing.80%ofallcompanydataisunstructuredandcurrentCognitiveAnalyticssystemscansearchallofittofindtheanswertoyourquestion.

6StephenLucci,2016,

Artificialintelligenceinthe21stcentury:Alivingintroduction

Mexico

Neighbour

USA

President

BarackObama

Spouse

Father

MichelleObama

Father

Mother

Mother

MaliaObama

Sibbling

SashaObama

Figure3:Aknowledgebaseextractedfromtext

LearningenablestheCognitiveSystemtoimproveovertimeintwomajorways.

Firstly,byinteractingwithhumans,andobtainingfeedbackfromtheconversationpartnerorbyobservingtwointeractinghumans.Secondly,fromallthedataintheknowledgebase,newknowledgecanbeobtainedusinginference.

AnotherimportantaspectofCognitiveAnalyticsistheabilitytousecontext.ContextenablesaCognitiveAnalyticssystemtoinfermeaningfromlanguage.Forexample,achatbotcantakeintoaccounttheconversationhistorytoinferwhoisreferredtobythewordhe:

User:

AI:

User:

AI:

WhoisObama’swife?MichelleObama.

Howoldishe?

BarackObamais55yearsold.

Figure4:Exampleconversationofacognitivesystem

ArtificialIntelligence|ArtificialIntelligencedefined

10

/amelia/

09

Forthissimpleexercise,thesystemneedstobeawareofnamesthatrepresentpeople,relationshipsbetweenpeople,genderandthecommonsensetoinferthatObamareferstoBarackObama.Allofthiscontextualinformationisrequiredtomaketherightinferencestoanswerbothquestions.

SinceCognitiveSystemsareawareofcontext,canunderstandunstructureddataandreasonaboutinformation,theycancommunicatewithhumansaswell.ThisenablesthesystemtounderstandaquestionposedinEnglish,nolongerrequiringthetime-consumingprocessof

convertingthequestionintoaformatthecomputercanworkwith.Forexample,

acallcenterrepresentativecognitivesystemcanquicklyansweracustomer’squestionaboutcampinggearbyusinginformationfromproductdescriptions,customerreviews,saleshistories,topicalblogs,andtravelmagazines.7CognitiveSystemscanunderstandandcommunicatethroughmanymediums,includingspeech,image,video,signlanguage,graphsoranycombinationofthese.

Robotics

AIisanimportantenablingfactorindesignandoperationalizingsmartrobotsandotherprocessautomationapplications.

Initsmostsimpleform,arobotmaybeamachinethatisprogrammedtoperformasimpletask,byfollowingstep-by-step

instructions.Itcouldconsistofarule-basedenginethatexplicitelytellsthesystemwhattodowhenacertainconditionoccurs.ArobotinacarfactoryIsprogrammedlikethatandhardlyconsidered“intelligent”.

Butroboticsexistinavarietyofmuchmoreintelligentshapes,rangingfromunmannedautonomousvehicles(UAV’s),drones,smartvacuumcleanerstointelligentchatbotsandsmartassistantsetc.Howadvancedrobots

areisvividifwelookatrobotsdevelopedbyBostonDynamics8andMIT’sCheetahII9.OtherexampleisAmelia10,anintelligentassistantwithNLPcapabilities.Keyaspectofroboticsisthatitcombineshardware(mechanicalparts,sensors,screensetc.)withintelligentsoftwareanddatatoperformataskforwhichcertainlevelofintelligenceisrequired(e.g.orientation,motion,interactionetc.).

SmartMachines

Themajorthemeinusingtheterm“SmartMachines”isautonomy.SmartMachinesaresystemsthat–tosomeextend-areabletomakedecisionsbythemselves,requiringnohumaninput.CognitiveAnalyticssystemscanbeSmartMachines,aswell

asrobots,oranykindofAI,aslongasitadherestothisrule.Inthecaseofarobot,autonomycouldconsistsofacapabilitytoplanwhereitwantstogo,whatitwantstoachieveandhowtoovercomeobstacles.Ratherthanbeinghuman-controlledorsimplyfollowinginstructions,itcouldachievehigher-levelgoalslikegettinggroceries,inspectingbuildingsandsoforth.Thisisenabledbyplanningmethods,self-preservationinstinctsontopoftheskillsthatanormalrobotalreadyrequires.

InthecaseofaCognitiveSystem,itwillpro-activelytrytolearnnewfacts,gaugeopinionsandlearnnewcommonsenserulesbyengaginginactiveconversationwithhumans,askingquestionsanddouble-checkingthemwithdatafoundonline.Itwillalsoactivelyinformdecisionmakersaboutchangesithasobserved,forexampleiftheopinionofcustomersonsocialmediasuddenlymakesaswing.Itcouldevenactuponthesechanges,intheexampleengagingwiththecustomersorsharingthepositiveopinionsonthesocialmediaoutletsofthecompany.

SinceSmartMachinesareautonomousandintelligent,theymightstartcommunicatingamongthemselves.Thisleadstomulti-agentsystemsthatcanmaketrades

toimprovetheirutility.Thebuilding-inspectingrobotcanaskadronetoinspecttheroofforhim,tradingthisfavorforanotherfavor,liketransportinggoodsorsimplycurrency.

ACognitiveSystemthatbecomesaSmartMachinecanspecializeinaspecificarea,becominganexpertinthatarea.Now,otherSmartMachinescanaskitforinformationinthatarea,anditwillbeabletoprovidemorerelevantanswersmorequicklythanageneralCognitiveSystemthatisnotspecialized.InformationbrokerslikethisimprovetheoverallutilityofthewholenetworkofSmartMachines.

Conclusion

ThetermsMachineLearning,Cognitive,RoboticsandsmartmachinesareusedofteninrelationshiptoAI,orsometimesevenassynonyms.AIisacomplexfieldofinterest,withmanyshapesandforms.Thereforewehavetriedtoshinesomelightonthemostusedterminology.Insubsequentblogs,wewilldivedeeperintechniquesbehindAIsystems,business

applications,someassociatedtechnologytrendsandthetop5risksandconcerns.

7

Deloitte,Cognitiveanalytics™Thethree-minuteguide

8

/

9/research/dynamic-locomotion-mit-cheetah-2

10

ArtificialIntelligence|ArtificialIntelligencetechniquesexplained

ArtificialIntelligence|ArtificialIntelligencetechniquesexplained

ArtificialIntelligence|ArtificialIntelligencetechniquesexplained

PAGE

11

4/wiki/Support_vector_machine

12

ArtificialIntelligencetechniquesexplained

Inorderto‘demystify’ArtificialIntelligence,andinsomewaygetmorepeopleinvolvedinAI,wearepublishingaseriesofarticlesexplainingtheworldofAI,zoominginonthetechniquesthatareassociatedwithAI,themostappealingbusinessapplications,andpotentialissueswecanexpect.

The

firstblog

articleexplainedsomeofthemostcommonlyuseddefinitionsofAI.InthissecondarticlewewillexplainsomefundamentalAItechniquesused:Heuristics,SupportVectorMachines,

NeuralNetworks,MarkovDecisionProcess,andNaturalLanguageProcessing.

Heuristics

Supposewehavecoinswiththefollowingdenominations:5cents,4cents,3cents,and1centandweneedtodeterminetheminimumnumberofcoinstoget7cents.Inordertosolvethisproblemwecanmakeuseofatechniquecalled“heuristics”.

Webster1definesthetermHeuristicas“involvingorservingasanaidto

learning,discovery,orproblem-solvingbyexperimentalandespeciallytrialanderrormethods”.Inpractice,thismeansthatwheneverproblemsgettoolargeortoocomplextofindtheguaranteedbestpossiblesolutionusingexactmethods,heuristicsareawaytoemployapracticalmethodtofindasolutionthatisnotguaranteedtobeoptimal,butonethatissufficientfortheimmediategoals.

Forsomeproblems,tailoredheuristicscanbedesignedthatexploitthestructurepresentintheproblem.Anexampleofsuchatailoredheuristicwouldbeagreedyheuristicfortheabovementionedcoin-

changingproblem.Nowagreedyheuristicwouldbetoalwayschoosethelargestdenominationpossibleandrepeatthisuntilwegettothedesiredvalueof7.Inourexample,thatmeansthatwewouldstartwithfirstselectingone5centcoin.Fortheremaining2cents,thelargestdenominationwecanchooseis1cent,leavinguswiththesituationwherewestillhavetocover1centforwhichweagainuse1cent.

Soourgreedyheuristicgivesusasolutionof3coins(5,1,1)togettothevalueof

7cents.Itcanbeeasilyseenthatanother,better,solutionofonly2coinsexistusingthe3and4centcoins.Whilethegreedyheuristicforthecoinchangingproblemdoesnotprovidethebestsolutionforthisparticularcase,inmostcasesitwillresultinasolutionthatisacceptable.

Besidessuchtailoredheuristicsforspecificproblems,alsocertaingenericheuristicsexist.Justlikeneuralnetworks,someofthesegenericheuristicsarebasedonprocessesinnature.Twoexamplesof

suchgenericheuristicsareAntColonyOptimization2andgeneticalgorithms3.Thefirstisbasedonhowsimpleantsareabletoworktogethertosolvecomplexproblemsandthelatterisbasedontheprincipleofsurvivalofthefittest.

1

/dictionary/heuristic

2/wiki/Ant_colony_optimization_algorithms

3/wiki/Genetic_algorithm

Figure1

1

3

2

Figure3 Figure2

Atypicalproblemwhereheuristicsareappliedtofindacceptablesolutionsquicklyisvehiclerouting,wheretheobjectiveistofindroutesforoneormorevehiclesthathavetovisitanumberoflocations.

SupportVectorMachines

Thequestionwhetheranemailisspamornotspamisanexampleofaclassificationproblem.Inthesetypesofproblems,theobjectiveistodeterminewhetheragivendatapointbelongstoacertainclassornot.Afterfirsttrainingaclassifiermodelondatapointsforwhichtheclassisknown(e.g.

asetofe-mailsthatarelabeledasspamornotspam),youcanthenusethemodeltodeterminetheclassofnew,unseendata-points.ApowerfultechniqueforthesetypesofproblemsisSupportVectorMachines4(SVM).

ThemainideabehindSVMisthatyoutrytofindtheboundarylinethatseparatesthetwoclasses,butinsuchawaythat

theboundarylinecreatesamaximumseparationbetweentheclasses.Todemonstratethis,wewillusethefollowingsimpledataforourclassificationproblem(Figure1).

Inthisexample,thegreencirclesandtheredsquarescouldrepresenttwodifferentsegmentsinatotalsetofcustomers(e.g.highpotentialandlowpotential),basedonallkindsofpropertiesforeachofthecustomers.Anylinethatkeepsthegreencirclesontheleftandtheredsquaresontherightisconsideredavalidboundarylinefortheclassificationproblem.Thereisaninfinitenumberofsuchlinesthatcanbedrawnand4differentexamplesarepresentedontop(Figure2).

Asstatedbefore,withSVMyoutrytofindtheboundarylinethatmaximizestheseparationbetweenthetwoclasses.Intheprovidedexample,thiscanbedrawnasFigure3:

Thetwodottedlinesarethetwoparallelseparationlineswiththelargestspacebetweenthem.Theactualclassificationboundarythatisusedwillbethesolidlineexactlyinthemiddleofthetwodottedlines.

ThenameSupportVectorMachinecomesfromthedatapointsdirectlyoneitheroftheselinesarethesupportingvectors.Inourexample,wehad3supportingvectors.

Ifanyoftheotherdatapoints(i.e.notasupportingvector)ismovedslightly,thedottedboundarylinesarenotaffected.However,ifthepositionofanyofthesupportingvectorsisslightlychanged(e.g.datapoint1ismovedslightlytotheleft),thepositionofthedottedboundarylineswillchangeandthereforethepositionofthesolidclassificationlinealsochanges.

Biologicalneuron

Artificialneuron

X1

X2

Output

X3

Inreallife,dataisnotasstraightforwardasinthissimplifiedexample.Wenormallyworkwithmuchmorethantwodimensions.Besideshavingstraightseparationlines,theunderlyingmathematicsforanSVMalsoallowsfor

certaintypeofcalculationsorkernelsthatresultinboundarylinesthatarenon-linear.

SVMclassificationmodelscanalsobefoundinimagerecognition,likefacerecognitionorconvertinghandwritingtotext.

Figure4:Graphicalrepresentationofabiologicalneuron(left)andanartificialneuron(right)

ArtificialNeuralNetworks

Animalsareabletoprocess(visualorother)informationfromtheirenvironmentandreactadaptivelytoachangingsituation.

Theyusetheirnervoussystemtoperformsuchbehavior.Theirnervoussystemcanbemodeledandsimulatedanditshouldbepossibleto(re)producesimilarbehaviorinartificialsystems.ArtificialNeuralNetworks(ANN)canbedescribedasprocessingdevicesthatarelooselymodeledaftertheneuralstructureofabrain.Thebiggestdifferencebetweenthetwoisthatthe

ANNmighthavehundredsorthousandsneurons,whereastheneuralstructureofananimalorhumanbrainhasbillions.

Thebasicprincipleofaneuralstructureisthateachneuronisconnectedwith

acertainstrengthtootherneurons.Basedontheinputstakenfromtheoutputofotherneurons(alsoconsideringtheconnectionstrength)anoutputisgeneratedwhichcanbeusedasinputagainbyotherneurons,seeFigure1(left).Thisbasicideahasbeentranslatedintoanartificialneuralnetworkbyusingweightstoindicatethestrengthoftheconnectionbetweenneurons.Furthermore,eachneuronwilltaketheoutputfromtheconnectedneuronsasinputanduseamathematicalfunctiontodetermineitsoutput.Thisoutputisthenusedbyotherneuronsagain.

Whereinthebiologicalbrainlearningtakesplacebystrengtheningorweakeningthebondsbetweendifferentneurons,intheANNthelearningtakesplacebychangingtheweightsbetweentheneurons.Byprovidingtheneuralnetworkwithalargesetoftrainingdatawithknownfeaturesthebestweightsbetweentheartificialneurons(i.e.strengthofthebond)canbecalculatedinordertomakesuretheneuralnetworkbestrecognizesthefeatures.

Hiddenlayers

Inputlayer

Outputlayer

TheneuronsoftheANNcanbestructuredintoseverallayers5.Figure5showsanillustrativeschemeofsuchlayering.Thisnetworkconsistsofaninputlayer,where

Figure5:SchematicofaconnectedANN

alltheinputsarereceived,processedandconvertedtooutputstothenextlayers.Thehiddenlayersconsistofoneormorelayersofneuronseachpassingthroughinputsandoutputs.Finally,theoutputlayerreceivesinputsofthelasthiddenlayerandconvertsthistotheoutputfortheuser.

Figure2showsanexamplenetworkwhereallneuronsinonelayerareconnected

toallneuronsinthenextlayer.Suchanetworkiscalledfullyconnected.Dependingonthetypeofproblemyouwanttosolvedifferentconnectionpatternsareavailable.Forimagerecognitionpurposes,typically

5

/chap1.html

ArtificialIntelligence|ArtificialIntelligencetechniquesexplained

ArtificialIntelligence|ArtificialIntelligencetechniquesexplained

6

/~vardi/dag01/givan1.pdf

7

/html/ArtInt_224.html

14

8MoreonRNN:

http://karpathy.github.io/2015/05/21/rnn-effectiveness/

15

Convolutionalnetworksareused,whereonlygroupsofneuronsfromonelayerare

connectedtogroupsofneuronsinthenextlayer.Forspeechrecognitionpurposes,typicallyRecurrentnetworksareused,whichallowforloopsfromneuronsinalaterlayerbacktoanearlierlayer.

MarkovDecisionProcess

AMarkovDecisionProcess(MDP)isaframeworkfordecision-makingmodelingwhereinsomesituationstheoutcome

ispartlyrandomandpartlybasedontheinputofthedecisionmaker.Another

applicationwhereMDPisusedisplanning,wheretheplanningisoptimized.The

basicgoalofMDPistofindapolicyforthedecisionmaker,tellshimwhichparticularactionshouldbetakenatwhichstate.

AnMDPmodelconsistsofthefollowingparts6:

Asetofpossiblestates:forexample,thiscanrefertoagridworldofarobotorthestatesofadoor,dooropenanddoorclosed.

Asetofpossibleactions:afixedsetofactionsarobotforexamplecantake,suchasgoingnorth,left,southorwest.Orwithrespecttoadoor,closingoropeningdoor.

Transitionprobabilities:thisistheprobabilityofgoingfromonestatetoanotherstate.Forexample,whatistheprobabilitythatthedoorisclosed,aftertheactionofclosingthedoor

isperformed.

Rewards:theseareusedtoguidetheplanning.Withrespecttotherobotandthegridexample,arobotmaywanttomovenorthtoreachitsdestination.Actuallygoingnorthwillresultinahigherreward.

OncetheMDPisdefined,apolicycanbetrainedusing“Valueiteration”or“PolicyIteration”.Thesemethodscalculatetheexpectedrewardsforeachofthestates.Thepolicythengivesthebestactionthatcanbetakenfromeachstate.

Asanexample,wewilldefineagridwhichcanbeseenasanideal,finiteworldfor

arobot7.ThisexamplegridisshowninFigure6.

Therobotcanmove(action)fromeachpositioninthegrid(state)infourdirections,namelynorth,left,rightandsouth.Theprobabilitythattherobotgoesintothedesireddirectionis0.7and0.1ifitgoestowardsanyoftheother3directions.Arewardof-1(i.e.apenalty)isgiveniftherobotbumpsintoawallanddoesn’tmove.Also,additionalrewardsandpenaltiesaregiveniftherobotreachesthecellsthatarecoloredgreenandred,respectively.Basedontheprobabilitiesandrewardsapolicy(function)canbemadeusingtheinitialandfinalstate.

AnotherexamplewhereMDPcanbeusedistheinventoryplanningproblem,whereastockkeeperormanagereachweekhastodecidehowmanyunitshavetobeordered.TheinventoryplanningcanbemodeledasanMDP,wherethestatescanbeconsideredpositiveinventoryand

shortages.Possibleactionsareforinstanceorderingnewunitsorbackloggingtothenextweek.Transitionprobabilitiescanbeconsideredastheactionthatwillbetakenbasedonthedemandandinventoryforthecurrentweek.Rewards,orinthiscase,costsaretypicallyunitordercostsandinventorycosts.

+3

-3

-10

+10

-1

-1

-1

-1

Figure6:Example–gridworldofarobot

NaturalLanguageProcessing

NaturalLanguageProcessing,orNLPinshort,isatermforeverythingfromspeechrecognitiontolanguagegeneration,eachrequiringdifferenttechniques.Afewoftheimportanttechniqueswillbeexplainedbelow,whicharePart-of-Speechtagging,NamedEntityRecognition,andParsing.

Letusexaminethesentence“Johnhit