IP Library › Granted Patent US 11,488,044

Granted Patent B2

US 11,488,044 · App. 15/965,540 · Granted Nov 1, 2022

Classification and transformation of sequential event data

Inventors: William Enerson Harvey (San Francisco, CA); Thomas Janos Atwood (San Francisco, CA); Marc-Henri Gires (New York, NY)

Assignee: P44, LLC

G06N7/005 G06F9/542 G06F16/258 G06F16/285 G06N20/00 G06Q10/047

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 11,488,044
App. No.: 15/965,540
Granted: Nov 1, 2022
Kind: B2

External Links

USPTO Patent Center↗ Full Patent PDF↗

Abstract

A method and system are provided that apply a combination of machine learning and graph techniques to classify and transform sequential event data. In some embodiments, the method and system are applied to generate raw data in the shipping industry to automatically classify a sequence of status codes extracted from EDI data files corresponding to a series of physical events experienced by a shipping container into a sequence of meaningful milestones to provide improved visibility regarding the actual status of the shipping container. The method and system can be applied to classify and transform sequential event data for use in the shipping industry and in other applications.

Claims (221)

1. A system for processing events, comprising:

a processor configured to:

receive a current indicator corresponding to a current event;

append the current indicator to a sequence of indicators comprising previously received indicators sequentially ordered in a received order, wherein the sequence of indicators corresponds to a series of sequential events to form a current sequence of indicators;

generate current metrics for each indicator in the current sequence of indicators;

classify each indicator in the sequence of indicators in response to the current metrics by referencing a milestone graph, wherein the milestone graph is configured to define a valid ordered sequence of transitions to milestones and constraints associated with each transition from one milestone in the ordered sequence to another milestone in the ordered sequence;

receive a subsequent indicator corresponding to a subsequent event;

append the subsequent indicator to the current sequence of indicators to form an updated sequence of indicators;

generate updated metrics for each indicator in the updated sequence of indicators; and

classify, using a machine learning technique and based on the milestone graph, each indicator in the updated sequence of indicators in response to the updated metrics to generate a classification result for each indicator in the updated sequence of indicators and to improve an efficiency in finding an optimal solution in a tractable manner; and

a memory coupled to the processor and configured to provide the processor with instructions.

2. The system of claim 1 , wherein the valid ordered sequence of transitions to milestones comprises a plurality of valid ordered sequences of transitions to milestones, and wherein the processor is further configured to:

generate a set of current milestone probabilities including a probability of rejection for each indicator in the current sequence of indicators using at least one machine learning technique;

associate each of the current milestone probabilities in each set of current milestone probabilities for each indicator in the current sequence of indicators that is not a probability of rejection with a transition to a milestone;

classify each indicator in the current sequence of indicators in response to the current milestone probabilities;

generate a set of updated milestone probabilities including a probability of rejection for each indicator in the updated sequence of indicators using the at least one machine learning technique;

associate each of the updated milestone probabilities in each set of updated milestone probabilities for each indicator in the updated sequence of indicators that is not a probability of rejection with a transition to a milestone; and

classify each indicator in the updated sequence of indicators in response to the updated milestone probabilities.

3. The system of claim 1 , wherein the valid ordered sequence of transitions to milestones comprises a plurality of valid ordered sequences of transitions to milestones, and wherein the processor is further configured to:

detect and remove duplications of indicators from the current sequence of indicators to reduce a computational complexity and to improve an efficiency associated with determining an optimal classification solution;

generate a set of current milestone probabilities including a probability of rejection for each indicator in the current sequence of indicators using at least one machine learning technique;

reference a milestone graph defining a valid ordered sequence of transitions to milestones and associated constraints;

generate a current search space graph comprising a set of current valid paths through a set of current milestones in response to the referenced milestone graph and the current sequence of indicators;

classify each indicator in the current sequence of indicators in response to the current milestone probabilities by referencing the current search space graph;

detect and remove duplications of indicators from the updated sequence of indicators to reduce a computational complexity and to improve an efficiency associated with determining an optimal classification solution;

generate a set of updated milestone probabilities including a probability of rejection for each indicator in the updated sequence of indicators using the at least one machine learning technique;

reference the milestone graph defining the valid ordered sequence of transitions to milestones and associated constraints;

generate an updated search space graph comprising a set of updated valid paths through a set of updated milestones in response to the referenced milestone graph and the updated sequence of indicators; and

classify each indicator in the updated sequence of indicators in response to the updated milestone probabilities by referencing the updated search space graph.

