Probabilities of causation are proven to be critical in modern decision-making. This paper deals with the problem of estimating the probabilities of causation when treatment and effect are not binary. Pearl defined the binary probabilities of causation, such as the probability of necessity and sufficiency (PNS), the probability of sufficiency (PS), and the probability of necessity (PN). Tian and Pearl then derived sharp bounds for these probabilities of causation using experimental and observational data. In this paper, we define and provide theoretical bounds for all types of probabilities of causation with multivalued treatments and effects. We further discuss examples where our bounds guide practical decisions and use simulation studies to evaluate how informative the bounds are for various data combinations.

The unit selection problem aims to identify a set of individuals who are most likely to exhibit a desired mode of behavior or to evaluate the percentage of such individuals in a given population, for example, selecting individuals who would respond one way if encouraged and a different way if not encouraged. Using a combination of experimental and observational data, Li and Pearl solved the binary unit selection problem (binary treatment and effect) by deriving tight bounds on the "benefit function," which is the payoff/cost associated with selecting an individual with given characteristics. This paper extends the benefit function to the general form such that the treatment and effect are not restricted to binary. We then propose an algorithm to test the identifiability of the nonbinary benefit function and an algorithm to compute the bounds of the nonbinary benefit function using experimental and observational data.

Probabilities of causation play a crucial role in modern decision-making. Pearl defined three binary probabilities of causation, the probability of necessity and sufficiency (PNS), the probability of sufficiency (PS), and the probability of necessity (PN). These probabilities were then bounded by Tian and Pearl using a combination of experimental and observational data. However, observational data are not always available in practice; in such a case, Tian and Pearl’s Theorem provided valid but less effective bounds using pure experimental data. In this paper, we discuss the conditions that observational data are worth considering to improve the quality of the bounds. More specifically, we defined the expected improvement of the bounds by assuming the observational distributions are uniformly distributed on their feasible interval. We further applied the proposed theorems to the unit selection problem defined by Li and Pearl.

The unit selection problem aims to identify a set of individuals who are most likely to exhibit a desired mode of behavior, for example, selecting individuals who would respond one way if encouraged and a different way if not encouraged. Using a combination of experimental and observational data, Li and Pearl derived tight bounds on the "benefit function" - the payoff/cost associated with selecting an individual with given characteristics. This paper shows that these bounds can be narrowed significantly (enough to change decisions) when structural information is available in the form of a causal model. We address the problem of estimating the benefit function using observational and experimental data when specific graphical criteria are assumed to hold.

This paper addresses the problem of estimating causal effects when adjustment variables in the back-door or front-door criterion are partially observed. For such scenarios, we derive bounds on the causal effects by solving two non-linear optimization problems, and demonstrate that the bounds are sufficient. Using this optimization method, we propose a framework for dimensionality reduction that allows one to trade bias for estimation power, and demonstrate its performance using simulation studies.

The problem of individualization is crucial in almost every field of science. Identifying causes of specific observed events is likewise essential for accurate decision making as well as explanation. However, such tasks invoke counterfactual relationships, and are therefore indeterminable from population data. For example, the probability of benefiting from a treatment concerns an individual having a favorable outcome if treated and an unfavorable outcome if untreated; it cannot be estimated from experimental data, even when conditioned on fine-grained features, because we cannot test both possibilities for an individual. Tian and Pearl provided bounds on this and other probabilities of causation using a combination of experimental and observational data. Those bounds, though tight, can be narrowed significantly when structural information is available in the form of a causal model. This added information may provide the power to solve central problems, such as explainable AI, legal responsibility, and personalized medicine, all of which demand counterfactual logic. This paper derives, analyzes, and characterizes these new bounds, and illustrates some of their practical applications.

Traditional causal inference techniques assume data are independent and identically distributed (IID) and thus ignores interactions among units. However, a unit’s treatment may affect another unit's outcome (interference), a unit’s treatment may be correlated with another unit’s outcome, or a unit’s treatment and outcome may be spuriously correlated through another unit. To capture such nuances, we model the data generating process using causal graphs and conduct a systematic analysis of the bias caused by different types of interactions when computing causal effects. We derive theorems to detect and quantify the interaction bias, and derive conditions under which it is safe to ignore interactions. Put differently, we present conditions under which causal effects can be computed with negligible bias by assuming that samples are IID. Furthermore, we develop a method to eliminate bias in cases where blindly assuming IID is expected to yield a significantly biased estimate. Finally, we test the coverage and performance of our methods through simulations.

