NETWORKS

CROSS-REFERENCE TO RELATED APPLICATIONS

[0001] This application claims the benefit of U.S. Provisional Application serial number 62/518072, filed on 12-JUN-2017, which is incorporated in its entirety by this reference.

TECHNICAL FIELD

[0002] This invention relates generally to the artificial intelligence field, and more specifically to new and useful systems and methods for event prediction using schema networks in the artificial intelligence field.

BACKGROUND

[0003] While computer vision remains a complex problem in artificial intelligence, recent achievements such as the recursive cortical network (RCN) have enabled computers to identify objects from visual data efficiently and with high accuracy. However, just as with human vision, object recognition is only a part of the skillset needed to effectively interact with an environment. Humans observe how objects interact with each other to infer properties of those objects; for example, by observing how a sphere reacts when dropped onto a hard surface, a human may be able to infer whether a ball is made of rubber, cork, or steel. This knowledge makes it easier to accurately interpret past events, and likewise, to predict future events.

[0004] Unfortunately, traditional approaches to computer vision are often inefficient at modeling the latent properties of objects observed from visual data. Thus, there is a need in the artificial intelligence field to create new and useful systems and methods for event prediction using schema networks. This invention provides such new and useful systems and methods.

BRIEF DESCRIPTION OF THE FIGURES [0005] FIGURE 1 is a factor graph representation of a system of an invention embodiment;

[0006] FIGURE 2 is a factor graph representation of a system of an invention embodiment;

[0007] FIGURE 3 is a factor graph representation of a system of an invention embodiment;

[0008] FIGURE 4 is a factor graph representation of a system of an invention embodiment;

[0009] FIGURE 5 is a factor graph representation of a system of an invention embodiment;

[0010] FIGURE 6 is a factor graph representation of a system of an invention embodiment;

[0011] FIGURES 7A and 7B are factor graph representations of a system of an invention embodiment;

[0012] FIGURE 8 is a factor graph representation of a system of an invention embodiment;

[0013] FIGURE 9A is a network representation of a recursive cortical network;

[0014] FIGURE 9B is a hierarchical representation of entity relationships of a system of an invention embodiment;

[0015] FIGURE 10 is a network representation of an entity dictionary of a system of an invention embodiment and connections;

[0016] FIGURE 11 is a chart representation of a method of an invention embodiment; and

[0017] FIGURE 12 is a network representation of attribute hierarchy of a method of an invention embodiment.

DESCRIPTION OF THE INVENTION EMBODIMENTS

[0018] The following description of the invention embodiments of the invention is not intended to limit the invention to these invention embodiments, but rather to enable any person skilled in the art to make and use this invention. [0019] One of the great problems of artificial intelligence research is that of generalization. Researchers have struggled to create machine learning models that are able to efficiently generalize information learned in training to new problems; resultantly, these models suffer in performance without exhaustive training (if such training is even feasible).

[0020] Some have attempted to address this issue by integrating object-based and relational representations in their models. For example, the Gestalt principle states that the ability to perceive objects as bounded figures in front of an unbounded background is fundamental to all visual perception. In this field, researchers have created models that detect objects and assign hardcoded properties to these objects (and/or to relationships between objects) to aid in recognition. While reasoning forward with such models (i.e., predicting future states of an environment based on contextual input) is relatively straightforward, reasoning backward is difficult if not impossible. Resultantly, these systems may be incapable of providing explanations for past events or determining causality.

[0021] The systems and methods of the present application are directed to event prediction using schema networks. More specifically, these systems and methods rely on the implementation of a generative model which allows for both forward and backward reasoning (enabling different causes of events to be distinguished) and does not require that latent properties of objects or relationships between objects be hardcoded (increasing the flexibility and usefulness of the model in generalization). l. System for Event Prediction

[0022] A system loo for event prediction using schema networks includes antecedent entity states no, schema factors 120, and consequent entity states 140, as shown in FIGURE 1. The system 100 may additionally include context variables 130.

[0023] The system 100 is implemented using a generative neural network. Neural networks and related systems, including recursive cortical networks (RCNs), convolutional neural networks (CNNs), hierarchical compositional networks (HCNs), HMAX models, Slow Feature Analysis (SFA) systems, and Hierarchical Temporal Memory (HTM) systems may be used for a wide variety of tasks that are difficult to complete using standard rule-based programming. These tasks include many in the important fields of computer vision and speech recognition.