4. The system of claim 1 , wherein the valid ordered sequence of transitions to milestones comprises a plurality of valid ordered sequences of transitions to milestones, and wherein the processor is further configured to:

generate a set of current milestone probabilities including a probability of rejection for each indicator in the current sequence of indicators using at least one machine learning technique;

reference a milestone graph defining a valid ordered sequence of transitions to milestones and associated constraints;

generate a current search space graph comprising a set of current valid paths through a set of current milestones in response to the referenced milestone graph and the current sequence of indicators;

classify each indicator in the current sequence of indicators in response to the selected current milestone probabilities;

generate a set of updated milestone probabilities including a probability of rejection for each indicator in the updated sequence of indicators using the at least one machine learning technique;

reference the milestone graph defining the valid ordered sequence of transitions to milestones and associated constraints;

classify each indicator in the updated sequence of indicators in response to the selected updated milestone probabilities.

5. The system of claim 1 , wherein the valid ordered sequence of transitions to milestones comprises a plurality of valid ordered sequences of transitions to milestones, and wherein the processor is further configured to:

generate a set of current milestone probabilities including a probability of rejection for each indicator in the current sequence of indicators using at least one machine learning technique;

reference a milestone graph defining a valid ordered sequence of transitions to milestones and associated constraints;

generate a current search space graph comprising a set of current valid paths through a set of current milestones in response to the referenced milestone graph and the current sequence of indicators;

select a current milestone probability from the set of current milestone probabilities for each indicator in the current sequence of indicators that maximizes a current product of the selected current milestone probabilities across all indicators in the current sequence of indicators in response to the current search space graph, wherein the current milestone probability for each indicator in the current sequence of indicators is selected in response to satisfying constraints on transitions to selected current milestones associated with each of the selected current milestone probabilities so as to form a valid path as defined by the current search space graph;

classify each indicator in the current sequence of indicators in response to the selected current milestone probabilities;

generate a set of updated milestone probabilities including a probability of rejection for each indicator in the updated sequence of indicators using the at least one machine learning technique;

reference the milestone graph defining the valid ordered sequence of transitions to milestones and associated constraints;

select an updated milestone probability from the set of updated milestone probabilities for each indicator in the updated sequence of indicators that maximizes an updated product of the selected updated milestone probabilities across all indicators in the updated sequence of indicators in response to the updated search space graph, wherein the updated milestone probability for each indicator in the updated sequence of indicators is selected in response to satisfying constraints on transitions to selected updated milestones associated with each of the selected updated milestone probabilities so as to form a valid path as defined by the updated search space graph; and

classify each indicator in the updated sequence of indicators in response to the selected updated milestone probabilities.

6. The system of claim 1 , wherein the valid ordered sequence of transitions to milestones comprises a plurality of valid ordered sequences of transitions to milestones, and wherein the processor is further configured to:

generate a set of current milestone probabilities including a probability of rejection for each indicator in the current sequence of indicators using at least one machine learning technique;

reference a milestone graph defining a valid ordered sequence of transitions to milestones and associated constraints;

generate a current search space graph comprising a set of current valid paths through a set of current milestones in response to the referenced milestone graph and the current sequence of indicators;

classify each indicator in the current sequence of indicators in response to the selected current milestone probabilities;

generate a set of updated milestone probabilities including a probability of rejection for each indicator in the updated sequence of indicators using the at least one machine learning technique;

reference the milestone graph defining the valid ordered sequence of transitions to milestones and associated constraints;

select an updated milestone probability from the set of updated milestone probabilities for each indicator in the updated sequence of indicators in response to finding an updated shortest path through the updated search space graph; and

classify each indicator in the updated sequence of indicators in response to the selected updated milestone probabilities.

7. The system of claim 6 , wherein the processor is further configured to find the current shortest path through the current search space graph using a uniform cost search algorithm and to find the updated shortest path through the updated search space graph using the uniform cost search algorithm.

8. The system of claim 1 , wherein the valid ordered sequence of transitions to milestones comprises a plurality of valid ordered sequences of transitions to milestones, and wherein the processor is further configured to:

generate a set of current milestone probabilities including a probability of rejection for each indicator in the current sequence of indicators using at least one machine learning technique;

reference a milestone graph defining a valid ordered sequence of transitions to milestones and associated constraints;

generate a current search space graph comprising a set of current valid paths through a set of current milestones in response to the referenced milestone graph and the current sequence of indicators;

associate a current cost function with each edge in the current search space graph;

