IP Library › Granted Patent US 12,511,486
Granted Patent B2
US 12,511,486 · App. 18/218,211 · Granted Dec 30, 2025

Bottom-up neural semantic parser

Inventors: Maxwell Crouse (Chicago, IL); Pavan Kapanipathi Bangalore (White Plains, NY); Achille Belly Fokoue-Nkoutche (White Plains, NY); Tamir Klinger (Brooklyn, NY); Subhajit Chaudhury (White Plains, NY); Ramon Fernandez Astudillo (White Plains, NY); Tahira Naseem (Briarcliff Manor, NY)
Assignee: International Business Machines Corporation
G06F40/30G06F40/205G06F40/40
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,511,486
App. No.
18/218,211
Granted
Dec 30, 2025
Kind
B2
Abstract

A decoder of a neural semantic parser receives input data associated with a natural language expression. An action is selected from a queue of actions, the queue of actions storing at least one action, the action being associated with an element from vocabulary of the natural language expression. The selected action is processed to build a tree structure where the processing of the selected action expands the tree structure with a node representing the element, where the tree structure is expanded bottom-up. A set of new actions is generated based on the node associated with the selected action and the vocabulary. The set of new actions is added to the queue of actions. The decoder repeats selecting, processing, generating and adding until a criterion is met. A logical form of the natural language expression is output based on the tree structure.

Claims (44)

1 . A computer-implemented method comprising:

receiving input data associated with a natural language expression;

selecting an action from a queue of actions, by a decoder of a neural semantic parser, the queue of actions storing at least one action, the action being associated with an element from vocabulary of the natural language expression;

processing the selected action to build a tree structure, by the decoder, wherein the processing of the selected action expands the tree structure with a node representing the element, wherein the tree structure is expanded bottom-up;

generating, by the decoder, a set of new actions based on the node associated with the selected action and the vocabulary, wherein each action in the set of new actions is a tuple representing a symbol drawn from the vocabulary, an ordered list of arguments, wherein each of the arguments is a node in the tree structure, and a probability that the symbol should be part of a returned output;

adding, by the decoder, the set of new actions to the queue of actions;

repeating, by the decoder, the selecting, processing, generating and adding until a criterion is met; and

outputting, by a decoder of a neural semantic parser, a logical form of the natural language expression, the logical form being a machine interpretable meaning representation of the input data, wherein the logical form is provided as an s-expression representing the tree structure, wherein symbols of the s-expression represent nodes of the tree structure.

2 . The computer-implemented method of claim 1 , wherein the tree structure is a directed acyclic graph (DAG).

3 . The computer-implemented method of claim 1 , wherein the action is selected based on the action meeting a threshold probability that the element is to be used in expanding the tree structure.

4 . The computer-implemented method of claim 1 , wherein the action is selected that has highest probability that the element is to be used in expanding the tree structure.

5 . The computer-implemented method of claim 1 , wherein the generating the set of new actions based on the node associated with the selected action and the vocabulary further includes, determining a probability that the tree structure should contain a new node representing an element of the vocabulary that has the node as an argument.

6 . The computer-implemented method of claim 1 , wherein the generating the set of new actions based on the node associated with the selected action and the vocabulary further includes, determining a probability that the tree structure should contain a new node representing an element of the vocabulary that has a pair of nodes in the tree structure as a left argument and a right argument.

7 . The computer-implemented method of claim 1 , wherein the action includes a generation action that makes the node a parent to an existing single node in the tree structure.

8 . The computer-implemented method of claim 1 , wherein the action includes a pointer action that makes the node a parent to an existing pair of sibling nodes in the tree structure.

9 . A computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions readable by a device to cause the device to:

receive input data associated with a natural language expression;

select an action from a queue of actions the queue of actions storing at least one action, the action being associated with an element from vocabulary of the natural language expression;

process the selected action to build a tree structure wherein the processing of the selected action expands the tree structure with a node representing the element, wherein the tree structure is expanded bottom-up;