[0024] Neural networks and related systems can be represented as distributed processing elements that implement summation, multiplication, exponentiation or other functions on the elements incoming messages/signals. Such networks can be enabled and implemented through a variety of implementations. For example, a system may be implemented as a network of electronically coupled functional node components. The functional node components can be logical gates arranged or configured in a processor to perform a specified function. As a second example, the system may be implemented as a network model programmed or configured to be operative on a processor. The network model is preferably electronically stored software that encodes the operation and communication between nodes of the network. Neural networks and related systems may be used in a wide variety of applications and can use a wide variety of data types as input such as images, video, audio, natural language text, analytics data, widely distributed sensor data, or other suitable forms of data.

[0025] The system 100 functions to enable event prediction (e.g., predicting future state given an initial state and input), event explanation (e.g., determining what input caused an entity to change state from an initial state to a future state), and regression planning (e.g., determining what input could cause an entity to change state from an initial state to a desired future state).

[0026] The system 100 operates on entities: groups of attributes associated with at least one observable feature. For example, the system 100 may include an entity for a ball detected by visual perception; the ball in turn may have a number of attributes associated with it, such as position, hardness, and friction coefficient. Entity attributes are represented by variables; at least one of these variables is preferably observable, while others maybe either observable or latent (noting that a latent variable is a variable whose value is not directly observed, but rather inferred from observation of observable variables). For example, the ball's position is an observable variable (since the position may be tracked by visual perception), while the ball's hardness and friction coefficient are latent variables.

[0027] Variables of the system 100 are preferably binary random variables, but may additionally or alternatively be multinomial random variables. Further, continuous variables may be represented by a binary discretization (a continuous variable is represented by a set of binary variables). Alternatively, variables of the system 100 may be of any type and may be expressed in any manner.

[0028] Each entity may be associated with a number of states; each state represents a set of values for an entity's attributes at a particular time. By linking different time states of an entity to contextual information (e.g., the states of other entities, context variables 130, etc.) via schema factors 120, the system 100 can be used to predict future entity states, to explain past entity states, to explore the effects various contextual data has on entity state, and/or to determine what context might be necessary to cause a particular entity state.

[0029] Entity attributes are preferably universal; that is, each entity of the system

100 has the same set of attribute variables (which may take on any allowed values for a given entity state). Alternatively, entities may have one or more non-universal attributes. The set of attribute variables corresponding to a given entity may be referred to as an attribute set.

[0030] In a given state transition, an antecedent entity state 110 is an initial entity state (e.g., time = t), while a consequent entity state 140 is a later entity state (e.g., time = t+i). Alternatively, a consequent entity state 140 maybe at the same time as an antecedent entity state 110 (e.g., when one event causes another to occur simultaneously or substantially simultaneously). Note that these terms are used in the context of a given state transition; for example, for an entity with three states (Si at t = to, S2 at t = to+i, S3 at t = to+2), S2 is consequent to Si but antecedent to S3.

[0031] Each schema factor 120 preferably represents a conditional distribution predicting an entity state transition when certain conditions are satisfied. For example, a schema factor 120 may be used to model one marble being moved by another after a collision, as shown in FIGURE 2. In this example, if Marble 2 is in contact with Marble 1 and has a non-zero velocity at time to, the position of Marble 1 will be changed by collision with Marble 2 at time t=to+i. A set of schema factors 120 maybe used to model many or all of the observable attributes of an entity in this way; for example, a second schema factor 120 may be used to determine position change of Marble 2 caused by Marble 1, a third schema factor 120 may be used to determine position change of Marble 1 due to gravity, etc.

[0032] These examples show how the system 100 enables event prediction via schema factors 120. Likewise, as shown in FIGURE 3, the system 100 may enable event explanation: here, backward message propagation identifies that a liquid's flammability in the presence of a nearby flame results in the liquid catching fire (transitioning from OnFire false to true). And as shown in FIGURE 4, consequent states maybe predicted or explained by the system 100 even when occurring simultaneously with antecedent states; for example, the system 100 may model how pushing a first block to the right also simultaneously pushes a second block directly to the right of the first block.

[0033] Schema factors may also be used to predict rewards given to a reinforcement learning agent.

