# US 2019/0378028 A1 · Accelerating machine learning inference with probabilistic predicates > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2019/0378028 A1 - Document ID: US20190378028A1 - Status: Published application - Kind: A1 - Application number: 16/003,495 - Filed: 2018-06-08 - Published: 2019-12-12 - Earliest claimed: 2018-06-08 - Applicants: Microsoft Technology Licensing, LLC - Inventors: Surajit Chaudhuri; Srikanth Kandula; Yao Lu - Web page: https://patentgrep.com/patent/US20190378028A1 ## CPC - G06F 16/90335: {Query processing} - G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks - G06F 16/2453: Query optimisation - G06F 16/248: Presentation of query results - G06N 5/048: Fuzzy inferencing - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS ## Abstract Implementations are presented for utilizing probabilistic predicates (PPs) to speed up searches requiring machine learning inferences. One method includes receiving a search query comprising a predicate for filtering blobs in a database utilizing a user-defined-function (UDF). The filtering requiring analysis of the blobs by the UDF to determine blobs that pass the filtering. Further, the method includes determining a PP sequence of PPs based on the predicate. Each PP is a classifier that calculates a PP-blob probability of satisfying a PP clause. The PP sequence defines an expression to combine the PPs. Further, the method includes operations for performing the PP sequence to determine a blob probability that the blob satisfies the expression, determining which blobs meet an accuracy threshold, discarding the blobs with the blob probability less than the accuracy threshold, and executing the database query over the blobs that have not been discarded. The results are then presented. ## Claims ### Claim 1 A method comprising: receiving a query to search a database, the query comprising a predicate for filtering blobs in the database utilizing a user-defined-function (UDF), the filtering requiring analysis of the blobs by the UDF to determine if the blobs pass the filtering specified by the predicate; determining a PP sequence of one or more probabilistic predicates (PP) based on the predicate, each PP being a binary classifier associated with a respective clause, the PP calculating a PP-blob probability that each blob satisfies the clause, the PP sequence defining an expression to combine the PPs of the PP sequence based on the predicate; performing the PP sequence to determine a blob probability that the blob satisfies the expression, the blob probability based on the PP-blob probabilities and the expression; determining which blobs have a blob probability greater than or equal to an accuracy threshold; discarding, from the search, the blobs with the blob probability less than the accuracy threshold; executing the database query over the blobs that have not been discarded, the database search utilizing the UDF; and providing results of the database search. ### Claim 2 (depends on 1) The method as recited in claim 1, wherein the blob is one of an image, a video, or a text document, wherein each PP performs a binary classification to determine if the blob meets the clause of the PP. ### Claim 3 (depends on 1) The method as recited in claim 1, wherein the query includes the accuracy threshold, wherein each PP is associated with a PP accuracy, cost of executing the PP, and a reduction rate. ### Claim 4 (depends on 3) The method as recited in claim 3, wherein determining the PP sequence further includes: selecting PPs, from an available pool of PPs, based on: the accuracy threshold in the query and the cost, PP accuracy, and reduction rates of PPs in the available pool of PPs. ### Claim 5 (depends on 1) The method as recited in claim 1, wherein the expression includes a logical OR operation of a first clause of a first PP and a second clause of a second PP, wherein performing the PP sequence further includes: executing the first PP to generate a first set of passing blobs that meet the first clause and a first set of failing blobs that do not meet the first clause; executing the second PP on the first set of failing blobs to generate a second set of passing blobs that meet the second clause and a second set of failing blobs that do not meet the second clause; and continuing the PP sequence with a union of the first set of passing blobs and the second set of passing blobs. ### Claim 6 (depends on 1) The method as recited in claim 1, wherein the expression includes a logical AND operation of a third clause of a third PP and a fourth clause of a fourth PP, wherein performing the PP sequence further includes: executing the third PP to generate a third set of passing blobs that meet the third clause and a third set of failing blobs that do not meet the third clause; executing the fourth PP on the third set of passing blobs to generate a fourth set of passing blobs that meet the fourth clause and a fourth set of failing blobs that do not meet the fourth clause; and continuing the PP sequence with the fourth set of passing blobs. ### Claim 7 (depends on 1) The method as recited in claim 1, wherein the expression includes a logical NOT operation of a fifth clause, wherein determining the PP sequence further includes: selecting between executing a fifth PP associated with the fifth clause or executing a sixth PP associated with a clause that is a logical NOT of the fifth clause. ### Claim 8 (depends on 1) The method as recited in claim 1, further comprising: analyzing queries received to search the database; selecting PPs based on the analyzed queries; and training the selected PPs. ### Claim 9 (depends on 1) The method as recited in claim 1, wherein the UDF includes one or more feature extractors and one or more classifiers, wherein each PP operates on the blobs in the database without using the feature extractors and the classifiers of the UDF. ### Claim 10 (depends on 1) The method as recited in claim 1, wherein each PP is a classifier trained with labeled data for a plurality of training blobs. ### Claim 11 A system comprising: a memory comprising instructions; and one or more computer processors, wherein the instructions, when executed by the one or more computer processors, cause the one or more computer processors to perform operations comprising: receiving a query to search a database, the query comprising a predicate for filtering blobs in the database utilizing a user-defined-function (UDF), the filtering requiring analysis of the blobs by the UDF to determine if the blobs pass the filtering specified by the predicate; determining a PP sequence of one or more probabilistic predicates (PP) based on the predicate, each PP being a binary classifier associated with a respective clause, the PP calculating a PP-blob probability that each blob satisfies the clause, the PP sequence defining an expression to combine the PPs of the PP sequence based on the predicate; performing the PP sequence to determine a blob probability that the blob satisfies the expression, the blob probability based on the PP-blob probabilities and the expression; determining which blobs have a blob probability greater than or equal to an accuracy threshold; discarding, from the search, the blobs with the blob probability less than the accuracy threshold; executing the database query over the blobs that have not been discarded, the database search utilizing the UDF; and providing results of the database search. ### Claim 12 (depends on 11) The system as recited in claim 11, wherein the blob is one of an image, a video, or a text document, wherein each PP performs a binary classification to determine if the blob meets the clause of the PP. ### Claim 13 (depends on 11) The system as recited in claim 11, wherein the query includes the accuracy threshold, wherein each PP is associated with a PP accuracy, cost of executing the PP, and a reduction rate. ### Claim 14 (depends on 13) The system as recited in claim 13, wherein determining the PP sequence further includes: selecting PPs, from an available pool of PPs, based on: the accuracy threshold in the query and the cost, PP accuracy, and reduction rates of PPs in the available pool of PPs. ### Claim 15 (depends on 11) The system as recited in claim 11, wherein the expression includes a logical OR operation of a first clause of a first PP and a second clause of a second PP, wherein performing the PP sequence further includes: executing the first PP to generate a first set of passing blobs that meet the first clause and a first set of failing blobs that do not meet the first clause; executing the second PP on the first set of failing blobs to generate a second set of passing blobs that meet the second clause and a second set of failing blobs that do not meet the second clause; and continuing the PP sequence with a union of the first set of passing blobs and the second set of passing blobs. ### Claim 16 A non-transitory machine-readable storage medium including instructions that, when executed by a machine, cause the machine to perform operations comprising: receiving a query to search a database, the query comprising a predicate for filtering blobs in the database utilizing a user-defined-function (UDF), the filtering requiring analysis of the blobs by the UDF to determine if the blobs pass the filtering specified by the predicate; determining a PP sequence of one or more probabilistic predicates (PP) based on the predicate, each PP being a binary classifier associated with a respective clause, the PP calculating a PP-blob probability that each blob satisfies the clause, the PP sequence defining an expression to combine the PPs of the PP sequence based on the predicate; performing the PP sequence to determine a blob probability that the blob satisfies the expression, the blob probability based on the PP-blob probabilities and the expression; determining which blobs have a blob probability greater than or equal to an accuracy threshold; discarding, from the search, the blobs with the blob probability less than the accuracy threshold; executing the database query over the blobs that have not been discarded, the database search utilizing the UDF; and providing results of the database search. ### Claim 17 (depends on 16) The non-transitory machine-readable storage medium as recited in claim 16, wherein the blob is one of an image, a video, or a text document, wherein each PP performs a binary classification to determine if the blob meets the clause of the PP. ### Claim 18 (depends on 16) The non-transitory machine-readable storage medium as recited in claim 16, wherein the query includes the accuracy threshold, wherein each PP is associated with a PP accuracy, cost of executing the PP, and a reduction rate. ### Claim 19 (depends on 18) The non-transitory machine-readable storage medium as recited in claim 18, wherein determining the PP sequence further includes: selecting PPs, from an available pool of PPs, based on: the accuracy threshold in the query and the cost, PP accuracy, and reduction rates of PPs in the available pool of PPs. ### Claim 20 (depends on 16) The non-transitory machine-readable storage medium as recited in claim 16, wherein the expression includes a logical OR operation of a first clause of a first PP and a second clause of a second PP, wherein performing the PP sequence further includes: executing the first PP to generate a set of first passing blobs that meet the first clause and a set of first failing blobs that do not meet the first clause; executing the second PP on the set of first failing blobs to generate a set of second passing blobs that meet the second clause and a set of second failing blobs that do not meet the second clause; and continuing the PP sequence with a union of the set of first passing blobs and the set of second passing blobs.