Assumptions about equality of effects are commonly made in causal inference tasks. For example, the well-known “difference-in-differences” method assumes that confounding remains constant across time periods. Similarly, it is not unreasonable to assume that causal effects apply equally to units undergoing interference. Finally, sensitivity analysis often hypothesizes equality among existing and unaccounted for confounders. Despite the ubiquity of these “equality constraints,” modern identification methods have not leveraged their presence in a systematic way. In this paper, we develop a novel graphical criterion that extends the well-known method of generalized instrumental sets to exploit such additional constraints for causal identification in linear models. We further demonstrate how it solves many diverse problems found in the literature in a general way, including difference-in-differences, interference, as well as benchmarking in sensitivity analysis.

Modern causal analysis involves two major tasks, discovery and identification. The first aims to learn a causal structure compatible with the available data, the second leverages that structure to estimate causal effects. Rather than performing the two tasks in tandem, as is usually done in the literature, we propose a symbiotic approach in which the two are performed simultaneously for mutual benefit; information gained through identification helps causal discovery and vice versa. This approach enables the usage of Verma constraints, which remain dormant in constraint-based methods of discovery, and permit us to learn more complete structures, hence identify a larger set of causal effects than previously achievable with standard methods.

The past three decades have seen the development of powerful tools for modeling and computing causal relationships which may have major impact on data science. My talk will illustrate how these tools work in seven tasks: 1. Encoding causal assumptions in transparent and testable way 2. Predicting the effects of actions and policies 3. Computing counterfactuals and finding causes of effects 4. Computing direct and indirect effects (Mediation) 5. Integrating data from diverse sources. 6. Recovering from missing data 7. Discovering causal relations from data. A friendly, non-technical account of these ideas is available in: “The Book of Why: the new science of cause and effect,” Judea Pearl and Dana MacKenzie, (Basic Books, 2018). http://bayes.cs.ucla.edu/WHY/.

Causal inference requires assumptions about the data generating process, many of which are unverifiable from the data. Given that some causal assumptions might be uncertain or disputed, formal methods are needed to quantify how sensitive research conclusions are to violations of those assumptions. Although an extensive literature exists on the topic, most results are limited to specific model structures, while a general-purpose algorithmic framework for sensitivity analysis is still lacking. In this paper, we develop a formal, systematic approach to sensitivity analysis for arbitrary linear Structural Causal Models (SCMs). We start by formalizing sensitivity analysis as a constrained identification problem. We then develop an efficient, graph-based identification algorithm that exploits non-zero constraints on both directed and bidirected edges. This allows researchers to systematically derive sensitivity curves for a target causal quantity with an arbitrary set of path coefficients and error covariances as sensitivity parameters. These results can be used to display the degree to which violations of causal assumptions affect the target quantity of interest, and to judge, on scientific grounds, whether problematic degrees of violations are plausible.

The unit selection problem aims to identify a set of individuals who are most likely to exhibit a desired mode of behavior, which is defined in counterfactual terms. A typical example is that of selecting individuals who would respond one way if encouraged and a different way if not encouraged. Unlike previous works on this problem, which rely on ad-hoc heuristics, we approach this problem formally, using counterfactual logic, to properly capture the nature of the desired behavior. This formalism enables us to derive an informative selection criterion which integrates experimental and observational data. We demonstrate the superiority of this criterion over A/B-test-based approaches.

Traditional methods for handling incomplete data, including Multiple Imputation and Maximum Likelihood, require that the data be Missing At Random (MAR). In most cases, however, missingness in a variable depends on the underlying value of that variable. In this work, we devise model-based methods to consistently estimate mean, variance and covariance given data that are Missing Not At Random (MNAR). While previous work on MNAR data require variables to be discrete, we extend the analysis to continuous variables drawn from Gaussian distributions. We demonstrate the merits of our techniques by comparing it empirically to state of the art software packages.

Current machine learning systems operate, almost exclusively, in a statistical, or model-blind mode, which entails severe theoretical limits on their power and performance. Such systems cannot reason about interventions and retrospection and, therefore, cannot serve as the basis for strong AI. To achieve human level intelligence, learning machines need the guidance of a model of reality, similar to the ones used in causal inference. To demonstrate the essential role of such models, I will present a summary of seven tasks which are beyond reach of current machine learning systems and which have been accomplished using the tools of causal inference.

The Multi-Armed Bandit problem with Unobserved Confounders (MABUC) considers decision-making settings where unmeasured variables can influence both the agent’s decisions and received rewards (Bareinboim et al., 2015). Recent findings showed that unobserved confounders (UCs) pose a unique challenge to algorithms based on standard randomization (i.e., experimental data); if UCs are naively averaged out, these algorithms behave sub-optimally, possibly incurring infinite regret. In this paper, we show how counterfactual-based decision-making circumvents these problems and leads to a coherent fusion of observational and experimental data. We then demonstrate this new strategy in an enhanced Thompson Sampling bandit player, and support our findings’ efficacy with extensive simulations.