[0034] In many implementations of the system 100, it may be possible for multiple schemas to predict a given state. In such implementations, the system 100 may include a mechanism for selecting a casual schema, an example of which is as shown in FIGURE 5. In this example mechanism, the system 100 includes a schema variable 121 for each schema factor 120, as well as a schema OR factor 122. A schema variable 121 represents the probability that a given schema factor 120 results in a state change, while the schema OR factor integrates all modeled causation on the same attribute variable, enabling reasoning with proper explaining-away. In the example as shown in FIGURE 5, each schema factor 120 provides a schema for a transition of Attribute 1 of Entity 2.

[0035] While schema factors 120 preferably couple variables of exactly two entities, schema factors 120 may additionally or alternatively couple to any number of variables, states, and/or entities. The system 100 may additionally or alternatively include a self- transition factor 123 and self-transition variable 124, as shown in FIGURE 6. The self- transition factor 123 and self-transition variable 124 model the probability of a state change occurring in the absence of any predicted state change by a schema factor 120.

[0036] Schema factors 120 may have any activation function; e.g., logical functions such as a Boolean-based selection function for AND, OR, NOT, XOR operations of node selection. Note that schema factors 120 (and other factors of the system 100) may be either deterministic or probabilistic, enabling the use of uncertainty in a model.

[0037] Context variables 130 are variables not exclusively associated with an entity. While the system 100 may include any type of variable not exclusively associated with an entity, two examples of context variables 130 are external context variables 131 and relationship variables 132. External context variables 131 are variables not directly linked to any entity. For example, for a vision system connected to an autonomous vehicle, the velocity of the vehicle (relevant to physical predictions about perceived visual data) may be an external context variable 131, as shown in FIGURE 7A. External context variables 131 can also include 'action' variables: e.g., in an arcade game, control signals (MoveUp, MoveDown, etc.). Relationship variables 132 are latent variables that encode attributes of a relationship between two or more entities (as opposed to the previously mentioned latent variables, which encode attributes of individual entities). For example, two light switches (each an entity) may each control a different light within a room. Since the wiring of the switches is not observable, relationship variables 132 may be used to store which switches link to which lights. For example, a schema factor 120 controlling the first of these two lights is as shown in FIGURE 7B.

[0038] Note that the number of observed entities within the system 100 may change at different times. The creation and/or deletion of observed entities may themselves be predicted and/ or explained by variables (e.g., an 'exists' variable).

[0039] The system 100 may be represented in any suitable manner (e.g., as a Bayesian network). In one implementation of an invention embodiment, the system 100 is constructed in a factor graph representation using binary random variable nodes (represented by circles/ovals) and factor nodes (represented by squares/rectangles), as shown in FIGURE 8. [0040] Here, the state representation is factored into a set of N entity states S = {sj, ... , %} where N is the number of entities and each entity state is an assignment of binary attributes s _t = {s _i)1 , ... , s _iiM } . This factored state representation allows for the factorization of the transition distribution

[0041 ] where a* is some action executed in s ^t . Each transition T _{t j} is modeled by a factor graph comprising: l) a set of variable nodes corresponding to attributes of entities in state s ^t (including the transition target s ), 2) a set of schema factor nodes, 3) a set of schema variable nodes (one coupled to each factor node), 4) a self-transition factor node, 5) a self-transition variable node, 6) a schema OR factor node and 7) the transition target (a variable node) after transition: sfj ^"1 (e.g., as shown in FIGURE 6).

[0042] In this implementation, the schema factor nodes are AND factor nodes defined by:

the schema OR factor n

and the self- transition factor node is a factor node as follows:

Ai _j = AND(→ _i ... ,→ _k , s _j )

where Φ are schemas. Accordingly, transition distributions can be calculated as

7^† ) = Otf(¾ ^< ¾ ;)

[0043] State prediction is straightforward given the aforementioned transition distributions. Planning (e.g., searching for action sequences that either achieve or avoid a given set of entity attribute state and/or reward states at given times) is preferably accomplished by belief propagation combined with forward and/or backward search. In one implementation, planning can aim to maximize the sum (or exponentially discounted sum) of all predicted rewards across a given number of timesteps. A belief propagation stage preferably recursively calculates which entity states are reachable at each time step, via forward propagation, and/or recursively calculates which entity states are conditions to achieve a target state, via backward propagation. Depending on the task, both max- product and sum-product belief propagation are possible. The belief propagation stage preferably is performed for a maximum number of time steps or until the target state is achieved. To maximize the probability of avoiding a state, the system 100 may attempt to find a plan that violates at least one condition of each schema that predicts the state to occur. In one implementation, this method can be used to avoid negative rewards. Alternatively, state prediction and planning may be accomplished in any manner.

