09 Dec 2013

Visualizing Inference in Large Bayesian Networks

1 Introduction The application of machine learning in the 21st century is increasingly both exciting and challenging, with many orders of magnitude more digital data available than before. The amount of text data on the internet has increased from an estimated couple terabytes in 1997, to Twitter.com alone storing 50 gigabytes of new tweets daily [1][2]. This does not count the many private databases used in enterprise, such as the petabytes of customer and transaction information Wal-Mart Stores retains [3]. Though the collection of raw data will continue to have its challenges and costs, significant attention has now turned to the problem of utilizing all of this data. Whether the goal is indexing, data-mining, or building predictive models, today's challenge is fundamentally tied to the enormous number of observations and variables captured. This is the so-called “big data” problem. Equally important as the algorithms or storage systems are the visualization methods. Presentation is not simply an aesthetic concern. Edward Tufte writes that “often the most effective way to describe, explore, and summarize a set of numbers – even a very large set – is to look at pictures of those numbers,” and that data graphics can be both “the simplest [and] most powerful” of methods [4]. Bayesian networks in many applications enable efficient and scalable statistical and causal modeling [5], and have a natural visual representation following from their graph structure. By viewing a visual representation of the graph structure one can quickly identify potential correlations or causal relationships between variables simply by viewing the presence of edges in the rendered graph structure. Beyond this simple case, more sophisticated analysis by visual means alone is difficult, especially as the model grows in size. Viewing conditional distributions with more than a couple parent variables quickly becomes unwieldy, and networks with upwards of 50 variables can be difficult for a user to navigate and parse visually. Recent work has focused on improving visualization and navigation in large networks of up to thousands of variables [6], and is not a solved problem yet. To understand these large, modern networks more efficiently, and in turn better utilize the wealth of data available in the era of big data, new methods of visualization are needed. To this end, we introduce two ideas to assist the visual analysis of large Bayesian networks: inference diffs and relevance filtering. 2 Summary of Prior Work Though creating effective ways to visualize Bayesian networks is not a new problem (relative to the age of “Bayesian networks” proposed in detail by Pearl in 1988 [7]), it appears to be a problem that has received rela- Draft (v5) 1 2013 December 9 Visualizing Inference in Large Bayesian Networks Clifford Champion Department of Computer Science and Engineering University of California, San Diego cchampio@cs.ucsd.edu Abstract In this project we address the challenge of viewing and using Bayesian networks as their structural size and complexity grows. We introduce two new visualization methods, inference diffs, and relevance filtering, to enable visual analysis of information flow in these networks, and to enable direct comparison of two evidence configurations simultaneously. We implement and discuss the performance of these visualization methods on two modestly large networks, built from real-world data. tively little attention. While there have been advances in visualizing large graphs such as those surveyed by Schaeffer [8], these methods depend on basic graph-theoretic information at most, such as cliques and node degree, and don't directly consider the probabilistic aspects of Bayesian networks. Nevertheless, some variety of visual designs and principles specific to Bayesian networks have been developed or explored over time, and are briefly recounted here. To visualize causal relationships globally, so-called temporal or causal layouts are popular, placing ancestors (e.g. independent variables) near the top of the visual layout and descendents (e.g. dependent variables) near the bottom, for a generally downward flow of edge directions, for a downward flow of causation. This kind of layout is often used without explicit mention and is a feature of some directed graph layout algorithms, but Zapato- Rivera et al., and Chiang et al. called out this layout explicitly [9][10]. To visualize local influence (i.e. between exactly two variables) the direction of the edge arrow is of course wellestablished for indicating the direction of modeled cause and effect. Beyond simply the edge direction, or its presence at all, Zapato-Rivera et al. explored fixed color assignments to independent variables, and color mixtures thereof to dependent variables, weighted to indicate relative strength influence from the parent variables [9]. Zapato-Rivera also considered varying edge lengths, so that mutually influential nodes appear nearer to one another than if uninfluential. Further, both Zapato- Rivera et al. and Koiter explored varying edge thickness to indicate influence between parent and child variables, using thick lines for strong influence. Each discussed various analytical definitions for computing the input values needed for these visualization techniques [9] [11]. To visualize conditional probability tables (CPTs), Chaing et al. proposed miniature 2d heatmaps attached to edges [10], however this is appears to be well-defined only for children with exactly one parent each. Cossalter et al. introduced “bubble lines” connecting nodes in the network to floating CPT windows, making it easier for the user to keep their bearings while debugging CPTs in large networks. They also introduced a numerical difference view for viewing CPTs of two variables expected to have similar local distributions [12]. To visualize the presence of evidence, common practice in literature is to draw a double-border around observed nodes (variables with evidence), or to use shading on the interior of the node. Williams and Amant experimented with using different colors of shading to indicate different evidence values [13]. To visualize marginal and posterior distributions, at least three techniques have been explored. Software application Netica used rectangular nodes instead of circular, in order to embed bar charts for the marginal probability masses of each variable [14]. Software application BayesiaLab allowed the user to open a distribution window for each variable and compare the prior (no evidence) and posterior (with evidence) distributions of a variable in two horizontal bar charts overlaid on one another [15]. Zapato-Rivera et al. used node diameter to indicate large or small posterior probabilities for binaryvalued variables, and animation thereof to indicate changes to posteriors under changing evidence [9]. To visualize local and global information simultaneously, Sundararajan et al. employed a partition and fish-eye approach to graph layout, letting the user define and inspect local areas of interest in the network while still seeing the context and structure of the full network [6]. A common trait among most of the approaches is their dependence on relatively static information about the network, whether this be the conditional probability tables, or simple posterior or marginal distributions. Our goal is to create a visualization that captures a more dynamic view of the Bayesian networks, hopefully shining new light on information flow; and to scale effectively in large networks. We outline our basic design choices next, using or iterating on prior work, and upon this foundation introduce a more dynamic approach to visualizing Bayesian networks using inference diffs. Draft (v5) 2 2013 December 9 3 Visual Foundation 3.1 Assumptions and Principles Our approach is to define a visual language equally suited for print or personal computer, and consistent with the principles proposed by Edward Tufte on “graphical displays” [4]. When a human-computer interaction is discussed, we assume one user at a time, that they are using a mouse or a touch-screen interface, and that their display size and DPI is that of an average tablet or desktop display. Our underlying model to visualize is a Bayesian network of finitely many random variables, and each variable having a finite event space. We assume at the very least the user would desire to be able to view the Bayesian network structure, inspect local conditional probability distributions, see marginal or posterior distributions, inspect the event space of each variable, and otherwise clearly see the basic makeup of the network instance. These assumptions are sufficient for defining the foundation of our visual design. To stay disciplined and focused, we will also seek to avoid “chart junk”, avoid distorting data or potentially misleading the user, and avoid unnecessary ink, maximizing the “data-ink ratio” [4]. Every pixel or drop of ink should convey information and convey so unambiguously. 3.2 Network Structure and Random Variables The most basic information in a Bayesian network is the structure and random variables therein. To present the structure is to present the (learned or constructed) causal influence between variables. Logically, this object is a directed acyclic graph (DAG); visually, this is traditionally a collection of labeled circles and arrows between them. We largely continue this tradition. Random variables must be clearly identifiable, while at the same time clutter must be kept under control, otherwise it becomes noise. To this end, there are two views: structural and legend. The structural view present a variable as a single, circumscribed capital letter, taken from the first letter in the name of the variable. The legend view maps these letters to their full variable names, such A to age. Capital letters are used in the structural view for readability. As with previous methods, vertical ordering in the structural view is presented causally top-down to the extent possible, though this is not always possible, especially in large networks. To scale to large networks, we perform two more things. First, where two or more random variables have the same single letter in the structural view, we suffix their name with a unique number, chosen sequentially from 1. This numerical suffix appears both in the structural view and the legend view in subscript type. Second, both views are scrollable and both follow loosely the same top-to-bottom variable ordering. On the appearance of random variables in the structural view, we de-emphasize the dark stroke that traditionally circumscribes the variable, as we will be using this stroke to carry meaning later. Until then, this shading decision comes at cost our to data-ink ratio. Finally, we reserve the use of color when simply presenting structure, so that color may be used to present other aspects of the model, discussed next. 3.3 Coloring the Event Space Representing values from the event spaces of our random variables, clearly and succinctly to the user, will be critical for inference diffs discussed later. We choose color this our modality, assigning on a variable-by-variable basis a unique color for each value in the variable's event space. We only guarantee unique color assignment Draft (v5) 3 2013 December 9 Figure 1: Structural and legend views. within each variable, not over the collection of variables. This permits us to design a reusable, optimal color palette with minimal visual confusion when within the context of a single variable. Though there is possible ambiguity in values of different variables sharing a same color, our design avoids this ambiguity by always framing color in the context of a specific variable. Where two or more variables share the same event space, we reuse the color mapping for stronger consistency. To indicate what in fact the color assignments are for each value and each variable, we augment our legend view to list each event space value with corresponding assigned colors, seen in Figure 2. For categorical event spaces our color map is constructed so that no two contiguous colors are perceived too near to one another: for example, orange may follow green but may not follow brown. For ordered event spaces the color map is constructed in the opposite fashion by sequentially choosing neighboring hues on the color wheel, e.g. from the blue region, through yellow, to the red region. As will be important later, we ensure any presented color order (value order) is constant, e.g. for a particular variable, blue always appears first before orange. 3.4 Conditional Probability Tables One of practical difficulties with Bayesian networks can be the size of each conditional probability table (CPT), or its local distribution. Recall that the size of a random variable's CPT is generally the number of probability weight assignments specified, which grows exponentially in the number of parent variables (or the in-degree of the variable). Some tools present the CPT as a single table with columns for each permutation of parent values, but this tends to require a large horizontal scrolling area. We propose that vertical scrolling is more natural, and present our CPT vertically. We present each conditional probability distribution for a given parent permutation as a simple vertical list of probability densities. We stack each such list vertically, and separate each by their corresponding parent value permutation, placed above it. We use our event space color mappings here, for each probability density and each parent value; and again use corresponding abbreviated variable names (e.g. A1). 3.5 Embedded Distributions Viewing the marginal distribution of each variable should be convenient; that is, we want a clear way to see P (X ) for each random variable X . Most tools require the user open an additional window to see such distributions, either in tabular form or bar chart. We simply embed the distribution directly in the variable in the structural view. To do this we construct a pie chart using our event space color mapping, and render pie slices proportional in size to the posterior probability mass of each Draft (v5) 4 2013 December 9 Figure 3: Conditional probability table view for a variable T2. Figure 2: Values in each random variable event space are mapped to a preset color palette. Figure 4: Marginal or posterior distributions are embedded directly in the variable via area pie chart. value, starting at the 12 o'clock position, allocating slices in clockwise order. This highly visual approach conveniently presents an overview of the entire statistical model to the user, without their needing to inspect variables one-by-one in sequence, or in additional views. Where more precise numerical inspection is needed, a we use an additional color-coded tabular view similar to our CPT view. 3.6 Evidence Arguably the greatest power of a Bayesian network model (once it is trained or constructed) is in computing posterior distributions of arbitrary evidence, i.e. P(X | E) . We will not explicitly discuss causal modeling and interventions (the analogue of evidence) until later, as most of our visual design for statistical models has a natural extension into causal models. From a visualization perspective it is important that the user clearly see which variables currently have evidence and which do not; and furthermore, what specific values of evidence have been specified. To indicate that a variable has user-defined evidence, we circumscribe the variable in the structural view with a strong black stroke. Moreover, the interior of node is colored entirely with the associated color of the evidence value, as seen in Figure 5. Finally, all embedded distributions for non-evidence nodes are updated in the structural view to reflect each variable's new, posterior distribution. Our previous visualization which embeds marginal distributions is of course simply a special case of visualizing posterior distributions with an empty evidence set. We will formalize our notion of evidence in finer detail shortly. 4 Making an Inference Diff 4.1 Motivation With a basic visual foundation established, we focus our attention to more sophisticated visual analysis methods. The basic idea we introduce first is that of an inference diff. Inference and information flow is an important capability of Bayesian networks. Consider a large network which models the health of components in a large multi-component system. One may wish to use this network to ask which components' probabilities of failure are affected by one or more other variables, for instance ambient air temperature, and for those affected, to what degree; or the inverse of this and ask what are the most likely environmental conditions given a failure in one or more components. As networks grow in size, the answers to these questions can be as difficult to find as the right question to ask in the first place. There are analytical tools such as d-separation; however, such a tool is limited in its application, largely because a Bayesian network is itself inherently limited in its ability to describe certain independent relations [16]. Recall that for a network G , its I-map I (G) may not be a minimal I-map, meaning G contains unnecessary edges and is too safe in its conditional independence claims. Moreover, for a true joint distribution it may be impossible for any Bayesian network to have a perfect I-map (or P-map). There may also be context-specific independencies in the network, not discernible in network structure alone. Further, the user may not need to know or care about certain dependencies if small or approximately independent. In each case these issues can lessen the usefulness of d-separation analysis in practice, or require more complicated analysis. On the other hand there is exhaustive computation, using inference algorithms to produce complete posterior distributions for some or all of the non-evidence Draft (v5) 5 2013 December 9 Figure 5: Evidence nodes are circumscribed with a strong black stroke, and colored according to their evidence. All other nodes' embedded distributions are updated to reflect their posterior distributions. For example, T1's embedded distribution now reflects P(T1 | V=v , A=a) rather than simply P(T1) . variables. Such output is much more detailed and precise, but suffers from another limitation in that it is static. From it there is no direct indication of how or to what degree belief propagation occurred. There is simply a before and after state of the distribution. What we would like is a way to visualize in an obvious way the effects of information flow through the network. To this end we find inspiration in modern software engineering practices and so-called “diff” tools (short for “difference” tool). Reviewing the “diff” of two or more human-readable files is an every-day practice in commercial software development, generally aided by the use of color and side-by-side before-and-after views. As a means of visualizing change, diffs are highly effective and visually intuitive. Our goal is to find an as-effective method of viewing inference and information flow in Bayesian networks, in hopes of enabling a more powerful kind of visual analysis. 4.2 Definition We start with a mathematical definition an “inference diff”. Given a Bayesian network B describing a probabilistic model over n random variables {Xi : i∈[1,n] } , each with finite event space Si , and given two evidence sets E1 and E2 , each an element of the set of partial observations ×i=1 n Si ∪{?} , we define an inference diff Δ to be the set of pairs Δ={ ( P(X i | E1) , P( X i | E2) ) : i∈[1, n] } . In other words, an inference diff is the set of pairs of conditional probability distributions, for each random variable, and according to two sets of evidence. For example if the random variables of the network are X , A , and B , and B takes on value b in E1 then E1=(? , ? ,b) and P(X | E1)=P(X | B=b) . If an evidence set is equal to (? ,? , ... , ?) we say that it is empty. Note that we use ? to represent “unobserved” or “unspecified”. 4.3 Visualization To visualize inference diffs we extend our use of pie charts. First we establish convention that evidence set E1 is in fact the evidence set when simply using the network to view a single set of posterior results. For instance Figure 5 represents an E1 with values for two variables, and an E2 that is empty. To augment our visualization for the case when E2 is non-empty, we introduce for each variable a “ring” chart, concentric with the variable's existing pie chart. We reuse the event space color map established for that variable, maintain a consistent event space ordering, and again weight the chart slices in proportion to posterior probability masses for that variable, this time conditioned on E2 . To indicate which variables have evidence specified, we continue to use the strong black stroke, applied to either the pie, the ring, or both, in accordance with which variable and evidence set has evidence. By carefully reserving use of the black stroke earlier, we are able to apply it here in a more nuanced fashion, to help disambiguate from which evidence set a variable's evidence is specified. This concentric design allows the user to make direct comparisons of the effects of evidence sets E1 and E2 , quickly and easily. At least two classes of queries can be performed now and produce interesting visual answers. First, one can view information flow more concretely, simply by setting E1=×{?} , and E2 to any partial observation. Second, one can make direct comparisons between different non-empty evidence sets, such as asking whether observing some three variables is different than observing only two of them, or asking how different is it to observe variable X i having some value than to observe variable X j having that value. Draft (v5) 6 2013 December 9 Figure 6: An inference diff between two evidence sets. Here variable A10 has observed values in both sets, indicated by a black stroke around both the inner circle (evidence set 1) and the outer ring (evidence set 2). 5 Relevance Filtering While the inference diff enables direct comparisons of the effects of different evidence on each variable, it doesn't necessarily help guide the user to the variables they may be interested in the most. This can be a problem in large Bayesian networks, where there is simply too much information visible simultaneously, or where the user itself lacks familiarity with the variables in the model. What we would hope to achieve is a way to guide the user to the variables they are likely to be interested in, given some provided evidence. To accomplish this we use the inference diff as our basis, and add to it relevance filtering. 5.1 Definition We define the relevance of a random variable X i as simply the symmetric Kullback-Leibler (KL) divergence [17] of that random variable given its inference diff. More precisely, given an inference diff Δ derived from evidence sets E1 and E2 , we define the relevance rΔ of a random variable X as rΔ( X )= DKL ( P( X | E1) || P ( X | E2) ) +DKL ( P( X | E2) || P(X | E1) ) . The function DKL indicates the Kullback–Leibler divergence, with standard definition DKL(P||Q)=Σi ln( P(i) Q(i) )∗P(i) for probability distributions P and Q sharing the same event space. We use the symmetric KL divergence so that our definition of relevance is also symmetric. Given two random variables X i and X j , if rΔ( Xi ) < r Δ(X j) then we say that X j is more relevant than X i given evidence sets E1 and E2 . This definition of relevance is chosen intuitively. Because distributions which differ greatly have high KL divergence values, we are saying that the variables whose conditional distributions changed the most (between E1 and E2 ) are the variables that are most relevant to the user. 5.2 Visualization With relevance defined, we have our final mathematical tool to complete our visualization method. For large networks it can be easy for evidence sets to produce minimal differences in the posterior distributions of variables. It is with this situation in mind that we apply our definition of relevance. To do this, we first decide which variables are relevant enough for the user. Given the current inference diff Δ , we sort the variables of Δ in descending order according to their relevance. Second, we introduce a user-configurable relevance threshold, represented as a percent value c between 0% and 100%. Finally, we tag each random variable X i as either “relevant” or “irrelevant” according to whether whether X i is in the top c percent of variables ordered by relevance. Lastly, we adjust our visualization in the structure and legend views. Variables which are irrelevant according to threshold c are shrunk, dimmed, and their pie and ring charts removed in the structure view. We also shorten the edge lengths between any two collapsed variables, and edges connecting at least one irrelevant variable are changed to a dotted line rendering. The overall effect is to shrink the virtual space needed for the entire graph structure, which focuses the user's attention on the relatively small number of variables remaining. For these remaining variables we continue to show the pie and ring charts associated with the inference diff. We also remove from the legend view irrele- Draft (v5) 7 2013 December 9 Figure 7: An inference diff with relevance filtering enabled. Variables A and V contain evidence in at least one evidence set each. Compared with the structure seen in Figure 1, variables labeled C, T2, and X were least relevant given the evidence sets, and thus are reduced in size and visibility. vant variables. The end result is a user-controllable level of visual complexity, and a clear and concise, qualitative view of information flow where most impactful. 6 Data Set Examples To test our proposed visualizations, we developed a simple application called B-Vis. In building this application we implemented our own structure learning and inference based on existing algorithms in the literature, open-sourced separately as F-AI [18]. For graph layout we choose the library Graph# [19], making small modifications as necessary. Unless otherwise noted we use the “Sugiyama Efficient” method found in Graph#, which we presume is based on one or more of the layered graph drawing algorithms of Kozo Sugiyama [20]. 6.1 San Francisco Traffic Data Set Our first data set consists of San Francisco bay area highway system traffic flow measurements (“Traffic” set), acquired by Krause and Guestrin [21] and modified by Shahaf et al. [22] into four discrete bins of traffic flow quantity. The set consists of 4415 samples and 32 traffic sensor measurements per sample, with no missing data. From this we train a Bayesian network, learning both structure and CPTs, using a uniform Dirichlet prior and an in-degree limit of two for each variable. Figure 8 shows the learned structure, final layout, and embedded marginal distributions. Note that the network size and structure makes it inherently tall, such that the view must be zoomed out in order to fit the entire network on a standard resolution display without scrolling. Next we configure some evidence. We let E1 be empty, and E2 contain an evidence value of 'medium' (mapped to green) for variable A4. We configure relevance filtering to preserve the top 20% most relevant variables. Figure 9 shows our visualized result. Note that because of relevance filtering, not only do we clearly see the variables which are likely to interest us the most, but we are also able to zoom in on our network view, fitting all of the network on-screen without scrolling; embedded posterior distributions on the relevant variables are clear to see and compare. We chose variable A4 (A11 in the original data set) for this example because of its potentially large influence according to the network structure, with a vertex degree of 14. Relevance filtering in this instance presented a visually manageable total of only 5 connected variables, those 5 with which Draft (v5) 8 2013 December 9 Figure 8: A network trained on the Traffic set. No evidence sets are specified, revealing all variables and their marginal distributions. Figure 9: An inference diff of the Traffic network with relevance filtering enabled, choosing the top 20% most relevant variables given the evidence sets. were most affected by the change in evidence. Because the Sugiyama layout algorithm is layered means there is also resemblance between the before and after layouts. The Traffic data set is somewhat special-case in that all variables share the same event space, and that the variables are highly correlated for identical event values. 6.2 U.S. 1990 Census Data Set For a larger and more interesting network, we consider the 1990 U.S. Census data set (“Census”), discretized by Meek et al. [23][24]. This set contains responses and classifications of 2.4 million individuals stored in 68 attributes. For the purposes of testing our visualizations, work we train on only the first 10,000 randomized examples. As with before we use a uniform Dirichlet prior, but increase our in-degree limit to 3 for this training. The trained network is visible in its entirety in Figure 10. We again use the Siguyama layout method. Note that due to the size of this network, we must zoom quite far out just to see it in its entirety. To test relevance filtering we configure evidence set 1 in our inference diff to be empty, and evidence set 2 an observation of true for variable 'income4'. Variable 'income4' indicates that the individual reported some form of interest, dividend, or rental income/loss in the prior year [23][24][25]. Most individuals in the U.S. don't report income of this kind, so it is perhaps an interesting question to ask the network model: how does knowing a person receives income of this type change our other statistical beliefs about the person? Though our inference diff provides direct before-andafter comparisons, sixty-seven other variables is a large number to sift through. We configure relevance filtering to again return the 20% most relevant variables, and find some interesting results, both as it pertains to the model, and to the visualization, seen in Figure 11. The visual analysis quickly reveals that the twelve variables most affected (in no special order) are: year of immigration ('immigr'), place of birth ('pob'), their Hispanic heritage ('hispanic'), the relationship to the homeowner ('relat2'), whether the individual is part of a subfamily ('subfam1'), how many subfamilies are present ('subfam2'), whether the individual works on a farm ('income3'), whether the individual served in the military during no major war or conflict ('othrserv'), their ancestry ('ancstry2'), their means of transportation to work ('means'), their status in the job market ('avail'), and the employment status of their parents ('remplpar') [25]. With the twelve (or generally, configurable number of) most interesting variables brought to the user's attention, they can now drill down into more detail where sought. For instance our updated belief about means of travel to work has changed in an interesting way. Figure 12 shows the inference diff for variable 'means'. We see that the knowing the person receives interest, dividends, or rental income greatly increases the statistical chance that they do not commute to work each day, and greatly reduces the chance that they commute by means other than car, such as bike or rail. Another feature of the output is revealing. Note that none of the three variables directly connected to 'income4' were included in the filtered output ('rearning', 'rpincome', and 'income6'). Though this may seem counter-intuitive, it is not unreasonable. Depending on the local distributions (e.g. CPTs) at each variable, the effects of evidence can amplify from link to link according to inference, in a manor similar to error accumulation. Further, with three trails out of 'income4', there is opportunity for small local changes to join elsewhere with a combining effect. Or the opposite can occur, such as with the example evidence sets used on the Traffic network (Figure 9). This visualization method can be revealing of the kind of information flow possible in Bayesian networks in general, and in comparisons involving specific, arbitrary evidence. Draft (v5) 9 2013 December 9 Draft (v5) 10 2013 December 9 Figure 10: Census network, consisting of 68 variables, zoomed out to reveal entire structure. Figure 11: Census network, with relevance filtering enabled for the current inference diff. The top 20% most relevant variables retain their embedded posterior distributions, while all other variables are reduced in size and visibility. 7 Future Work 7.1 Challenges and Scaling Further Maintaining layout stability is particularly important. The user must be able to adjust relevance filtering without radical changes to the layout, otherwise the experience quickly becomes disorienting. We were able to maintain a minimally sufficient level of stability, simply by using the “Sugiyama Efficient” algorithm in Graph#. Though this has some inherent stability due to its layered solution, it is not quite perfect for our needs. We would like to incorporate a customized or more sophisticated layout algorithm with inference diffs and relevance filtering in mind. Such an algorithm may continue to be layered, for instance with stability addressed in more detail in Sugiyama's original works [20]; or forceddirected with constraints, which has ongoing exploration [26]. It may also be possible to combine the fish-eye techniques of Sundararajan et al., by automatically configuring their interest areas using the locations of our relevant variables after relevance filtering [6]. Our choice of color as a modality for values is challenging when scaling to large event spaces. For instance, some variables in the Census data set contained over 15 possible values. Our color mapping at present contains only 6 unique color values, meaning that for such variables some colors were used multiple times. Because we present a consistent ordering, both radially and in the legend view values, ambiguity is mostly removed, but requires additional mental energy on the part of the user. For categorical variables with significantly more than 15 values, the effectiveness of the color mapped approach is expected to fall apart. For color-blind users, using a limited color palette creates further difficulty in scaling. One interesting possibility may lay in collapsing colors in inference diffs, where the probability masses of certain values are small or have changed very little in the diff for that variable. Coloring continuous-valued variables is not addressed here, but may be possible as well, perhaps by bounding the event space and assigning distinct colors to special points of significance in the event space, with weighted color blending radially. 7.2 Applications to Other Graphical Models With respect to Bayesian networks, though the models presented here are statistical, rather than causal, an inference diff is possibly most useful in a network with truly causal modeling. For example in medicine, one could quickly ask the network for a visual answer to the question: given a patient with conditions X and Y , i.e. X =true ,Y=true in E1 and E2 , what are the largest differences expected between prescribing treatment A versus treatment B , i.e. do (A=true , B= false) in E1 and do (A= false , B=true) in E2 . Other probabilistic network models may benefit from inference diff and relevance filtering visualizations, such as Markov random fields which have similar inference and belief propagation capabilities. 7.3 Unused Modalities Unused visual modalities could be explored, or unused past work revisited. Edge thickness and edge colors could possibly carry additional information. Having more than two evidence sets, by using more than one ring chart per variable, may also be possible and useful. Instead of beginning embedded distributions' slices at the 12 o'clock position, the start degree could be varied and demarcated to carry significance of some kind. The shape of nodes in the structural view could also convey information, such as whether the node captures a causal dependency. Draft (v5) 11 2013 December 9 Figure 12: Inference diff of variable 'means' (of transportation). The diff is generated from an empty evidence set 1, and a evidence set 2 with 'income4'=true. 7.4 Other Metrics for Relevance Metrics other than KL-divergence may be useful or more appropriate for relevance filtering. Regardless of the basic metric chosen, it may be useful if weights can be attached to values in the event spaces, such that large changes to probability masses of low-weight events count less toward making that variable relevant. 8 Conclusion Visualization methods are increasingly important as the scope and quantity of data increases. The flexibility and distributed nature of Bayesian networks, and graphical models in general, make them one of many useful tools for machine learning. In this project explored ways to visualize these networks, and introduced a number of new visualization techniques. First, viewing the structure of a network is but half the coin. We complete the other half by placing posterior distributions directly in the network as embedded pie charts. Second, direct comparisons are incredibly useful tools, yet past visualizations have struggled with this. We propose inference diffs as a method of meaningful direct comparisons, with concentric pie and ring charts for visualization. Finally, navigating efficiently in large Bayesian networks is generally a challenge. We introduce relevance filtering, with KL divergence as a mathematical basis, as a tool to guide the user to variables of interest in the model. Appendix A: Specifying Evidence In implementing B-Vis we sought a convenient interaction model for allowing the user to add or remove evidence. Further, we wanted the interaction to exhibit cohesiveness with the existing design language. The practical challenges are in presenting potentially many possible values efficiently (e.g. without resorting to scrolling or multi-level menus), and in providing a mechanism for choosing the target evidence set (i.e. E1 or E2 ). In keeping with the use of color and circular charts, we opted for a radial menu approach, seen in Figure 13. Each node in the network is directly clickable, opening a radial menu with color-coded choices available for each possible value in the event space for that variable. The user then simply drags a value from the radial menu onto either the inner circle or the inner ring, corresponding to evidence sets 1 and 2 respectively. To remove evidence, the user performs the action in reverse, dragging from the inner circle or ring to anywhere else outside of the node. As with before, the legend view provides a reference of the event space to color mapping for the user. We also fade the rest of the network to remove visual complexity while choosing evidence. Also note that because no keyboard input is necessary, this interaction model is also touch-screen friendly. Appendix B: Inference Algorithm Used For inference in the above networks we implemented approximate inference using Gibbs sampling, a Markov chain method with theoretical convergence to the true posterior distribution [16]. This implementation is available publicly under our F-AI project [18]. To reduce the effects of statistical dependence from particle to particle, we retain only one out of ever 4 adjacent particles when building new posterior distributions. To seed the Markov chain we begin with a forward sampling of the network, followed by a warmup period of 250 Gibbs samples. Because this computational approach is iterative, we are able to regularly update the embedded distributions in BVis, effectively creating a real-time animation of the convergence toward the stationary distribution. We update the structural view in B-Vis approximately once every Draft (v5) 12 2013 December 9 Figure 13: An example of the evidence menu. This variable's event space is of size six, with corresponding color-coded values available for drag-drop into evidence sets 1 or 2. 3,000 variable-iterations, or every 60 iterations for a 50 variable network. Appendix C: Learning Algorithm Used To create the Bayesian networks seen, we wrote our own implementation of general structure learning and CPT learning. Our algorithm is based almost entirely on the ideas presented in section 18.4 of Koller and Friedman [16], and amounts to an iterative search over the space of possible network structures. Each possible structure has an associate score, and the goal is to find a structure of maximal score. We use the Bayesian information criterion (BIC) score for this purpose. We use a uniform Dirichlet prior to effectively adjust the sufficient statistics of the training set, which combined with the BIC score acts to control the level of complexity in the resulting network structure. The search algorithm is initialized with a fully disconnected network, and at each iteration chooses the best edge operation among a candidate of operations. Each candidate operation is either an edge addition, edge deletion, or edge reversal, so long as the operation will not violate acyclicity. We compute the change to the total score of the network for each candidate action, and for that iteration of search choose the action with largest improvement to the total network score. If no action is found that increases the total score, the search is halted and the most recent structure is returned. Because each edge operation affects at most two local family scores, most family scores from iteration to iteration do not change. As further suggested in Koller and Friedman [16], we exploit this fact to cache previously computed family scores, and invalidate only when a chosen edge operation affects the associated variable of a cached family score. This makes the algorithm a dynamic programming algorithm, and significantly improves the computational demand. Further, we also cache various sufficient statistics values associated with the training set, also speeding up the overall process. Appendix D: Software Design An important philosophy in the application design was that anything that can be visualized should be visualized. The software design of B-Vis can be divided into three main modules: the statistical learning & inference, the application data model, and the graphics presentation. Learning and inference is implemented in F# (a derivative of OCaml) on the Microsoft .NET Framework v4.5. Variables, event spaces, observations, distributions, and Bayesian networks are all represented through objectoriented types, while algorithms are generally implemented as pure functions. An important realization partway through the development process was that complexity was significantly reduced in adopting an immutable design approach for each object type. The final implementation of most objects are in fact immutable, such that most methods that would otherwise mutate an object instead return a new instance of a derivative object. Anecdotally, when the probability distribution type was converted to be immutable, a significant speedup in structure learning occurred, presumably due to a more hardware cache-friendly memory access pattern. All learning and inference code is available publicly on GitHub as project F-AI [18]. The application data model, written in C#, was an important separate layer in the development of B-Vis. The data model maintains a source of truth for the application, and manages a number of background threads for simultaneous user-input and background processing. At any given moment up to four threads are active, for learning, inference, layout, and user-input & rendering. In a model-view-controller paradigm, our data model acts as both a model and controller, translating user actions into messages for the learning, inference, and layout threads. This approach was advantageous in that it separated user-interface and rendering concerns from threading and computational concerns. Finally for user-input and presentation we used the vector drawing features of Microsoft WPF v4.5. We implemented a number of reusable visual controls, for individual responsibilities such as rendering pie charts, ring charts, for rendering vertices and edges, and for routing raw user-input events to the application data model. Acknowledgments I'd like to acknowledge the CSE department at UC San Draft (v5) 13 2013 December 9 Diego for their thoughtful curriculum design and faculty. I'd like to thank Prof. Charles Elkan for his instruction and guidance, both in the subjects of machine learning and in data graphics. References [1] M. Lesk, How Much Information Is There In the World?, 1997 http://courses.cs.washington.edu/courses/cse590s/03au /lesk.pdf [2] Twitter, Inc.. U.S. Securities and Exchange Commission Form S-1. . 2013 http://www.sec.gov/Archives/edgar/data/1418091/0001 19312513390321/d564001ds1.htm [3] Editorial Staff. Data, data everywhere. The Economist. 2010 http://www.economist.com/node/15557443 [4] E. R. Tufte. The Visual Display of Quantitative Information. Graphics Press LLC. 2001 [5] J. Pearl, Bayesian Networks, 2000 [6] P. K. Sundararajan; O. J. Mengshoel; T. Selker, Multifocus and Multi-window Techniques for Interactive Network Exploration, 2013 [7] J. Pearl. Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan Kaufmann. 1988 [8] S. E. Schaeffer. Graph clustering. Computer Science Review 1-1. 2007 [9] J.-D. Zapata-Rivera; E. Neufeld; J. E. Greer. Visualization of Bayesian Belief Networks. Proceedings of IEEE Visualization’99. 1999 [10] C.-H. Chiang; P. Shaughnessy; G. Livingston; G. Grinstein. Visualizing Graphical Probabilistic Models. Technical Report 2005-017, UML CS. 2005 [11] J. R. Koiter. Visualizing Inference in Bayesian Networks. PhD diss., University of Pittsburgh. 2006 [12] M. Cossalter; O Mengshoel; T. Selker. Visualizing and Understanding Large-Scale Bayesian Networks. The AAAI-11 Workshop on Scalable Integration of Analytics and Visualization. 2011 [13] L. Williams; R. St. Amant. A Visualization Technique for Bayesian Modeling. Proc. of IUI. Vol. 6.. 2006 [14] Netica. http://www.norsys.com/netica.html. Accessed 2013 [15] BayesiaLab. http://www.bayesia.com/. Accessed 2013 [16] D. Koller, N. Friedman. Probabilistic Graphical Model: Principles and Techniques. Massachusetts Institute of Technology. 2009 [17] S. Kullback; R. A. Leibler. On Information and Sufficiency. The Annals of Mathematical Statistics 22.1 . 1951 [18] F-AI. https://github.com/duckmaestro/F-AI. Accessed 2013 [19] Graph#. http://graphsharp.codeplex.com/. Accessed 2013 [20] K. Sugiyama. Graph Drawing and Applications for Software and Knowledge Engineers. World Scientific Pub Co Inc. 2002 [21] A. Krause, C. E. Guestrin. Near-optimal Nonmyopic Value of Information in Graphical Models. Twenty-First Conference on Uncertainty in Artificial Intelligence. 2012 [22] D. Shahaf; A. Chechetka; C. Guestrin. Learning Thin Junction Trees via Graph Cuts. International Conference on Artificial Intelligence and Statistics. 2009 [23] C. Meek, B. Thiesson, D. Heckerman. The Learning- Curve Sampling Method Applied to Model-Based Clustering. The Journal of Machine Learning Research. 2002 [24] K. Bache, M. Lichman. UCI Machine Learning Repository. University of California. 2013 http://archive.ics.uci.edu/ml [25] U.S. Dept. of Commerce, Bureau of the Census, and Inter-university Consortium for Political and Social Research. Census of Population and Housing, 1990.. 1995 http://econ.ucdenver.edu/public/census90/documentati on/1990Codebook.htm [26] T. Dwyer, K. Marriot, M. Wybrow. Topology preserving constrained graph layout. Springer Berlin Heidelberg. 2009 Draft (v5) 14 2013 December 9

Source Code

The source code for the above project is available on GitHub: F-AI.