# US 12,217,166 B2 · Markov processes using analog crossbar arrays

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 12,217,166 B2
- Document ID: US12217166B2
- Status: Granted
- Kind: B2
- Application number: 17/321,617
- Filed: 2021-05-17
- Published: 2022-11-17
- Granted: 2025-02-04
- Earliest claimed: 2021-05-17
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Mark S. Squillante; Ogunzhan Murat Onen; Tayfun Gokmen; Vasileios Kalantzis; Tomasz J. Nowicki; Wilfried Haensch; Lior Horesh
- Web page: https://patentgrep.com/patent/US12217166B2

## CPC

- G06N 3/065: Analogue means
- G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks
- G06F 7/523: Multiplying only
- G06F 17/16: Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)}
- G06N 3/047: Probabilistic or stochastic networks
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method is presented for computing an equilibrium distribution of Markov processes. The method includes storing weight values in an analog crossbar array of transition probability matrices, where the analog crossbar array of transition probability matrices represents a weight matrix with m rows and n columns, computing an eigenvector associated with a real eigenvalue of modulus one for each of the transition probability matrices, applying a gradient-based eigenvalue solver to converge to a dominant eigenpair, and determining a probability of changing from one state to another state in a stochastic entity based on outcomes of the gradient-based eigenvalue solver.

## Claims

### Claim 1

A computer-implemented method for computing an equilibrium distribution of Markov processes, the method comprising:
storing weight values in an analog crossbar array of transition probability matrix devices, wherein the weight values in the analog crossbar array of transition probability matrix devices represent a weight matrix with m rows and n columns;
computing, by a processor, an eigenvector associated with a real eigenvalue of modulus one for each of the weight values from the transition probability matrix devices;
applying, by a processor, a gradient-based eigenvalue solver to converge to a dominant eigenpair;
determining a probability of changing from one state to another state in a stochastic entity based on outcomes of the gradient-based eigenvalue solver; and
performing a process with an artificial intelligence (AI) model using an AI accelerator chip that employs the equilibrium distribution of Markov processes.

### Claim 2 (depends on 1)

The computer-implemented method of claim 1, wherein the gradient-based eigenvalue solver performs a number of iterations, wherein each iteration is a matrix-vector product.

### Claim 3 (depends on 2)

The computer-implemented method of claim 2, wherein the matrix-vector product is given as z=x′(P−I) and an update is given as x=x−2η(P−I) z′, where η denotes a learning rate, P is a transition probability matrix, I is an initial state, x denotes a vector representing an initial approximation of the equilibrium distribution, x′ represents column vectors, and z′ represents row vectors.

### Claim 4 (depends on 3)

The computer-implemented method of claim 3, wherein each of the matrix-vector products with the transition probability matrix are performed using the analog crossbar array.

### Claim 5 (depends on 4)

The computer-implemented method of claim 4, wherein, once the dominant eigenpair is computed, the dominant eigenpair is scaled so that a sum of its entries is equal to one.

### Claim 6 (depends on 1)

The computer-implemented method of claim 1, wherein the transition probability matrices include all probabilities that a variable will transition from one state to another, or remain the same.

### Claim 7 (depends on 1)

The computer-implemented method of claim 1, wherein negative entries are omitted from the equilibrium distribution.

### Claim 8

A computer-implemented method for computing an equilibrium distribution of Markov processes, the method comprising:
storing weight values in an analog crossbar array of transition probability matrix devices, wherein the weight values in the analog crossbar array of transition probability matrix devices represent a weight matrix with m rows and n columns;
solving an augmented linear system by solving a stochastic gradient descent-based procedure in which the rows of the weight values of the transition probability matrix devices are used as data samples;
scaling a solution of the augmented linear system so that a sum of its entries is equal to one;
determining a probability of changing from one state to another state in a stochastic entity; and
performing a process with an artificial intelligence (AI) model using an AI accelerator chip that employs the equilibrium distribution of Markov processes.

### Claim 9 (depends on 8)

The computer-implemented method of claim 8, wherein the augmented linear system computes an approximation to x by an iterative process, where x denotes a vector representing an initial approximation of the equilibrium distribution.

### Claim 10 (depends on 9)

The computer-implemented method of claim 9, wherein, in each iteration, x=x+ηA′(b−Ax) is updated, where n denotes a learning rate,
A
=
[
T
analog
-
I
1
^
′
]
⁢
and
⁢
b
=
[
0
^
′
1
]
.

### Claim 11 (depends on 10)

The computer-implemented method of claim 10, wherein matrix-vector products with the transition probability matrix A are performed using the analog crossbar array.

### Claim 12 (depends on 9)

The computer-implemented method of claim 9, wherein A=(P−I) and b is set to zero, where I is an initial state, P is transition probability matrix, and
b
=
[
0
^
′
1
]
.

### Claim 13 (depends on 9)

The computer-implemented method of claim 9, wherein, at each iteration, an approximate equilibrium distribution vector x is scaled so that a sum of its entries is equal to one.

### Claim 14 (depends on 8)

The method computer-implemented of claim 8, wherein negative entries are omitted from the equilibrium distribution.

### Claim 15

A computer program product for computing an equilibrium distribution of Markov processes, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a computer to cause the computer to:
store weight values in an analog crossbar array of transition probability matrix devices, wherein the weight values in the analog crossbar array of transition probability matrix devices represent a weight matrix with m rows and n columns;
compute an eigenvector associated with a real eigenvalue of modulus one for each of the weight values from the transition probability matrix devices;
apply a gradient-based eigenvalue solver to converge to a dominant eigenpair;
determine a probability of changing from one state to another state in a stochastic entity based on outcomes of the gradient-based eigenvalue solver; and
performing a process with an artificial intelligence (AI) model using an AI accelerator chip that employs the equilibrium distribution of Markov processes.

### Claim 16 (depends on 15)

The computer program product of claim 15, wherein the gradient-based eigenvalue solver performs a number of iterations, wherein each iteration is a matrix-vector product.

### Claim 17 (depends on 16)

The computer program product of claim 16, wherein the matrix-vector product is give as z=x′(P−I) and an update is given as x=x−2η(P−I) z′, where η denotes a learning rate, P is a transition probability matrix, I is an initial state, x denotes a vector representing an initial approximation of the equilibrium distribution, x′ represents column vectors, and z′ represents row vectors.

### Claim 18 (depends on 17)

The computer program product of claim 17, wherein each of the matrix-vector products with the transition probability matrix are performed using the analog crossbar array.

### Claim 19 (depends on 18)

The computer program product of claim 18, wherein, once the dominant eigenpair is computed, the dominant eigenpair is scaled so that a sum of its entries is equal to one.

### Claim 20 (depends on 15)

The computer program product of claim 15, wherein negative entries are omitted from the equilibrium distribution.