[0044] The system 100 is preferably coupled to an entity observation network such as the recursive cortical network (RCN) of U.S. Patent Application No. 13/895,225, the entirety of which is incorporated by this reference. Additionally or alternatively, the system 100 may be coupled to any neural network capable of defining entities, detecting entities, and/or observing entity attributes. Alternatively, the system 100 may be not coupled to a neural network.

[0045] If the system 100 is connected to an entity observation network (e.g., a visual hierarchy), that network may interact with the system 100 in several ways. For example, a visual hierarchy may be used to 1) track entities and report observable attributes (e.g., position) to the system 100, 2) infer latent variables from visual data alone, and/or 3) predict a future visual state based on predictions of the system 100.

[0046] For example, a visual network may observe a particular pool (coupled to a group of visual network features and corresponding to an entity of a schema network). If the visual network knows that the entities of this pool typically move together, the visual network can use this information to set latent attributes of the entities in question, enabling better prediction. Likewise, each pool state may correspond to a different entity state.

[0047] Further, the hierarchy of the visual network may be used to create a hierarchy of entities. For example, features of an RCN subnetwork as shown in FIGURE 9A may correspond to entities in an example system 100 as shown in FIGURE 9B; PF (parent feature) corresponds to El, CFi corresponds to CF2, and so on. An update to a latent variable of El may, using this hierarchy, be pushed to entities below it in the hierarchy (E2, E3, E4, E5), or vice versa (from children to parents). For example, two halves of a ball may represent child entities, while the entire ball is a parent entity. If a first half of the ball is bouncy, then the whole ball is likely to be bouncy (propagation from child to parent), and likewise, the other half of the ball is likely to be bouncy (propagation from parent to the sibling of the first child).

[0048] Entities may be connected at any level or subnetwork to entity observation networks. Further, entity observation networks may pass information to the system 100 in any manner. In one example, an entity observation network passes information to an entity dictionary 150 as shown in FIGURE 10; this dictionary may contain information such as entity identifiers, attribute estimates for entities, state measurements, etc. In this example, either or both of the entity observation network and the system 100 may update entity dictionary 150 values. Additionally or alternatively, the entity dictionary 150 may be updated in any manner.

2. Schema Network Learning

[0049] A method 200 for event prediction using schema networks includes receiving a set of entity states S220 and learning a set of schemas S230, as shown in FIGURE 11. The method 200 may additionally or alternatively include processing input data S210 and/or learning latent attributes S240.

[0050] The method 200 functions to set structure of a schema network such that the schema network is enabled to perform event prediction and/or explanation based on the training set data (ideally generalizable to other data). The method 200 is preferably implemented by a computing system (e.g., computer, distributed computing system, etc.).

[0051] S210 includes processing input data. S210 functions to produce a set of entity states (S) from a set of input data (e.g., a set of images), actions, and rewards. Entities are preferably specified using an entity observation network (e.g., an RCN operating on visual data that creates entities from observed features), but may be specified in any manner. Input data may be any set of data for which inference or generation is desired; e.g., images, video, audio, speech, medical sensor data, natural language data, financial data, application data, traffic data, environmental data, etc.

[0052] S210 may additionally or alternatively include preprocessing input data to remove contradictions (e.g., the same input appearing twice with different labels).

