{"id":{"repo_id":"texas","oai_identifier":"oai:repositories.lib.utexas.edu:2152/ETD-UT-2011-08-4331"},"canonical_url":"https://search.dev.ndltd.org/etd/texas/oai:repositories.lib.utexas.edu:2152/ETD-UT-2011-08-4331","repository":{"repo_id":"texas","name":"University of Texas","base_url":"https://repositories.lib.utexas.edu/server/oai/request"},"display":{"title":"Greedy structure learning of Markov Random Fields","abstract":"Probabilistic graphical models are used in a variety of domains to capture and represent general dependencies in joint probability distributions. In this document we examine the problem of learning the structure of an undirected graphical model, also called a Markov Random Field (MRF), given a set of independent and identically distributed (i.i.d.) samples. Specifically, we introduce an adaptive forward-backward greedy algorithm for learning the structure of a discrete, pairwise MRF given a high dimensional set of i.i.d. samples. The algorithm works by greedily estimating the neighborhood of each node independently through a series of forward and backward steps. By imposing a restricted strong convexity condition on the structure of the learned graph we show that the structure can be fully learned with high probability given $n=\\Omega(d\\log (p))$ samples where $d$ is the dimension of the graph and $p$ is the number of nodes. This is a significant improvement over existing convex-optimization based algorithms that require a sample complexity of $n=\\Omega(d^2\\log(p))$ and a stronger irrepresentability condition. We further support these claims with an empirical comparison of the greedy algorithm to node-wise $\\ell_1$-regularized logistic regression as well as provide a real data analysis of the greedy algorithm using the Audioscrobbler music listener dataset. The results of this document provide an additional representation of work submitted by A. Jalali, C. Johnson, and P. Ravikumar to NIPS 2011.","abstract_html":"Probabilistic graphical models are used in a variety of domains to capture and represent general dependencies in joint probability distributions. In this document we examine the problem of learning the structure of an undirected graphical model, also called a Markov Random Field (MRF), given a set of independent and identically distributed (i.i.d.) samples. Specifically, we introduce an adaptive forward-backward greedy algorithm for learning the structure of a discrete, pairwise MRF given a high dimensional set of i.i.d. samples. The algorithm works by greedily estimating the neighborhood of each node independently through a series of forward and backward steps. By imposing a restricted strong convexity condition on the structure of the learned graph we show that the structure can be fully learned with high probability given $n=\\Omega(d\\log (p))$ samples where $d$ is the dimension of the graph and $p$ is the number of nodes. This is a significant improvement over existing convex-optimization based algorithms that require a sample complexity of <span class=\"etd-inline-math\">n=\\Omega(d<sup>2</sup>\\log(p))</span> and a stronger irrepresentability condition. We further support these claims with an empirical comparison of the greedy algorithm to node-wise <span class=\"etd-inline-math\">\\ell<sub>1</sub></span>-regularized logistic regression as well as provide a real data analysis of the greedy algorithm using the Audioscrobbler music listener dataset. The results of this document provide an additional representation of work submitted by A. Jalali, C. Johnson, and P. Ravikumar to NIPS 2011.","abstract_has_math":true,"creators":["Johnson, Christopher Carroll"],"institution":"University of Texas at Austin","degree_name":"Master of Science in Computer Sciences","degree_level":"Masters","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":["Ravikumar, Pradeep"],"committee_chairs":[],"committee_members":["Dhillon, Inderjit"],"year":2011,"date_issued":"2011-08","date_published":"2011-08","updated_at":"2026-07-24T05:01:06Z","subjects":["Machine learning","Graphical models","Markov Random Fields","Structure learning","Probability","Uncertainty","Greedy algorithms"],"languages":["eng"],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2152/ETD-UT-2011-08-4331","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Ravikumar, Pradeep"]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Dhillon, Inderjit"]},{"key":"dc:creator","label":"Author","values":["Johnson, Christopher Carroll"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2011-11-04T16:54:37Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2011-11-04T16:54:37Z"]},{"key":"dc:date.issued","label":"Date","values":["2011-08"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Masters"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science in Computer Sciences"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Texas at Austin"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Machine learning","Graphical models","Markov Random Fields","Structure learning","Probability","Uncertainty","Greedy algorithms"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/2152/ETD-UT-2011-08-4331"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["text"]},{"key":"dc:description.abstract","label":"Abstract","values":["Probabilistic graphical models are used in a variety of domains to capture and represent general dependencies in joint probability distributions. In this document we examine the problem of learning the structure of an undirected graphical model, also called a Markov Random Field (MRF), given a set of independent and identically distributed (i.i.d.) samples. Specifically, we introduce an adaptive forward-backward greedy algorithm for learning the structure of a discrete, pairwise MRF given a high dimensional set of i.i.d. samples. The algorithm works by greedily estimating the neighborhood of each node independently through a series of forward and backward steps. By imposing a restricted strong convexity condition on the structure of the learned graph we show that the structure can be fully learned with high probability given $n=\\Omega(d\\log (p))$ samples where $d$ is the dimension of the graph and $p$ is the number of nodes. This is a significant improvement over existing convex-optimization based algorithms that require a sample complexity of $n=\\Omega(d^2\\log(p))$ and a stronger irrepresentability condition. We further support these claims with an empirical comparison of the greedy algorithm to node-wise $\\ell_1$-regularized logistic regression as well as provide a real data analysis of the greedy algorithm using the Audioscrobbler music listener dataset. The results of this document provide an additional representation of work submitted by A. Jalali, C. Johnson, and P. Ravikumar to NIPS 2011."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Greedy structure learning of Markov Random Fields"]}]}],"canonical_facts":{"dc:contributor.advisor":["Ravikumar, Pradeep"],"dc:contributor.committeemember":["Dhillon, Inderjit"],"dc:creator":["Johnson, Christopher Carroll"],"dc:date.accessioned":["2011-11-04T16:54:37Z"],"dc:date.available":["2011-11-04T16:54:37Z"],"dc:date.issued":["2011-08"],"dc:description":["text"],"dc:description.abstract":["Probabilistic graphical models are used in a variety of domains to capture and represent general dependencies in joint probability distributions. In this document we examine the problem of learning the structure of an undirected graphical model, also called a Markov Random Field (MRF), given a set of independent and identically distributed (i.i.d.) samples. Specifically, we introduce an adaptive forward-backward greedy algorithm for learning the structure of a discrete, pairwise MRF given a high dimensional set of i.i.d. samples. The algorithm works by greedily estimating the neighborhood of each node independently through a series of forward and backward steps. By imposing a restricted strong convexity condition on the structure of the learned graph we show that the structure can be fully learned with high probability given $n=\\Omega(d\\log (p))$ samples where $d$ is the dimension of the graph and $p$ is the number of nodes. This is a significant improvement over existing convex-optimization based algorithms that require a sample complexity of $n=\\Omega(d^2\\log(p))$ and a stronger irrepresentability condition. We further support these claims with an empirical comparison of the greedy algorithm to node-wise $\\ell_1$-regularized logistic regression as well as provide a real data analysis of the greedy algorithm using the Audioscrobbler music listener dataset. The results of this document provide an additional representation of work submitted by A. Jalali, C. Johnson, and P. Ravikumar to NIPS 2011."],"dc:format.mimetype":["application/pdf"],"dc:identifier.uri":["http://hdl.handle.net/2152/ETD-UT-2011-08-4331"],"dc:language.iso":["eng"],"dc:subject":["Machine learning","Graphical models","Markov Random Fields","Structure learning","Probability","Uncertainty","Greedy algorithms"],"dc:title":["Greedy structure learning of Markov Random Fields"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Masters"],"thesis:degree_name":["Master of Science in Computer Sciences"],"thesis:institution_name":["University of Texas at Austin"]},"updated_at":"2026-07-24T05:01:06Z"}