editorial Free Access Share on Preface to the ACM TIST Special Issue on Causal Discovery and Inference Authors: Kun Zhang Max-Planck Institute for Intelligent Systems, Germany Max-Planck Institute for Intelligent Systems, GermanyView Profile , Jiuyong Li University of South Australia, Australia University of South Australia, AustraliaView Profile , Elias Bareinboim University of California, Los Angeles, CA University of California, Los Angeles, CAView Profile , Bernhard Schölkopf Max-Planck Institute for Intelligent Systems, Germany Max-Planck Institute for Intelligent Systems, GermanyView Profile , Judea Pearl University of California, Los Angeles, CA University of California, Los Angeles, CAView Profile Authors Info & Claims ACM Transactions on Intelligent Systems and TechnologyVolume 7Issue 2January 2016 Article No.: 17pp 1–3https://doi.org/10.1145/2840720Published:09 January 2016Publication History 4citation265DownloadsMetricsTotal Citations4Total Downloads265Last 12 Months26Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The Multi-Armed Bandit problem constitutes an archetypal setting for sequential decision-making, permeating multiple domains including engineering, business, and medicine. One of the hallmarks of a bandit setting is the agent's capacity to explore its environment through active intervention, which contrasts with the ability to collect passive data by estimating associational relationships between actions and payouts. The existence of unobserved confounders, namely unmeasured variables affecting both the action and the outcome variables, implies that these two data-collection modes will in general not coincide. In this paper, we show that formalizing this distinction has conceptual and algorithmic implications to the bandit setting. The current generation of bandit algorithms implicitly try to maximize rewards based on estimation of the experimental distribution, which we show is not always the best strategy to pursue. Indeed, to achieve low regret in certain realistic classes of bandit problems (namely, in the face of unobserved confounders), both experimental and observational quantities are required by the rational agent. After this realization, we propose an optimization metric (employing both experimental and observational distributions) that bandit agents should pursue, and illustrate its benefits over traditional algorithms.

Selection bias is caused by preferential exclusion of units from the samples and represents a major obstacle to valid causal and statistical inferences; it cannot be removed by randomized experiments and can rarely be detected in either experimental or observational studies. In this paper, we provide complete graphical and algorithmic conditions for recovering conditional probabilities from selection biased data. We also provide graphical conditions for recoverability when unbiased data is available over a subset of the variables. Finally, we provide a graphical condition that generalizes the backdoor criterion and serves to recover causal effects when the data is collected under preferential selection.

In causal inference, all methods of model learning rely on testable implications, namely, properties of the joint distribution that are dictated by the model structure. These constraints, if not satisfied in the data, allow us to reject or modify the model. Most common methods of testing a linear structural equation model (SEM) rely on the likelihood ratio or chi-square test which simultaneously tests all of the restrictions implied by the model. Local constraints, on the other hand, offer increased power (Bollen and Pearl, 2013; McDonald, 2002) and, in the case of failure, provide the modeler with insight for revising the model specification. One strategy of uncovering local constraints in linear SEMs is to search for overidentified path coefficients. While these overidentifying constraints are well known, no method has been given for systematically discovering them. In this paper, we extend the half-trek criterion of (Foygel et al., 2012) to identify a larger set of structural coefficients and use it to systematically discover overidentifying constraints. Still open is the question of whether our algorithm is complete.

Bayesian networks (BN) are an extensively used graphical model for representing a probability distribution in artificial intelligence, data mining, and machine learning. In this paper, we propose a simple model for large random BNs with bounded indegree, that is, large directed acyclic graphs (DAG) where the edges appear at random and each node has at most a given number of parents. Using this model, we can study useful asymptotic properties of large BNs and BN algorithms with basic combinatorics tools. We estimate the expected size of a BN, the expected size increase of moralization, the expected size of the Markov blanket, and the maximum size of a minimal d-separator. We also provide an upper bound on the average time complexity of an algorithm for finding a minimal d-separator. In addition, the estimates are evaluated against BNs learned from real world data.

Graphical models that depict the process by which data are lost are helpful in recovering information from missing data. We address the question of whether any such model can be submitted to a statistical test given that the data available are corrupted by missingness. We present sufficient conditions for testability in missing data applications and note the impediments for testability when data are contaminated by missing entries. Our results strengthen the available tests for MCAR and MAR and further provide tests in the category of MNAR. Furthermore, we provide sufficient conditions to detect the existence of dependence between a variable and its missingness mechanism. We use our results to show that model sensitivity persists in almost all models typically categorized as MNAR.