[0053] S210 preferably includes, for each entity state, recording the states of all entities within local neighborhoods (relatively to the entities' current positions). These states can be converted in to a fixed-length binary feature vector for a given number of attributes and neighborhood size. For example, if each entity includes two observable attributes, and the neighborhood includes eight adjacent neighbors (e.g., a pixel surrounded by nearest pixels), the binary feature vector has 18 elements. Alternatively, S210 may produce entity states in any manner.

[0054] S220 includes receiving a set of entity states. Entity states are preferably those generated in S210, but may additionally or alternatively be received from any source (e.g., from an external entity detection system, via hardcoding, etc.).

[0055] For each timestep, the output of the schema network being trained is an estimation of y, a binary vector representing the outputs corresponding to input entity states X. X may be represented by a matrix of dimension N x D (where N is the number of entities and D is the length of the binary feature vector previously described). The output of the schema network for this prediction task is thus:

y = f _w (x) = xw^

where W is a matrix of dimension D x M (M representing the number of schemas, each column representing an individual schema). W is preferably initialized as an empty set (filled in in S230).

[0056] S230 includes learning a set of schemas. S230 preferably includes modifying the set of schemas (i.e., the matrix W) to reduce the prediction error of the schema network as previously described. S230 may include measuring prediction error using any suitable objective function; for example:

N where the first term computes the prediction error, the second term estimates the complexity, and parameter C controls the trade-off between the two.

[0057] S230 may find a solution to this objective function in any manner. In one implementation of an invention embodiment, S230 includes learning the set of schemas using a greedy solution in which linear programming (LP) relaxations are used to find new schema.

[0058] In this implementation, S230 takes as input vectors {x _n } for which f _w (x _n ) =

0 and the corresponding output scalars y _n . Next, S230 includes finding a cluster of input samples that can be solved with a single (relaxed) schema while keeping precision. Selecting an input sample and placing it in a "solved" set, S230 preferably solves the following:

min (1— x _n )w

we{o,i} ^D Z—

n:y _n =l

such that (1 - x _n )w > 1 V _n ..y _n=0 and (1 - x _n )w = 0 V _nesolved .

[0059] Then, S230 preferably simplifies the resulting schema w by placing all samples for which (1— x _n )w = 0 in the "solved" set and solving:

min w ^T 1 ^→

we{o,i} ^D

such that (1 - x _n )w > 1 V _n . _yn=0 and (1 - x _n )w = 0 V _nesolved .

[0060] If the found schema w is binary, S230 includes adding the schema to the network W. If not, S230 may repeat the previous minimization using binary programming, but only optimizing over the elements of w found to be non-zero (clamping the others to zero).

[0061 ] In this implementation, preferably only the input-output pairs for which the current schema network is predicting an output of zero are passed, and the process of adding new schemas preferably stops when a predefined complexity limit is reached. Alternatively, S230 may include stopping schema network addition in any manner (e.g., after a time limit or a certain number of schema additions).

[0062] While these steps describe how schema networks are found for a given transition, it is understood that S230 may be used to determine schema networks that apply across many or all transitions contained within an input dataset (e.g., by refining the schema network using this technique on successive timestep transitions).

[0063] S240 includes learning latent attributes. While S230 functions to learn schemas based on observed attributes (and potentially hardcoded or otherwise provided attributes), S240 functions to create new attributes that may describe entity behavior. S240 is preferably useful in cases where an event cannot be predicted to a threshold reliability with any current variables; alternatively, S240 may be used for any purpose.

[0064] S240 preferably includes adding a latent variable to the entity states involved in a given transition if the schema predicting a particular event fails to meet a reliability threshold. Alternatively, S240 may add latent variables in any case where a latent variable improves schema performance.

[0065] Latent variables added by S240 are preferably specific to a given schema, but S240 may include testing the latent variables to see if they improve performance in other schemas; in this case, S240 may include applying the latent variables across multiple or all schemas.

[0066] S240 may additionally or alternatively include learning latent variable structure, as shown in FIGURE 12. Such structure, once learned, can be used to infer all variable states in a given latent variable structure from a single latent variable observation.

[0067] The methods of the preferred embodiment and variations thereof can be embodied and/or implemented at least in part as a machine configured to receive a computer-readable medium storing computer-readable instructions. The instructions are preferably executed by computer-executable components preferably integrated with a computer system. The computer-readable medium can be stored on any suitable computer-readable media such as RAMs, ROMs, flash memory, EEPROMs, optical devices (CD or DVD), hard drives, floppy drives, or any suitable device. The computer- executable component is preferably a general or application specific processor, but any suitable dedicated hardware or hardware/firmware combination device can alternatively or additionally execute the instructions.

[0068] As a person skilled in the art will recognize from the previous detailed description and from the figures and claims, modifications and changes can be made to the preferred embodiments of the invention without departing from the scope of this invention defined in the following claims.