(PDF) Visualising high-dimensional state spaces with "Tuple Plots

Visualising high-dimensional state spaces with “Tuple Plots” Susan Stepney arXiv:1905.08729v1 [physics.data-an] 12 May 2019 University of York, UK 12 May 2019 Abstract Complex systems are described with high-dimensional data that is hard to visualise. Inselberg’s parallel coordinates are one representation technique for visualising high-dimensional data. Here we generalise Inselberg’s approach, and use it for visualising trajectories through high dimensional state spaces. We introduce two geometric projections of parallel coordinate representations – ‘plan tuple plots’ and ‘side tuple plots’ – and demonstrate a link between state space and ordinary space representations. We provide examples from many domains to illustrate use of the approach, including Cellular Automata, Random Boolean Networks, coupled logistic maps, reservoir computing, search algorithms, Turing Machines, and flocking. Contents 1 Introduction 1 2 Inselberg’s Parallel coordinate plots 2.1 Introduction . . . . . . . . . . . . . . . . . . . 2.1.1 Notation . . . . . . . . . . . . . . . . . 2.1.2 Definition . . . . . . . . . . . . . . . . 2.1.3 Visualising high dimensional geometry 2.1.4 Visualising data . . . . . . . . . . . . 2.2 Polar parallel coordinate plots . . . . . . . . . 2.3 Generalisation . . . . . . . . . . . . . . . . . . 2 2 2 3 3 3 5 5 3 Plan Tuple Plots 3.1 Looking down . . . . . . . . . . . . . 3.1.1 Motivation . . . . . . . . . . 3.1.2 Definition of plan tuple plot . 3.1.3 Ensembles and trajectories . 3.1.4 Vectors . . . . . . . . . . . . 3.2 No information loss . . . . . . . . . . 3.3 Examples . . . . . . . . . . . . . . . 3.3.1 Hypersphere surface . . . . . 3.3.2 Elementary cellular automata 3.3.3 Random boolean networks . . 3.3.4 Coupled logistic maps . . . . 3.3.5 Reservoir computer dynamics 3.3.6 Search algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 7 7 7 7 8 9 9 9 9 11 14 18 19 20 ii Axis ordering . . . . . . . . . . . . . . . . . . 20 4 Side Tuple Plots 4.1 Looking sideways . . . . . . . . . . . 4.1.1 Motivation . . . . . . . . . . 4.1.2 Definition of side tuple plot . 4.1.3 Ensembles and trajectories . 4.2 Information loss . . . . . . . . . . . . 4.3 Examples . . . . . . . . . . . . . . . 4.3.1 Hypersphere surface . . . . . 4.3.2 Elementary cellular automata 4.3.3 Coupled logistic maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 25 25 25 25 27 27 27 27 27 5 Hybrid Tuple Plots 5.1 Motivation . . . . . . . . . . . 5.2 Definition of hybrid tuple plots 5.3 Examples . . . . . . . . . . . . 5.3.1 Turing machines . . . . 5.3.2 Flocking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 32 32 32 32 32 . . . . . . . . . . . . . . . 6 Further work 36 7 Summary and Conclusions 37 A Bibliography 38 1. Introduction Complex systems can have complex and high dimensional state spaces. As we try to understand such systems, it is valuable to be able to visualise their state spaces. But high-dimensional spaces are hard to visualise using conventional orthogonal coordinate systems. Inselberg [5, 6] introduces parallel coordinates as a technique for visualising high dimensional spaces. Parallel coordinates have been exploited in two main application areas: geometry in higher dimensions (ℜN ) [5, 6]; visualising and exploring large data sets (thousands, or millions, of data points) in high dimensional (N of a few tens) spaces [10]. Here, we generalise the technique to visualise both populations of multiple data points, and the trajectory of a single high dimensional point, in a potentially high dimensional (N of 100s or more) state space. The structure of this report is as follows. §2 describes Inselberg’s parallel coordinates, and some existing generalisations. §3 introduces plan tuple coordinates, and illustrates them in the context of cellular automata, random boolean networks, coupled logistic maps, reservoir computing, and population-based search. §4 introduces side tuple coordinates, and illustrates them in the context of coupled logistic maps. §5 discusses hybrid tuple coordinates, and illustrates them in the context of Turing machines, and flocking visualisations. §6 discusses further generalisations that could be developed. 1 2. Inselberg’s Parallel coordinate plots 2.1 Introduction Conventionally, N D coordinate systems are drawn with N orthogonal axes, with the obvious difficulties of visualisation when N > 3, or even N = 3 on paper; each datum is represented as a single point, with its coordinates given by the projections onto the various axes. In 1985 Inselberg [5] introduced parallel coordinates. In parallel coordinates, the N axes are drawn in 2D space as a set of N equally spaced parallel lines (usually arranged vertically like fence posts or a series of y axes arranged along a single x axis, or occasionally horizontally like ladder rungs or a series of x axes up a single y axis); each datum is represented as a polyline joining the relevant coordinate value on each axis. Figure 2.1 demonstrates the approach. There the z Figure 2.2: Plotting a 14D point p14 in parallel coordinates. 3D point p3 is shown in both orthogonal and parallel coordinates. In orthogonal coordinates the point p ∈ ℜ3 is represented by the black disc, with dashed construction lines added for clarity. In parallel coordinates the point p ∈ ℜ × ℜ × ℜ is represented by the polyline passing through the three coordinate values. Unlike the orthogonal form, the parallel coordinate form can be readily extended to higher dimensions, ℜN , N > 3 (see figure 2.2). z 2.1.1 Notation Here and later we use the following notation to define the various plot types: y y x 1. the real interval [a, b] = {x ∈ ℜ | a ≤ x ≤ b} 2. the integer interval a..b = {k ∈ Z | a ≤ k ≤ b} 3. a data type V : the set of values that the various components of the point to be plotted can take; wlg we assume V ⊆ ℜ, if not, assume an injective function scale : V → ℜ is used to make the data values numerical 4. an N D point to be plotted: p = N (p1 , p2 , . . . , pN ) = (pn )N ∈ V n=1 5. a set of M such N -D points to be plotted: M N { pm }M m=1 = { pmn }m=1; n=1 6. a 2D position in the plotting plane: x = (x, y) ∈ ℜ2 7. a set of M such 2D positions in the plotting M plane: { xm }M m=1 = { (xm , ym ) }m=1 8. a set of symbols S used to plot points in the plotting plane x (a) (b) z y x (c) x y z (d) Figure 2.1: Plotting a 3D point p3 : (a) in orthogonal coordinates, showing guide lines; (b) p3 also projected onto axes, joined with a polyline; (c) removing the unprojected p3 and guide lines; (d) “flattening” into parallel coordinates. 2 2.1. Introduction 2.1.2 3 Definition Given this notation, we can define the standard parallel coordinates plot as: 2 Definition: Parallel coordinates plot 3 Given N 1. an N D point p = (pn )N n=1 ∈ V 2. a set of M such N -D points: { pm }M m=1 4 A parallel coordinates plot displays the point p in the rectangular-coordinate plane as the set of points {xn }N n=1 = together with a polyline joining the xn points. See figure 2.2. A parallel coordinates plot displays the set of M points { pm }M m=1 as a collection of M individual point p plots overlayed in the same rectangular-coordinate plane. See figure 2.3. 2.1.3 5 N { (n, pn ) }n=1 Visualising high dimensional geometry 6 7 Figure 2.3: 100 random points on the surface of an nD hypersphere, for n = 2–7. Inselberg’s original emphasis was on geometrical applications in high dimensions (plotting lines, surfaces, hyperspheres, etc, see figures 2.3, 2.4), so the This data mining use is often interactive, highlightparallel axes are necessarily equally spaced, in order ing subsets of the plot, to help clarify and explore to maintain the relevant geometrical properties. structure in the large number of overlapping data lines. 2.1.4 Visualising data Parallel coordinates are also used for visualising large data sets. Many data points correspond to many lines in the parallel system (see figure 2.5). Such plots are used in data mining, where the coordinates can be heterogeneous. This leads to techniques for scaling, reversing, and ordering the coordinates to expose patterns and clusters in the data. (See figure 2.6 for the effect of reordering the iris data axes. Reordering is also used to expose structure in RBNs, §3.3.3.) Smoothing the polylines to curves is also used to highlight clustering structure (rather than geometrical structures). There are uses other than visualisation. For example, Ye and Lin [24] use parallel coordinates to optimise a simulated annealing algorithm in N D. They express the N D search point in parallel coordinate space, and then approximate its polyline by an M D polynomial (where M < N ), thus reducing the dimensionality of the search space. Another example of use is illustrating the algorithm for generating a permutation from a vector of real numbers [9]: the desired permutation is that used to sort the vector into order (figure 2.7). 4 Chapter 2. Inselberg’s Parallel coordinate plots 2 0 1 2 3 0 1 3 2 0 2 1 3 0 2 3 1 0 3 1 2 0 3 2 1 1 0 2 3 1 0 3 2 1 2 0 3 1 2 3 0 1 3 0 2 1 3 2 0 2 0 1 3 2 0 3 1 2 1 0 3 2 1 3 0 2 3 0 1 2 3 1 0 3 0 1 2 3 0 2 1 3 1 0 2 3 1 2 0 3 2 0 1 3 2 1 0 3 4 5 6 7 Figure 2.4: 100 random points on the surface of an nD hypersphere, for n = 2–7. Here, the coordinate values of each point are sorted in descending order (by symmetry, this is also a point on the surface of the hypersphere); It is clear that for points where one dimension has a large value, the other dimensions have small values. Figure 2.6: A parallel coordinates plot, of the iris data, all 24 permutations of the xi . (a) (a) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 16 14 15 9 4 6 11 3 0 12 2 5 1 18 10 17 19 7 13 8 (b) (b) sepal len sepal w petal len petal w Figure 2.5: A parallel coordinates plot of the 4D iris data set, eliding the vertical axes: (a) plot of all 150 data points; (b) colour coded plot by species. Figure 2.7: A real vector representing a permutation; N = 20. (a) the unsorted real vector; (b) the vector plotted with components in ascending order; the corresponding order of the axes gives the permutation represented by the real vector. 2.2. Polar parallel coordinate plots 2.2 5 Polar parallel coordinate plots Parallel coordinates lay out N coordinate axes in parallel on a plane. There are analogous ideas that use different layouts, such as using polar coordinates [20, §9.4.2.3] to lay out the axes in a radial pattern. Such examples are called star plots, or spider plots. See figure 2.8.1 Wilkinson calls these multi-dimensional plots “polar parallel coordinates” plots [20, §9.4.2.3], because in his graphics grammar, they are produced by passing a parallel coordinate plot through a polar transform. Definition: Polar parallel coordinates plot Figure 2.8: Plotting a 14D point p14 in radial coordinates. 2.3 Generalisation Parallel coordinates are one possible way of visualising the large dimensional state spaces of dyGiven namical systems, a formalism suitable for several N 1. an N D point p = (pn )N ∈ V unconventional computational models [17]. n=1 The rest of this report modifies parallel coordiA polar parallel coordinates plot displays nates to visualise the state space trajectories of high p in the (r, θ) polar-coordinate plane as the dimensional dynamical systems. A trajectory is a set of points time series of state space points. This series could N be shown on a single parallel coordinates plot as { xn }N n=1 = { (pn , 2πn/N ) }n=1 a collection of lines, but this loses the time ordertogether with a closed polyline joining the xn ing. However, many parallel coordinate plots can points. (See figure 2.8.) be reduced to a 1D view without loss of information, and then the time series can be visualised by plotting the time series as a sequence of 1D states. This approach has the advantage of not giving There are two conceptual steps in this visualisaundue prominence to the first and last coordinates, tion process: and makes ‘shapes’ that are readily comparable. It • a high dimensional space can be represented has the disadvantage of emphasising large values using coordinate axes that are “flattened”, and more than small ones, due to area effects. laid out in parallel, rather than arranged orthogonally (Inselberg’s parallel coordinates) 1 Note that these are different from superficially similar radar plots (different authors use different names for these plots; the names used here follow [20, §9.4.2.3, §9.1.6.4]). A radar plot is a 2D plot, in polar coordinates, where the angular dimension represents some continuous or discrete angular variable, such as time of day, month of year, or compass direction, and a single 2D datum is represented as a single point on the 2D plot. In a spider plot, in contrast, the n radial lines represent the different axes of the different dimensions, and a single nD datum is represented by n points on the 2D plot, one per axis, joined by a closed polyline. • the coordinate axes do not need to be drawn in the plane of the paper; they can be drawn in other projections (see figure 2.9) These plots exploit the trivial isomorphism between X N , an N dimensional point, and X × X . . . X (N times), of N 1D points representing the tuple of the point’s N coordinates. Plots exploiting the latter structure are here referred to as 6 Chapter 2. Inselberg’s Parallel coordinate plots V V D D T T (a) 3d view (b) plan projection V V D T (c) side projection T D (d) front projection / elevation Figure 2.9: A parallel coordinates plot of multiple N D points, each point in a separate time ‘plane’ T . Each point has its own marker shape, to help distinguish it here; marker colour represents the value, the height on the V axis. (a) the full 3d plot; (b) the ‘plan projection’, top view; (c) the ‘side projection’ view; (d) the ‘front projection’ (or elevation) view, recovering the standard parallel coordinates plot of multiple points. “tuple plots”, a term that covers all of parallel coordinates, polar parallel coordinates, and the plots developed here in the later chapters. The name is modified to reference the geometry used to draw the individual axes: plan tuple plots (§3) and side tuple plots (§4). 3. Plan Tuple Plots 3.1 3.1.1 Looking down Motivation Consider a system with N identical dimensions each with values drawn from an ordered set V . We could draw this using N parallel coordinates. Imagine these axes are lines sicking up from the ground, like fence posts; consider looking “down” on these coordinates from above (figures 2.9b, 3.1), so the line of each fence post is foreshortened into a point. The lower values are further away, so we might think that perspective would make the circles representing these points look smaller, with say size proportional to value v ∈ V (figure 3.1b). Alternatively, the further away values might appear to be “fainter”, shaded differently, with grey level proportional to value v (figure 3.1c). Or we could simply “paint” a suitable range of colours on the axes at different levels (figure 3.1d). We can reorder the axes to help expose properties of the data. The permutation example from 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 16 14 15 9 4 6 11 3 0 12 2 5 1 18 10 17 19 7 13 8 Figure 3.2: The permutation example from figure 2.7, drawn as plan tuple plot. The upper view has the axes in their original order. The lower view has the axes permuted to show the data in ascending order. figure 2.7 can be redrawn in plan view, as figure 3.2. See also §3.4. 3.1.2 Definition of plan tuple plot We use this “looking down” idea to define plan tuple plots. We plot one 2D point for each component of the tuple; its position represents the axis index, and its symbol (size, shape, colour) represents its value. Definition: plan tuple plot Given 1. an N D state space V N N 2. an N D point p = (pn )N n=1 ∈ V 3. a plotting function sym : V → S 4. a position function ̟ : 1..N → ℜ2 that maps the component indexes to positions in the plotting plane (a) (b) A plan tuple plot displays the point p in the plotting plane as the set of points (c) N { xn }N n=1 = { ̟(n) }n=1 (d) Figure 3.1: 20D real-valued random data (so N = 20, V = ℜ): (a) parallel coordinates plot; (b) the ‘plan’ view, from projecting the values onto the horizontal axis: plan tuple plot using data points with sizes proportional to their value v; (c) plan tuple plot, using grey levels instead of sizes; (d) plan tuple plot, using a diverging colour range, with low values being red, moving through yellow, to high values being blue, suitable for ranges with positive and negative values. where each xn point is plotted using the symbol sym(pn ). See figure 3.3. In the basic case, ̟(n) = (n, 1): the points are plotted evenly along the x axis, in axis order. The axes may be permuted using ̟, so that the points are plotted evenly along the x axis, in permuted axis order. Examples using a permuted or7 8 Chapter 3. Plan Tuple Plots size/colour = p1 position n = 1 pi ... i pj ... j pN ... N Figure 3.3: Illustration of definition of plan tuple plot of the N D point p = (p1 , . . . , pi , . . . , pj , . . . , pN ) ∈ V N . Here the plotting function sym maps each value v ∈ V to a symbol s ∈ S where the size of s is proportional to v. Each component pn is plotted on the horizontal axis line at position (n, 1) using symbol sym(pn ). The axis line itself may be elided. der include: the sorted display of figure 3.2; Random Boolean Networks (§3.3.3). In the general case, ̟ can be a function that takes axis n to some position in the (x, y) plotting plane: the points are plotted at these positions. Examples using a general position function include: Boolean hypercubes plotted on Hilbert curves [19]; Game of Life CA (§3.3.2). 3.1.3 Ensembles and trajectories With parallel coordinates, multiple points can be plotted as multiple overlapping polylines. With plan tuple plots, such overlapping would obscure the data. We might wish to display an ensemble of points, representing some population in N D space, or a time series of points, representing some trajectory through N D space. If we animated a plan tuple plot of a sequences of states, the N symbols representing the N D point would stay fixed in position (on their axis position), and change in size or colour (as their value changes). We can turn the animation into a static display if we use a 1D plan tuple plot for a single point, and use the second dimension of the plot to display the different points (see figure 2.9b). Assume we have some indexed set of N D points that we wish to plot: p1 , p2 , . . . , pM . We may wish to permute the points’ indexes to expose structure, unless the indexes represent some intrinsic order, such as time. We can then plot pj along the x axis that intercepts the y axis at j. t Figure 3.4: A trajectory, or time series, as a plan tuple plot. Definition: ensemble plan tuple plot Given 1. an N D state space V N 2. an indexed set of M N D points: M N { pm }M m=1 = { pmn }m=1; n=1 where each N N -D point p = (pn )n=1 ∈ V N 3. a plotting function, sym : V → S 4. a position function of the axes’ indexes, ̟n : 1..N → ℜ 5. a position function of the points’ indexes, ̟m : 1..M → ℜ An ensemble plan tuple plot displays each of these pm in the plotting plane as a plan tuple plot, with N M N {xmn }M m=1; n=1 = {(̟n (n), ̟m (m))}m=1; n=1 where each xmn point is plotted using the symbol sym(pmn ). In the basic case, ̟n (n) = n, ̟m (m) = m: each point is plotted evenly along the x axis, in axis order, at a height m up the y axis. If M represents time, then ̟m (m) = −m is conventionally used, to maintain the temporal order, and to have time increase down the page (figure 3.4). This trajectory visualisation does not necessarily make cycles in the trajectory immediately visible, but they can be inferred as repeated patterns of states. 3.2. No information loss 9 Example: hypersphere plan tuple plot Figure 3.5: An array of unit 2D vectors: the initial state is a uniform rotation; each timestep each node has a small random rotation applied. 3.1.4 Vectors If the values V are vector, rather than scalar, we can adapt the symbol used with the plan plot. Each 2D vector value (direction and size) can be plotted as a small arrow. See for example, figure 3.5. 3.2 No information loss An important feature of the plan tuple plot is that it loses no information, other than possible loss of resolution between the symbols. Where the different values can be suitably distinguished (drawn from a small finite set, say), such as for the CA and RBN examples shown above, there is no loss of resolution. Figure 3.17 shows an example of a plan tuple plot used with continuous-valued data, V = [0, 1]. Here the grey scales encode the real values with finite resolution; compare orthogonal and standard parallel coordinates, which use position to encode the real values also with finite resolution. 3.3 3.3.1 Examples Hypersphere surface Given an N D hypersphere of radius r, a point p = (p1 , p2 , . . . , pN ) on its surface obeys p21 + p22 + . . . p2N = r2 Given 1. an N D state space V N = [0, r]N 2. an indexed set of M state space points {pm } sampled at random from the positive hyper-octant of the surface of a hypersphere 3. a plotting function sym = cubehelix that maps a component value p ∈ V to a colour scale with extremes 0 7→ white, r 7→ black 4. each of the M point has its axes individually permuted so that the values are in descending order 5. an axis position function ̟n = Id 6. an index position function ̟m on the indexes m ∈ 1..M such that points pm are sorted in ascending order of their maximum component values max({pmn }N n=1 ) An ensemble plan tuple plot displays each of these pm in the plotting plane as a plan tuple plot, with N M N {xmn }M m=1; n=1 = {(̟m (m), n)}m=1; n=1 We additionally ensure that each point p has pi ≥ pj if i > j, by sorting the point’s components into descending order. By symmetry, this is also a point on the sphere, and this sorting helps to expose the structure. The use of ̟m means that points closer to an orthogonal axis, which have one large component value, and the rest small, occur towards the top of the plot; points maximally distant from the orthogonal axes, which have all component values approximately equal, occur lower in the plot. The resulting ensemble plan tuple plot for M = 100, N = 2..10 is shown in figure 3.6. 10 Chapter 3. Plan Tuple Plots 2 3 4 5 6 7 8 9 10 bar Figure 3.6: Ensemble plan tuple plot of 100 points on the surface of the positive hyper-octant of an N -dimensional hypersphere, N = 2–10. The coordinate values of each point are sorted in descending order (by symmetry, this is also a point on the surface of the hypersphere). The ensemble of points are sorted in order of the maximum coordinate value. From this is is clear that when there is one large value (see the points towards the top of the plot), visible as a single dark square, then all the other values are small, visible as very light coloured squares, whereas when there is no very large value (see the points in the bottom part of the plot), there can be several medium sized values, with intermediate colour squares. 3.3. Examples 3.3.2 11 Elementary cellular automata Consider an elementary cellular automaton (ECA) [21] with N nodes. Each node has 3 inputs, from its left and right neighbour, and from itself. The specific ECA is defined by the choice of a boolean function of three inputs. Each node has a binary-valued state. At each timestep, the state of each node is updated in parallel, by applying the boolean function to its inputs. An ECA with N nodes laid out in 1D line in (physical) space1 has an (abstract) state space of BN . The parallel coordinate view has one axis line per node, each with two possible values, 0 or 1. Example: 1D ECA plan tuple plot Consider 1. an N D state space V N = BN 2. an indexed set of T state space points {pt } forming a time series of the time evolution of the CA 3. a plotting function sym = {0 7→ white, 1 7→ black} 4. the identity axis position function on axes n ∈ 1..N 5. the reverse index position function on t ∈ 1..T , so that time runs down the plot. The resulting trajectory plan tuple plot for Elementary CA rule 110, with N = 400 cells, T = 200 timesteps, and a random (50% 0s, 50% 1s) initial condition p1 is shown in figure 3.7. This is identical to the standard display of a 1D ECA. Hence the standard representation is in fact a visualisation of the state space in a plan tuple plot, and the usual time series representation, of consecutive lines of state, is a picture of the trajectory through this state space. 1 The “dimensionality” of the layout in physical space (a 1D line of nodes) is unrelated to the dimensionality of the state space (of N D, because there are N nodes); if the same N nodes were instead laid out in a 2D grid, or even a 27D grid, say, it would not affect the dimensionality of the state space. Instead, this “1D” refers to the topology of the connections between the nodes, and hence the potential information flow between the nodes. Figure 3.7: Plan tuple plot of the time evolution of Elementary CA rule 110, with N = 400 cells, T = 200 timesteps, and a random (50% 0s, 50% 1s) initial condition. Similarly, one could consider the standard display of a 2D CA, such as Conway’s Game of Life [4], as a plan tuple plot of the state space formed by projecting down on the parallel coordinates arranged in a 2D grid, one coordinate line rising from the site of each cell. A time series plot here is harder, as it would be 3D [23, fig.4.11]. Animation is customarily used to visualise trajectories. We can use a plan tuple plot to visualise other aspects of the state, such as filtering the plot to expose further structure [23]. For example, figure 3.8 plots the lookup table entry used to produce the state value, in the following way. Example: 1D ECA lookup plan tuple plot Consider 1. an N D state space V N = (0..7)N 2. an indexed set of T points (for calculation purposes) {pt }Tt=0 forming a time series of the time evolution of the CA, where pt ∈ BN ; and a further indexed set of T − 1 state space points {st }Tt=1 , where snt = 4p(n−1)(t−1) + 2p(n)(t−1) + p(n+1)(t−1) (index arithmetic performed modulo N ) 3. a plotting function sym that maps 0..7 to a set of colours 4. the identity axis position function on axes n ∈ 1..N 12 Chapter 3. Plan Tuple Plots 30 41 54 Figure 3.8: Plan tuple plot of the time evolution of Elementary CA rule 110 table accesses, for the ECA in figure 3.7. 5. the reverse index position function on t ∈ 1..T , so that time runs down the plot. This plot highlights structure in the generation process [22, fig.3]. 60 62 90 Figure 3.9 shows both state, and lookup entry, plots for several elementary CAs. We can use this style of visualisation to get an intuition for various behaviours of CAs. For example, some CA rules demonstrate sensitive dependence on initial conditions: the effect of a minimal (one cell state) change to the initial condition propagates across the system, eventually resulting in a completely different dynamics. See figure 3.10. For example, an input might “clamp” part of a CA into particular substate (by fixing the value of some bits for many timesteps). This not only perturbs the system at the point where the bits are clamped, but can also change the global dynamics. Clamping some bits in a CA can result in “walls” across which information cannot flow, isolating regions, and hence changing the dynamical structure of the system. See figure 3.11. 120 184 (a) (b) (c) (d) (e) Figure 3.9: Plan tuple plot of Elementary CA rules with N = 100 cells, T = 40 timesteps, and a random (50% 0s, 50% 1s) initial condition: (a) ECA rule number; (b) time evolution of the state; (c) time evolution of the lookup table access; (d) colour bar indicating the colour used to display each lookup table entry (000 at the bottom, 111 at the top); (e) bar indicating whether each lookup entry results in a 0 (white) or 1 (black) as the next state. 3.3. Examples 13 (a) ECA rule 45 (b) ECA rule 110 Figure 3.10: Sensitive dependence on initial conditions. Each plot overlays the evolutions of two initial states differing in only one bit: the growing central dark region is different; the outer regions are the same. N = 971, random initial state s0 , over 646 timesteps. (a) ECA rule 25 (b) ECA rule 110 Figure 3.11: Dependence of CA dynamics on a “clamped” bit. The upper plot shows ordinary periodic boundary conditions; the lower plot shows the same initial conditions, but with the central bit “clamped” to 0. 14 Chapter 3. Plan Tuple Plots 3.3.3 Random boolean networks A random boolean network (RBN) [3, 8] comprises N nodes. Each node has K inputs assigned randomly from K of the N nodes (an input may be from the node itself); the wiring pattern is fixed throughout the lifetime of the network. Each node has its own randomly chosen a boolean function of its K inputs. Each node has a binary valued state. At each timestep, the state of each node is updated in parallel, by applying the node’s boolean function to its inputs. Example: plot Figure 3.12: Plan tuple plot of the time evolution of a K = 2 RBN with N = 200 nodes, T = 80 timesteps: nodes in arbitrary order. unsorted RBN plan tuple Consider 1. an N -D state space V N = BN 2. an indexed set of T state space points {pt } forming a time series of the time evolution of the RBN 3. a plotting function sym = {0 7→ white, 1 7→ black} 4. the identity position function on the axes’ indexes n ∈ 1..N 5. the reverse position function on the points’ indexes t ∈ 1..T , so that time runs down the plot page. The resulting trajectory plan tuple plot for a K = 2 RBN with N = 200 nodes, T = 80 timesteps, and an all-zeros initial condition p1 is shown in figure 3.12. Figure 3.13: Plan tuple plot of the time evolution of a K = 2 RBN with N = 200 nodes, T = 80 timesteps: nodes permuted to expose the ‘frozen core’. 3. a plotting function sym = {0 7→ white, 1 7→ black} 4. a position function that permutes the axes’ indexes n ∈ 1..N so that nodes that have a value of zero for more timesteps have a lower index 5. the reverse position function on the points’ indexes t ∈ 1..T , so that time runs down the plot. The resulting trajectory plan tuple plot is shown in figure 3.13. For CAs, the order of the parallel coordinates respects the topology of the space. With RBNs, there is no obvious ordering of the coordinates (nodes). We can use this visualisation to get an intuition We can impose an ordering that highlights interesting structure, such as exposing the “frozen core” of for the documented behaviours of RBNs: their variability, their frozen cores, their attractor structure, unchanging values [15, 16]. their dependence on K and canalised functions. See figures 3.14–3.16; see [16] for further examples, inExample: sorted RBN plan tuple plot cluding the visualisation of the effect of various netConsider work perturbations. 1. an N D state space V N = BN 2. an indexed set of T state space points {pt } forming a time series of the time evolution of the RBN 3.3. Examples 15 Figure 3.14: Visualisation of the time evolution of 12 typical K = 2 RBNs, with N = 100. Every 60 timesteps the nodes are reinitialised to a new random configuration, to explore other attractors. They exhibit ordered behaviour: short transients, and low period attractors. 16 Chapter 3. Plan Tuple Plots Figure 3.15: Visualisation of the time evolution of four typical K = 2 RBNs, with N = 400. Every 100 timesteps the nodes are reinitialised to a new random configuration, to explore other attractors. They exhibit ordered behaviour: short transients, and low period attractors. 3.3. Examples (a) 47 17 (b) 64 (c) 84 (d) 90 (e) 92 (f) 95 (g) 100 Figure 3.16: Visualisation of the time evolution of typical K = 3 RBNs, with N = 100, t = 80, initial condition all nodes “on”; columns have an increasing amount of canalisation, with the indicated number of canalised nodes. 18 Chapter 3. Plan Tuple Plots 3.3.4 Coupled logistic maps The logistic map xn+1 = λxn (1 − xn ) is a wellknown 1D discrete time dynamical system. N maps can be coupled together to form an N D system. For example, Kaneko [7] discusses coupled map lattices, and Sinha and Ditto [11, 12, 13] consider one-way threshold coupled lattices (TCL). Here we use the Sinha and Ditto example. Consider a set of N cells, each with a state x ∈ [0, 1]. At each timestep, each cell’s state is updated by applying the logistic map at its fully chaotic value: f (x) = 4x(1 − x). Next, any ‘excess’ value is transferred: the cells are considered in order 1..N ; if cell n has a value greater than the threshold parameter x∗ , its value is reduced to x∗ , and the excess δ = xn − x∗ is transferred to cell n + 1, increasing its value to xn+1 + δ. Any excess from the last cell xN is removed from the system. See algorithm 1. Algorithm 1 Threshold coupled lattice timestep. for each cell n do xn ← f (xn ) {logistic update} end for for n = 1 to N do {excess propagation} if xn > x∗ then δ ← xn − x∗ ; xn ← x∗ ; xn+1 ← xn+1 + δ end if end for Example: Threshold coupled lattice plan tuple plot Consider 1. an N D state space V N = [0, 1]N 2. an indexed set of T state space points {pt } forming a time series of the time evolution of the TCL 3. a plotting function grey that maps a component value p ∈ [0, 1] to a greyscale with extremes 0 7→ white, 1 7→ black 4. the identity position function on the axes’ indexes n ∈ 1..N 5. the reverse position function on the points’ indexes t ∈ 1..T , so that time runs down the plot. The resulting trajectory plan tuple plot is shown in figure 3.17. Figure 3.17: Plan tuple plots of the threshold coupled lattice, threshold x∗ = 0.971, number of cells N = 200, T = 100 timesteps: the x axis shows the individual cell; each cell’s value xn ∈ [0, 1] is indicated by its colour, as shown in the lower colour bar. Two different random initial conditions are shown. 3.3. Examples 3.3.5 19 Reservoir computer dynamics Reservoir computing [2, 18] is often used as a computational model for unconventional substrates [1]. It comprises an underlying dynamical system (discrete time, continuous space) usually described as a recurrent neural network, plus a training method. Here we look just at the internal dynamics, of a relatively simplified variant (various parameters set to convenient values). The equation used here is: pt+1 = tanh (ρpt .W + ut v) (3.1) where p is the system state vector (each component thought of as a node, or neuron, in the network); t is the timestep; ρ is the gain parameter; W is a random weight matrix connecting the neurons, with weights initially drawn from U [−1, 1], then the matrix normalised so that its largest singular value is 1; u is the input, or driving, signal; v is a random input weight vector, with weights drawn from U [−1, 1]. Example: Reservoir plan tuple plot Consider 1. an N D state space V N = [−1, 1]N 2. an indexed set of T state space points {pt } forming a time series of the time evolution of the reservoir 3. a plotting function that maps a component value p ∈ [−1, 1] to a colourscale with extremes −1 7→ orange, 1 7→ purple, passing through 0 7→ white 4. a position function on the axes’ indexes that plots mostly negative values nodes to the left, positive to the right 5. the reverse position function on the points’ indexes t ∈ 1..T , so that time runs down the plot. The resulting trajectory plan tuple plots are shown in figure 3.18. Figure 3.18: Plan tuple plots of a reservoir dynamics, N = 100 nodes, initial state x = 0; 100 timesteps, Each node’s value xn ∈ [−1, 1] is indicated by its colour, as shown in the lower colour bar (brown for −1, through white for 0, to purple for 1). Two different input functions are shown. In the top plot the input cycles through u = 1 for 20 timesteps followed by u = 0 for 20 timesteps. In the bottom plot it cycles through u = 1 for 20 timesteps, u = 0 for 10 timesteps, u = −1 for 20 timesteps, u = 0 for 10 timesteps. In the left plots ρ = 1 (fading memory region); the transitions between driven dynamics (|u| = 1) and decaying dynamics (u = 0) are clear. In the right plots ρ = 2 (chaotic region); the transitions between driven dynamics (|u| = 1) and chaotic free dynamics (u = 0) are clear. 20 Chapter 3. Plan Tuple Plots i i eral, we have: ẋ1 = f1 (x1 , x2 , . . . , xN ) (a) (b) j ẋ2 = f2 (x1 , x2 , . . . , xN ) j Figure 3.19: Cross mutation (reversing the central path segment: 2-opt). (a) original path . . . , i − 1, i, i + 1, . . . , j − 1, j, j + 1, . . .; (b) final path . . . , i − 1, j, j − 1, . . . , i + 1, i, j + 1, . . . i (a) i j (b) j Figure 3.20: Reroute mutation (a restricted form of 3-opt) (a) original path . . . , i − 1, i, i + 1, . . . , j − 1, j, j + 1, . . .; (b) final path . . . , i − 1, i + 1, . . . , j − 1, j, i, j + 1, . . . 3.3.6 Search algorithms ... ẋN = fN (x1 , x2 , . . . , xN ) This general case allows every ẋi to depend on all N of the xj . However, specific cases can have a more restricted dependence. Instead of considering one N D dynamical system, we can consider these as networks of N coupled 1D dynamical systems, with the network nodes corresponding to the variables xi , and edges providing the coupling information linking the nodes that appear in the corresponding fi . An example is the MSEIR model of infection2 , with equations: Ṁ = B − δM S − µM Ṡ = δM S − βSI − µS Here we show some examples of visualising the trajectory of a search algorithm. The task is to search for a permutation that finds the shortest route through several points: the Travelling Salesman Problem. The search uses two different permutation mutations, as shown in figures 3.19 and 3.20. Figures 3.21 and 3.22 illustrate the trajectories of two different forms of hill-climbing. Ė = βSI − (ǫ + µ)E I˙ = ǫE − (γ + µ)I Ṙ = γI − µR We draw a network with the variables as nodes, and an edge from variable X to variable Y if the equation for Ẏ contains X. We then lay out this network in a line in a way that minimises the length of the edges (since we are interested in edge length, not direction, we form an undirected graph; figure 3.23). This provides a natural order for the 3.4 Axis ordering axes in the tuple plot, as it best captures the flow We have seen one example of re-ordering the axes of information between the variables represented by to highlight the dynamical structure, in the RBN each axis. example, §3.3.3. Additionally, the ECA example, Consider the Turing Machine that is the cur§3.3.3, is naturally in the order that repects the rent best contender for the 6-state, 2-symbol Busy topology. But these are special cases. There is a Beaver3 . Considering just the states (ignoring symway to get a “good” (but not necessarily the best) bols and head movements), it has the following order automatically, by examining the structure of possible state transitions: A → B; A → E; B → the system. C; B → F ; C → D; C → B; D → E; D → C; E → Consider an N D dynamical system expressed as A; E → D; F → H; F → C. Drawing these nodes a set of first order ordinary differential equations 2 en.wikipedia.org/wiki/Epidemic model#The MSEIR (the same argument applies to systems defined with model 3 en.wikipedia.org/wiki/Busy beaver#Examples a set of discrete time difference equations). In gen- 3.4. Axis ordering (a) 21 132.49 132.49 132.49 103.28 102.36 108.23 (b) (c) Figure 3.21: 22 city TSP searched by hill climbing, 130 steps, in plan tuple plot. Black curve is optimal path; red curve is found path. (a) reroute mutations only; (b) 50/50 reroute and cross mutations; (c) cross mutations only 22 Chapter 3. Plan Tuple Plots (a) 89.64 90.72 87.17 79.80 80.07 80.73 (b) (c) Figure 3.22: 22 city TSP searched by hill climbing, 250 steps, in plan tuple plot, with 50/50 cross and reroute mutations, greedy initial condition. Black curve is optimal path; red curve is found path. Colour map chosen such that optimal path has uniform change in colour. Greedy initialisation starts at city: (a) 0; (b) 8; (c) 16. 3.4. Axis ordering M 23 S E I R Figure 3.23: MSEIR model in network form. A B C D E F H (a) (a) A E D C B F H (b) Figure 3.24: 6 state TM Busy Beaver contender: (a) alphabetical node order; (b) revised node order to minimise communication distance. (b) in alphabetical order results in the network shown in figure 3.24a. Rearranging to minimise information communication distance results in figure 3.24b, a candidate axis order (see §5.3.1). We can use a similar approach to order the nodes in an RBN. For example, figure 3.25 shows Random Boolean network plan plots with three different node orderings shown in figure 3.26. The order(c) ing by minimising the communication distance results in a better plot than random, but in the RBN Figure 3.25: RBN: (a) random; (b) revised node orcase there is a further improvement possible, based der to minimise communication distance; (c) sorted to on the frozen core. The minimal communication expose frozen core. distance ordering is a first choice, but the structure of the system may provide a better choice. 24 Chapter 3. Plan Tuple Plots 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 20 0 15 4 24 10 18 25 11 5 2 22 23 3 29 9 28 6 14 7 19 26 27 12 8 17 16 21 1 13 27 20 7 17 12 5 18 26 14 6 23 10 15 0 22 29 3 4 24 9 28 2 8 19 21 13 11 16 25 1 (a) (b) (c) Figure 3.26: RBN: (a) random; (b) revised node order to minimise communication distance; (c) sorted to expose frozen core. 4. Side Tuple Plots 4.1 4.1.1 Looking sideways maps values to a position in the plotting plane Motivation A symbol side tuple plot displays p on the Again consider a system with N identical dimenvertical y-axis line as the set of points sions each with values drawn from an ordered set N V , plotted using N parallel coordinates. Consider { xn }N n=1 = { (1, ̟v (pn )) }n=1 now looking “across” these coordinates, from the where each xn point is plotted using the symside elevation (figures 2.9c, 4.1). The various coorbol sym(n). dinate lines are overlaid, and seen as one. See figure 4.2a, where the symbol for each All the values are projected onto this resultdimension has a different size; alternatively, ing single merged coordinate line. The higherit might have a different colour, or shape, or numbered dimensions are further away, so we might combination of these. think that perspective would make the symbols representing these points look smaller (figure 4.1b). The position function ̟v allows values to be Alternatively, the further away dimensions might scaled before being plotted. appear to be “fainter” (figure 4.1c). Or we could simply “paint” a suitable colours on each axis (figDefinition: Density side tuple plot ure 4.1d). Note that values on nearer axes may Given occlude those on further axes. 1. an N D state space V N Once there are many dimensions, the side tuple N 2. an N D point p = (pn )N n=1 ∈ V plot is in danger of becoming cluttered with multi3. a number of bins B ple overlapping symbols. An alternative is a density 4. a binning function β : V → 1..B, that side tuple plot, where the symbol used represents a partitions V ; if V has an order ≤, then density histogram of the number of axes that have the partition respects the order a value in the given range (figure 4.1e). v1 ≤ v2 ⇒ β(v1 ) ≤ β(v2 ) 5. a density function ρ : 1..B → [0, 1] 4.1.2 Definition of side tuple plot ρ(b) = #{ pn | β(pn ) = b }N n=1 /N We use this “looking across” idea to define side 6. a plotting function sym : [0, 1] → S tuple plots. We plot one 2D point for each compoA density side tuple plot displays p on the nent of the tuple; its position represents its value, vertical y-axis line as the set of bins and its symbol (size, shape, colour) represents (a) the axis index or (b) the density of axis indexes B { xb }B b=1 = { (1, b) }b=1 falling within the spatial extent of the symbol. where each bin xb is plotted using the symbol sym(ρ(b)). (See figure 4.2b.) Definition: Symbol side tuple plot Given 1. an N D state space V N N 2. an N D point p = (pn )N n=1 ∈ V 3. a plotting function sym : 1..N → S 4. a position function ̟v : V → ℜ that 4.1.3 Ensembles and trajectories We might wish to display an ensemble of points, representing some population in N D space, or a time series of points, representing some trajectory 25 26 Chapter 4. Side Tuple Plots (a) (b) (c) (d) (e) Figure 4.1: 20D real-valued random data (so N = 7, V = ℜ): (a) parallel coordinates plot; (b) the ‘side’ view, from projecting the values onto a single vertical axis: side tuple plot using data points with sizes diminishing with higher dimension, and semi-transparent markers; (c) side tuple plot, using data points with grey levels diminishing with higher dimension; (d) side tuple plot, using data points with a colour range, useful if different dimensions have categorically different meanings; (e) side tuple plot, using a density histogram of the data points. pmax #pmax pn+1 #pn+1 pN N p1 1 pi i pn pj j pmin position size/colour (a) #pn #pmin position size/colour (b) Figure 4.2: Side tuple plot of the point p = (p1 , . . . , pi , . . . , pj , . . . , pN ) ∈ V N . (a) Symbol side tuple plot. There is a symbol representing each dimension n ∈ 1 . . . N . The line is an axis with positions corresponding to values pn ∈ V . (The vertical line itself may be elided.) Each pn is plotted on the line at a position representing the value of pn with a symbol representing the dimension n. Symbols for higher dimensions may be occluded by symbols for lower dimensions with the same value. (b) Density side tuple plot. The axis is divided into equal-sized bins, and the colour of each bin indicates the number of dimensions whose value falls in that bin. 4.2. Information loss through N D space. If we animated a side tuple plot of a sequences of states, the N symbols representing the N D point would stay fixed in size or colour (designating their axis position), and change in position (as their value changes). We can turn the animation into a static display if we use a 1D plan tuple plot for a single point, and use the second dimension of the plot to display the different points (see figure 2.9c). Definition: ensemble symbol side tuple plot Given 1. an N D state space V N 2. a set of M N D points to be plotted: M N { p m }M m=1 = { pmn }m=1; n=1 where each N N D point p = (pn )N n=1 ∈ V 3. a plotting function sym : 1..N → S 4. a position function ̟v : V → ℜ that maps values to a position in the plotting plane 5. a position function of the points’ indexes ̟m : 1..M → ℜ An ensemble symbol side tuple plot displays each of these pm in the plotting plane as a side tuple plot, with N {xmn }M m=1; n=1 = N {(̟m (m), ̟v (pmn ))}M m=1; n=1 where each pmn point is plotted using the symbol sym(pmn ). There is an analogous definition for an ensemble density side tuple plot. A trajectory through this state space can be visualised by showing consecutive states in consecutive columns as a time series (figure 4.3). This trajec- 27 tory visualisation does not necessarily make cycles in the trajectory immediately visible, but they can be inferred as repeated patterns of states. 4.2 Information loss Unlike the plan tuple plot, the side tuple plot can lose some information. For a given point, if different dimensions have the same value, the symbols will be overlayed, and the ‘higher’ numbered dimension data occluded; this can be mitigated to some degree by the use of transparent symbols. The density plot allows the values of all dimensions to be captured, but loses the information of which dimension is which. 4.3 4.3.1 Examples Hypersphere surface Figure 4.5 plots 100 points from the surface of a hypersphere in an ensemble side tuple plot. Contrast with the plan tuple plot of figure 3.6. 4.3.2 Elementary cellular automata See figure 4.4, 4.6. The more chaotic class 3 ECAs have a more uniform distribution in the side tuple plot, whereas the class 2 ECAs have a more varied distribution, indicating that rules are being accessed differently because of their increased structure. 4.3.3 Coupled logistic maps A particular instance of a threshold coupled lattice is shown in figure 4.7, in a side tuple plot. Contrast with the plan tuple plot of figure 3.17. The different views can be used to highlight different aspects of the system’s trajectory through its state space. 28 Chapter 4. Side Tuple Plots t (a) t t (b) (c) Figure 4.3: A trajectory, or time series, as a side tuple plot: (a) symbol plot, using symbol size; (b) symbl plot, using symbol colour; (c) density plot. (a) (b) (c) (d) Figure 4.4: Side tuple plot of the lookup table access, of Elementary CA rule 110 with N = 400 cells, T = 200 timesteps, and a random (50% 0s, 50% 1s) initial condition (right column). The plan tuple plot is repeated from figure 3.8, for reference. 4.3. Examples 29 2 3 4 5 6 7 8 9 10 Figure 4.5: Ensemble density side tuple plot of 100 points on the surface of the positive hyper-octant of an N -dimensional hypersphere, N = 2–10. The ensemble of points are sorted in order of the maximum coordinate value. 30 Chapter 4. Side Tuple Plots 30 41 54 60 62 90 120 184 (a) (b) (c) (d) (e) Figure 4.6: Side tuple plot of the lookup table access, of Elementary CA rules with N = 100 cells, T = 40 timesteps, and a random (50% 0s, 50% 1s) initial condition (right column). The plan tuple plot, and colour bar, and lookup table bar, are repeated from figure 3.9, for reference. 4.3. Examples 31 Figure 4.7: Side tuple plot of the threshold coupled lattice, threshold x∗ = 0.971, number of cells N = 200, 50 timesteps: the x axis shows time running across the page; the y axis shows the histogrammed value of each of the 200 cells. 5. Hybrid Tuple Plots 5.1 figures 5.2–5.4). This allows visualisation of the relationship between machine state changes and head position, for example. Note how this involves a design decision on the state component. The #Q states could be displayed using one axis with a #Q-valued state (as in the leftmost axis of figure 5.1a), or as #Q-axes of binary values with the constraint that exactly one of the values may be ‘on’ (the leftmost part of figure 5.1b). We use the latter for the hybrid tuple plots, as it is more visually accessible. Motivation The plan and side tuple plots defined above assume homogeneous dimensions. Complicated and complex systems can have heterogeneous dimensions, for example, a mix of continuous and discrete dimensions. We can use a hybrid of different appropriate techniques for these different dimensions to get a visualisation of the whole state space. 5.2 Definition of hybrid tuple plots 5.3.2 Assume the full heterogeneous N D state space V N can be partitioned into d subspaces: V1N1 × V2N2 × . . . × VdNd , where each of the subspaces ViNi is homogeneous. A hybrid tuple plot then is a concatenation of individual plots appropriate for each of the subspaces. Flocking Consider an N particle flocking simulation, with a 6N D state (phase) space, comprising 3D positions and 3D velocities of the N particles. The parallel coordinates are 6N lines, with values from R (figure 5.5a). However, these have structure. 3N of the lines represent position, 3N represent velocity. Moreover, triples of lines represent 3D posi5.3 Examples tion and 3D velocity of a single particle. First, consider drawing each of these triples in conven5.3.1 Turing machines tional orthogonal coordinates instead of parallel coConsider a Turing machine (TM) (see, eg, [14, ordinates, reserving the parallel form for the N + ch.3]). It has a finite set of (machine) states Q, N copes of these orthogonal triples (figure 5.5b). a finite tape alphabet Γ, and a transition function Then use the side projected form to overlay the N δ : Q × Γ → Q × Γ × {L, R} which defines how position sets, and the N velocity sets separately the machine state changes and how the head reads, (figure 5.5c). The resulting hybrid orthogonal/side writes and moves on the tape. The full state space tuple plot is the same as the ordinary 3D view of N (configuration space) of a TM is Q × Z × (Z → Γ), particle positions and N -particle velocities in two which captures the machine state, the head posi- separate 3D spatial plots. (Note that in typical flocking visualisations, only the spatial aspect is tion, and the tape state. Thus we have a heterogeneous set of coordinates: shown; here it is clear that the whole state-space one for the machine state, q ∈ Q, one for the head plot includes the velocity part too.) As with homogeneous side tuple plots, this plot position, h ∈ Z, and an infinite (unbounded) set for loses information about which point represents the state of the tape at each position, t ∈ Z → Γ. If we draw the tape state in a plan tuple plot, and which set of axes (which particle). This is particsuitably arrange the other two coordinates, we can ularly important in relating between the position produce a 1D representation of a TM state (fig- and velocity plots. Colour may be used to highure 5.1), and a visualisation of a TM execution tra- light particular particles across the plots. jectory by a time series of these states (for example, Particle space superficially looks homogeneous in 32 5.3. Examples 33 Figure 5.1: Hybrid tuple plots of a 3 tape-symbol TM: (a) the parallel coordinates view (leaving the polyline implicit): the state space q ∈ Q, the head position h ∈ Z, the tape t ∈ Z → Γ; (b) the various coordinates rearranged, and the tape as a plan tuple plot; (c) combining these into a hybrid visualisation of the state space. the dimensions, whereas our hybrid form is not homogeneous. In particle state space, rotating the axes in the individual 3D spaces make sense: the choice of 3D spatial axes is arbitrary. However, arbitrary rotations of the axes in the full 6N -D phase space do not make the same kind of sense, as this would merge “individual” particles. The choice of the N sets of 6D axes is not arbitrary. Once the N subsets of pairs of triples have been identified, however, the N sets can be rearranged (essentially relabelling the particles), which demonstrates that a side plot is suitable. The “lost” information is just the arbitrary particle label. The topology on the N sets is of a totally connected graph: all particles communicate with all other particles. × × × × × × × × × × × × × × × × × × × × × × Figure 5.2: Hybrid tuple plot time series view of a 2 (machine) state “Busy Beaver” TM, and a 3 state BB. 34 Chapter 5. Hybrid Tuple Plots × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × Figure 5.3: Hybrid tuple plot time series view of a 4 (machine) state “Busy Beaver” TM. × × × × × × × × × Figure 5.4: Hybrid tuple plot time series view of the first 150 steps of a 5 (machine) state “Busy Beaver” TM. 5.3. Examples 35 (x, y, z)1 (x, y, z)N (x, y, z)2 (vx , vy , vz )1 { { { { ... { { ... (vx , vy , vz )2 (vx , vy , vz )N (a) ... ... (b) (c) Figure 5.5: Views of a 6N dimensional phase space comprising 3D positions and velocities of N particles: (a) parallel coordinates; (b) hybrid tuple plot: each individual particle 3D position and velocity set is combined into an orthogonal coordinate set, and the different particles’ spaces are shown in parallel; (c) side tuple plot 6. Further work This report defines how to plot a state space of fixed size at fixed resolution. If this approach helps to make the structure of complex state spaces clear, then there are techniques enhancements that could be developed. It should be possible to ‘zoom out’, to get a coarse-grained overview of a state structure. In plan tuple plots, zooming out could make (some) axes move closer together and merge, so they are not individually resolved, but display the combined value, or some kind of average value, of the combined state components. Some axes might, for some reason, be ‘closer together’ than others, and so merge first; for example, in a boids plot, the three axes of a single boid’s position or velocity might merge to give a scalar position or speed. This violates Inselberg’s original ‘equidistant axes’ rule, but that rule is used to allow geometrical reasoning over the space, so need be followed only in such cases. In the trajectory plan or side plots, the time dimension could be coarse grained in a similar manner. If the coarse graining timescale is an attractor cycle length, this would covert a multi-step dynamic behaviour into a single static value. Correspondingly, it should be possible to ‘zoom in’ to restore the original. In such a case, it might not be immediately obvious at first glance what the underlying dimensionality of the space is: there might be a further zoom in available that would 36 reveal more structure. Dimensions might be lost on zooming out because they become somehow too small to see: a toroidal tube looks like a 3D tube when close, a 2D torus when zoomed out somewhat, a 1D ring when zoomed out further, a 0D point from a distance, and invisible from a great distance. A flock from a distance might be describable as one macroscopic emergent point entity; closer in the individual boids become apparent, and their microstate dimensions appear. The number of dimensions might change because the system state becomes larger: a new tape square is added to a Turing Machine; a boid is born; a new object is created in a program. How to change the number of dimensions the case of discrete time is relatively straightforward: a new dimension axis is added at the relevant timestep. For a case like a Turing Machine or a growing CA, this can be seen as a ‘lazy’ extension of a finite but growing state space. The state space might be seen as hierarchical: a macro-dimension for an object with micro-dimensions for its internals. For continuous time systems, the mechanism(s) of state space growth are not so clear: a new dimension might initially be very small (and so invisible unless zoomed in sufficiently), then steadily grow or uncurl; there might be some fractal structure; it might “fade in”. 7. Summary and Conclusions As new unconventional computational devices are developed, new tools are needed to help explore their behaviour. Visualisation is a powerful tool, and parallel coordinates are one way of visualising high dimensional spaces. We have described the use of parallel coordinates for visualising state space, and trajectories through that space. Two generalised forms introduced here, plan tuple plots and side tuple plots, can be used to simplify, condense, and clarify the plots. When the various dimensions of the state space can be interpreted as individuals, such as cells in a CA, or nodes in an RBN or neural network, then the tuple plots coincide with some conventional plots in the literature. Plan tuple ensemble plots in these cases plot the individuals along a (typically horizontal) line, and indicate their state values through symbols or colour scales. These plots coincide with conventional ways of plotting the time evolution of ECAs (§3.3.2) and RBNs (§3.3.3). Here we generalise, both by highlighting the role of axis ordering to clarify structure (§3.4), and by applying to nonboolean systems (§3.3.4, §3.3.5). Side tuple plots in these cases plot the individuals along the same (typically vertical) value axis, and distinguish between individuals through symbols or colour scales. These plots coincide with conventional ways of plotting multiple individuals in a single individual’s state space, such as flocking particles (§5.3.2). Here we expose that structure, and generalise to ensembles, typically ordered time series, of such plots. We have unified these conventional cases into a generalised common framework. With careful design of hybrid coordinate systems that incorporate multiple forms of plot, much information about the dynamics of a system can be compactly encoded and visualised (§5.3.1). Using these plots in a standardised way should help communicate complex systems dynamics more clearly, with less cognitive load needed for interpreting the various plots. 37 A. Bibliography [1] Matthew Dale, Julian F. Miller, and Susan Stepney. Reservoir Computing as a Model for In-Materio Computing. In Andrew Adamatzky, editor, Advances in Unconventional Computing, pages 533–571. Springer, 2017. [13] Sudeshna Sinha and William L. Ditto. Computing with distributed chaos. Physical Review E, 60(1):363–377, July 1999. [2] Joni Dambre, David Verstraeten, Benjamin Schrauwen, and Serge Massar. Information processing capacity of dynamical systems. Scientific Reports, 2:514, July 2012. [15] Susan Stepney. Visualising random boolean network dynamics. In GECCO 2009, Montreal, Canada, July 2009, pages 1781–82. ACM Press, 2009. [3] Barbara Drossel. Random Boolean Networks. In H. G. Schuster, editor, Reviews of Nonlinear Dynamics and Complexity, volume 1. Wiley, 2008. arXiv:0706.3351. [4] Martin Gardner. Mathematical games: The fantastic combinations of John Conway’s new solitaire game “life”. Scientific American, 223(4):120–123, 1970. [5] Alfred Inselberg. The plane with parallel coordinates. The Visual Computer, 1(2):69–91, 1985. [6] Alfred Inselberg. Parallel Coordinates: visual multidimensional geometry and its applications. Springer, 2009. [7] Kunihiko Kaneko. Spatiotemporal intermittency in coupled map lattices. Progress of Theoretical Physics, 74(5):1033–1044, 1985. [14] Michael Sipser. Introduction to the Theory of Computation. International Thompson Publishing, 1997. [16] Susan Stepney. Visualising the dynamics of random boolean networks: examples of network size, mutation, canalisation. Technical Report YCS-2010-448, Department of Computer Science, University of York, February 2010. [17] Susan Stepney. Nonclassical computation: a dynamical systems perspective. In Grzegorz Rozenberg, Thomas Bäck, and Joost N. Kok, editors, Handbook of Natural Computing, volume II, chapter 52. Springer, 2011. [18] D. Verstraeten, B. Schrauwen, M. D’Haene, and D. Stroobandt. An experimental unification of reservoir computing methods. Neural Networks, 20(3):391–403, 2007. [19] Janet Wiles and Bradley Tonkes. Visualisation of hierarchical cost surfaces for evolutionary computing. In Proceedings of the 2002 Congress on Evolutionary Computation, pages 157–162. IEEE Press, 2002. [8] Stuart A. Kauffman. The Origins of Order. Oxford University Press, 1993. [9] John McCaskill, Julian F. Miller, Susan Stepney, and Peter Wills. Encoding and representation of information processing in irregular computational matter. In Susan Stepney, Steen Rasmussen, and Martyn Amos, editors, Computational Matter, pages 231–248. Springer, 2018. [20] Leland Wilkinson. The Grammar of Graphics. Springer, 2nd edition, 2005. [10] Rida Moustafa and Ed Wegman. Multivariate continuous data — parallel coordinates. In Antony Unwin, Martin Theus, and Heike Hofmann, editors, Graphics of Large Datasets: visualizing a million, chapter 7, pages 143–155. Springer, 2006. [22] Andrew Wuensche. Classifying cellular automata automatically; finding gliders, filtering, and relating spacetime patterns, attractor basins, and the Z parameter. Complexity, 4:47–66, 1999. [11] Sudensha Sinha and Debabrata Biswas. Adaptive dynamics on a chaotic lattice. Physical Review Letters, 71(13):2010–2013, September 1993. [12] Sudeshna Sinha and William L. Ditto. Dynamics based computation. Physical Review Letters, 81(10):2156– 2159, September 1998. 38 [21] Stephen Wolfram. Statistical mechanics of cellular automata. Reviews of Modern Physics, 55(3):601–644, 1983. [23] Andrew Wuensche. Exploring Discrete Dynamics: the DDLab manual. Luniver Press, 2nd edition, 2016. [24] Hong Ye and Zhiping Lin. Speed-up simulated annealing by parallel coordinates. European Journal of Operational Research, 173:59–71, 2006.