Title: Markov Random Field Structure Estimator
Version: 0.4.2
Date: 2024-10-21
Description: Three algorithms for estimating a Markov random field structure.Two of them are an exact version and a simulated annealing version of a penalized maximum conditional likelihood method similar to the Bayesian Information Criterion. These algorithm are described in Frondana (2016) <doi:10.11606/T.45.2018.tde-02022018-151123>.The third one is a greedy algorithm, described in Bresler (2015) <doi:10.1145/2746539.2746631).
License: GPL (≥ 3)
Maintainer: Rodrigo Carvalho <rodrigorsdc@gmail.com>
LinkingTo: Rcpp
Imports: Rcpp
Depends: gtools, Rfast
NeedsCompilation: yes
Packaged: 2024-10-21 17:19:50 UTC; rodrigo
Author: Rodrigo Carvalho [aut, cre], Florencia Leonardi [rev, ths]
Repository: CRAN
Date/Publication: 2024-10-21 17:40:01 UTC

Bresler's non-binary Markov random field structure estimator

Description

A greedy algorithm to estimate Markovian neighborhoods.

Usage

mrfse.ci(a_size, sample, tau, max_degree=ncol(sample)-1)

Arguments

a_size

Size of the alphabet.

sample

A integer-valued matrix. Each value must belong range 0 and a_size - 1. Matrix has dimension n x V, where n is number of samples and V is number of nodes.

tau

A hyperparameter. See references.

max_degree

The maximum length of a candidate Markovian neighborhood. Must be non-negative and less than ncol(sample).

Value

A list filled with estimated Markov neighborhood for each graph vertex

Author(s)

Rodrigo Carvalho

References

