Answering Natural Language Queries From Spreadsheets
Imagine a site owner shares information on the web using spreadsheets or databases. I wrote a related post at Natural Language Query Responses. We see Google with patents focused on data tables natural language queries. Today’s blog post is about answering questions about spreadsheets or databases written using natural language.
A searcher may want to access that information combined in many ways. This is something that Google has patented. I will go over this patent granted in May 2021 and what it says.
The patent starts with data tables in spreadsheets and then shows how the search engine might make it easier for a searcher to use that information.
A spreadsheet is a data document that includes one or more data tables storing data under different categories.
Sometimes the spreadsheet may perform calculation functions. For example, a searcher may want certain data from the spreadsheet. The searcher can then construct a database search query to look for the desired data.
Sometimes, the spreadsheet may not store the searcher-desired data set. The searcher may use available data from the spreadsheet to derive the desired data.
The searcher may review the spreadsheet identifying relevant data entries in the spreadsheet to compile a formula using the calculation function associated with the spreadsheet to calculate the result.
For example, when the spreadsheet records a test score for each student in a class, a searcher may want to know the average score of the class.
Then the searcher may need to compile a formula by summing up the test scores and then dividing by the number of students to find the average score of the class.
The data table may then calculate the average score of the class based on the compiled formula.
Thus the searcher may need to compile a formula and input it into the data table for calculation, which may be inefficient when processing a large amount of data. It also requires a high level of knowledge of database operations from the searcher.
This granted patent covers systems and methods to process natural language queries on data tables, such as spreadsheets.
According to the patent, natural language queries may originate from a searcher.
A natural language query may find a query term and a grid range from a data table relevant to the query term.
A table summary may be created, including data entities based on the grid range.
A logic operation may then apply to the number of data entities to derive the query term.
The logic operation may then be turned into a formula executable on the data table. Finally, you can apply the formula to the data table to generate a result in response to the natural language query.
Natural language queries can be submitted through a searcher interface at a computer or manually or vocally entered by a searcher.
Natural language queries can be received at servers from computers through HTTP requests.
Natural language queries can originate in a first language (e.g., non-English, etc.) and then be translated into a second language, e.g., English, for processing.
A grid range is identified at a computer when the data table is stored at the computer or a server after receiving the natural language query when the data table is stored at the server.
The data table includes any data table stored at a computer, a remote server or a cloud.
The number of data entities includes any of dimensions, dimension filters, and metrics.
The result is presented to the searcher via a visualization format, including any answer statement, a chart, or a data plot.
The search engine may obtain Searcher feedback after the result is provided to the searcher. For example, the formula may be associated with the natural language query or the query term when the searcher feedback is positive.
When the searcher feedback is negative, an alternative interpretation of natural language queries may be provided, and alternative results may be provided based on the alternative interpretation.
Systems and methods for processing a natural language query in data tables
Inventors: Nikunj Agrawal, Mukund Sundararajan, Shrikant Ravindra Shanbhag, Kedar Dhamdhere, McCurley Garima, Kevin Snow, Rohit Ananthakrishna, Daniel Adam Gundrum, Juyun June Song, and Rifat Ralfi Nahmias
Assignee: Google LLC
US Patent: 10,997,227
Granted: May 4, 2021
Filed: January 18, 2017
Abstract
Systems and methods are disclosed herein for processing a natural language query on data tables.
According to some embodiments, a natural language query may be originated by a searcher via a searcher interface.
The natural language query may be parsed to obtain a query term, and a grid range may be identified in a data table as relevant to the query term.
A table summary may be prepared, including many data entities based on the grid range.
A logic operation may then be determined to apply to the plurality of data entities to derive the query term.
The logic operation may then be translated into a formula executable on the data table. The formula is applied to the data table to generate a result in response to the natural language query.
To provide an overall understanding of the disclosure, certain illustrative embodiments will now be described, including systems and methods for connecting with remote databases.
In particular, a connection between an application and a remote database is described.
The application modifies the data format imported from the remote database before displaying the modified data to the searcher.
However, it will be understood by one of ordinary skill in the art that the systems and methods described herein may be adapted and modified as is appropriate for the application being addressed and that the systems and methods described herein may be employed in other suitable applications, and that such other additions and modifications will not depart from the scope thereof.
Generally, the computerized systems described herein may comprise one or more engines, which include a processing device or devices, such as a computer, microprocessor, logic device, or other device or processor that is configured with hardware, firmware, and software to carry out one or more of the computerized methods described herein.
Systems and methods for processing a natural language query allow a searcher to enter a query for data in natural language.
The natural language query may be translated into a structured database query. When the structured database query indicates the data is not readily available in the data table, existing data entries may be identified in the data table that may be relevant to generate the desired data. Then, the formula may be automatically compiled to derive the desired data based on the available data entries.
For example, when the data source includes a spreadsheet that records a test score for each student in a class, a searcher may input a natural language query, “what is the average score of the class?”
The natural language query may be interpreted and parsed by extracting terms from the query, such as “what,” “is,” “the,” “average,” “score,” “of,” “the,” and “class.”
Among the extracted terms, the term “average score” may be identified as a key term of the query based on previously stored key terms that are commonly used.
It may then be determined that no data entry is available in the spreadsheet corresponding to the data category “average score,” e.g., no column header corresponds to “average score.”
Logic may then be identified to derive an “average score” from the existing data entries.
For example, it may be determined that an “average score” may be calculated by summing up all the test scores in the class and dividing the sum by the total number of students.
A formula may then be automatically generated to calculate the “average score” and output the calculation result to the searcher in response to the natural language query.
The generated formula may be stored in association with a tag “average score” such that even when the spreadsheet is updated with more data entries, e.g., with new test scores associated with additional students, the formula may still be applicable to automatically calculate an average score of the class, in response to the natural language query.
In this way, a searcher may get an answer about their data in a faster and more efficient way than by manually entering formulas or doing other forms of analysis by hand.
For searchers who may not know all the spreadsheet features, the platform may help the searcher generate structured queries or even formulas.
A Computerized System for Data Tables Natural Language Query Processing
The system includes a server, two remote databases (generally referred to as a remote database), searcher devices (generally referred to as a searcher device), and/or other related entities that communicate with one another over a network. The searcher devices contain searcher interfaces (generally referred to as searcher interface) respectively.
Each searcher device includes a device such as a personal computer, a laptop computer, a tablet, a smartphone, a personal digital assistant, or any other suitable type of computer or communication device.
Searchers at the searcher device access and receive information from the server and remote databases over the network.
The searcher device may include components, such as an input device and an output device.
A searcher may operate the searcher device to input a natural language query via the searcher interface, and the processor may process the natural language query.
The searcher device may process the natural language query and search within a local database.
The searcher device may send the natural language query to a remote server storing data tables and using a processor to analyze the natural language query.
The server may provide updates and may access remote databases a-b for a data query.
Thus, when a natural language query is received at the searcher device, upon translation of the query into a database query, the database query may be performed locally at the searcher device, at the data tables stored at the server, or at the remote databases (e.g., cloud, etc.).
The searcher device may have a locally installed spreadsheet application for a searcher to review data and enter a natural language query.
Aspects of Processing Natural Language Queries Using Spreadsheets
Natural language queries may be received with a searcher interface.
Natural language queries may be questions from searchers such as the growth of monthly total sales” “what is the average score of MATH 301.,”
Natural language queries may be entered by a searcher with input devices or articulated by a searcher using a microphone through the searcher device.
Natural language queries may come from an analytics application and be passed through to the server via an application programming interface (API) from another program.
For example, a business analytics software may include a list of business analytics questions such as “how’s the growth of monthly total sales” in a natural language. Then, the question may be sent to the server.
Natural language queries may originate in many different natural languages. It may be translated into a language compatible with the platform (e.g., the operating system, or the natural language query processing tool, and/or the like), such as English, etc.
Natural language queries may extract key terms, and a query string may be generated.
The parsing may be performed at the searcher device.
The server may receive a parse request over HTTP from the searcher device.
The server may send a request to an analytics module.
For example, for a natural language question, “what is the monthly growth of sales,” words in the question may be extracted and assessed to rule out words such as “what,” “is,” “the,” “of,” etc. as meaningful query terms.
Words such as “monthly growth” and “sales” may be identified as query terms based on previously stored query term rules and/or heuristics from previously processed queries.
The query string may optionally be sent to the server. Alternatively, natural language queries may be processed within one or more spreadsheets that are locally stored on the searcher device.
One or more data tables or spreadsheets, or a grid range of a spreadsheet, may be identified as relevant to the query string.
A table detection module may be used to output tables detected from originally stored data tables or spreadsheets, e.g., based on heuristics or machine learning. For example, natural language key terms from the query string may be used to identify relevant data tables/spreadsheets.
When the query string includes key terms such as “growth,” “monthly,” “sales,” data tables/spreadsheets that have a column or a row recording monthly sales may be identified.
As another example, data tables/spreadsheet can also be identified based on previously used data tables for similar query strings, e.g., when a natural language query “what is the monthly distribution of sales” identified a certain data table, the same data table may be identified for the query “how’s the growth of monthly total sales” as well.
The selected range of cells from the data table may be flipped in orientation if necessary.
The searcher may manually select the cells by selecting a single cell or a range of cells that may belong to a table.
The cells surrounding the selection are analyzed for possible table structures.
A table schema may be generated based on the selected range of cells.
Sometimes when the whole table schema is too small, to avoid communication of a large number of small messages from the computer to the server and improve communication efficiency, several table schemas may be sent in a batch request to the server.
When the identified table is too large to include in an XMLHttpRequest (XHR) request, the searcher device may only send the grid range of the detected table (for chart recommendations), and the server may determine a table structure from the sent grid range.
The server may prepare a table summary by extracting the dimensions, columns, rows, metrics, dimension filters, and/or other characteristics of the detected data table and map the extracted table characteristics to cell ranges or addresses in a spreadsheet.
For example, for a data table recording monthly sales data of the year, the table summary may include the number and index of rows and columns, the corresponding value in a cell identified by the row and column number, the metric of the value, and/or the like.
The server may extract operations to the data table and translate the operations into one or more formulas executable on the data table.
The server may send the formula(s) back to the searcher device. The formula(s) may be applied to the detected data table to generate a result in response to a natural language query.
In some implementations, the generated result may be presented via different visualization, such as, but not limited to, a pie chart, a data plot, and/or the like.
When the searcher receives the result in response to the original question via a searcher interface (e.g., see FIG. 4), the searcher may provide feedback on the result.
For example, the searcher may provide a positive rating if the result is accurate.
Or, the searcher may submit a negative rating when the result is unsatisfactory, e.g., misinterpreting the question, insufficient data, etc.
When the searcher feedback is positive, the server may save the formula building objects such as the table summary and formula(s) associated with the query string for machine learning purposes. The formula may be reused or used as a reference when similar questions are received.
When the searcher feedback is negative, the server may disassociate the formula building objects with the question. When similar questions are received, such questions are not to be interpreted in the same way.
The server may optionally obtain further information from the searcher’s feedback on the result.
For example, if the searcher asks, “how’s the monthly growth of sales,” and a result of the monthly increase from last month to the current month is, although, still. Still, the searcher submits negative feedback. The searcher interface may prompt the searcher to provide further information.
The searcher may be prompted to re-enter the question with a time period “how’s the monthly growth of sales from ______ to ______?” Or the searcher interface may prompt the searcher to confirm whether the identified data entities “monthly growth” and “sales” are accurate.
As another example, the searcher interface may provide suggested queries to the searcher if the server fails to parse and identify what the natural language query is.
Other additional methods may be employed for the searcher to provide further detailed feedback to refine the question.
The server may provide an alternative interpretation of the query string based on information obtained and generate an alternative formula using the alternative table summary.
Then the server may proceed to provide the updated result to the searcher.
Data Flows between the Client-Side and the Server-Side to Process Data Tables Natural Language Queries
A searcher interface may present an answer panel, which may post a query request to a backend.
The query may include a query string (e.g., the question asked by a searcher, or key terms extracted from the original natural language question asked by the searcher, etc.), a list of data entities (e.g., table schema generated based on key terms from the query string, etc.), a grid range from an existing data table, or the like.
The backend server may run using a java environment. It may pass the query request to a series of modules such as a get-answer action module, an entity list extractor, an analytics module, a query interpreter, a table detector, or the like.
The get-answer action module may act as a communication interface receiving the client request, which may include query parameters such as a query string (e.g., the question asked by the searcher, etc.), a grid range of the data table detected in and around cell selection, or the like.
If the request has reached the server, the grid range may contain a constructed table. If no data table is detected or the selected grid range does not contain any data, the answer panel interface may not be presented to a searcher initially.
The get-answer action module may send the grid range information to the entity list extractor to get a table view of the data entity list based on the grid range information, e.g., a sub-table with columns rows defining relevant data entities.
The entity list extractor may construct a table schema, e.g., a data entity list including data entities relevant to the query.
The entity list extractor may obtain a table summary (e.g., including column headers, data types, labels column, cell metrics, and/or other properties) from the table detector.
The entity list extractor may also build a typed table from the grid range and pass it on to the table detector for summarization.
The entity list extractor may provide a table view that represents the data entity list.
The entity list may be in a data structure as a per-table knowledge graph, represented by graph nodes such as but not limited to dimensions, dimension filters, metrics, and/or the like.
Dimensions may include the header of a column whose values act as row keys (or labels) into the table.
For example, “Country” will be a dimension in a table with country names as labels or row keys).
Dimension filters may include values in the dimension column (row keys/label column).
For example, “India” “U.S.A” is the dimension filters for the dimension “Country.” Metrics may include all number columns taken as metrics or column values.
Generally, a searcher may look for metrics for a particular dimension filter (or label). For example, in the string “Population of India,” “Population” is identified as a metric, and dimension filter is identified as “India” for dimension “Country.”
The entity list extractor may provide an entity list table view to the get-answer action module.
The entity list table view may be generated by extracting metrics, dimensions, and dimension filters from the table summary.
For example, it may be assumed that all column headers that correspond to cells with numeric values are metrics (e.g., a column header “population” is a metric as in the above example), all string and date/time column headers are dimensions (e.g., a column header “country,” a text string, is a dimension).
The values in these dimension columns are dimension filters (e.g., values under the column header “country” such as “U.S.A.,” “India,” etc., are dimension filters).
Other determination of the metrics, dimensions, and dimension filters can be applied.
In addition, the entity list table view may serve to reverse lookup row and column indices given a dimension, metric, or dimension filter string, which may be used to map parameters such as dimensions, metrics, dimension filters back to the grid row, and column indices during formula construction.
To allow this, the entity list table view may provide a metrics-to-column number map, a dimensions-to-column number map, and a dimension-filters-to-row-and-column pair map.
The table detector may extract information from a data table and generate a table summary, determining what entities in the table can generate a formula to derive the query term.
Tables can be generally represented as a common object, which stores the data in a table, the column headers and types of data in the columns, and derived facts about the data.
The table detector may extract information from a data table in several steps.
First, light parsing of cells and inference of column headers and data types may be performed.
For cells with numeric values between 1900 and 2100, the cells may be interpreted as years instead of pure numeric values.
The table detector may then filter out spurious rows and columns, including but not limited to empty rows/columns, numeric columns with ID numbers, columns for taking notes, and/or the like.
The table detector may then add column-based statistics.
For example, for all column types, the number of missing or distinct values may be recorded.
The number of negative/positive/floats/zero values and the sum, standard deviation, monotonicity, and uniformity of the array may be recorded.
For string columns, the ratio of numeric to non-numeric characters, an average string length, and a maximum string length may be recorded.
The table object created from the input table cell values from the data table may create an aggregate table.
Each column in the aggregate table may be inspected to determine the number of unique values compared to the total values (e.g., the range of data values).
If the column is categorical (e.g., when the unique values in the column are a subset of the entire spectrum of data values), then the column may be used to create an aggregated table.
For each categorical column, two aggregated objects may be created in association with the column.
A new “count” aggregated object may be created to record information relating to the “count” of a unique value.
For example, each row of the object may represent a unique value. In each row, the first cell stores the unique value, and the second cell records the number of times that the respective unique value appears in the original categorical column.
A new “sum” aggregated object may be created to record the total sum of each unique value in the original table.
For example, each row of the object represents a unique value, and each column of the object represents a categorical numeric column in the original table.
The value in each cell of the object represents a sum of unique values of all cells in the respective categorical column that contain the respective unique value (based on the respective row of the object).
The “count” and “sum” objects may be examples of objects for aggregation.
Alternatively, average aggregation objects may be created, e.g., using an average value of the “count” or “sum.” The objects recording the count and sum of each unique value may be used to carry information from the original data table.
The get-answer action module may also send a parse request, including data entity list information and query information, to the analytics module, generating a parse response.
The parse response may include a structured data table/spreadsheet query represented as the query in the protocol buffer.
The query interpreter may interpret returned query response to an executable formula string using the entity list table view passed on from the get-answer action module.
The query interpreter may include various comparable classes for formula builder, e.g., a particular formula builder may correspond to one type of formula.
Here a given set and count of fields in the query may correspond to only one formula, e.g., a query with exactly two metrics corresponds to a correlation formula.
For example, the query interpreter may invoke a variety of operations.
An example operation includes a query scoring operation, e.g., scoreQuery (the query in the protocol buffer), which returns a score, built by counting the number of fields of the input query in the protocol buffer it can consume, or returns a negative/zero score if the fields in the query in the protocol buffer are not sufficient to build a formula.
For example, if the input query in the protocol buffer having two-dimension filters and a dimension is passed to a formula builder that requires at least one dimension filter and at least one dimension, the scoreQuery( ) operator may return a score of two (e.g., one point for satisfying the at least one dimension requirement and one point for satisfying the at least one dimension filter requirement).
The two (non-zero scores) indicate that the parameters included in the query in the protocol buffer are sufficient for formula building.
A given query may have more than one formula builder that may return the same score, e.g., if another formula builder requires just two-dimension filters, the input query in the protocol buffer in the above example would also be given a score of two with this formula builder.
The query interpreter may then run a getFormula (query in the protocol buffer, EntityListTableView) operation, based on the input of the query and the entity list table view.
After determining that a query score is a positive number, the query interpreter may return a formula built by joining data in the input values query in the protocol buffer and EntityListTableView.
The query interpreter may take in a list of formula builders available (injected) and may interpret the input query in the protocol buffer by first scoring each formula builder by the number of fields of the input query in the protocol buffer may consume.
This may filter out a set of formula builders that cannot understand the input query in the protocol buffer.
If there is at least one formula builder with a positive score in response to the input query in the protocol buffer, the formula builder with the highest score may be used to map a formula.
In this way, the formula builder that consumes the maximum number of fields from the input query in the protocol buffer can construct the possible formula parses.
The query interpreter may be structured as a class with multiple smaller formula builders plugged into it.
In this way, the query interpreter structure can be expandable with additional formula builders.
For example, when a different type of query is received, a new formula type may be added to the formula builders without changing the existing formula builder.
When the get-answer action module receives a formula from the query interpreter, a JSON response including the formula may be returned to the answer panel at the frontend (e.g., at the client-side).
The answer panel may then provide the formula to a formula preview calculator, which may, in turn, generate a result based on the formula. The answer panel may then provide the result to the searcher.
A Searcher Interface Diagram Showing the Answer Panel to Data Tables Natural Language Queries
An example mobile interface may show example mobile screens of the answer panel.
The answer panel may have an interface on a desktop computer, e.g., similar to a browser-based application.
A searcher can type a natural language question in the query box, e.g., “how’s the growth of monthly totals?”
The query box may provide a suggested query in response to the searcher entered question to help searchers better understand how to structure their own questions using precise terms.
The question intake at the query box may also automatically complete or correct typographical mistakes from the searcher-entered question. In addition, the data entities for the query can be auto-completed.
The query may be annotated with the same colors with relevant sections in a spreadsheet to show how key terms in the query relate to sections in the spreadsheet.
An answer may be provided, e.g., a statement containing a calculated result of the “monthly total.”
The answer may include a human-friendly interpretation of the answer in natural language, e.g., “for every week, monthly total increases by,” and the calculated result, “$1,500.”
The query “how’s the growth of monthly totals” may take various visualization formats.
For example, a chart may be generated showing different data plots over a period of time, such as the monthly totals, commission income, sales of product and service income, etc., as related to the query question “growth of monthly total.”
The answer panel may further provide analytics of the data plots.
The answer screen may include a rating button, a “like” or “dislike” button, or a “thumbs up” or “thumbs down” button for the searcher to provide feedback to the answer to the original question asked.