Recent Patents in Signal Processing (May 2016) – Markovian models

For our May 2016 issue, we cover recent patents granted in the area of Markovian probabilistic modeling in signal processing applications, including Markov chains, Hidden Markov Models, Markov Random fields and Monte Carlo simulations.

Patent no. 9,253,201 systems, methods, and media for detecting network anomalies are provided. In some embodiments, a training dataset of communication protocol messages having argument strings is received. The content and structure associated with each of the argument strings is determined and a probabilistic model is trained using the determined content and structure of each of the argument strings. A communication protocol message having an argument string that is transmitted from a first processor to a second processor across a computer network is received. The received communication protocol message is compared to the probabilistic model and then it is determined whether the communication protocol message is anomalous.

The invention no. 9,225,738 presents improved techniques, which involve flagging anomalous behavior in a current session when there is sufficient difference between an observed distribution of Markov events in the current session and an observed distribution of Markov events in a global session. Here, "Markov events" refer to events such as web page transitions and web page addresses. During a user session, a testing server generates a frequency distribution of a set of Markov events of the user session. The testing server also obtains a frequency distribution of previously observed Markov events of a global session, i.e., sets of sessions of previous user sessions or training sessions. The testing server then computes an anomaly statistic depending on the Markov events that indicates a difference between the user session and the global session. The testing server may produce an alert if the anomaly statistic differs significantly from some nominal value.

In patent no. 9,203,429 systems and methods are provided for encoding information using a code specified by a target Markov distribution. The systems and methods include selecting a set of parameters comprising a block length, a plurality of weight metrics, and a threshold, and estimating a Markov distribution associated with the selected set of parameters from a plurality of data blocks defined by the selected parameters. The systems and methods further include modifying the set of parameters based on the estimated Markov distribution, and encoding the information using the modified set of parameters.

In the invention no. 9,189,708 systems and techniques are provided for pruning a node from a possible nodes list for Hidden Markov Model with label transition node pruning. The node may be a label transition node. A frame may be at a predicted segmentation point in decoding input with the Hidden Markov Model. The node may be scored at the frame. The node may be pruned from the possible nodes list for the frame when score for the node is greater than the sum of a best score among nodes on the possible nodes list for the frame and a beam threshold minus a penalty term. A possible nodes list may be generated for a subsequent frame using label selection. A second node may be pruned from the possible nodes list for the subsequent frame with early pruning.

Systems and methods are provided in patent no. 9,183,503 for identifying combinatorial feature interactions, including capturing statistical dependencies between categorical variables, with the statistical dependencies being stored in a computer readable storage medium. A model is selected based on the statistical dependencies using a neighborhood estimation strategy, with the neighborhood estimation strategy including generating sets of arbitrarily high-order feature interactions using at least one rule forest and optimizing one or more likelihood functions. A damped mean-field approach is applied to the model to obtain parameters of a Markov random field (MRF); a sparse high-order semi-restricted MRF is produced by adding a hidden layer to the MRF; indirect long-range dependencies between feature groups are modeled using the sparse high-order semi-restricted MRF; and a combinatorial dependency structure between variables is output.

Patent no. 9,159,329 introduces a method and system for improving the quality of speech generated from Hidden Markov Model (HMM)-based Text-To-Speech Synthesizers using statistical post-filtering techniques. An example method involves: (a) determining a scale factor that, when applied to a synthesized reference spectral envelope, minimizes a statistical divergence between a natural reference spectral envelope and the synthesized reference spectral envelope, where the synthesized reference spectral envelope is generated by a state of an HMM; (b) for a given synthesized subject spectral envelope generated by the state of the HMM, determining an enhanced synthesized subject spectral envelope based on the determined scale factor; and (c) generating, by a computing device, a synthetic speech signal including the enhanced synthesized subject spectral envelope.

Patent no. 9,135,564 proposes a method for determining an optimum policy by using a Markov decision process in which T subspaces each have at least one state having a cyclic structure includes identifying, with a processor, subspaces that are part of a state space; selecting a t-th subspace among the identified subspaces; computing a probability of, and an expected value of a cost of, reaching from one or more states in the selected t-th subspace to one or more states in the t-th subspace in a following cycle; and recursively computing a value and an expected value of a cost based on the computed probability and expected value of the cost, in a sequential manner starting from a (t-1)-th subspace.