Guy Bresler. 2015. Efficiently Learning Ising Models on Arbitrary Graphs. In Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (STOC '15). Association for Computing Machinery, New York, NY, USA, 771–782. DOI:https://doi.org/10.1145/2746539.2746631

Examples

library(mrfse)
a_size = c(0, 1)
s = matrix(sample(a_size, size=1000, replace=TRUE), ncol=5)
mrfse.ci(length(a_size), s, 0.2)

Conservative approach for Bresler's non-binary estimator

Description

A greedy algorithm to estimate Markovian neighborhoods.

Usage

mrfse.ci.con(a_size, sample, tau, max_degree=ncol(sample)-1)

Arguments

a_size

Size of the alphabet.

sample

A integer-valued matrix. Each value must belong range 0 and a_size - 1. Matrix has dimension n x V, where n is number of samples and V is number of nodes.

tau

A hyperparameter. See references.

max_degree

The maximum length of a candidate Markovian neighborhood. Must be non-negative and less than ncol(sample).

Value

A adjacency matrix of the estimated Markov random field graph.

Author(s)

Rodrigo Carvalho

References

Guy Bresler. 2015. Efficiently Learning Ising Models on Arbitrary Graphs. In Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (STOC '15). Association for Computing Machinery, New York, NY, USA, 771–782. DOI:https://doi.org/10.1145/2746539.2746631

Examples

library(mrfse)
a_size = c(0, 1)
s = matrix(sample(a_size, size=1000, replace=TRUE), ncol=5)
mrfse.ci.con(length(a_size), s, 0.2)

Non-conservative approach for Bresler's non-binary estimator

Description

A greedy algorithm to estimate Markovian neighborhoods.

Usage

mrfse.ci.ncon(a_size, sample, tau, max_degree=ncol(sample)-1)

Arguments

a_size

Size of the alphabet.

sample

A integer-valued matrix. Each value must belong range 0 and a_size - 1. Matrix has dimension n x V, where n is number of samples and V is number of nodes.

tau

A hyperparameter. See references.

max_degree

The maximum length of a candidate Markovian neighborhood. Must be non-negative and less than ncol(sample).

Value

A adjacency matrix of the estimated Markov random field graph.

Author(s)

Rodrigo Carvalho

References

Guy Bresler. 2015. Efficiently Learning Ising Models on Arbitrary Graphs. In Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (STOC '15). Association for Computing Machinery, New York, NY, USA, 771–782. DOI:https://doi.org/10.1145/2746539.2746631

Examples

library(mrfse)
a_size = c(0, 1)
s = matrix(sample(a_size, size=1000, replace=TRUE), ncol=5)
mrfse.ci.ncon(length(a_size), s, 0.2)

Create a sampler for Markov random field.

Description

Create a sampler for Markov random field from a DAG

Usage

mrfse.create.sampler(dag_adj, A)

Arguments

dag_adj

An direct acyclic graph adjacency matrix

A

Size of alphabet

Value

A list filled with the following components:

neigh: A list of neighborhood. For each i, neigh[[i]] is a markovian neighborhood of vertex i

probs: A list of probabilities. For each i, probs[[i]] is matrix of probabilities of vertex i given your markovian neighborhood. Those probabilites will be used to generate a sample.

moral_adj: moral graph of adj_dag

topol_sort: topological sort of adj_dag

num_nodes: number of nodes de adj_dag

A: alphabet size

Author(s)

Rodrigo Carvalho

Examples

library(mrfse)
adj = matrix(c(0, 1, 0, 0, 0, 0, 0, 1, 0), byrow=TRUE, ncol=3)
mrfse.create.sampler(adj, 3)

A Markov random field structure estimator

Description

A penalized likelihood BIC-based to estimate Markovian neighborhoods.

Usage

mrfse.exact(a_size, sample, c, max_neigh= ncol(sample) - 1)

Arguments

a_size

Size of the alphabet.

sample

A integer-valued matrix. Each value must belong range 0 and a_size - 1. Matrix has dimension n x V, where n is number of samples and V is number of nodes.

c

The penalization constant. Must be positive.

max_neigh

The maximum length of a candidate Markovian neighborhood. Must be non-negative and less than ncol(sample).

Value

A list filled with estimated Markov neighborhood for each graph vertex

Author(s)

Rodrigo Carvalho

References

FRONDANA, Iara Moreira. Model selection for discrete Markov random fields on graphs. São Paulo : Instituto de Matemática e Estatística, University of São Paulo, 2016. Doctoral Thesis in Estatística. <doi:10.11606/T.45.2018.tde-02022018-151123> http://www.teses.usp.br/teses/disponiveis/45/45133/tde-02022018-151123/publico/tese_Iara_Frondana.pdf

Examples

library(mrfse)
a_size = c(0, 1)
s = matrix(sample(a_size, size=1000, replace=TRUE), ncol=5)
mrfse.exact(length(a_size), s, 1.0)

Conservative approach for Frondana's mrfse

Description

Conservative construction of the estimated Markov random field graph.

Usage

mrfse.exact.con(a_size, sample, c, max_neigh = ncol(sample) - 1)

Arguments

a_size

Size of the alphabet.

sample

A integer-valued matrix. Each value must belong range 0 and a_size - 1. Matrix has dimension n x V, where n is number of samples and V is number of nodes.

c

The penalization constant. Must be positive.

max_neigh

The maximum length of a candidate Markovian neighborhood. Must be non-negative and less than ncol(sample).

Value

A adjacency matrix of the estimated Markov random field graph.

Author(s)

Rodrigo Carvalho

References

FRONDANA, Iara Moreira. Model selection for discrete Markov random fields on graphs. São Paulo : Instituto de Matemática e Estatística, University of São Paulo, 2016. Doctoral Thesis in Estatística. <doi:10.11606/T.45.2018.tde-02022018-151123> http://www.teses.usp.br/teses/disponiveis/45/45133/tde-02022018-151123/publico/tese_Iara_Frondana.pdf

Examples

library(mrfse)
a = c(0, 1)
s = matrix(sample(a, size=1000, replace=TRUE), ncol=5)
mrfse.exact.con(length(a), s, 1.0)

Non-conservative approach for Frondana's mrfse

Description

Conservative construction of the estimated Markov random field graph.

Usage

mrfse.exact.ncon(a_size, sample, c, max_neigh = ncol(sample) - 1)

Arguments

a_size

Size of the alphabet.

sample

A integer-valued matrix. Each value must belong range 0 and a_size - 1. Matrix has dimension n x V, where n is number of samples and V is number of nodes.

c

The penalization constant. Must be positive.

max_neigh

The maximum length of a candidate Markovian neighborhood. Must be non-negative and less than ncol(sample).

Value

A adjacency matrix of the estimated Markov random field graph.

Author(s)

Rodrigo Carvalho

References

FRONDANA, Iara Moreira. Model selection for discrete Markov random fields on graphs. São Paulo : Instituto de Matemática e Estatística, University of São Paulo, 2016. Doctoral Thesis in Estatística. <doi:10.11606/T.45.2018.tde-02022018-151123> http://www.teses.usp.br/teses/disponiveis/45/45133/tde-02022018-151123/publico/tese_Iara_Frondana.pdf

Examples

library(mrfse)
a = c(0, 1)
s = matrix(sample(a, size=1000, replace=TRUE), ncol=5)
mrfse.exact.ncon(length(a), s, 1.0)

A Markov random field structure estimator using simulated annealing approach

Description

A penalized likelihood BIC-based to estimate Markovian neighborhoods.

Usage

mrfse.sa(a_size, sample, c, t0, iterations=1000, max_neigh=ncol(sample)-1)

Arguments

a_size

Size of the alphabet.

sample

A integer-valued matrix. Each value must belong range 0 and a_size - 1. Matrix has dimension n x V, where n is number of samples and V is number of nodes.

c

The penalization constant. Must be positive.

t0

Inital temperature

iterations

Number of simulated annealing iterations

max_neigh

The maximum length of a candidate Markovian neighborhood. Must be non-negative and less than ncol(sample).

Value

A list filled with estimated Markov neighborhood for each graph vertex

Author(s)

Rodrigo Carvalho

References

FRONDANA, Iara Moreira. Model selection for discrete Markov random fields on graphs. São Paulo : Instituto de Matemática e Estatística, University of São Paulo, 2016. Doctoral Thesis in Estatística. <doi:10.11606/T.45.2018.tde-02022018-151123> http://www.teses.usp.br/teses/disponiveis/45/45133/tde-02022018-151123/publico/tese_Iara_Frondana.pdf

Examples

library(mrfse)
a_size = c(0, 1)
s = matrix(sample(a_size, size=1000, replace=TRUE), ncol=5)
mrfse.sa(length(a_size), s, 1.0, 500, 1000)

Cnservative approach for Frondana's mrfse using simulated annealing

Description

A penalized likelihood BIC-based to estimate Markovian neighborhoods.

Usage

mrfse.sa.con(a_size, sample, c, t0, iterations=1000, max_neigh=ncol(sample)-1)

Arguments

a_size

Size of the alphabet.

sample

A integer-valued matrix. Each value must belong range 0 and a_size - 1. Matrix has dimension n x V, where n is number of samples and V is number of nodes.

c

The penalization constant. Must be positive.

t0

Inital temperature

iterations

Number of simulated annealing iterations

max_neigh

The maximum length of a candidate Markovian neighborhood. Must be non-negative and less than ncol(sample).

Value

A adjacency matrix of the estimated Markov random field graph.

Author(s)

Rodrigo Carvalho

References

FRONDANA, Iara Moreira. Model selection for discrete Markov random fields on graphs. São Paulo : Instituto de Matemática e Estatística, University of São Paulo, 2016. Doctoral Thesis in Estatística. <doi:10.11606/T.45.2018.tde-02022018-151123> http://www.teses.usp.br/teses/disponiveis/45/45133/tde-02022018-151123/publico/tese_Iara_Frondana.pdf

Examples

library(mrfse)
a_size = c(0, 1)
s = matrix(sample(a_size, size=1000, replace=TRUE), ncol=5)
mrfse.sa.con(length(a_size), s, 1.0, 500, 1000)

Non-conservative approach for Frondana's mrfse using simulated annealing

Description

A penalized likelihood BIC-based to estimate Markovian neighborhoods.

Usage

mrfse.sa.ncon(a_size, sample, c, t0, iterations=1000, max_neigh=ncol(sample)-1)

Arguments

a_size

Size of the alphabet.

sample

A integer-valued matrix. Each value must belong range 0 and a_size - 1. Matrix has dimension n x V, where n is number of samples and V is number of nodes.

c

The penalization constant. Must be positive.

t0

Inital temperature

iterations

Number of simulated annealing iterations

max_neigh

The maximum length of a candidate Markovian neighborhood. Must be non-negative and less than ncol(sample).

Value

A adjacency matrix of the estimated Markov random field graph.

Author(s)

Rodrigo Carvalho

References

FRONDANA, Iara Moreira. Model selection for discrete Markov random fields on graphs. São Paulo : Instituto de Matemática e Estatística, University of São Paulo, 2016. Doctoral Thesis in Estatística. <doi:10.11606/T.45.2018.tde-02022018-151123> http://www.teses.usp.br/teses/disponiveis/45/45133/tde-02022018-151123/publico/tese_Iara_Frondana.pdf

Examples

library(mrfse)
a_size = c(0, 1)
s = matrix(sample(a_size, size=1000, replace=TRUE), ncol=5)
mrfse.sa.ncon(length(a_size), s, 1.0, 500, 1000)

Generate a independent sample of a Markov random field

Description

Generate a independent sample of a Markov random field according to the probilities of the sampler.

Usage

mrfse.sample(sampler, n)

Arguments

sampler

A sampler created by mrfse.create.sampler function

n

Size of sample

Value

A matrix whose number of columns is the number of nodes. Each line is a single independent sample of Markov random field given by the probabilites of sampler.

Author(s)

Rodrigo Carvalho

Examples

library(mrfse)
adj = matrix(c(0, 1, 0, 0, 0, 0, 0, 1, 0), byrow=TRUE, ncol=3)
sampler = mrfse.create.sampler(adj, 3)
mrfse.sample(sampler, 3000)