select a current milestone probability from the set of current milestone probabilities for each indicator in the current sequence of indicators in response to finding a current path through the current search space graph that minimizes a combination of current cost functions associated with each edge traversed by the current path;

classify each indicator in the current sequence of indicators in response to the selected current milestone probabilities;

generate a set of updated milestone probabilities including a probability of rejection for each indicator in the updated sequence of indicators using the at least one machine learning technique;

reference the milestone graph defining the valid ordered sequence of transitions to milestones and associated constraints;

associate an updated cost function with each edge in the updated search space graph; select an updated milestone probability from the set of updated milestone probabilities for each indicator in the updated sequence of indicators in response to finding an updated path through the updated search space graph that minimizes a combination of updated cost functions associated with each edge traversed by the updated path; and

classify each indicator in the updated sequence of indicators in response to the selected updated milestone probabilities.

9. The system of claim 8 , wherein the current cost function associated with each edge in the current search space graph traversed by the current path is a negative logarithm of the current milestone probability associated with the transition to the particular milestone defined by each edge in the current search space graph traversed by the current path and wherein the updated cost function associated with each edge in the updated search space graph traversed by the updated path is a negative logarithm of the updated milestone probability associated with the transition to the particular milestone defined by each edge in the updated search space graph traversed by the updated path.

10. The system of claim 1 , wherein the valid ordered sequence of transitions to milestones comprises a plurality of valid ordered sequences of transitions to milestones, and wherein the processor is further configured to:

generate a set of current milestone probabilities including a probability of rejection for each indicator in the current sequence of indicators using at least one machine learning technique;

reference a milestone graph defining a valid ordered sequence of transitions to milestones and associated constraints;

generate a current search space graph comprising a set of current valid paths through a set of current milestones in response to the referenced milestone graph and the current sequence of indicators;

associate a current cost function with each edge in the current search space graph;

limit the set of current milestone probabilities to a subset of highest current milestone probabilities for each indicator in the current sequence of indicators and select a current milestone probability from the limited subset of highest current milestone probabilities to reduce a complexity of the current search space graph, wherein the current milestone probability is selected in response to finding a current path through the current search space graph that minimizes a combination of current cost functions associated with each edge traversed by the current path;

classify each indicator in the current sequence of indicators in response to the selected current milestone probabilities;

generate a set of updated milestone probabilities including a probability of rejection for each indicator in the updated sequence of indicators using the at least one machine learning technique;

reference the milestone graph defining the valid ordered sequence of transitions to milestones and associated constraints;

associate an updated cost function with each edge in the updated search space graph; limit the set of updated milestone probabilities to a subset of highest updated milestone probabilities for each indicator in the updated sequence of indicators and select an updated milestone probability from the limited subset of highest updated milestone probabilities to reduce a complexity of the updated search space graph, wherein the updated milestone probability is selected in response to finding an updated path through the updated search space graph that minimizes a combination of updated cost functions associated with each edge traversed by the updated path; and

classify each indicator in the updated sequence of indicators in response to the selected updated milestone probabilities.

11. The system of claim 10 , wherein the processor is further configured to:

limit the subset of highest current milestone probabilities to a subset of highest current milestone probabilities for each indicator in the current sequence of indicators by setting a current threshold; and limit the subset of highest updated milestone probabilities to a subset of highest updated milestone probabilities for each indicator in the updated sequence of indicators by setting an updated threshold.

12. The system of claim 1 wherein the sequential events are sequential physical events, the current event is a current physical event, the subsequent event is a subsequent physical event, and wherein the processor is further configured to determine an entity associated with the current indicator, wherein the previously received indicators and the subsequent indicator correspond to physical events associated with the entity.

13. A method of processing sequential events comprising:

receiving a current indicator corresponding to a current event;

appending the current indicator to a sequence of indicators comprising previously received indicators sequentially ordered in a received order, wherein the sequence of indicators corresponds to a series of sequential events to form a current sequence of indicators;

generating current metrics for each indicator in the current sequence of indicators;

classifying each indicator in the sequence of indicators in response to the current metrics by referencing a milestone graph, wherein the milestone graph is configured to define a valid ordered sequence of transitions to milestones and constraints associated with each transition from one milestone in the ordered sequence to another milestone in the ordered sequence;

receiving a subsequent indicator corresponding to a subsequent event;

appending the subsequent indicator to the current sequence of indicators to form an updated sequence of indicators;

generating updated metrics for each indicator in the updated sequence of indicators; and