In the approach of patent no. 9,129,214, a method comprises receiving title interaction data, wherein the title interaction data specifies, an order in which users interacted with a plurality of titles; generating a plurality of statistical models, each statistical model of the plurality of statistical models specifying a plurality of probabilities, wherein the plurality of probabilities represent, for each first title of the plurality of titles and each second title of the plurality of titles, a likelihood that a user will interact with the first title then next interact with the second title; refining the plurality of statistical models based on the title interaction data; determining a plurality of weight values corresponding to the plurality of statistical models for a particular user; identifying, for the particular user, one or more recommended titles of the plurality of titles based on the plurality of weight values and the plurality of statistical models

The invention no. 9,110,817 relates to a method for creating a Markov process that generates sequences. Each sequence has a finite length L, comprises items from a set of a specific number n of items, and satisfies one or more control constraints specifying one or more requirements on the sequence. The method comprises the steps of receiving data defining an initial Markov process of a specific order d and having an initial probability distribution and of receiving data defining one or more control constraints. The method further comprises the step of generating data defining intermediary matrices, each matrix being of dimension nd by n, by zeroing out transitions in the initial Markov process data that are forbidden by the one or more control constraints.

If you have an interesting patent to share when we next feature patents related to Markovian models, or if you are especially interested in a signal processing research field that you would like to highlight in this section, please send email to Csaba Benedek (benedek.csaba AT sztaki DOT mta DOT hu).

References

Number: 9,253,201
Title: Detecting network anomalies by probabilistic modeling of argument strings with markov chains
Inventors: Song; Yingbo (Hazlet, NJ), Keromytis; Angelos D. (New York, NY), Stolfo; Salvatore J. (Ridgewood, NJ)
Issued:  February 2, 2016
Assignee: The Trustees of Columbia University in the City of New York (New York, NY)

Number: 9,225,738
Title: Markov behavior scoring
Inventors: Chiles; Richard (Castro Valley, CA)
Issued:  December 29, 2015
Assignee: EMC Corporation (Hopkinton, MA)

Number: 9,203,429
Title: Systems and methods for using markov distribution codes in data storage systems
Inventors:  Chaichanavong; Panu (Bangkok, TH), Varnica; Nedeljko (San Jose, CA), Nangare; Nitin (Santa Clara, CA)
Issued:  December 1, 2015
Assignee: Marvell International Ltd.

Number: 9,189,708
Title: Pruning and label selection in hidden markov model-based OCR
Inventors: Fujii; Yasuhisa (Sunnyvale, CA)
Issued:  November 17, 2015
Assignee: Google Inc. (Mountain View, CA)

Number: 9,183,503
Title: Sparse higher-order Markov random field
Inventors: Min; Renqiang (Plainsboro, NJ), Qi; Yanjun (Princeton, NJ)
Issued:  November 10, 2015
Assignee: NEC Laboratories America, Inc. (Princeton, NJ)

Number: 9,159,329
Title: Statistical post-filtering for hidden Markov modeling (HMM)-based speech synthesis
Inventors:  Agiomyrgiannakis; Ioannis (London, GB), Eyben; Florian Alexander (Munich, DE)
Issued:  October 13, 2015
Assignee: Google Inc. (Mountain View, CA)

Number: 9,135,564
Title: Using cyclic Markov decision process to determine optimum policy
Inventors: Osogami; Takayuki (Tokyo, JP), Rudy; Raymond H. (Tokyo, JP)
Issued:  September 15, 2015
Assignee: International Business Machines Corporation (Armonk, NY)

Number: 9,129,214
Title: Personalized markov chains
Inventors:  Gomez-Uribe; Carlos (Los Gatos, CA), Bharadwaj; Vijay (Los Gatos, CA), Molins Jimenez; Antonio (San Francisco, CA)
Issued:  September 8, 2015
Assignee: Netflix, Inc. (Los Gatos, CA)

Number: 9,110,817
Title: Method for creating a markov process that generates sequences
Inventors:  Pachet; Francois (Paris, FR), Roy; Pierre (Paris, FR), Barbieri; Gabriele (Paris, FR)
Issued:  August 18, 2015
Assignee: Sony Corporation (Tokyo, JP)