ryan mcdonald gunftecisupennedu computationally hard problems speech language processing expressiveness vs tractability learning inference website httpwwwcisupenneduryantmnaaclws06 call papers modern machine learning methods maximum entropy models decision trees support vector machines provided language processing community robust tools supervised learning problems simple outputs methods provide natural mechanisms representing linguistic knowledge weighted features obtain high accuracy maximizing performance training data unfortunately one wishes apply similarly robust techniques problems complex outputs one limited models nice computational properties formulated terms sequence tree representations even relatively simple structures polynomial time algorithms exist strong restrictions locality features markov assumption sequences context free assumption trees moreover even assumptions complexity algorithms grow unwieldy even remaining polynomial instance case synchronous lexicalized context free grammars recent work ranking sampling approximate solutions problems indicated researchers coming back hard problems speech text efficient algorithms known exist might even argue language processing gain richer global feature representations new machine learning solutions purpose workshop explore new research aimed identifying solving speech language processing problems practical computational properties also wish explore adaptation current stateoftheart inference learning algorithms problems beyond sequence tree analysis particular workshop following themes problem identification specification formal investigations computational properties new old problems speech parsing translation summarization information extraction common language processing areas moving beyond markov contextfree assumptions underlying representations identifying linguistic implausibility assumptions global feature functions incorporate much richer information sentence document level properties well long distance dependencies joint representations incorporating syntax phrasestructure dependencies etc semantics entities relations predicatearguments efficient solutions problems historically viewed intractable appropriate natural representations problems effects complexityperformance structure search identifying old solutions eg classification sequential labeling new problems appropriate flexible solutions required learning inference approximate inference algorithms pros cons pruning techniques new approximation algorithms hard problems including based beam search sampling motivated methods surveys known approximation pruning methods identifying specific properties success failure efficiency vs performance tradeoffs formal characterizations search errors relation complexity approximate parameter estimation training techniques models parameter estimation intractable generative discriminative frameworks effects approximate parameter estimation performance learning parameters respect approximation search batch vs online learning techniques combined approximate inference joint structures complex systems pipelined methods sufficient need joint learning inference achieve maximum benefit benefits joint inference learning factorizable structures worth computational cost trade loss functions tractability necessary use structure components predicted separately theoretical practical comparisons computational complexity performance different loss functions differences complex onepass systems versus stackedmultipass decoding encourage submission papers address themes workshop interested completed work well works progress submissions maximum 8 pages use hltnaacl formatting guidelines obtained furthermore reviewing process blind names affiliations need removed title page well selfreferences reveal authors identity submissions sent gunftecisupennedu hltnaacl workshop submission title dates march 3 2006 paper submissions due 1159pm est april 7 2006 paper acceptance notification april 21 2006 camera ready versions due june 9 2006 workshop workshop website httpwwwcisupenneduryantmnaaclws06 organizers pc organizers hal daumé iii isi ryan mcdonald upenn contact gunftecisupennedu fernando pereira upenn program committee jeff bilmes washington michael collins mit jason eisner johns hopkins radu florian ibm liang huang upenn thorsten joachims cornell chris quirk microsoft dan roth uiuc noah smith johns hopkins charles sutton umass ben taskar berkeley wed 06 aug 2008 162836 0500 uai hltnaacl 2006 wrkshp computationally hard problems speech language processing