Patent Description:
The present invention relates to system for automated detection of critical transitions and, more particularly, to a system for automated detection of critical transitions using predicted system trajectories.

One central characteristic of complex social-technological systems is their self-organized emerging interactions which provide the benefits of exchanging information and resources effectively, yet at the same time increases the risk and pace of spreading attacks or failures. A small perturbation on a complex system operating in a high-risk unstable region can induce a critical transition that leads to unstoppable catastrophic failures.

There are a few recent works of early warning signals for heterogeneously networked dynamical systems. Kwon and Yang (see the List of Incorporated Cited Literature References, Literature Reference No. <NUM>) use transfer entropy to analyze financial market data. They calculate pair-wise transfer entropy to form a transfer entropy matrix and demonstrate the asymmetrical influence from mature markets to emerging markets using transfer entropy. Their method estimates global transfer entropy, not local transfer entropy changing in time; therefore, their method cannot handle dynamics and structure changes in directional influence.

Staniek and Lehnertz (see Literature Reference No. <NUM>) introduced a robust and computationally efficient method to estimate transfer entropy using a symbolization technique. Their demonstration of symbolic transfer entropy (STE) on brain electrical activity data shows STE is able to detect the asymmetric dependences and identify the hemisphere containing the epileptic focus without observing actual seizure activity. However, their emphasis is also not on identifying the dynamics of the complex system structure.

Scheffer et al. (see Literature Reference No. <NUM>) surveys state-of-the-art methods that originated in the ecological domain. These methods focus only on homogeneous lattices with signals such as increased temporal correlation, skewness, and spatial correlations of the population dynamics, thus are not able to deal with heterogeneously networked dynamical systems.

Moon and Lu (see Literature References No. <NUM> and <NUM>) developed a spectral early warning signals (EWS) theory that detects the approaching of critical transitions and can estimate the system structure and network connectivity near critical transitions using the covariance matrix. Although spectral EWS quantifies how much entities of a system are moving together, the symmetric nature of covariance spectrum does not permit the analysis of directional influences among entities. HRL337-EPO.

<NPL> proposes a wavelet-based extension of transfer entropy.

Thus, a continuing need exists for a system for automated detection of critical transitions in heterogeneously networked dynamical system using an information dynamic spectrum framework that permits analysis of directional influences among entities.

The present invention relates to system for predicting critical transitions, and to a corresponding computer implemented method and computer program product, as set forth in the appended independent claims. Other preferred aspects of the present invention are set forth in the dependent claims, as follows.

In another aspect, the system estimates the TE trajectory by the natural logarithm (ln) with an unknown coefficient a and a constant c according to the following: <MAT> where t represents time.

In another aspect, the system estimates the unknown coefficient a with various discrete time steps by taking the derivative of g(t) = a ln(t) + c to obtain <MAT> then obtaining a discretized version of the unknown coefficient a according to the following: <MAT>.

In another aspect, the system determines the unknown coefficient a according to the following:.

In another aspect, the system determines a predicted value for a future time Tend + td according to the following: <MAT> where td is the desired time length for prediction.

The objects, features and advantages of the present invention will be apparent from the following detailed descriptions of the various aspects of the invention in conjunction with reference to the following drawings, where:.

The present invention relates to a system for automated detection of critical transitions and, more particularly, to a system for automated detection of critical transitions using predicted system trajectories.

The following description is presented to enable one of ordinary skill in the art to make and use the invention and to incorporate it in the context of particular applications. Various modifications, as well as a variety of uses in different applications will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to a wide range of aspects. Thus, the present invention is not intended to be limited to the aspects presented, but is to be accorded the widest scope as set forth in the appended claims.

In the following detailed description, numerous specific details are set forth in order to provide a more thorough understanding of the present invention. However, it will be apparent to one skilled in the art that the present invention may be practiced without necessarily being limited to these specific details, and that the scope of the present invention is that as set forth in the appended claims. In other instances, well-known structures and devices are shown in block diagram form, rather than in detail, in order to avoid obscuring the present invention.

The reader's attention is directed to all papers and documents which are filed concurrently with this specification and which are open to public inspection with this specification.

All the features disclosed in this specification, (including any accompanying claims, abstract, and drawings) may be replaced by alternative features serving the same, equivalent or similar purpose, unless expressly stated otherwise.

Furthermore, any element in a claim that does not explicitly state "means for" performing a specified function, or "step for" performing a specific function, is not to be interpreted as a "means" or "step" clause as specified in <NUM> U. Section <NUM>, Paragraph <NUM>. In particular, the use of "step of" or "act of" in the claims herein is not intended to invoke the provisions of <NUM> U. <NUM>, Paragraph <NUM>.

Before describing the invention in detail, first a list of cited references is provided. Next, a description of the various principal aspects of the present invention is provided. Subsequently, an introduction provides the reader with a general understanding of the present invention. Finally, specific details of the present invention are provided to give an understanding of the specific aspects.

The following references are cited throughout this application. For clarity and convenience, the references are listed herein as a central resource for the reader.

The references are cited in the application by referring to the corresponding literature reference number.

The present invention has three "principal" aspects. The first is a system for automated detection of critical transitions. The system is typically in the form of a computer system operating software or in the form of a "hard-coded" instruction set. This system may be incorporated into a wide variety of devices that provide different functionalities. The second principal aspect is a method, typically in the form of software, operated using a data processing system (computer). The third principal aspect is a computer program product. The computer program product generally represents computer-readable instructions stored on a non-transitory computer-readable medium such as an optical storage device, e.g., a compact disc (CD) or digital versatile disc (DVD), or a magnetic storage device such as a floppy disk or magnetic tape. Other, non-limiting examples of computer-readable media include hard disks, read-only memory (ROM), and flash-type memories. These aspects will be described in more detail below.

A block diagram depicting an example of a system (i.e., computer system <NUM>) of the present invention is provided in <FIG>. The computer system <NUM> is configured to perform calculations, processes, operations, and/or functions associated with a program or algorithm. In one aspect, certain processes and steps discussed herein are realized as a series of instructions (e.g., software program) that reside within computer readable memory units and are executed by one or more processors of the computer system <NUM>. When executed, the instructions cause the computer system <NUM> to perform specific actions and exhibit specific behavior, such as described herein.

The computer system <NUM> may include an address/data bus <NUM> that is configured to communicate information. Additionally, one or more data processing units, such as a processor <NUM> (or processors), are coupled with the address/data bus <NUM>. The processor <NUM> is configured to process information and instructions. In an aspect, the processor <NUM> is a microprocessor. Alternatively, the processor <NUM> may be a different type of processor such as a parallel processor, or a field programmable gate array.

The computer system <NUM> is configured to utilize one or more data storage units. The computer system <NUM> may include a volatile memory unit <NUM> (e.g., random access memory ("RAM"), static RAM, dynamic RAM, etc.) coupled with the address/data bus <NUM>, wherein a volatile memory unit <NUM> is configured to store information and instructions for the processor <NUM>. The computer system <NUM> further may include a nonvolatile memory unit <NUM> (e.g., read-only memory ("ROM"), programmable ROM ("PROM"), erasable programmable ROM ("EPROM"), electrically erasable programmable ROM "EEPROM"), flash memory, etc.) coupled with the address/data bus <NUM>, wherein the nonvolatile memory unit <NUM> is configured to store static information and instructions for the processor <NUM>. Alternatively, the computer system <NUM> may execute instructions retrieved from an online data storage unit such as in "Cloud" computing. In an aspect, the computer system <NUM> also may include one or more interfaces, such as an interface <NUM>, coupled with the address/data bus <NUM>. The one or more interfaces are configured to enable the computer system <NUM> to interface with other electronic devices and computer systems. The communication interfaces implemented by the one or more interfaces may include wireline (e.g., serial cables, modems, network adaptors, etc.) and/or wireless (e.g., wireless modems, wireless network adaptors, etc.) communication technology.