classifying, using a machine learning technique and based on the milestone graph, each indicator in the updated sequence of indicators in response to the updated metrics to generate a classification result for each indicator in the updated sequence of indicators and to improve an efficiency in finding an optimal solution in a tractable manner.

14. The method of claim 13 , wherein the valid ordered sequence of transitions to milestones comprises a plurality of valid ordered sequences of transitions to milestones, the method further comprising:

generating a set of current milestone probabilities including a probability of rejection for each indicator in the current sequence of indicators using at least one machine learning technique;

associating each of the current milestone probabilities in each set of current milestone probabilities for each indicator in the current sequence of indicators that is not a probability of rejection with a transition to a milestone;

classifying each indicator in the current sequence of indicators in response to the current milestone probabilities;

generating a set of updated milestone probabilities including a probability of rejection for each indicator in the updated sequence of indicators using the at least one machine learning technique;

associating each of the updated milestone probabilities in each set of updated milestone probabilities for each indicator in the updated sequence of indicators that is not a probability of rejection with a transition to a milestone; and

classifying each indicator in the updated sequence of indicators in response to the updated milestone probabilities.

15. The method of claim 13 , wherein the valid ordered sequence of transitions to milestones comprises a plurality of valid ordered sequences of transitions to milestones, the method further comprising:

detecting and removing duplications of indicators from the current sequence of indicators to reduce a computational complexity and to improve an efficiency associated with determining an optimal classification solution;

generating a set of current milestone probabilities including a probability of rejection for each indicator in the current sequence of indicators using at least one machine learning technique;

referencing a milestone graph defining a valid ordered sequence of transitions to milestones and associated constraints;

generating a current search space graph comprising a set of current valid paths through a set of current milestones in response to the referenced milestone graph;

classifying each indicator in the current sequence of indicators in response to the current milestone probabilities by referencing the current search space graph;

detecting and removing duplications of indicators from the updated sequence of indicators to reduce a computational complexity and to improve an efficiency associated with determining an optimal classification solution;

generating a set of updated milestone probabilities including a probability of rejection for each indicator in the updated sequence of indicators using the at least one machine learning technique;

referencing the milestone graph defining the valid ordered sequence of transitions to milestones and associated constraints;

generating an updated search space graph comprising a set of updated valid paths through a set of updated milestones in response to the referenced milestone graph; and

classifying each indicator in the updated sequence of indicators in response to the updated milestone probabilities by referencing the updated search space graph.

16. The method of claim 14 , wherein the valid ordered sequence of transitions to milestones comprises a plurality of valid ordered sequences of transitions to milestones, the method further comprising:

generating a set of current milestone probabilities including a probability of rejection for each indicator in the current sequence of indicators using at least one machine learning technique;

referencing a milestone graph defining a valid ordered sequence of transitions to milestones and associated constraints;

generating a current search space graph comprising a set of current valid paths through a set of current milestones in response to the referenced milestone graph;

selecting a current milestone probability from the set of current milestone probabilities for each indicator in the current sequence of indicators that maximizes a current product of the selected current milestone probabilities across all indicators in the current sequence of indicators in response to the current search space graph, wherein the current milestone probability for each indicator in the current sequence of indicators is selected in response to satisfying constraints on transitions to selected current milestones associated with each of the selected current milestone probabilities so as to form a valid path as defined by the current search space graph;

classifying each indicator in the current sequence of indicators in response to the selected current milestone probabilities;

generating a set of updated milestone probabilities including a probability of rejection for each indicator in the updated sequence of indicators using the at least one machine learning technique;

referencing the milestone graph defining the valid ordered sequence of transitions to milestones and associated constraints;

generating an updated search space graph comprising a set of updated valid paths through a set of updated milestones in response to the referenced milestone graph;

selecting an updated milestone probability from the set of updated milestone probabilities for each indicator in the updated sequence of indicators that maximizes an updated product of the selected updated milestone probabilities across all indicators in the updated sequence of indicators in response to the updated search space graph, wherein the updated milestone probability for each indicator in the updated sequence of indicators is selected in response to satisfying constraints on transitions to selected updated milestones associated with each of the selected updated milestone probabilities so as to form a valid path as defined by the updated search space graph; and

classifying each indicator in the updated sequence of indicators in response to the selected updated milestone probabilities.

17. The method of claim 14 , wherein the valid ordered sequence of transitions to milestones comprises a plurality of valid ordered sequences of transitions to milestones, the method further comprising: