SpringerBriefs in Electrical and Computer Engineering Speech Technology SeriesEditor AmyNeustein For furthervolumes: http://www.springer.com/series/10043 Editor’s Note Theauthorsofthisserieshavebeenhandselected.Theycomprisesomeofthemost outstanding scientists—drawn from academia and private industry—whose research is marked by its novelty, applicability, and practicality in providing broad-based speech solutions. The Springer Briefs in Speech Technology series provides the latest findings in speech technology gleaned from comprehensive literaturereviewsandempiricalinvestigationsthatareperformedinbothlaboratory andreallifesettings.Someofthetopicscoveredinthisseriesincludethepresenta- tion of real life commercial deployment of spoken dialog systems, contemporary methods of speech parameterization, developments in information security for automated speech, forensic speaker recognition, use of sophisticated speech analytics in call centers, and an exploration of new methods of soft computing forimprovinghuman–computerinteraction.Thoseinacademia,theprivatesector, theselfserviceindustry,lawenforcement,andgovernmentintelligenceareamong the principal audience for this series, which is designed to serve as an important and essential reference guide for speech developers, system designers, speech engineers, linguists, and others. In particular, a major audience of readers will consist of researchers and technical experts in the automated call center industry where speech processing is a key component to the functioning of customer care contactcenters. Amy Neustein, Ph.D., serves as editor in chief of the International Journal of Speech Technology (Springer). She edited the recently published book Advances in Speech Recognition: Mobile Environments, Call Centers and Clinics (Springer 2010), and serves as quest columnist on speech processing for Womensenews. Dr.NeusteinisthefounderandCEOofLinguisticTechnologySystems,aNJ-based think tank for intelligent design of advanced natural language-based emotion detection software to improve human response in monitoring recorded conversationsofterrorsuspectsandhelplinecalls. Dr.Neustein’sworkappearsinthepeerreviewliteratureandinindustryandmass media publications. Her academic books, which cover a range of political, social, and legal topics, have been cited in the Chronicles of Higher Education and have won her a pro Humanitate Literary Award. She serves on the visiting faculty of the National Judicial College and as a plenary speaker at conferences in artificial intelligence and computing. Dr. Neustein is a member of MIR (machine intelli- genceresearch)Labs,whichdoesadvancedworkincomputertechnologytoassist underdeveloped countries in improving their ability to cope with famine, disease/ illness, and political and social affliction. She is a founding member of the NewYorkCitySpeechProcessingConsortium,anewlyformedgroupofNY-based companies, publishing houses, and researchers dedicated to advancing speech technologyresearchanddevelopment. Ami Moyal (cid:129) Vered Aharonson Ella Tetariy (cid:129) Michal Gishri Phonetic Search Methods for Large Speech Databases AmiMoyal VeredAharonson AfekaAcademicCollege AfekaAcademicCollege ofEngineering ofEngineering Tel-Aviv,Israel Tel-Aviv,Israel EllaTetariy MichalGishri AfekaAcademicCollege AfekaAcademicCollege ofEngineering ofEngineering Tel-Aviv,Israel Tel-Aviv,Israel ISSN2191-8112 ISSN2191-8120(electronic) ISBN978-1-4614-6488-4 ISBN978-1-4614-6489-1(eBook) DOI10.1007/978-1-4614-6489-1 SpringerNewYorkHeidelbergDordrechtLondon LibraryofCongressControlNumber:2012956552 #TheAuthor(s)2013 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpart of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation,broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionor informationstorageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilar methodologynowknownorhereafterdeveloped.Exemptedfromthislegalreservationarebriefexcerpts inconnectionwithreviewsorscholarlyanalysisormaterialsuppliedspecificallyforthepurposeofbeing enteredandexecutedonacomputersystem,forexclusiveusebythepurchaserofthework.Duplication ofthispublicationorpartsthereofispermittedonlyundertheprovisionsoftheCopyrightLawofthe Publisher’s location, in its current version, and permission for use must always be obtained from Springer.PermissionsforusemaybeobtainedthroughRightsLinkattheCopyrightClearanceCenter. ViolationsareliabletoprosecutionundertherespectiveCopyrightLaw. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publicationdoesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexempt fromtherelevantprotectivelawsandregulationsandthereforefreeforgeneraluse. While the advice and information in this book are believed to be true and accurate at the date of publication,neithertheauthorsnortheeditorsnorthepublishercanacceptanylegalresponsibilityfor anyerrorsoromissionsthatmaybemade.Thepublishermakesnowarranty,expressorimplied,with respecttothematerialcontainedherein. Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) Preface A leading use of speech recognition technology is the conversion of large speech databases into text for indexing and retrieval purposes. Using a large vocabulary continuous speech recognition (LVCSR) engine seems to provide a natural solu- tion,asspeechcanbefullyconvertedintotextandthenindexedandsearched. One method used for searching speech databases is Keyword Spotting (KWS). Speech recognition technology is used in KWS-based applications to enable spe- cificwordstobeidentifiedoutofastreamofcontinuousspeech.Thisisparticularly useful when a relatively small number of words need to be quickly pinpointed withinahugespeechdatabase. KWScanbeimplementedusingvariousmethods.Thephoneticsearchapproach is presented together with an analysis of its computational complexity. Following which, an anchor-based phonetic search algorithm is presented with evaluation results of its computational complexity. The KWS recognition performance using the anchor-based search is compared to an exhaustive search on several speech databases. The purpose of this brief is to present the challenges involved in performing phonetic search KWS in large speech databases, with a specific focus on efficient searching.Ideally,alltheunderlyingalgorithmsandrelatedtopicswouldhavebeen presented,howeverthiswouldbeincongruentwiththevalueofa“brief.”Thus in compensation,variouspublishedworkswerereferredtoincaseswhereadditional informationmaybehelpfultothereader. OurresearchiscurrentlyfocusedonphoneticsearchbasedKWSwithinalattice of phonemes and an extension of the search to multiple lattices generated from several languages in order to support KWS in languages with limited language resources. Tel-Aviv,Israel AmiMoyal VeredAharonson EllaTetariy MichalGishri v Acknowledgments The underlying anchor-based algorithm research reported here was partially supported by grants funded by the chief scientist of the Israeli Ministry of Com- merce.Theoriginalresearchtargetedthereductionoftheactivevocabularyusedby a speech recognition engine (Tetariy et al. 2010). We took this approach and appliedittoefficientkeywordspottinginlargespeechdatabases. WethanktheAfekaAcademicCollegeofEngineeringforinstitutionalsupport andespeciallytoProf.MotiSokolov,thecollegepresident,whohasbelievedinand supportedouractivitiesfromday1. Our appreciation to Springer for providing us with the opportunity to publish thisbrief. vii Contents 1 KeywordSpottingOutofContinuousSpeech. . . . . . . . . . . . . . . . . . . 1 1.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 ProblemFormulation:KWSinLargeSpeechDatabases. . . . . . . . . 5 1.3 TargetApplicationsofKeywordSpotting. . . . . . . . . . . . . . . . . . . 6 2 KeywordSpottingMethods. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1 LVCSR-BasedKWS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 AcousticKWS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.3 PhoneticSearchKWS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.4 Discussion:WhyPhoneticSearch?. . . . . . . . . . . . . . . . . . . . . . . . 9 2.4.1 ResponseTime. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.4.2 KWSPerformance. . .. . . . . . . .. . . . . . . .. . . . . . . .. . . . 10 2.4.3 KeywordFlexibility. .. . . . .. . . . .. . . . .. . . . .. . . . .. . . 10 3 PhoneticSearch. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.1 TheSearchMechanism. . .. . . . . . .. . . . . .. . . . . . .. . . . . .. . . . 13 3.2 UsingPhoneticSearchforKWS. . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.3 ComputationalComplexityAnalysis. . . . . . . . . . . . . . . . . . . . . . . 16 4 SearchSpaceComplexityReduction. . . . . . . . . .. . . . . . . . . .. . . . . . 19 4.1 Overview. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.2 ComplexityReductioninPhoneticSearch. . . . . . . . . . . . . . . . . . . 21 4.3 Anchor-BasedPhoneticSearch. . . . . . . . . . . . . . . . . . . . . . . . . . . 23 5 EvaluatingPhoneticSearchKWS. . . . . . .. . . . . . . . . . . . . . .. . . . . . 29 5.1 PerformanceMetrics. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5.2 EvaluationProcess. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 5.3 EvaluationDatabases. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 6 EvaluationResults. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 6.1 ExhaustiveSearch. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 6.1.1 TextualBenchmark. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 ix x Contents 6.1.2 KWSonSpeech. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 6.1.2.1 SingleThreshold. . . . . . . . . . . . . . . . . . . . . . . . . 37 6.1.2.2 MultipleThresholds. . . . . . . . . . . . . . . . . . . . . . . 38 6.2 Anchor-BasedSearch. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 6.2.1 TextualBenchmark. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 6.2.2 ReducedComplexityKWSonSpeech. . . . . . . . . . . . . . . . 39 6.2.2.1 SingleThreshold. . . . . . . . . . . . . . . . . . . . . . . . . 39 6.2.3 MultipleThresholds. .. . . . .. . . . .. . . . .. . . . .. . . . .. . . 42 6.3 LessonsLearnedfromtheEvaluation. . . . . . . . . . . . . . . . . . . . . . 43 7 Summary. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 GlossaryofAcronyms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 References. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49