generate a set of new actions based on the node associated with the selected action and the vocabulary, wherein each action in the set of new actions is a tuple representing a symbol drawn from the vocabulary, an ordered list of arguments, wherein each of the arguments is a node in the tree structure, and a probability that the symbol should be part of a returned output;

add the set of new actions to the queue of actions;

repeat selecting, processing, generating and adding until a criterion is met; and

output a logical form of the natural language expression, the logical form being a machine interpretable meaning representation of the input data, wherein the logical form is provided as an s-expression representing the tree structure, wherein symbols of the s-expression represent nodes of the tree structure.

10 . The computer program product of claim 9 , wherein the tree structure is a directed acyclic graph (DAG).

11 . The computer program product of claim 9 , wherein the action is selected based on the action meeting a threshold probability that the element is to be used in expanding the tree structure.

12 . The computer program product of claim 9 , wherein the action is selected that has highest probability that the element is to be used in expanding the tree structure.

13 . The computer program product of claim 9 , wherein the device is further caused to determine a probability that the tree structure should contain a new node representing an element of the vocabulary that has the node as an argument, in generating the set of new actions.

14 . The computer program product of claim 9 , wherein the device is further caused to determine a probability that the tree structure should contain a new node representing an element of the vocabulary that has a pair of nodes in the tree structure as a left argument and a right argument, in generating the set of new actions.

15 . The computer program product of claim 9 , wherein the action includes a generation action that makes the node a parent to an existing single node in the tree structure.

16 . The computer program product of claim 9 , wherein the action includes a pointer action that makes the node a parent to an existing pair of sibling nodes in the tree structure.

17 . A system comprising:

at least one computer processor;

at least one memory device coupled with the at least one computer processor;

the at least one computer processor configured to at least:

receive input data associated with a natural language expression;

select an action from a queue of actions the queue of actions storing at least one action, the action being associated with an element from vocabulary of the natural language expression;

process the selected action to build a tree structure wherein the processing of the selected action expands the tree structure with a node representing the element, wherein the tree structure is expanded bottom-up;

generate a set of new actions based on the node associated with the selected action and the vocabulary, wherein each action in the set of new actions is a tuple representing a symbol drawn from the vocabulary, an ordered list of arguments, wherein each of the arguments is a node in the tree structure, and a probability that the symbol should be part of a returned output;

add the set of new actions to the queue of actions;

repeat selecting, processing, generating and adding until a criterion is met; and

output a logical form of the natural language expression, the logical form being a machine interpretable meaning representation of the input data, wherein the logical form is provided as an s-expression representing the tree structure, wherein symbols of the s-expression represent nodes of the tree structure.

18 . The system of claim 17 , wherein the tree structure is a directed acyclic graph (DAG).

19 . The system of claim 17 , wherein the action is selected based on the action meeting a threshold probability that the element is to be used in expanding the tree structure.

