Archive for the ‘Graphical Models’ Category

An Introduction to Graphical Models

Sunday, August 31st, 2014

An Introduction to Graphical Models by Michael I. Jordan.

A bit dated (1997), slides, although “wordy” ones, that introduce you to graphical models.

Makes a nice outline to check your knowledge of graphical models.

I first saw this in a tweet by Data Tau.

Graphical models toolkit for GraphLab

Friday, February 21st, 2014

DARPA* project contributes graphical models toolkit to GraphLab by Danny Bickson.

From the post:

We are proud to announce that following many months of hard work, Scott Richardson from Vision Systems Inc. has contributed a graphical models toolkit to GraphLab. Here is a some information about their project:

Last year Vision Systems, Inc. (VSI) partnered with Systems & Technology Research (STR) and started working on a DARPA* project to develop intelligent, automatic, and robust computer vision technologies based on realistic conditions. Our goal is to develop a software system that lets users ask queries of photo content, such as “Does this person look familiar?” or “Where is this building located?” If successful, our technology would alert people to scenes that warrant their attention.

We had an immediate need for a solid, scalable graph-parallel computation engine to replace our internal belief propagation implementation. We quickly gravitated to GraphLab. Using this framework, we designed the Factor Graph toolkit based on Joseph Gonzalez’s initial implementation. A factor graph, a type of graphical model, is a bipartite graph composed of two types of vertices: variable nodes and factor nodes. The Factor Graph toolkit is able to translate a factor graph into a graphlab distributed-graph and perform inference using a vertex-program which implements the well known message-passing algorithm belief propagation. Both belief propagation and factor graphs are general tools that have applications in a variety of domains.

We are very excited to get to work on key problems in the Machine Learning/Machine Vision field and to be a part of the powerful communities, like GraphLab, that make it possible.

I admit to not always being fond of DARPA projects but every now and again they fund something worthwhile.

If machine vision becomes robust enough, you could start a deduped porn service. 😉 I am sure other use cases will come to mind.

If you haven’t looked at GraphLab recently, you should.

Foundations of Data Science

Sunday, September 29th, 2013

Foundations of Data Science by John Hopcroft and Ravindran Kannan.

From the introduction:

Computer science as an academic discipline began in the 60’s. Emphasis was on programming languages, compilers, operating systems, and the mathematical theory that supported these areas. Courses in theoretical computer science covered nite automata, regular expressions, context free languages, and computability. In the 70’s, algorithms was added as an important component of theory. The emphasis was on making computers useful. Today, a fundamental change is taking place and the focus is more on applications. There are many reasons for this change. The merging of computing and communications has played an important role. The enhanced ability to observe, collect and store data in the natural sciences, in commerce, and in other elds calls for a change in our understanding of data and how to handle it in the modern setting. The emergence of the web and social networks, which are by far the largest such structures, presents both opportunities and challenges for theory.

While traditional areas of computer science are still important and highly skilled individuals are needed in these areas, the majority of researchers will be involved with using computers to understand and make usable massive data arising in applications, not just
how to make computers useful on specifi c well-defi ned problems. With this in mind we have written this book to cover the theory likely to be useful in the next 40 years, just as automata theory, algorithms and related topics gave students an advantage in the last 40 years. One of the major changes is the switch from discrete mathematics to more of an emphasis on probability, statistics, and numerical methods.

In draft form but impressive!

Current chapters:

  1. Introduction
  2. High-Dimensional Space
  3. Random Graphs
  4. Singular Value Decomposition (SVD)
  5. Random Walks and Markov Chains
  6. Learning and the VC-dimension
  7. Algorithms for Massive Data Problems
  8. Clustering
  9. Topic Models, Hidden Markov Process, Graphical Models, and Belief Propagation
  10. Other Topics [Rankings, Hare System for Voting, Compressed Sensing and Sparse Vectors]
  11. Appendix

I am certain the authors would appreciate comments and suggestions concerning the text.

I first saw this in a tweet by CompSciFact.

Accelerating Inference: towards a full Language, Compiler and Hardware stack

Friday, December 14th, 2012

Accelerating Inference: towards a full Language, Compiler and Hardware stack by Shawn Hershey, Jeff Bernstein, Bill Bradley, Andrew Schweitzer, Noah Stein, Theo Weber, Ben Vigoda.

Abstract:

We introduce Dimple, a fully open-source API for probabilistic modeling. Dimple allows the user to specify probabilistic models in the form of graphical models, Bayesian networks, or factor graphs, and performs inference (by automatically deriving an inference engine from a variety of algorithms) on the model. Dimple also serves as a compiler for GP5, a hardware accelerator for inference.

From the introduction:

Graphical models alleviate the complexity inherent to large dimensional statistical models (the so-called curse of dimensionality) by dividing the problem into a series of logically (and statistically) independent components. By factoring the problem into subproblems with known and simple interdependencies, and by adopting a common language to describe each subproblem, one can considerably simplify the task of creating complex Bayesian models. Modularity can be taken advantage of further by leveraging this modeling hierarchy over several levels (e.g. a submodel can also be decomposed into a family of sub-submodels). Finally, by providing a framework which abstracts the key concepts underlying classes of models, graphical models allow the design of general algorithms which can be efficiently applied across completely different fields, and systematically derived from a model description.