We address the problem of transferring causal knowledge learned in one environment to another, potentially different environment, when only limited experiments may be conducted at the source. This generalizes the treatment of transportability introduced in [Pearl and Bareinboim, 2011; Bareinboim and Pearl, 2012b], which deals with transferring causal information when any experiment can be conducted at the source. Given that it is not always feasible to conduct certain controlled experiments, we consider the decision problem whether experiments on a selected subset Z of variables together with qualitative assumptions encoded in a diagram may render causal effects in the target environment computable from the available data. This problem, which we call z-transportability, reduces to ordinary transportability when Z is all-inclusive, and, like the latter, can be given syntactic characterization using the do-calculus [Pearl, 1995; 2000]. This paper establishes a necessary and sufficient condition for causal effects in the target domain to be estimable from both the non-experimental information available and the limited experimental information transferred from the source. We further provides a complete algorithm for computing the transport formula, that is, a way of fusing experimental and observational information to synthesize an unbiased estimate of the desired causal relation.

This paper considers the problem of transferring experimental findings learned from multiple heterogeneous domains to a different environment, in which only passive observations can be collected. Pearl and Bareinboim (2011) established a complete characterization for such transfer between two domains, a source and a target, and this paper generalizes their results to multiple heterogeneous domains. It establishes a necessary and sufficient condition for deciding when effects in the target domain are estimable from both statistical and causal information transferred from the experiments in the source domains. The paper further provides a complete algorithm for computing the transport formula, that is, a way of fusing observational and experimental information to synthesize an unbiased estimate of the desired effects.

Controlling selection bias, a statistical error caused by preferential sampling of data, is a fundamental problem in machine learning and statistical inference. This paper presents a simple criterion for controlling selection bias in the odds ratio, a widely used measure for association between variables, that connects the nature of selection bias with the graph modeling the selection mechanism. If the graph contains certain paths, we show that the odds ratio cannot be expressed using data with selection bias. Otherwise, we show that a d-separability test can determine whether the odds ratio can be recovered, and when the answer is affirmative, output an unbiased estimand of the odds ratio. The criterion can be test in linear time and enhances the power of the estimand.

This paper considers the problem of transferring experimental findings learned from multiple heterogeneous domains to a target environment, in which only limited experiments can be performed. We reduce questions of transportability from multiple domains and with limited scope to symbolic derivations in the do-calculus, thus extending the treatment of transportability from full experiments introduced in Pearl and Bareinboim (2011). We further provide different graphical and algorithmic conditions for computing the transport formula for this setting, that is, a way of fusing the observational and experimental information scattered throughout different domains to synthesize a consistent estimate of the desired effects.