In one aspect, the computer system <NUM> may include an input device <NUM> coupled with the address/data bus <NUM>, wherein the input device <NUM> is configured to communicate information and command selections to the processor <NUM>. In accordance with one aspect, the input device <NUM> is an alphanumeric input device, such as a keyboard, that may include alphanumeric and/or function keys. Alternatively, the input device <NUM> may be an input device other than an alphanumeric input device. In an aspect, the computer system <NUM> may include a cursor control device <NUM> coupled with the address/data bus <NUM>, wherein the cursor control device <NUM> is configured to communicate user input information and/or command selections to the processor <NUM>. In an aspect, the cursor control device <NUM> is implemented using a device such as a mouse, a track-ball, a track-pad, an optical tracking device, or a touch screen. The foregoing notwithstanding, in an aspect, the cursor control device <NUM> is directed and/or activated via input from the input device <NUM>, such as in response to the use of special keys and key sequence commands associated with the input device <NUM>. In an alternative aspect, the cursor control device <NUM> is configured to be directed or guided by voice commands.

In an aspect, the computer system <NUM> further may include one or more optional computer usable data storage devices, such as a storage device <NUM>, coupled with the address/data bus <NUM>. The storage device <NUM> is configured to store information and/or computer executable instructions. In one aspect, the storage device <NUM> is a storage device such as a magnetic or optical disk drive (e.g., hard disk drive ("HDD"), floppy diskette, compact disk read only memory ("CD-ROM"), digital versatile disk ("DVD")). Pursuant to one aspect, a display device <NUM> is coupled with the address/data bus <NUM>, wherein the display device <NUM> is configured to display video and/or graphics. In an aspect, the display device <NUM> may include a cathode ray tube ("CRT"), liquid crystal display ("LCD"), field emission display ("FED"), plasma display, or any other display device suitable for displaying video and/or graphic images and alphanumeric characters recognizable to a user.

The computer system <NUM> presented herein is an example computing environment in accordance with an aspect. However, the non-limiting example of the computer system <NUM> is not strictly limited to being a computer system. For example, an aspect provides that the computer system <NUM> represents a type of data processing analysis that may be used in accordance with various aspects described herein. Moreover, other computing systems may also be implemented. Indeed, the scope of the present technology is not limited to any single data processing environment, but rather to the scope as set forth in the appended claims. Thus, in an aspect, one or more operations of various aspects of the present technology are controlled or implemented using computer-executable instructions, such as program modules, being executed by a computer. In one implementation, such program modules include routines, programs, objects, components and/or data structures that are configured to perform particular tasks or implement particular abstract data types. In addition, an aspect provides that one or more aspects of the present technology are implemented by utilizing one or more distributed computing environments, such as where tasks are performed by remote processing devices that are linked through a communications network, or such as where various program modules are located in both local and remote computer-storage media including memory-storage devices.

An illustrative diagram of a computer program product (i.e., storage device) embodying the present invention is depicted in <FIG>. The computer program product is depicted as floppy disk <NUM> or an optical disk <NUM> such as a CD or DVD. However, as mentioned previously, the computer program product generally represents computer-readable instructions stored on any compatible non-transitory computer-readable medium. The term "instructions" as used with respect to this invention generally indicates a set of operations to be performed on a computer, and may represent pieces of a whole program or individual, separable, software modules. Non-limiting examples of "instruction" include computer program code (source or object code) and "hard-coded" electronics (i.e. computer operations coded into a computer chip). The "instruction" is stored on any non-transitory computer-readable medium, such as in the memory of a computer or on a floppy disk, a CD-ROM, and a flash drive. In either event, the instructions are encoded on a non-transitory computer-readable medium.

One central characteristic of complex social-technological systems is their self-organized emerging interactions which provide the benefits of exchanging information and resources effectively, yet at the same time increase the risk and pace of spreading attacks or failures. A small perturbation on a complex system operating in a high-risk unstable region can induce a critical transition that leads to unstoppable catastrophic failures. In the system according to the principles of the present invention, catastrophic failures can be avoided by detecting early warnings of critical transitions and predicting the likelihood of system trajectories and the lead time to the critical points.

The invention described herein is built upon the invention described in the priority application<CIT>, entitled, "Detection and Identification of Directional Influences Using Dynamic Spectrum" (hereinafter referred to as the '<NUM> application), which is an information dynamic spectrum framework that goes beyond unidirectional diffusion dynamics to investigate heterogeneously networked dynamical systems with transient directional influence.

The '<NUM> application describes the development of a novel Associative Transfer Entropy (ATE) measure which decomposes the pair-wise directional influence of transfer entropy to associative states of asymmetric, directional information flows. Multivariate time series of complex systems were transformed into the spectrum of Transfer Entropy Matrix (TEM) and Associative Transfer Entropy Matrix (ATEM) to capture information dynamics of the system. The novel spectral radius measures of TEM and ATEM were developed to detect early warning signals of source-driven instability, and induce directional influence structure to identify the source and reveal dynamics of directional influences. The framework described in the '<NUM> application enables one not only to accurately detect, predict, and mitigate abrupt behavior changes in complex systems, but also to understand, design, and build more sustainable and resilient complex systems.

The idea of associative transfer entropy is to decompose transfer entropy (TE) by constraining associated states of two processes. The simplest case of ATE is two influence classes: one positive ATE+ and the other negative ATE-. In this case, ATE is able to distinguish two situations where the amount of information transfer is the same but have opposite effects: the source drives the destination the same direction in ATE+, and the source drives the destination the opposite direction in ATE-. For dynamic data, meaning the amount of information flow is not constant, the TE/ATE of time series in a local time window is calculated, so that TE/ATE becomes a function of time. Such decomposition further enables one to investigate ATEM in the form of ATEM+ and ATEM-.

Given A TE+/TE cross-over signature as the early warning signals of critical transition, the present invention predicts (<NUM>) the likelihood of system trajectories and (<NUM>) the lead time to critical points. It was first observed that ATE+ and TE are maximized, at the same time that ATE-flattened, prior to the system switching to alternative stable regimes. Therefore, model-based statistical forecasting was applied to estimate the likelihood of ATE+/TE/ATE- trajectories. The lead time is predicted by estimating the critical point based on the projected flattening of ATE-trajectories. The prediction method according to the principles of the present invention will continuously output the update of probabilistic cones as the system progresses. Determining the likelihood and lead time of critical points will enable further developments of a mitigation strategy to avoid critical transitions. Each of these aspects will be described in further detail below.

Described is a system to address the need of automated detection of emerging transitions, and identify sources of instability from time series of complex systems. The techniques according to the principles of the present invention can be used to detect directional influences apart from intrinsic dynamics so that one can derive encapsulated interaction modules to predict behavior trajectories. The system according to the principles of the present invention will enable the advancement in analyzing dynamics of complex networks.

Advantages of the system and method described herein include, but are not limited to, (<NUM>) providing an effective measure for quantifying associative, asymmetric directional influences, whereas other methods only can handle either symmetric or directional influences; (<NUM>) providing an effective formulation for capturing system-wise directional influences, whereas other methods can only handle pair-wise directional influence, or system-wise symmetrical influence; (<NUM>) providing an effective measure for detecting instability in systems with directional influence dynamics, whereas other methods assume uti-directional diffusion dynamics; (<NUM>) providing an effective method for characterizing instability trends of aggregated directional influences, whereas other methods can only detect instability with simple thresholding; and (<NUM>) providing an effective method to reveal sources and structures in changing dynamics of directional influences, whereas other methods can only handle stationary dynamics.

The asymmetric measure, transfer entropy, <MAT> quantifies the amount of information transfer from source xj to destination xi, It has been used to demonstrate the asymmetrical influence from mature markets to emerging markets by analyzing stock market indices, as described in Literature Reference Nos. <NUM> and <NUM>. Yet, current state-of-the-art only considers average pair-wise information transfers and statistical analysis, without including the more fundamental object of an information dynamic spectrum (i.e., time-varying information transfer) to explain the emergence of directional influences.

In the previously developed information dynamic spectrum theory described in the '<NUM> application, the dynamics of a complex network were formulated as: dX = F(X)dt + σdW, where <MAT> is a differentiable function that explains the dynamics of the system ofm elements X(t) = [x<NUM>(t) x<NUM>(t). xm(t)]T and is defined by F(X(t)) = [f<NUM>(X(t)) f<NUM>(X(t)). fm(X(t))]T. This captures both the dynamics of individual entities and the networked interactions between the entities. For example, element xi(t) can be the ith stock index of the ith trading day. The last term, σdW, corresponds to white noise scaled by σ. To reveal the unknown F(X), this problem is further simplified by linear approximation: F(X) ≈F(X<NUM>) + J(X<NUM>)(X-X<NUM>), for X near X<NUM>, where <MAT> is the Jacobian matrix. Therefore, the local temporal dynamics can be obtained pair-wise. The measure associative transfer entropy (ATE) at state Dk, for i ≠ j is defined by: <MAT> where Dk is a subset of D that represents a certain associated state between xi and xj. The purpose of ATE is to capture information transfer between two variables for a particular state association. For example, TE may be decomposed into two influence classes: one positive and the other negative.

If the internal dynamics within each node is negligible comparing to interactions among nodes, it is conjectured that <MAT> for some linear function g. Let TDk be an associative transfer entropy matrix (ATEM).

To appropriately deal with dynamic data, meaning the amount of information flow from one to another is not static, TE/ATE curves were generated as functions of time, calculated over sliding windows.

Since the TEM matrix is non-symmetric, its eigenvalues are complex-valued. The spectral radius of the TEM matrix is used to measure the total amount of information flow of the entire network.

To efficiently estimate transfer entropy of continuous data, Staniek and Lehnertz (see Literature Reference No. <NUM>) proposed a method using a symbolization technique that is robust and computationally fast, which had been introduced with the concept of permutation entropy. In the '<NUM> application, the symbolization technique of Staniek and Lehnertz was adapted to calculate ATE. Specifically, the continuous-valued time sequence <MAT> was symbolized by first ordering the values of {x(t), x(t + <NUM>),. x(t + m)} with {<NUM>, <NUM>,. , m} and denoting x̃(t) = associated permutation of order m the symbol of x(t) at t. Then, the ATE of <MAT> is estimated by calculating ATE of <MAT>.

<FIG> show an ATE analysis of a non-foster network from the invention described in the '<NUM> application. The circuit is initially operated in the stable region, where there is no oscillation. Then a small perturbation is added. It is unknown whether the circuit will become oscillatory (unstable) or stay stable. An ATE analysis was performed to detect if the circuits would become synchronized (unstable). The plot in <FIG> is the circuit in voltage over time, where Ant1 represents Antenna <NUM>, Ant2 represents Antenna <NUM>, i1 represents port <NUM>, and i2 represents port <NUM>. The plot in <FIG> shows the TE/ATE+/ATE- curves over time. The curves are obtained from the absolute sum of spectrum of TEM/ATEM+/ATEM-, respectively. It was found that the spectral radius of TEM/ATEM+/ATEM- also show similar outcomes, but since TEM is the sum of ATEM+ and ATEM-, the ATE+ curve will never cross the TE curve. Thus, the absolute sum of the spectrum is more informative. As shown in <FIG>, the ATE+ curve crosses over the TE curve near time point <NUM>, indicating the increasing in synchronization. In addition, the ATE+ curve reaches its peak right before full synchronization, while the ATE- curve flattens because there is no negative association.

In the system according to the principles of the present invention, model-based statistical forecasting is used to estimate the TE/ATE+/ATE-trajectories. An advantage of analyzing the TE/ATE curves is that TE/ATE removes the spikes of the raw data, as shown in the circuit data example in <FIG>. It has been observed that the TE curve in this case can be well approximated by the natural logarithm with an unknown coefficient a and a constant c according to the following: <MAT>.

<FIG> shows curve fitting with a plot of the exponential function, and <FIG> illustrates curve fitting with a plot of the logarithmic function. The bold solid curves <NUM> are the TE curve from <FIG>. The bold dashed curves <NUM> are the fitted curves in the interval t ∈ [<NUM>, <NUM>]. The unbolded dashed curves <NUM> are the projections from the fitted curves. <FIG> shows that the logarithm is appropriate to fit the TE curve.

To estimate the coefficient a from TE/ATE± curves, instead of fitting them deterministically with the logarithmic function in equation (<NUM>), the rate of change was estimated with various discrete time steps. This generates a prediction cone, which will be described in detail below. From the derivative of equation (<NUM>), <MAT> the following discretized version for the unknown a was obtained: <MAT>.

For a fixed timestep Δt in a window [Tstart, Tend], the least squares was used to solve the unknown a. First, the following matrix equation was written: <MAT> where t<NUM>,. , tk + Δt ∈ [Tstart, Tend], where tk is the kth time point. The approximation of aΔt for the fixed timestep Δt was then obtained according to the following: <MAT>.

The constant corresponding to this timestep is then cΔt = g(Tend) - aΔt ln(Tend). Therefore, the predicted value for the future time Tend + td is <MAT> td is the desired time length for prediction.

Now that a method to estimate the constants c and a has been established, a probabilistic prediction cone (or light cone) can be generated at each time point as one varies Δt to obtain multiple estimates of c and a. Therefore, a probabilistic prediction cone at a given time consists of a collection of natural logarithm curves starting from that point.

To estimate the error of this prediction for the immediate next timestep, the following was calculated: <MAT> where <MAT>.

Let E be the collection of all errorΔt over all timesteps Δt and let σ = standard deviation of E. Let G be the collection of all predicted values GΔt (td) over all timesteps Δt and µ = mean(G). Therefore, the <NUM>% confidence interval for the future time Tend + td is: <MAT> where N is the size of E.

<FIG> shows the <NUM>% confidence interval of a predicted trajectory in unbolded solid lines <NUM>. The predicted trajectory for TE is represented by the unbolded dashed line <NUM>. The bold solid line <NUM> depicts the actual trajectory of TE. The prediction value and confidence interval are generated from the prediction cones, described above. Two points of the actual trajectory were outside the <NUM>% confidence interval, right before the non-foster circuits were fully synched around time t=<NUM>. These points are represented by diamonds <NUM> and indicate the possibility of a trend toward a critical transition.

<FIG> and <FIG> illustrate two time snapshots of the prediction cones <NUM> produced according to the method described above and the predicted trajectory value (represented by bold dashed curves <NUM>). The prediction cones are used to generate the prediction values with confidence intervals in <FIG>. The solid bold curves <NUM> represent the actual TE trajectory.

<FIG> is a flow diagram depicting the system for predicting system trajectories toward critical transitions according to the principles of the present invention. In a first step <NUM>, a set of multivariate time series of observables of a complex system is transformed into a set of symbolic multivariate time series. In a second step <NUM>, the system determines pair-wise time series of a TE measure. In a third step <NUM>, an ATE measure is determined. In a fourth step <NUM>, the system estimates ATE+, TE, and ATE- trajectories over time. In a fifth step <NUM>, a critical transition in the system is predicted using at least one of the ATE+, TE, and ATE-trajectories.

Claim 1:
A system for predicting critical transitions, the system comprising:
an electronic circuit having a plurality of components, each component having a time series of voltage measurements; and
one or more processors (<NUM>) and a non-transitory computer-readable medium (<NUM>) having executable instructions encoded thereon such that when executed, the one or more processors perform operations of:
transforming the time series of voltage measurements from the plurality of components of the electronic circuit into a set of symbolic multivariate time series;
determining a transfer entropy (TE) measure between two time series in the set of symbolic multivariate time series over a sliding time window;
determining an associative transfer entropy (ATE) measure, wherein the ATE measure is comprised of an ATE+ positive influence class and an ATE- negative influence class, and wherein the ATE measure captures information transfer for a state association Dk, between a variable xj and a variable xi, for i ≠ j according to the following: <MAT>
where Σ represents a summation, t represents a unit of time, p represents a joint probability of the variables, and | represents a conditional probability, wherein the variables xj and xi represent states of at least one component of the electric circuit;
estimating ATE+, TE, and ATE- trajectories over time; and
based on the estimated ATE+, TE, and ATE- trajectories, predicting instability in the electronic circuit.