206567160
Special Feature: Prometheus or Pandora: The Influence of Automation on Society
Even though computer technology may challenge one of man's last and most cherished illusions—that he alone is capable of thought—it can also show him how to live in harmony with nature.
37804897
Directions for Qualitative Reasoning
Sacks & Doyle provide an excellent overview of the fundamental limitations of the SPQR representations for reasoning about the qualitative properties of dynamic systems. We take this opportunity to outline some new directions for qualitative reasoning. In this paper, we provide a rigorous mathematical characterization for the term “qualitative property” in the context of static and dynamic systems. Based on these characterizations, we show that interval representations are well suited for reasoning about the qualitative properties of static systems such as qualitative comparative statics and qualitative stability. Moreover, we also show that symbolic computations help in the derivation of useful global properties of dynamic systems which can be used to guide numerical sampling of differential equations. The integration of symbolic and numeric methods provides a powerful approach for automating the qualitative analysis of differential equations.
16243913
Experiments with a Heuristic Compiler
This report describes some experiments in constructing a compiler that makes use of heuristic problem~solving techniques such as those incorporated in the General Problem Solver (GPS) [1]. The experiments were aimed at the dual objectives of throwing light on some of the problems of constructing more powerful programming languages and compilers, and of testing whether the task of writing a computer program can be regarded as a "problem" in the sense in which that term is used in GPS. The present paper is concerned primarily with the second objective--with analyzing some of the problem-solving processes that are involved in writing computer programs. At the present stage of their development, no claims will be made for the heuristic programming procedures described here as practical approaches to the construction of compilers. Their interest lies in what they teach us about the nature of the programming task.
10043574
Scientific Model-Building as Search in Matrix Spaces
Many reported discovery systems build discrete models of hidden structure, properties, or processes in the diverse fields of biology, chemistry, and physics. We show that the search spaces underlying many well-known systems are remarkably similar when re-interpreted as search in matrix spaces. A small number of matrix types are used to represent the input data and output models. Most of the constraints can be represented as matrix constraints; most notably, conservation laws and their analogues can be represented as matrix equations. Typically, one or more matrix dimensions grow as these systems consider more complex models after simpler models fail, and we introduce a notation to express this. The novel framework of matrix-space search serves to unify previous systems and suggests how at least two of them can be integrated. Our analysis constitutes an advance toward a generalized account of model-building in science.
6846387
Causality and Model Abstraction
Abstract Much of science and engineering is concerned with characterizing processes by equations describing the relations that hold among parameters of objects and govern their behavior over time. In formal descriptions of processes in terms of parameters and equations, the notion of causality is rarely made explicit. Formal treatments of the foundations of sciences have avoided discussions of causation and spoken only of functional relations among variables. Nevertheless, the notion of causality plays an important role in our understanding of phenomena. Even when we describe the behavior of a system formally in terms of acausal, mathematical relations, we often give an informal, intuitive explanation of why the system behaves the way it does in terms of cause-effect relations. In this paper, we will present an operational definition of causal ordering. The definition allows us to extract causal dependency relations among variables implicit in a model of a system, when a model is represented as a set of acausal, mathematical relations. Our approach is based on the theory of causal ordering first presented by Simon [22]. The paper shows how to use the theory and its extension in reasoning about physical systems. Further, the paper studies the relation of the theory to the problems of model aggregation.
5581562
Computer science as empirical inquiry: symbols and search
Computer science is the study of the phenomena surrounding computers. The founders of this society understood this very well when they called themselves the Association for Computing Machinery. The machine—not just the hardware, but the programmed, living machine—is the organism we study.
28048643
Generalization of an Elementary Perceiving and Memorizing Machine
The Elementary Perceiver and Memorizer (EPAM) is a context, and contains sufficient information to retrieve the model of human associative memory and the processes of image of the stimulus from the association memory when human verbal learning, written in the list-processing language necessary. IPL-V. A generalization of the EPAM model (called EPAM The complex image building processes also provide an assoIII), based on earlier experiments on EPAM 11, has been dative mechanism by means of which earlier learning can formulated and programmed. usefully be brought to bear on later learning. New stimuli arc In EPAM 111. stimulus configurations and their internal learned by associating together and modifying images of images are allowed indefinite complexity of sub-parts. Complex stimuli already learned. The model is an attempt to resolve internal images are built by associating together, in list structhe problem of how meaningful learning differs from nontures, tokens for retrieving information about the sub-parts meaningful learning, from the association memory. Empirical explorations of the model are concerned generally The concatenation of tokens by the image building process with variations in behaviour as a result of varying stimulus allows for the association of stimuli in many different contexts. and response meaningfulness. The token signifies the occurrence of a stimulus in a particular 3.ieM6HTapHan nporpaMMa jhh "H3yqaioinHx MauaeT coSbiTHe CTHMyjia b oco66hhom KOHTeKCTe, a npiiuihh" (3IIJIHM (EPAM)) npeacTaß^weTCH Moaejibio cyTCTByeT b aaHHOM naineKe aocTaToiHO HHdpopMauHH, accouHaTHßiioil nfiMfiTH h npoueccoß H3yiemm mob <rro6bi BooCpawenHe CTHMyjia moskho 6mjio Bbißec" y iciOBCKa; saiman Mo,Te.-ib narmcaHa b bh«6 si3uko, hs accouHaTHßHofl naMHTH b tom cnyqae, eoJiH sto A-1H pa3paf)OTKH CnHCKOB IPL 15. Ha OCHOBaHHH OKaHCeTCH Heo6xo«HMbiM. pe3y.ibTaTon Go.ice paiiHHx nonwTOK cihopMHyjinpoCjioiKHbie npoueccw, no3Bo^aiouiHe EPAM 111 CO3Ba.iacb ii cnporpaHMHpoßa,iacb ooo6meHHaH Moae^b naßaTb BoofipasKeHHH, Taicwe 3anaxaioT accoimaTHBEPAM jiß.inioumncHTaX Ha3bißaeMoft EPAM 111. Hiiit MexaHH3M, npn noMoiiw KOToporo npeAbiAymne B EPAM 111, mc.no noaiacTefl KOMiuieKCHbix <~thonuTH MoryT 3<h<beKTHßHbiM o6pa3oM BJiHHTb Ha cnemv.iob h BiiyTpeiiHHx hx n3oGpan<eHHH MomeT decayroiiuie. Hoßbie CTHMyjiu H3yiaioTCfl b pe3yjibTaTe npe.ie.-n.no yc.iovKHfiTbcu. OioiKHbie BiiyTpeHHHe accoiiHpoßaHHtf (tbm caMMM h Mo«H<bHKau.HH) HsyienH3oopn>KeHHn-iiMeiomHeMHoroypoßHeflHH(})opMauHH hux panbine BOo6pajKeHHft. MoaeJib npeacTaßJineT o no.tCTpyuTypectpohtch cnocoSoM accouHHpoßaHHH coCoft nonbrricy peuiHTb 3a«aqy o tom, KaKHM oopa3OM 3iia«iKon miMRKOB, npw noMomH kotopux cBe^eHHH pa3JinqaTb 3HaiaromHe CBeaenHH ot He3HaiaiomHx. o no.macTnx mo>kho BUBO«HTb H3 accouHaTHßHofl 3MnHpmiecKHe onwTbi npoßOflHmnecH Ha Mo^e^b, naMtiTii. Boo6me roßopn, hmciot c paaHUMH BH«aMH noße-3auen.ieHne iiaMeKOB npoueccoM co3«aHHH boosaeHHn, npoHCxofIHWHMH H3 pa3HOBHfIHOCTH 3HaienHfi pn>Kenmi no3Bo.ineT accou.HHpoßaTb cTHMy^u, npoHCTHMy^a h oTBeTa. cxoanmiio H3 Miioro pa3Hbix kohtckctob. HaMeK 03HaLa machine elementaire pour percevoir et mettre en mblir Information concernant les sous-parties, a partir de la moire (EPAM) est un modele de la memoire humaine d'assomemoire dissociation. ciation. et dcs process de la facon humaine d'apprendre L'enchainement dcs signes au moyen de l'image eUabor^e verbalement, 6crit en langage IPL-V. En partant dcs r«sulpermet d'associer dcs excitations dans un grand nombre de tnts de tests anteVieurs, on a dlabore' et programme" une contextes diffe>ents. Le signe montre qu'il existe une excitagcneralisation dv modele EPAM, appele EPAM 111. tion dans un contexte particulier et une information suffisante Sur EPAM 111, les configurations d'excitation et les images peut, grace ace signe, regene>er l'image de I'excitation a inteneures de ces configurations ont une complexitc indefinie partir de la memoire dissociation, quand cela est necessaire. de sous-parlies. Dcs images internes complexes sont dlaborees Les procedis complexes gui 61aborent l'image fournissent en groupant. en liste de structures, les signes destine* a retaaussi un m6canisme dissociation, permettant d'elaborer faci405 IX, 1] automata theory lement la toute premiere information a partir de la toute informations ayant un sens, de celles gui n'en ont pas. derniere. Les tests empiriques dv modele se rapportent gene>alement On decouvre de nouvelles excitations en groupant (et en aux variations de fonctionnement, celles-ci £tant le resultat modifiant) les images d'excitations deja connues. Cc modele d'excitations et de reponses variables. est un essai de r6soudre le probleme de la differentiation dcs
42465992
History of Artificial Intelligence
Though our discussion is e n t i t l e d "The History o f A r t i f i c i a l I n te l l i gence" , i n fac t we are focusing here on one b r i e f but h igh ly s i gn i f i can t moment in that h i s t o r y , the moment when a r t metamorphosed i t s e l f i n to science, from wish and dream to something l i k e r e a l i t y . As you w i l l learn from each of the discussants, th is metamorphosis took place at several locat ions during the ear ly to mid-1950s, and i t s ca ta lys t was the recogni t ion that the computer was the most promising medium yet in which to rea l i ze what had been a human dream since ea r l i es t t imes, the creat ion of man-made, rather than begotten i n te l l i gence .
6041481
Parallel preconditioning and approximation inverses on the Connection Machine
The authors present a new approach to preconditioning for very large, sparse, non-symmetric, linear systems. It explicitly computes an approximate inverse to the original matrix that can be applied most efficiently for iterative methods on massively parallel machines. The algorithm and its implementation on the Connection Machine CM-2 are discussed in detail and supported by timings obtained from real problem data.<<ETX>>
17442679
Inner Product Spaces for Bayesian Networks
Bayesian networks have become one of the major models used for statistical inference. We study the question whether the decisions computed by a Bayesian network can be represented within a low-dimensional inner product space. We focus on two-label classification tasks over the Boolean domain. As main results we establish upper and lower bounds on the dimension of the inner product space for Bayesian networks with an explicitly given (full or reduced) parameter collection. In particular, these bounds are tight up to a factor of 2. For some nontrivial cases of Bayesian networks we even determine the exact values of this dimension. We further consider logistic autoregressive Bayesian networks and show that every sufficiently expressive inner product space must have dimension at least Ω(n2), where n is the number of network nodes. We also derive the bound 2Ω(n) for an artificial variant of this network, thereby demonstrating the limits of our approach and raising an interesting open question. As a major technical contribution, this work reveals combinatorial and algebraic structures within Bayesian networks such that known methods for the derivation of lower bounds on the dimension of inner product spaces can be brought into play.
31930258
How Many Missing Answers Can Be Tolerated by Query Learners?
We consider the model of exact learning using an equivalence oracle and an incomplete membership oracle. In this model, a random subset of the learners membership queries is left unanswered. Our results are as follows. First, we analyze the obvious method for coping with missing answers: search exhaustively through all possible "answer patterns" associated with the unanswered queries. Thereafter, we present two specific concept classes that are efficiently learnable using an equivalence oracle and a (completely reliable) membership oracle, but are provably not polynomially learnable if the membership oracle becomes slightly incomplete. The first class will demonstrate that the aforementioned method of exhaustively searching through all possible answer patterns cannot be substantially improved in general (despite its apparent simplicity). The second class will demonstrate that the incomplete membership oracle can be rendered useless even if it leaves only a fraction 1/poly(n) of all queries unanswered. Finally, we present a learning algorithm for monotone DNF formulas that can cope with a relatively large fraction of missing answers (more than sixty percent), but is as efficient (in terms of run-time and number of queries) as the classical algorithm whose questions are always answered reliably.