Case Study on Web-Scale Natural Language Processing for URL Word Breaking

Explore how web-scale NLP techniques are applied to break down URLs into words effectively. Various models and evaluations are discussed to address the challenges of handling diverse language styles and the need for matched data to ensure accuracy in different languages. The study emphasizes the importance of large data sets and simple models in enhancing word breaking performance for web URLs.

• NLP
• Natural Language Processing
• Web-Scale
• URL Word Breaking
• Data Models

shli202 Follow

Uploaded on Sep 20, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Web Scale NLP: A Case Study on URL Word Breaking Kuansan Wang, Chris Thrasher, Bo-June (Paul) Hsu Microsoft Research, Redmond, USA WWW 2011 March 31, 2011 Microsoft Research

2. More Data > Complex Model Banko and Brill. Mitigating the Paucity-of-Data Problems. HLT 01 Microsoft Research 2

3. More Data > Complex Model There is no data like more data? CIKM 08 Microsoft Research 3

4. NLP for the Web Scale of the Web Avoid manual intervention Efficient implementations Dynamic Nature of the Web Fast adaptation Simple models with matched data! Global Reach of the Web Need rudimentary multi-lingual capabilities Diverse Language Styles of Web Contents Multi-style language models Microsoft Research

5. Outline Web-Scale NLP Word Breaking Models Evaluation Conclusion Microsoft Research 5

6. Word Breaking Large Data + Simple Model (Norvig, CIKM 2008) Use unigram model to rank all possible segmentations Pretty good, but with occasional embarrassing outcomes More data does not help! Extension to trigram alleviates the problem Microsoft Research

7. Word Breaking for the Web Web URLs exhibit variety of language styles Matched data is crucial to accuracy! and in different languages Microsoft Research

8. Outline Web-Scale NLP Word Breaking Models Evaluation Conclusion Microsoft Research 8

9. MAP Decision Rule Special case of Bayesian Minimum Risk Speech, MT, Parsing, Tagging, Information Retrieval, Distortion Signal ? Observation ? Channel Problem: Given ?, find ? ?opt= argmax ? ? ? = argmax ? ? ? ?(?) ? ? ? ? ? : transformation model ?(?): prior Microsoft Research

10. MAP for Word Breaker Transformation Signal ? Output ? Channel ?: tweeter hash tag or URL domain name Ex. 247moms, w84um8 ?: what user meant to say Ex. 24_7_moms, w8_4_u_m8 (wait for you mate) Microsoft Research

11. Plug-in MAP Problem MAP decision rule is optimal only if ?(?) and ? ? ? are the correct underlying distributions Adjustments needed when estimated models ?(?) and ? ? ? have unknown errors Simple logarithmic interpolation: ?opt= argmax ? Random Field /Machine Learning: log ? ? ? + ?log ? ? ?? ? ???log ? ??? ?opt= argmax log? ? ? = argmax ? Bayesian Point estimation is outdated Assume parameters are drawn from some distribution Microsoft Research

12. Baseline Methods GM: Geometric Mean (Keohn and Kline, 2003) Widely used, especially in MT systems ?opt= argmax ? BI: Binomial Model (Venkataraman, 2001) log? ? ? = ? log?#+ WL: Word Length Normalization (Kaitan et al, 2009) log? ? ? = ?log? ?? All special cases/variations of MAP ?log? ?? /?, ? = ?1,?2, ,?? ? ? 1 log 1 ?# Microsoft Research

13. Proposed Method ME: Maximum Entropy Principle Model ?(?|?) Special case of BI (?#= 0.5) and WL (uniform) ?(?) using Microsoft Web N-gram, ? = 1.0 http://web-ngram.research.microsoft.com Microsoft Web N-gram (http://web-ngram.research.microsoft.com) Web documents/Bing queries (EN-US market) Rudimentary multilingual (NAACL 10) Frequent updates (ICASSP 09) Multi-style language model (WWW 10, SIGIR 10) Body 1.2 B 60 M Title Anchor Query 150 M 1-gram 252M 5-gram 237 B 3.8 B 8.9 B - Microsoft Research

14. Outline Web-Scale NLP Word Breaking Models Evaluation Conclusion Microsoft Research 14

15. Data Set 100K randomly sampled URLs indexed by Bing Simple tokenization 266K unique tokens Mostly ASCII characters Metric: Precision@3 Manually labeled word breaks Multiple answers are allowed Microsoft Research

16. Language Model Style 99% 98% ME 97% 1-gram 96% 2-gram 3-gram Matched style is crucial to precision! 95% 94% 93% Body Title Query Anchor Title is best although Body is 100x larger Nav queries often word-split URLs, but Query worse than Title Microsoft Research 16

17. Model Complexity 99% 98% 3-gram BI (2) 97% WL (1) ME (0) 96% Simple model is sufficient with matched data! 95% Body Title Query Anchor With mismatched data, model choice is crucial With matched data, complex models do not help Microsoft Research 17

18. Outline Web-Scale NLP Word Breaking Models Evaluation Conclusion Microsoft Research 18

19. Best = Right Data + Smart Model Style of language trumps size of data There is no data like more data provided it s matched data! Right data alleviates Plug-in MAP problem Complicated machine learning artillery not required; simple methods suffice Smart model gives us: Rudimentary multi-lingual capability Fast inclusion of new words/phrases Eliminate needs of human labor in data labeling http://research.microsoft.com/en-us/um /people/kuansanw/wordbreaker/ Microsoft Research

20. BACKUP SLIDES Microsoft Research 20

21. GM 1-gram 2-gram 3-gram Body Body 59.01% 44.68% 44.78% Title Title 61.55% 60.31% 58.70% 99.00% Anchor 60.46% 55.25% 54.84% 98.50% Query 54.83% 54.27% 54.83% 98.00% Query 97.50% 97.00% 96.50% 96.00% Anchor 95.50% 95.00% 3-gram 2-gram 1-gram Note: BI, WL are oracle results Microsoft Research