20 . The system of claim 17 , wherein the action includes at least one of: a generation action that makes the node a parent to an existing single node in the tree structure; and a pointer action that makes the node a parent to an existing pair of sibling nodes in the tree structure.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jul 5, 2023
From: CROUSE, MAXWELL; KAPANIPATHI BANGALORE, PAVAN; FOKOUE-NKOUTCHE, ACHILLE BELLY; KLINGER, TAMIR; CHAUDHURY, SUBHAJIT; FERNANDEZ ASTUDILLO, RAMON; NASEEM, TAHIRA
To: INTERNATIONAL BUSINESS MACHINES CORPORATION
Reel/Frame 064154/0626 →
Continuity (1)
Related Publication 20250013829A1 · Jan 9, 2025
References Cited (93)
US 8131655B1 · Cosoi · 2012 [cited by examiner]
US 10078634B2 · Gou et al. · 2018 [cited by applicant]
US 10298700B2 · Borden · 2019 [cited by examiner]
US 11429876B2 · Bangalore et al. · 2022 [cited by applicant]
US 11966704B1 · Magary · 2024 [cited by examiner]
US 11977836B1 · Archambeau · 2024 [cited by examiner]
US 12165032B2 · Li · 2024 [cited by examiner]
US 20100161316A1 · Haug · 2010 [cited by examiner]
US 20110301942A1 · Collobert · 2011 [cited by examiner]
US 20140249804A1 · Jackson · 2014 [cited by examiner]
US 20150106079A1 · Bostick · 2015 [cited by examiner]
US 20150154173A1 · Kim · 2015 [cited by examiner]
US 20150261744A1 · Suenbuel · 2015 [cited by examiner]
US 20150356073A1 · Vion-Drury · 2015 [cited by examiner]
US 20180052817A1 · Bethard · 2018 [cited by examiner]
US 20190066660A1 · Liang · 2019 [cited by examiner]
US 20200104366A1 · Xu · 2020 [cited by examiner]
US 20210019370A1 · Andrassy · 2021 [cited by examiner]
US 20210209163A1 · Boxwell · 2021 [cited by examiner]
US 20220043981A1 · Liang · 2022 [cited by examiner]
US 20220129450A1 · Cao · 2022 [cited by examiner]
US 20220171932A1 · Parthasarathy · 2022 [cited by examiner]
US 20220188524A1 · Pfitzmann · 2022 [cited by examiner]
US 20220343903A1 · Mostafazadeh · 2022 [cited by examiner]
US 20230060589A1 · Ravishankar et al. · 2023 [cited by applicant]
US 20230111052A1 · Ray · 2023 [cited by examiner]
US 20230138152A1 · Jung · 2023 [cited by examiner]
US 20230305822A1 · Ferrucci · 2023 [cited by examiner]
US 20230306022A1 · Popescu · 2023 [cited by examiner]
US 20230342383A1 · Xia · 2023 [cited by examiner]
US 20240036837A1 · Tamilselvam · 2024 [cited by examiner]
US 20240176805A1 · Liu · 2024 [cited by examiner]
US 20240394251A1 · Brende · 2024 [cited by examiner]
US 20240427575A1 · Rajkumar Kannan · 2024 [cited by examiner]
US 20240427997A1 · Salama · 2024 [cited by examiner]
US 20250013829A1 · Crouse · 2025 [cited by examiner]
CN 105760462B · 2018 [cited by applicant]
CN 110765235A · 2020 [cited by applicant]
CN 110942769A · 2020 [cited by applicant]
CN 111898386A · 2020 [cited by applicant]
CN 115906868A · 2023 [cited by applicant]
Herzig, J., et al., “Span-based semantic parsing for compositional generalization” arXiv:2009.06040v2, Jun. 13, 2021, 14 pages. [cited by applicant]
Odena, A., et al., “Bustle: Bottom-Up program synthesis through learning-guided exploration”, arXiv:2007.14381v3, Sep. 30, 2021, 16 pages. [cited by applicant]
Rubin, O., et al., “SmBoP: Semi-autoregressive bottom-up semantic parsing”, arXiv:2010.12412v2, Apr. 11, 2021, 14 pages. [cited by applicant]
Andreas, J., et al., “Good-enough compositional data augmentation”, arXiv:1904.09545v4, May 19, 2020, 11 pages. [cited by applicant]
Bergen, L., et al., “Systematic generalization with edge transformers”, 35th Conference on Neural Information Processing Systems (NeurIPS 2021), iv:2112.00578v1, Dec. 1, 2021, 15 pages. [cited by applicant]
Crouse, M., “Question-Answering with Structural Analogy”, Ph.D. Thesis, Northwestern University, 2021, 107 pages. [cited by applicant]
Dong, L., et al., “Language to Logical Form with Neural Attention”, arXiv: 1601.01280v2, Jun. 6, 2016, 11 pages. [cited by applicant]
Dong, L., et al., “Coarse-to-Fine Decoding for Neural Semantic Parsing”, Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics, Jul. 15-20, 2018, pp. 731-742. [cited by applicant]
Drozdov, A., et al., “Compositional semantic parsing with large language models”, arXiv:2209.15003v2, Sep. 30, 2022, 59 pages. [cited by applicant]
Finegan-Dollack, C., et al., “Improving text-to-sql evaluation methodology”, arXiv:1806.09029v1, Jun. 23, 2018, 10 pages. [cited by applicant]
Furrer, D., et al., “Compositional Generalization in Semantic Parsing: Pre-training vs. Specialized Architectures”, arXiv:2007.08970v3, Sep. 22, 2021, 16 pages. [cited by applicant]
Gai, Y., et al., “Grounded Graph Decoding Improves Compositional Generalization in Question Answering”, arXiv:2111.03642v1, Nov. 5, 2021, 10 pages. [cited by applicant]
Guo, Y., et al., “Hierarchical Poset Decoding for Compositional Generalization in Language”, 34th Conference on Neural Information Processing Systems (NeurIPS 2020), arXiv:2010.07792v1, Oct. 15, 2020, 12 pages. [cited by applicant]
Herzig, J., et al., “Span-based Semantic Parsing for Compositional Generalization”, Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on … [cited by applicant]
Herzig, J., et al., “Unlocking Compositional Generalization in Pre-trained Models Using Intermediate Representations”, arXiv:2104.07478v1, Apr. 15, 2021, 13 pages. [cited by applicant]
Jambor, D., et al., “LAGr: Label Aligned Graphs for Better Systematic Generalization in Semantic Parsing”, arXiv:2110.07572v2, Jun. 1, 2022, 14 pages. [cited by applicant]
Jia, R., et al., “Data Recombination for Neural Semantic Parsing”, injectarXiv:1606.03622v1, Jun. 11, 2016, 11 pages. [cited by applicant]
Keysers, D., et al., “Measuring compositional generalization: A comprehensive method on realistic data”, arXiv: 1912.09713v2, Jun. 25, 2020, 38 pages. [cited by applicant]
Kwiatkowski, T., et al., “Lexical Generalization in CCG Grammar Induction for Semantic Parsing”, Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, Jul. 27-31, 2011, pp. 1512-1523. [cited by applicant]
Li, S., et al., “Graph-to-Tree Neural Networks for Learning Structured Input-Output Translation with Applications to Semantic Parsing and MathWord Problem”, Findings of the Association for Computational Linguistics: EMN… [cited by applicant]
Liang, P., et al., “Learning Dependency-Based Compositional Semantics”, Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, Jun. 19-24, 2011, pp. 590-599. [cited by applicant]
Liu, C., et al., “Learning Algebraic Recombination for Compositional Generalization”, arXiv:2107.06516v1, Jul. 14, 2021, 18 pages. [cited by applicant]
Wong, Y.W., et al., “Learning Synchronous Grammars for Semantic”, Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, Jun. 2007, pp. 960-967. [cited by applicant]
Xu, K., et al., “Graph2seq: Graph to sequence learning with attention-based neural networks”, arXiv:1804.00823v4, Dec. 3, 2018, 18 pages. [cited by applicant]
Zettlemoyer, L.S., et al., “Online Learning of Relaxed CCG Grammars for Parsing to Logical Form”, Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural La… [cited by applicant]
Zhao, K., et al., “Type-Driven Incremental Semantic Parsing with Polymorphism”, Human Language Technologies: The 2015 Annual Conference of the North American Chapter of the ACL, May 31-Jun. 5, 2015, pp. 1416-1421. [cited by applicant]
Zheng, H., et al., “Compositional Generalization via Semantic Tagging”, Findings of the Association for Computational Linguistics: EMNLP 2021, Nov. 7-11, 2021, pp. 1022-1032. [cited by applicant]
Crouse, M., et al., “Laziness Is a Virtue When It Comes to Compositionality in Neural Semantic Parsing”, arXiv:2305.04346v1 [cs.CL], May 7, 2023, 13 pages (Grace Period Disclosure). [cited by applicant]
Alvarez-Melis, et al., Tree-Structured Decoding With Doubly-Recurrent Neural Networks, ICLR, Feb. 6, 2017, 17 pages. [cited by applicant]
Carpenter B., Type-Logical Semantics, Language, Speech, and Communication, 1997, pp. 445-446. [cited by applicant]
Dahl, et al., Expanding the Scope of the ATIS Task: the ATIS-3 Corpus, HLT '94: Proceedings of the workshop on Human Language Technology, Mar. 8-11, 1994, pp. 43-48. [cited by applicant]
Dong, et al., Language to Logical Form with Neural Attention, Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, Aug. 7-12, 2016, pp. 33-43. [cited by applicant]
Higgins, et al., Scan: Learning Hierarchical Compositional Visual Concepts, arXiv: 1707.03389v3 [stat. ML], Jun. 6, 2018, 24 pages. [cited by applicant]
Hochreiter, et al., Long Short-Term Memory, Neural Computation, 1997, vol. 9, Issue 8, pp. 1735-1780. [cited by applicant]
Iyer, et al., Learning a Neural Semantic Parser from User Feedback, Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, Jul. 30-Aug. 4, 2017, pp. 963-973. [cited by applicant]
Kim, et al. ,Cogs: A Compositional Generalization Challenge Based on Semantic Interpretation, arXiv:2010.05465v1 [cs.CL], Oct. 12, 2020, 19 pages. [cited by applicant]
Krishnamurthy, et al., Neural Semantic Parsing with Type Constraints for Semi-Structured Tables, Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, Sep. 7-11, 2017, pp. 1516-1526. [cited by applicant]
Lake, et al., Building Machines That Learn and Think Like People, arXiv:1604.00289v3 [cs.Al], Nov. 2, 2016, 58 pages. [cited by applicant]
Lake, et al., Generalization Without Systematicity: On the Compositional Skills of Sequence-To-Sequence Recurrent Networks, arXiv: 1711.00350v3 [cs.CL], Jun. 9, 2018, 12 pages. [cited by applicant]
Mccarthy, et al., Recursive Functions of Symbolic Expressions and Their Computation By Machine, Part I, Communications of the ACM, Apr. 1, 1960, vol. 3, Issue 4, pp. 184-195. [cited by applicant]
Mccarthy, J., History of LISP, History of programming languages, Jun. 1, 1978, pp. 173-185. [cited by applicant]
Montague, R., The Proper Treatment of Quantification in Ordinary English, Springer, 1973, pp. 17-34. [cited by applicant]
Oren, et al., Improving Compositional Generalization in Semantic Parsing, Findings of the Association for Computational Linguistics: EMNLP 2020, Nov. 16-20, 2020, pp. 2482-2495. [cited by applicant]
Raffel, et al., Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer, arXiv:1910.10683v4 [cs.LG], Sep. 19, 2023, 67 pages. [cited by applicant]
Shaw, et al., Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?, arXiv:2010.12725v2 [cs.CL], Jun. 1, 2021, 17 pages. [cited by applicant]
Shaw, et al., Self-Attention with Relative Position Representations, Proceedings of NAACL-HLT 2018, Jun. 1-6, 2018, pp. 464-468. [cited by applicant]
Vaswani et al., Attention is All you Need, arXiv: 1706.03762v7 [cs.CL], Aug. 2, 2023, 15 pages. [cited by applicant]
Xiao, et al., Sequence-based Structured Prediction for Semantic Parsing, Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, Aug. 7-12, 2016, pp. 1341-1350. [cited by applicant]
Zelle, et al., Learning to Parse Database Queries Using Inductive Logic Programming, In Proceedings of the National Conference on Artificial Intelligence, Aug. 1996, pp. 1050-1055. [cited by applicant]
Zhang, et al., Spider: A Large-Scale Human-Labeled Dataset for Complex and Cross-Domain Semantic Parsing and Text-to-SQL Task, In EMNLP, Oct.-Nov. 2018, pp. 3911-3921. [cited by applicant]
Zhou, et al., AMR Parsing with Action-Pointer Transformer, arXiv:2104.14674v3 [cs.CL] May 18, 2021, 14 pages. [cited by applicant]
Zhou, et al., Structure-aware Fine-tuning of Sequence-to-sequence Transformers for Transition-based AMR Parsing, arXiv:2110.15534v1 [cs.CL] Oct. 29, 2021, 12 pages. [cited by applicant]