Document Open Access Logo

Weight Annotation in Information Extraction

Authors Johannes Doleschal , Benny Kimelfeld, Wim Martens, Liat Peterfreund

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2020.8.pdf
  • Filesize: 0.66 MB
  • 18 pages

Document Identifiers

Author Details

Johannes Doleschal
  • University of Bayreuth, Germany
  • Hasselt University, Belgium
Benny Kimelfeld
  • Technion - Israel Institute of Technology, Haifa, Israel
Wim Martens
  • University of Bayreuth, Germany
Liat Peterfreund
  • CNRS, IRIF - Université de Paris, France
  • University of Edinburgh, United Kingdom

Funding

This work was supported by the German-Israeli Foundation for Scientific Research and Development (GIF), grant I-1502-407.6/2019. The work of Johannes Doleschal and Wim Martens was also supported by the Deutsche Forschungsgemeinschaft (DFG), grant MA 4938/4-1. The work of Benny Kimelfeld and Liat Peterfreund was also supported by the Israel Science Foundation (ISF), grants 1295/15 and 768/19, and the DFG project 412400621 (DIP program).
  • Peterfreund, Liat: A part of the work was donewhile the author was affiliated with the Technion.

Acknowledgements

We are grateful to Matthias Niewerth for many useful discussions and his help regarding Theorem 7.1 and Shaull Almagor for many helpful comments regarding weighted automata. Furthermore, we thank the anonymous reviewers for ICDT 2020 for many helpful remarks.

Cite AsGet BibTex

