Saturday, May 20, 2017

Foundations of Evaluating Public Transit Networks, Part 6: Similar, Rather than Different

Last week in the Foundations of Evaluating Public Transit Networks series, I highlighted the fact that shifting the center of a Point Utility computation a small amount can have a substantial impact on the reachability map and the corresponding score. This presented the problem of how to measure the utility of a whole network when individual points may tell very different stories about how useful the network is. This post describes one strategy for solving this problem by focusing on how Point Utility measurements from different centers are similar rather than how they are different, and using techniques from the discipline of information theory to define this similarity in a rigorous way.

To ease this discussion, this post makes use of the following terminology. Network Utility (NU) is the hypothetical measurement of how useful a transit network is using Public Transit Analytics's definition of useful. In theory, it would be calculated by running a series of full-day Point Utility computations centered at each Sector of the service area. As explained in the last post, this is a very difficult measurement to make, owing to the large number of Sectors from which Point Utility calculations must be run. A related concept is Cumulative Point Utility (CPU). Rather than aggregating the results from every Sector, CPU is the result of generating the Point Utilities at some sample of the Sectors' centers and combining these. CPU has the benefit of being flexible in the amount of computation required; there are no restrictions on how many or few samples make up a CPU calculation. There is, of course, the tradeoff that fewer samples will produce results further away from the true Network Utility.

Information theory comes in handy in establishing what "further away" means. Mutual information is an information theoretic technique that measures how much information one random variable indicates about another. It uses the joint and marginal probability distributions of two random variables. Thus, to measure how far away one Point Utility measurement is from another, it must be possible to model a Point Utility as a probability distribution. The diagram below indicates how this can be done.

Consider the simplified Point Utility maps above. Recall that in a Point Utility map, each Sector is assigned a shade of green depending on how often the Sector can be reached. Each shade of green corresponds to a number, one through nine, referred to as the "bin value". Treat each Sector as an observation of a random variable. The value of that observation is the bin value of the Sector. Sectors that cannot be reached are given a bin value of zero. Looking over a whole Point Utility map, one can count the number of Sectors with each reachability bin value. These sums can be divided by the total number of Sectors, creating a probability distribution for what the bin value of an arbitrary Sector would be on that map.

When considering two different Point Utility maps, it is then possible to construct a joint probability distribution. To do this, choose a Sector on the first map and find the same Sector on the second map. Keep a count of each pair of observations; for example Sector one has a bin value of 9 in the first map and a bin value of 5 in the second map, so the pair (X=9, Y=5) is recorded. Continue this process for each Sector, obtaining a total of each observation. Dividing these by the number of Sectors yields the joint probability distribution for the bin values of the two Point Utility maps.

With the joint distribution, and the marginal distributions that can be computed from it, it is possible to compute the mutual information of two Utility measurements of any type. This calculation can be used in two ways. If the Network Utility has been computed at great cost, the mutual information can be used to determine how accurately a Cumulative Point Utility approximates the Network Utility. Once a sufficiently accurate CPU has been found, changes to the transportation network can be measured using CPU rather than NU, saving computational resources and money.

Furthermore, even if the Network Utility is unknown, mutual information sheds light on whether the Cumulative Point Utility is approaching it. Consider building a series of Cumulative Point Utilities by selecting an initial Sector at random, adding new random Sectors, and computing a new CPU for after each new Sector is added. After each CPU is measured, the mutual information between it and the previous CPU is measured. Initially the mutual information will decrease: mutual information between any two Point Utilities is relatively high because both PUs indicate that the plurality of Sectors are unreachable and thus the maps are similar. As more PUs are combined into the CPU, fewer points are outright unreachable, and thus the maps will be less similar from the perspective of mutual information. As more PU measurements are added, it is expected that the rate of decrease will slow or reverse, as the data added from a PU is capable of being inferred from the previous CPU. In a more concrete sense, this means that one can learn something about what is reachable at a point by considering the points around it. After all, that point has similar transit stops within its walking range. Eventually, the random points that were selected comprise nearly all the information about the transit network, even though they are not an exhaustive collection of every location on the map.

Public Transit Analytics is actively working through some of the practical concerns of using Cumulative Point Utility. It is unclear how many samples would be sufficient and what properties of a transit network may result in alterations to the sufficiency criteria. Nonetheless, the approach of using mutual information appears to be a promising one. Its ultimate promise is a way of measuring an entire transit network in an unbiased way not seen in other models available to planners today.