We address the problem of deciding whether there exists a consistent estimator of a given relation Q, when data are missing not at random. We employ a formal representation called `Missingness Graphs' to explicitly portray the causal mechanisms responsible for missingness and to encode dependencies between these mechanisms and the variables being measured. Using this representation, we define the notion of \textit{recoverability} which ensures that, for a given missingness-graph $G$ and a given query $Q$ an algorithm exists such that in the limit of large samples, it produces an estimate of $Q$ \textit{as if} no data were missing. We further present conditions that the graph should satisfy in order for recoverability to hold and devise algorithms to detect the presence of these conditions.

The study of transportability aims to identify conditions under which causal information learned from experiments can be reused in a different environment where only passive observations can be collected. The theory introduced in [Pearl and Bareinboim, 2011] (henceforth [PB, 2011]) defines formal conditions for such transfer but falls short of providing an effective procedure for deciding, given assumptions about differences between the source and target domains, whether transportability is feasible. This paper provides such procedure. It establishes a necessary and sufficient condition for deciding when causal effects in the target domain are estimable from both the statistical information available and the causal information transferred from the experiments. The paper further provides a complete algorithm for computing the transport formula, that is, a way of fusing experimental and observational information to synthesize an estimate of the desired causal relation.

Selection bias, caused by preferential exclusion of units (or samples) from the data, is a major obstacle to valid causal inferences, for it cannot be removed or even detected by randomized experiments. This paper highlights several graphical and algebraic methods capable of mitigating and sometimes eliminating this bias. These nonparametric methods generalize and improve previously reported results, and identify the type of knowledge that need to be available for reasoning in the presence of selection bias

We address the problem of transferring information learned from experiments to a different environment, in which only passive observations can be collected. We introduce a formal representation called "selection diagrams" for expressing knowledge about differences and commonalities between environments and, using this representation, we derive procedures for deciding whether effects in the target environment can be inferred from experiments conducted elsewhere. When the answer is affirmative, the procedures identify the set of experiments and observations that need be conducted to license the transport. We further discuss how transportability analysis can guide the transfer of knowledge in non-experimental learning to minimize re-measurement cost and improve prediction power.

I will review concepts, principles, and mathematical tools that were found useful in applications involving causal and counterfactual relationships. This semantical framework, enriched with a few ideas from logic and graph theory, gives rise to a complete, coherent, and friendly calculus of causation that unifies the graphical and counterfactual approaches to causation and resolves many long-standing problems in several of the sciences. These include questions of causal effect estimation, policy analysis, and the integration of data from diverse studies. Of special interest to KDD researchers would be the following topics:

Structural causal models offer a popular framework for exploring causal concepts. However, due to their limited expressiveness, structural models have difficulties coping with such concepts as actual (event-to-event) causation. In this article, we propose a new type of causal model, based on embedding structural considerations in the language of situation calculus. By using situation calculus as a basic language, we leverage its power to express complex, dynamically changing situations and, by relying on structural considerations, we can formulate an effective theory of counterfactuals within the situation-calculus.

Traditional databases commonly support efficient query and update procedures that operate in time which is sublinear in the size of the database. Our goal in this paper is to take a first step toward dynamic reasoning in probabilistic databases with comparable efficiency. We propose a dynamic data structure that supports efficient algorithms for updating and querying singly connected Bayesian networks. In the conventional algorithm, new evidence is absorbed in O(1) time and queries are processed in time O(N), where N is the size of the network. We propose an algorithm which, after a preprocessing phase, allows us to answer queries in time O(log N) at the expense of O(log N) time per evidence absorption. The usefulness of sub-linear processing time manifests itself in applications requiring (near) real-time response over large probabilistic databases. We briefly discuss a potential application of dynamic probabilistic reasoning in computational biology.

An approach to nonmonotonic reasoning that combines the principle of infinitesimal probabilities with that of maximum entropy, thus extending the inferential power of the probabilistic interpretation of defaults, is proposed. A precise formalization of the consequences entailed by a conditional knowledge base is provided, the computational machinery necessary for drawing these consequences is developed, and the behavior of the maximum entropy approach is compared to related work in default reasoning. The resulting formalism offers a compromise between two extremes: the cautious approach based on the conditional interpretations of defaults and the bold approach based on minimizing abnormalities.>

Abstract An important feature of Bayesian networks is that they facilitate explicit encoding of information about independencies in the domain, information that is indispensable for efficient inferencing. This article characterizes all independence assertions that logically follow from the topology of a network and develops a linear time algorithm that identifies these assertions. The algorithm's correctness is based on the soundness of a graphical criterion, called d ‐separation, and its optimality stems from the completeness of d ‐separation. An enhanced version of d ‐separation, called D ‐separation, is defined, extending the algorithm to networks that encode functional dependencies. Finally, the algorithm is shown to work for a broad class of nonprobabilistic independencies.

An operational domain-independent decision-aiding system for situation assessment tasks is described. The system elicits the user's perception of a given situation through a stylized English dialogue and focuses the user's attention on the issue of highest relevancy. Elicited problems are structured as networks where nodes represent variables and directed links represent causal relationships. The system uses a Bayesian inference procedure which combines causal and diagnostic reasoning using a bidirectional propagation of evidence in the form of belief parameters. Upon completion of the dialogue the system provides a formal structure representing relevant propositions, their interrelations, and their updated belief distributions.

This paper reports several properties of heuristic best-first search strategies whose scoring functions ƒ depend on all the information available from each candidate path, not merely on the current cost g and the estimated completion cost h . It is shown that several known properties of A* retain their form (with the minmax of f playing the role of the optimal cost), which helps establish general tests of admissibility and general conditions for node expansion for these strategies. On the basis of this framework the computational optimality of A*, in the sense of never expanding a node that can be skipped by some other algorithm having access to the same heuristic information that A* uses, is examined. A hierarchy of four optimality types is defined and three classes of algorithms and four domains of problem instances are considered. Computational performances relative to these algorithms and domains are appraised. For each class-domain combination, we then identify the strongest type of optimality that exists and the algorithm for achieving it. The main results of this paper relate to the class of algorithms that, like A*, return optimal solutions (i.e., admissible) when all cost estimates are optimistic (i.e., h ≤ h *). On this class, A* is shown to be not optimal and it is also shown that no optimal algorithm exists, but if the performance tests are confirmed to cases in which the estimates are also consistent, then A* is indeed optimal. Additionally, A* is also shown to be optimal over a subset of the latter class containing all best-first algorithms that are guided by path-dependent evaluation functions.

The paper summarizes recent analytical investigations of the mathematical properties of heuristics and their influence on the performance of common search techniques. The results are reported without proofs together with discussions of motivations and interpretations. The highlights include the following: the optimality of A*; relations between the precision of the heuristic estimates and the average complexity of the search; comparisons of the average complexities of A* and BACKTRACKING; procedures for comparing and combining nonadmissible heuristic functions; the influence of the weight w (in f = (l - w) g + wh) on the complexity of A*; the pruning power of alphabeta, SSS*, and SCOUT; the effect of successor ordering on search complexity, and the effect of search depth of the quality of decisions in game-playing.

The paper introduces three extensions of the A* search algorithm which improve the search efficiency by relaxing the admissibility condition. 1) A* employs an admissible heuristic function but invokes quicker termination conditions while still guaranteeing that the cost of the solution found will not exceed the optimal cost by a factor greater than 1 + . 2) R¿* may employ heuristic functions which occasionally violate the admissibility condition, but guarantees that at termination the risk of missing the opportunity for further cost reduction is at most ¿. 3) R¿*,* is a speedup version of R¿*, combining the termination condition of A* with the risk-admissibility condition of R¿*. The Traveling Salesman problem was used as a test vehicle to examine the performances of the algorithms A* and R¿*. The advantages of A* are shown to be significant in difficult problems, i.e., problems requiring a large number of expansions due to the presence of many subtours of roughly equal costs. The use of R¿* is shown to produce a 4:1 reduction in search time with only a minor increase in final solution cost.

This paper describes an operational version of a computerized, domain-independent, decision support system which is based on a novel, goal-directed structure for representing decision problems. The structure allows the user to state relations among aspects, effects, conditions, and goals, in addition to actions and states which are the basic components of the traditional decision tree approach. The program interacts with the user in a stylized English-like dialogue, starting with the stated objectives and proceeding to unravel the more detailed means by which these objectives can be realized. At any point in time, the program focuses the user's attention on the issues which are most crucial to the problem at hand. The structure used is more compatible with the way people encode knowledge about problems and actions, and therefore promises to offer the following advantages: 1) judgments and beliefs issued by the user constitute a more valid representation of the user's experience; and 2) the user may be guided toward the discovery of action alternatives he otherwise would not have identified.

The trade-offs between the required storage space and the validity of answers produced by probabilistic question-answering (PQA) systems are studies. If the correct answer to a given query is "yes" and the system, instead, issues the estimate that the query has a probability\piof being true, then the economic loss to the user can be measured by a distortion function that decreases monotonically with\pi. A system will be called elastic if a drastic memory saving may be achieved by tolerating a small level of average distortion. The main result reported is that for a large class of distortion measures (i.e., measures exceeding(1-\pi)^{\alpha}with\alpha>0), if a binary QA system (true-false answers) is inelastic then the corresponding probabilistic QA system must also be inelastic. This result implies, for example, that a PQA system that is designed to answer all binary questions on an arbitrary dataset is inelastic. Similarly a PQA system admitting singly conjunctive questions such as "Are bothxandyin the dataset?" is also inelastic.

This paper extends the notions of capacity and distribution-free error estimation to nonlinear Boolean classifiers on patterns with binary-valued features. We establish quantitative relationships between the dimensionality of the feature vectors (d), the combinational complexity of the decision rule (c), the number of samples in the training set (n), and the classification performance of the resulting classifier. Our results state that the discriminating capacity of Boolean classifiers is given by the product dc, and the probability of ambiguous generalization is asymptotically given by (n/dc 1)-i 0(1Og d)/d) for large d, and n = O(dc). In addition we show that if a fraction v of the training samples is misclassified then the probability of error (r) in subsequent samples satisfies P(17r - vl > e) : 2.773 exp (dc - e2n/8) for all distributions, regardless of how the classifier was discovered.

A method for studying the asymptotic behavior of discrete transformations is developed using numerical quadrature theory. This method allows a more convenient examination of the correlation properties of common unitary transforms for large block sizes. As a practical result of this method it is shown that the discrete cosine transform is asymptotically optimal for all finite-order Markov signals.

An improved analysis for an information system is described in which the input and output alphabets consist of (equiprobable) ordered lists of m items, with two distortion criteria: 1) the fraction of item-pairs found out of order and 2) the fraction of items found in wrong positions. For the former it is shown that, asm \rightarrow \infty, the rate-distortion functionR_{1} (D)is equivalent tomG(D)with, for smallD,G(D)=\log (2/D)-2+ O(D). For the latter,R_{2} (D) = m \log m(1 - D) + m(l - D)[\log(1 - D) - 1] + o(m).

A question-answering (QA) system answers queries from a given set about data sets drawn from a given ensemble. Shannon's rate-distortion functionR(D)provides the minimum amount of memory that a QA system must employ in order to achieve an average distortion less thanD(the distortion can, for example, be the average proportion of erroneous answers produced by the system). The ability of a system to convert an amountDof distortion into a saving in memory is measured by the ratioR(D)/R(0). A system will be called elastic if this ratio goes to zero asM, the size of the data set ensemble, tends to infinity. The asymptotic bounds toR(D)are derived, giving rise to elasticity conditions which involve only general system parameters.

It has been conjectured that error-allowance could improve dramatically the performance of data processing systems. This hypothesis is tested in the framework of question-answering (QA) systems with storage requirements as a complexity measure. Shannon's rate distortion functionR(D)represents the minimum amount of memory a system must employ in order to achieve an average distortion less thanD(the distortion can be, for example, the average proportion of erroneous answers produced by the system). The ability of a system to convert an amountDof distortion into memory savings is measured by the ratioR(D)/R(O). A system will be called elastic if this ratio goes to zero as the size of the dataset ensemble goes to infinity. Asymptotic bounds toR(D)are derived giving rise to elasticity conditions invoking the structure of the distortion matrix associated with the system. The bounds established represent a marked Improvement over former results by narrowing the gap between the necessary and sufficient conditions for elasticity. Moreover, conditions are established under which the amount of computation required for testing elasticity can be substantially reduced.

The complexity of question-answering systems which are permitted to submit probabilistic estimates of the truth of certain propositions is considered. Bounds are derived on the expected memory space and computational work required to produce probabilistic estimates of a specified quality. The general features of the bounds are similar to those of question-answering systems constrained to true-false type answers.

An interactive computer program has been designed and implemented that elicits a decision tree from a decisionmaker in an English-like conversational mode. It emulates a decision analyst who guides the decisionmaker in structuring and organizing his knowledge about a particular problem domain. The objectives of the research were: 1) to provide the decision analysis industry with a practical automated tool for eliciting decision structures where manual elicitation techniques are either infeasible or uneconomical, 2) to cast the decision analyst's behavior into a formal framework in order to examine the principles governing the elicitation procedure and gain a deeper understanding of the analysis process itself, and 3) to provide experimental psychologists with an automated research tool for coding subjects' perception of problem situations into a standard and formal representation. The approach centers on the realization that the process of conducting an elicitation dialogue is structurally identical to conducting a heuristic search on game trees, as is commonly practiced in artificial intelligence programs. Heuristic search techniques, when applied to tree elicitation, permit real-time rollback and sensitivity analysis as the tree is being formulated. Thus it is possible to concentrate effort on expanding those parts of the tree which are crucial for the resolution of the solution plan. The program requires the decisionmaker to provide provisional values at each intermediate stage in the tree construction, which estimate the promise of future opportunities open to him from that stage.

Traditional decision-analytic practice emphasizes the distinction between probability assessments and value (or utility) judgments. Whereas techniques for elicitation and integration of subjective probabilities often can be submitted to empirical tests of validity, the fidelity of encoding value judgments has so far defied measurements. A unified approach to the treatment of the two types of judgments is presented; value judgments are interpreted as conditional probability statements. Such formulation leads to rational methodologies and procedures for solving the following tasks: 1) empirical validation and refinement of value judgments and 2) aggregating value judgments obtained from a panel of experts.

This paper addresses the following question. A computer system is presented with a very long list of ordered items and files a summarized description of the data to facilitate answering queries about the order of the items in the list. What is the minimum storage space required to guarantee that the fraction of incorrect answers remains below a specified level?

In this correspondence, the rate-distortion function is calculated for a source emitting equiprobable precedence relations amongmobjects, using the fraction of pairs reproduced out-of-order as a distortion measure. For largem, the rate is approximately given byR(D) = m \log(1/D). The rate-distortion characteristics of cluster coding is seen to be nearly ideal for low-distortion conditions.

This paper considers the reduction in algorithmic complexity that can be achieved by permitting approximate answers to computational problems. It is shown that Shannon's rate-distortion function could, under quite general conditions, provide lower bounds on the mean complexity of inexact computations. As practical examples of this approach, we show that partial sorting ofNitems, insisting on matching any nonzero fraction of the terms with their correct successors, requiresO (N \log N)comparisons. On the other hand, partial sorting in linear time is feasible (and necessary) if one permits any finite fraction of pairs to remain out of order. It is also shown that any error tolerance below 50 percent can neither reduce the state complexity of binaryN-sequences from the zero-error value ofO(N)nor reduce the combinational complexity ofN-variable Boolean functions from the zero-error level ofO(2^{N}/N).

The ease of simulating a dyadic model on digital computers suggests approximating linear time-invariant (LTI) systems by dyadic models. Methods for calculating the best such approximations are provided. It is shown that the matrices characterizing the LTI system and its optimal dyadic approximant have identical diagonal elements in the Walsh domain. This fact is used to derive a direct transformation between the impulse-response function of an LTI system and that of its dyadic approximant. The transformation can be accomplished in less than N log N additions.

The covariance matrix of the Fourier coefficients ofN- sampled stationary random signals is studied. Three theorems are established. 1) If the covariance sequence is summable, the magnitude of every off-diagonal covariance element converges to zero asN \rightarrow \infty. 2) If the covariance sequence is only square summable, the magnitude of the covariance elements sufficiently far from the diagonal converges to zero asN \rightarrow \infty. 3) If the covariance sequence is square summable, the weak norm of the matrix containing only the off-diagonal elements converges to zero asN \rightarrow \infty. The rates of convergence are also determined when the covariance sequence satisfies additional conditions.

The possibility of gaining storage space is an argument often advanced in favor of permitting question-answering systems to make occasional errors. Absolute bounds are established on the amount of memory savings that is achievable with a specified error level for certain types of question-answering systems. Question-answering systems are treated as communication channels carrying information concerning the acceptable answers to an admissible set of queries. Shannon's rate-distortion theory is used to calculate bounds on the memory required for several question-answering tasks. For data retrieval, pattern classification, and position-matching systems, it was found that only small memory gains could be materialized from error tolerance. In pair-ordering tasks, on the other hand, more significant memory savings could be accomplished if small error rates are tolerated.

We study the form assumed by the classical time-frequency uncertainty relations in discrete as well as nontrigonometric spectral analysis. In particular we find that if anN-sample time signal is to contain a fraction\gammaof its energy inTconsecutive samples, then the minimum number of frequency components containing that same energy fraction must be greater thanN/T(2\gamma - 1)^2. It is also found that the discrete Walsh transform permits greater energy concentration (less uncertainty) than the discrete Fourier transform.

This correspondence concerns real-time Fourier processing of stationary data and examines the widespread belief that coefficients of the discrete Fourier transform (DFT) are "almost" uncorrelated. We first show that any uniformly boundedN \times NToeplitz covariance matrixT_Nis asymptotically equivalent to a nonstandard circulant matrixC_Nderived from the DFT ofT_N. We then derive bounds on a normed distance betweenT_NandC_Nfor finiteN, and show that\mid T_N - C_N \mid ^ 2 = O(1/N)for finite-order Markov processes. Finally we demonstrate that the performance degradation resulting from the use of DFT (as opposed to Karhunen-Loève expansion) in coding and filtering is proportional to\mid T_N - C_N \midand therefore vanishes as the inverse square root of the block sizeNwhenN \rightarrow \infty.

This paper develops performance criteria for evaluating transform data coding schemes under computational constraints. Computational constraints that conform with the proposed basis-restricted model give rise to suboptimal coding efficiency characterized by a rate-distortion relationR(D)similar in form to the theoretical rate-distortion function. Numerical examples of this performance measure are presented for Fourier, Walsh, Haar, and Karhunen-Loève transforms.

This correspondence develops tools for comparative evaluation of the effectiveness of unitary transformations in signal processing applications. Performance measures for the tasks of optimal filters and optimal coding are exemplified, and measures of similarity among representations are proposed.

Harmonic analysis of probability distribution functions has long served an important function in the treatment of stochastic systems. The tasks of generating moments and distributions of sums have been effectively executed in the Fourier spectrum. The properties of the Walsh-Hadamard transform of probability functions of discrete random variables is explored. Many analogies can be drawn between Fourier and Walsh analysis. In particular, it is shown that moments can be generated taking the Gibb's derivative of the Walsh spectrum and that products of Walsh spectra yield the distribution of dyadic sums. Stochastic systems with dyadic symmetry would benefit most from the properties of Walsh analysis and the computational advantages it offers. Some applications in the areas of information theory and pattern recognition are demonstrated.