Suggestive of sub-models of merging?

I first saw this in a tweet from Stefano Bertolo.

Stan: A (Bayesian) Directed Graphical Model Compiler

Sunday, January 22nd, 2012

Stan: A (Bayesian) Directed Graphical Model Compiler

Post with link to presentation to NYC machine learning meetup.

Stan: a C++ library for probability and sampling has not (yet) been released (BSD license) but has the following components:

From the Google Code page:

  • Directed Graphical Model Compiler
  • (Adaptive) Hamiltonian Monte Carlo Sampling
  • Hamiltonian Monte Carlo Sampling
  • Gibbs Sampling for Discrete Parameters
  • Reverse Mode Algorithmic Differentiation
  • Probability Distributions
  • Special Functions
  • Matrices and Linear Algebra

Slides for the NIPS 2011 tutorial

Monday, December 12th, 2011

Slides for the NIPS 2011 tutorial by Alex Smola.

From the post:

The slides for the 2011 NIPS tutorial on Graphical Models for the Internet are online. Lots of stuff on parallelization, applications to user modeling, content recommendation, and content analysis here.

Very cool! Wish I could have seen the tutorial!

Read slowly and carefully!

Your Help Needed: the Effect of Aesthetics on Visualization – Post

Friday, March 4th, 2011

Your Help Needed: the Effect of Aesthetics on Visualization

Your opportunity to make a contribution to the study of visualization!

From the website:

We have just launched an online study on measuring the effect of aesthetics in data visualization. If you have about 10-20 minutes of uninterrupted time, please head over to Aesthetic Impact [aesthetic-impact.com] and take part in our online study. The main task that will be expected from you, is to interact with a visualization, and describe what you have learned from it.

The study is not only meant for visualization fanatics, so please pass around the URL to any person who might be interested in participating. The only thing you need to know is that the study is less about usability, utility or usefulness, and more about measuring what non-trivial and unexpected insights you actually ‘get’ from interacting with a specific data representation.

As communicating insight is the main reason for any interactive visualization, we think that measuring this aspect has become really important. Yet, we require the help of many ‘users’ to be able to say something meaningful…

Chris Harrison’s Graphics – Post

Wednesday, January 12th, 2011

Chris Harrison’s Graphics reported by Bob Carpenter at LingPipe Blog.

Visualizations are like slide presentations.

They can be painful but you do encounter those that simply work.

These are ones that just work.

It is possible to visualize a topic map as a graph, yawn, but when was the last time you saw a graph outside of math class?

True, all maps are graphs but I would be willing to bet most people would not name a map as an example of a graph.

Why?

Because a map, at least a well done one, assists its reader in accomplishing some task of interest to them. Using the map is a goal, not an end unto itself.

Hmmm, maps with nodes and edges connecting those nodes,…, I know, how about Disney World Maps!

Those are maps of physical locations.

Questions:

  1. What are some of the characteristics of any one or more of the Disney maps? (3-5 pages, no citations)
  2. Find five examples of maps that are not maps of physical locations.
  3. What is different/same about the maps in #1 versus #2? (3-5 pages, no citations)

*****
PS: Depending on the status of diplomatic cables (hopefully from a number of countries), consider that a graph between the cables could be interesting.

More interesting would be photos of the folks mentioned, arranged by events or contacts they share in the US. Has characteristics of a graph but perhaps more immediately compelling.

Say showing photos of all the School of the Americas graduates clustered together, like in a high school yearbook or police mug photo book.

Or showing those same photos with US officials.

To facilitate human recognition of additional subjects to pursue.

Graphical Models

Tuesday, December 21st, 2010

Graphical Models Author: Zoubin Ghahramani

Abstract:

An introduction to directed and undirected probabilistic graphical models, including inference (belief propagation and the junction tree algorithm), parameter learning and structure learning, variational approximations, and approximate inference.

  • Introduction to graphical models: (directed, undirected and factor graphs; conditional independence; d-separation; plate notation)
  • Inference and propagation algorithms: (belief propagation; factor graph propagation; forward-backward and Kalman smoothing; the junction tree algorithm)
  • Learning parameters and structure: maximum likelihood and Bayesian parameter learning for complete and incomplete data; EM; Dirichlet distributions; score-based structure learning; Bayesian structural EM; brief comments on causality and on learning undirected models)
  • Approximate Inference: (Laplace approximation; BIC; variational Bayesian EM; variational message passing; VB for model selection)
  • Bayesian information retrieval using sets of items: (Bayesian Sets; Applications)
  • Foundations of Bayesian inference: (Cox Theorem; Dutch Book Theorem; Asymptotic consensus and certainty; choosing priors; limitations)

Start with this lecture before Dirichlet Processes: Tutorial and Practical Course