An overview of reconstructability analysis <s> V. Discussion <s> This tutorial paper discusses the known representations based on Binary Decision Diagrams (BDDs) for various types of discrete objects: incompletely specified functions, sets, finite state machines, binary and multi-valued relations, etc. While presenting the known material, the emphasis is on those aspects of implicit representations that are important to achieve speed-up in computation. The new material includes implicit representations for dichotomies, partitions, set systems, and information measures. The last type of objects, information measures, constitute a promising approach to problem solving in a number of areas, including decomposition of discrete functions and finite state machines. Multi-valued relations (MVRs) are presented as the most general representation for all the considered classes on discrete objects. Two complementary ways of representing MVRs are proposed: binary-encoded multivalued decision diagrams (BEMDDs) and labeled rough partitions (LRPs). The sizes of BEMDDs and LRPs are compared using a set of multi-valued benchmarks. <s> BIB001 </s> An overview of reconstructability analysis <s> V. Discussion <s> Fourier methods used in two‐ and three‐dimensional image reconstruction can be used also in reconstructability analysis (RA). These methods maximize a variance‐type measure instead of information‐theoretic uncertainty, but the two measures are roughly collinear and the Fourier approach yields results close to that of standard RA. The Fourier method, however, does not require iterative calculations for models with loops. Moreover, the error in Fourier RA models can be assessed without actually generating the full probability distributions of the models; calculations scale with the size of the data rather than the state space. State‐based modeling using the Fourier approach is also readily implemented. Fourier methods may thus enhance the power of RA for data analysis and data mining. <s> BIB002
In the example discussed above of IRA heuristic search, the first step can in principle be extended to much larger problems without difficulty, because single-predictingcomponent models do not require operations on the full state space, but depend rather on the size of the data. The second step, however, does require such operations, which as noted earlier limits the number of variables which can be analyzed to of order 20. This limitation does not preclude the use of RA for data mining applications involving many more than 20 variables, in that the first step can always be used to select a smaller subset for lattice searches. Still, it would clearly be desirable if the second step could be implemented for a greater number of variables. The barrier here is the current requirement for cyclic models of an IPF operation which operates on the entire state space. If models could be generated with a procedure that operated only on observed states and scaled with the data, larger problems could be addressed, since usually data is sparse. At present, it is not apparent how to assess multi-predicting-component models in an alternative way, but two approaches which use approximate assessment and do not require the full state space will now be briefly mentioned. The first involves the use of binary decision diagrams BIB001 . BDD make possible major economies of space and computing time by storing states not explicitly but implicitly in the paths of the diagram. So, while the size of the state space increases exponentially with the number of variables, the size of the graph does not, but the number of paths in the graph does, which allows the graph to represent the exponential dependence of the number of states on the number of variables. It is likely that to use BDD to analyze distributions the distribution frequencies will need to be binned, i.e., IRA problems have to be converted to SRA problems. If the resulting information loss is not severe, and if BDD can be applied to such SRA approximations, the size of the state space may become much less limiting. This approach is under investigation  . A second idea is to employ methods used in 3-dimensional image reconstruction  , and Fourier methods in particular. These methods allow the composition of multiple projections in a single step, regardless of cyclicity. They compute an approximation to IPF which may or may not suffice for practical purposes. Most critically, these methods scale with the data and not the state space. This approach is also under current investigation BIB002 . The use of Fourier methods in RA would bring RA into proximity to LDL methods which use wavelets, Walsh functions, Haar transforms, and similar global or local function-based decompositions. In summary, RA methods are general, being applicable to set-theoretic relations as well as probability distributions. Both SRA and IRA may be of interest to the machine learning and logic design community. SRA offers another approach to decomposition of relations and mappings, and IRA can be used for these purposes as well. The LDL community might profitably examine the use of log-linear latent variable modeling and state-based RA techniques. It might also consider extension of its techniques to distributions, where statistical considerations are necessary. The RA community and the social science log-linear community, on the other hand, can gain from a deeper familiarity with the LDL literature. RA methodology is potentially a valuable new approach to data mining. Current techniques can be applied to 10's or 100's of variables, and heuristic and approximate methods may substantially expand the range of RA modeling.