Johannes Doleschal, Benny Kimelfeld, Wim Martens, and Liat Peterfreund. Weight Annotation in Information Extraction. In 23rd International Conference on Database Theory (ICDT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 155, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICDT.2020.8

Abstract

The framework of document spanners abstracts the task of information extraction from text as a function that maps every document (a string) into a relation over the document’s spans (intervals identified by their start and end indices). For instance, the regular spanners are the closure under the Relational Algebra (RA) of the regular expressions with capture variables, and the expressive power of the regular spanners is precisely captured by the class of vset-automata - a restricted class of transducers that mark the endpoints of selected spans. In this work, we embark on the investigation of document spanners that can annotate extractions with auxiliary information such as confidence, support, and confidentiality measures. To this end, we adopt the abstraction of provenance semirings by Green et al., where tuples of a relation are annotated with the elements of a commutative semiring, and where the annotation propagates through the (positive) RA operators via the semiring operators. Hence, the proposed spanner extension, referred to as an annotator, maps every string into an annotated relation over the spans. As a specific instantiation, we explore weighted vset-automata that, similarly to weighted automata and transducers, attach semiring elements to transitions. We investigate key aspects of expressiveness, such as the closure under the positive RA, and key aspects of computational complexity, such as the enumeration of annotated answers and their ranked enumeration in the case of numeric semirings. For a number of these problems, fundamental properties of the underlying semiring, such as positivity, are crucial for establishing tractability.

Subject Classification

ACM Subject Classification
  • Information systems → Information extraction
  • Theory of computation → Transducers
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Data provenance
Keywords
  • Information extraction
  • regular document spanners
  • weighted automata
  • provenance semirings
  • K-relations

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. Shaull Almagor, Udi Boker, and Orna Kupferman. What’s Decidable about Weighted Automata? In Automated Technology for Verification and Analysis, pages 482-491, 2011. Google Scholar
  2. Antoine Amarilli, Pierre Bourhis, Stefan Mengel, and Matthias Niewerth. Constant-Delay Enumeration for Nondeterministic Document Spanners. In ICDT, pages 22:1-22:19, 2019. Google Scholar
  3. Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, and Cristian Riveros. Efficient Logspace Classes for Enumeration, Counting, and Uniform Generation. In PODS, pages 59-73, 2019. Google Scholar
  4. Laura Chiticariu, Rajasekar Krishnamurthy, Yunyao Li, Sriram Raghavan, Frederick Reiss, and Shivakumar Vaithyanathan. SystemT: An Algebraic Approach to Declarative Information Extraction. In ACL, pages 128-137, 2010. URL: http://www.aclweb.org/anthology/P10-1014.
  5. Jason P. C. Chiu and Eric Nichols. Named Entity Recognition with Bidirectional LSTM-CNNs. TACL, 4:357-370, 2016. Google Scholar
  6. T. Colcombet. Logic and regular cost functions. In LICS, pages 1-4, 2017. URL: https://doi.org/10.1109/LICS.2017.8005061.
  7. Thomas Colcombet, Denis Kuperberg, Amaldev Manuel, and Szymon Torunczyk. Cost Functions Definable by Min/Max Automata. In STACS), volume 47, pages 29:1-29:13, 2016. URL: https://doi.org/10.4230/LIPIcs.STACS.2016.29.
  8. Johannes Doleschal, Benny Kimelfeld, Wim Martens, Yoav Nahshon, and Frank Neven. Split-Correctness in Information Extraction. In PODS, pages 149-163, 2019. URL: https://doi.org/10.1145/3294052.3319684.
  9. Manfred Droste and Werner Kuich. Semirings and Formal Power Series, pages 3-28. Springer Berlin Heidelberg, 2009. URL: https://doi.org/10.1007/978-3-642-01492-5_1.
  10. Manfred Droste, Werner Kuich, and Heiko Vogler. Handbook of Weighted Automata. Springer Publishing Company, Incorporated, 1st edition, 2009. Google Scholar
  11. Samuel Eilenberg. Automata, Languages, and Machines. Academic Press, Inc., Orlando, FL, USA, 1974. Google Scholar
  12. Zoltán Ésik and Werner Kuich. Finite Automata, pages 69-104. Springer Berlin Heidelberg, 2009. URL: https://doi.org/10.1007/978-3-642-01492-5_3.
  13. Ronald Fagin, Benny Kimelfeld, Frederick Reiss, and Stijn Vansummeren. Document Spanners: A Formal Approach to Information Extraction. J. ACM, 62(2):12, 2015. URL: https://doi.org/10.1145/2699442.
  14. Ronald Fagin, Benny Kimelfeld, Frederick Reiss, and Stijn Vansummeren. Declarative Cleaning of Inconsistencies in Information Extraction. ACM Trans. Database Syst., 41(1):6:1-6:44, 2016. URL: https://doi.org/10.1145/2877202.
  15. Fernando Florenzano, Cristian Riveros, Martín Ugarte, Stijn Vansummeren, and Domagoj Vrgoc. Constant Delay Algorithms for Regular Document Spanners. In PODS, pages 165-177, 2018. Google Scholar
  16. J. Nathan Foster, Todd J. Green, and Val Tannen. Annotated XML: queries and provenance. In PODS, pages 271-280, 2008. Google Scholar
  17. Dominik D. Freydenberger. A Logic for Document Spanners. Theory Comput. Syst., 63(7):1679-1754, 2019. Google Scholar
  18. Dominik D. Freydenberger, Benny Kimelfeld, and Liat Peterfreund. Joining Extractions of Regular Expressions. In PODS, pages 137-149, 2018. Google Scholar
  19. Joshua Goodman. Semiring Parsing. Computational Linguistics, 25(4):573-605, 1999. Google Scholar
  20. Todd J. Green, Gregory Karvounarakis, and Val Tannen. Provenance semirings. In Proceedings of the Twenty-Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 11-13, 2007, Beijing, China, pages 31-40, 2007. URL: https://doi.org/10.1145/1265530.1265535.
  21. Abhay Kumar Jha, Vibhor Rastogi, and Dan Suciu. Query evaluation with soft-key constraints. In PODS, pages 119-128, 2008. Google Scholar
  22. Ines Klimann, Sylvain Lombardy, Jean Mairesse, and Christophe Prieur. Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton. Theoretical Computer Science, 327(3):349-373, 2004. URL: https://doi.org/10.1016/j.tcs.2004.02.049.
  23. Daniel Krob. The Equality Problem for Rational Series with Multiplicities in the tropical Semiring is Undecidable. IJAC, 4(3):405-426, 1994. URL: https://doi.org/10.1142/S0218196794000063.
  24. Yaoyong Li, Kalina Bontcheva, and Hamish Cunningham. SVM based learning system for information extraction. In Deterministic and Statistical Methods in Machine Learning, volume 3635 of Lecture Notes in Computer Science, pages 319-339, 2004. Google Scholar
  25. Francisco Maturana, Cristian Riveros, and Domagoj Vrgoc. Document Spanners for Extracting Incomplete Information: Expressiveness and Complexity. In PODS, pages 125-136, 2018. Google Scholar
  26. Franz Mayr and Sergio Yovine. Regular Inference on Artificial Neural Networks. In CD-MAKE, volume 11015 of Lecture Notes in Computer Science, pages 350-369, 2018. Google Scholar
  27. Joshua J. Michalenko, Ameesh Shah, Abhinav Verma, Richard G. Baraniuk, Swarat Chaudhuri, and Ankit B. Patel. Representing Formal Languages: A Comparison Between Finite Automata and Recurrent Neural Networks. In ICLR (Poster), 2019. Google Scholar
  28. Mehryar Mohri. Weighted Automata Algorithms, pages 213-254. Springer Berlin Heidelberg, 2009. URL: https://doi.org/10.1007/978-3-642-01492-5_6.
  29. Nanyun Peng, Hoifung Poon, Chris Quirk, Kristina Toutanova, and Wen-tau Yih. Cross-Sentence N-ary Relation Extraction with Graph LSTMs. TACL, 5:101-115, 2017. Google Scholar
  30. Liat Peterfreund, Dominik D. Freydenberger, Benny Kimelfeld, and Markus Kröll. Complexity Bounds for Relational Algebra over Document Spanners. In PODS, pages 320-334. ACM, 2019. Google Scholar
  31. Liat Peterfreund, Balder ten Cate, Ronald Fagin, and Benny Kimelfeld. Recursive Programs for Document Spanners. In ICDT, volume 127, pages 13:1-13:18, 2019. Google Scholar
  32. Hoifung Poon and Pedro M. Domingos. Joint Inference in Information Extraction. In AAAI, pages 913-918, 2007. Google Scholar
  33. Michael O. Rabin. Probabilistic automata. Information and Control, 6(3):230-245, 1963. URL: https://doi.org/10.1016/S0019-9958(63)90290-0.
  34. Alexander Ratner, Stephen H. Bach, Henry R. Ehrenberg, Jason Alan Fries, Sen Wu, and Christopher Ré. Snorkel: Rapid Training Data Creation with Weak Supervision. PVLDB, 11(3):269-282, 2017. Google Scholar
  35. Matthew Richardson and Pedro Domingos. Markov Logic Networks. Mach. Learn., 62(1-2):107-136, 2006. URL: https://doi.org/10.1007/s10994-006-5833-1.
  36. Christopher De Sa, Ihab F. Ilyas, Benny Kimelfeld, Christopher Ré, and Theodoros Rekatsinas. A Formal Framework for Probabilistic Unclean Databases. In ICDT, volume 127, pages 6:1-6:18, 2019. Google Scholar
  37. Jacques Sakarovitch. Elements of Automata Theory. Cambridge University Press, 2009. URL: https://doi.org/10.1017/CBO9781139195218.
  38. Sunita Sarawagi. Information Extraction. Foundations and Trends in Databases, 1(3):261-377, 2008. URL: https://doi.org/10.1561/1900000003.
  39. Roy Schwartz, Sam Thomson, and Noah A. Smith. Bridging CNNs, RNNs, and Weighted Finite-State Machines. In ACL, pages 295-305, 2018. Google Scholar
  40. Roberto Segala. Probability and Nondeterminism in Operational Models of Concurrency. In CONCUR, pages 64-78, 2006. Google Scholar
  41. Prithviraj Sen, Amol Deshpande, and Lise Getoor. PrDB: managing and exploiting rich correlations in probabilistic databases. VLDB J., 18(5):1065-1090, 2009. Google Scholar
  42. Warren Shen, AnHai Doan, Jeffrey F. Naughton, and Raghu Ramakrishnan. Declarative Information Extraction Using Datalog with Embedded Extraction Predicates. In VLDB, pages 1033-1044, 2007. URL: http://www.vldb.org/conf/2007/papers/research/p1033-shen.pdf.
  43. Jaeho Shin, Sen Wu, Feiran Wang, Christopher De Sa, Ce Zhang, and Christopher Ré. Incremental Knowledge Base Construction Using DeepDive. PVLDB, 8(11):1310-1321, 2015. URL: http://www.vldb.org/pvldb/vol8/p1310-shin.pdf.
  44. Charles A. Sutton and Andrew McCallum. An Introduction to Conditional Random Fields. Foundations and Trends in Machine Learning, 4(4):267-373, 2012. Google Scholar
  45. David Torrents, Mikita Suyama, Evgeny Zdobnov, and Peer Bork. A genome-wide survey of human pseudogenes. Genome research, 13(12):2559-2567, 2003. Google Scholar
  46. Lusheng Wang and Tao Jiang. On the Complexity of Multiple Sequence Alignment. Journal of Computational Biology, 1(4):337-348, 1994. Google Scholar
  47. Gail Weiss, Yoav Goldberg, and Eran Yahav. Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples. In ICML, volume 80, pages 5244-5253, 2018. Google Scholar
  48. Jin Y. Yen. Finding the k Shortest Loopless Paths in a Network. Management Science, 17(11):712-716, 1971. URL: http://www.jstor.org/stable/2629312.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact