bluuebunny/crossref_metadata_2025 huggingface dataset:
Capturing high‐level structure of naturally occurring, extended explanations using bottom‐up strategies
Authors: Mooney David J. , Carberry Sandra , McCoy Kathleen F.
Published: April 2007

This paper notes some structural features of naturally occurring, extended explanations and argues that current generation methodologies are inadequate for determining high‐level structure. We then present a computational model for generating high‐level structure, which is based on the hypothesis that high‐level structure is distinct from text structure at lower levels and is determined by the material to be conveyed rather than by independent, recursive text structuring devices. We propose that high‐level structure can be determined by bottom‐up processes that attempt to satisfy speaker, listener, and compositional goals, after which top‐down strategies can be used to organize the material about the selected framework.

Cet article relève certaines caractéristiques structurales ?explications étendues à occurrence naturelle et soutient que les méthodes de génération courantes ne permettent pas de déterminer adéquatement une stratégie de haut niveau. Les auteurs présentent ensuite un modèle computationnel de géneration de structures de haut niveau qui est basé sur ľhypothèse qu'une structure de haut niveau est différente ?une structure de texte aux nivaux inféiieurs, et qu'elle est déterminée par les données qui doivent ětre transmises plutǒt que par des mécanismes indépendants et récursifs de structure de texte. lis soutiennent qu'une structure de haut niveau peut ětre déterminée àľaide ?'un processus ascendant qui essaie de rencontrer les objectifs du locuteur, de ľauditeur et de composition, et que des stratégies descendantes peuvent ensuite ětre utilisées pour organiser les données a propos du cadre choisi.
GENERATING TEXT WITHOUT TREES
Authors: Sibun Penelope
Published: April 2007

In this paper, I present an architecture for generating extended text. This architecture is implemented in a system, Salix, which incrementally generates natural language texts whose structure is derived from the domain structure of the subject matter. The architecture is composed of data‐driven, domain‐independent strategies for producing increments of text. The strategies include metastrategies that combine or choose among all strategies that are applicable at each increment or decide what to do if no strategy applies. Salix's capabilities are demonstrated in generating texts, in the domains of houses and families, that are comparable to descriptions elicited from human speakers. Salix has also been utilized to generate texts about text style (Germain 1991). The approach to text generation presented here is compared to others in the literature along the dimensions of local organization, coherence, focusing, and domain independence. An argument is made for the approach presented here that locally organizes and incrementally generates coherent text.
SOME NEGLECTED ASPECTS OF THE GENERATION TASK
Authors: Ward Nigel
Published: April 2007

Looking to the future, generators will have more knowledge of language and will have to deal with inputs that are very rich in information. As a result, several problems will become more acute, including selecting what to say at the subproposition level and dealing with interaction among goals and dependencies among choices. This paper explains how these problems arise and why they are hard to handle within traditional architectures for generation. It also discusses why these issues have not been well addressed, including the current lack of demanding applications, excessive emphasis on linguistic traditions, the use of reverse engineering to determine generator inputs, and the tendency to research only one issue at a time.
PROLEGOMENA TO ANY FUTURE PROLEGOMENA
Authors: Ginsberg Matthew L.
Published: April 2007

The paper by Sacks and Doyle that is the focus of this debate resembles previous papers by Cheeseman and McDermott, leaping from the observation that a specific application of some AI technology is unable to solve a problem to the conclusion that the technology itself is of limited value. We argue that claims such as this should be made more cautiously in the future, and make constructive suggestions about future qualitative physics research based on Sacks and Doyle's results.
USING DISTRIBUTION‐FREE LEARNING THEORY TO ANALYZE SOLUTION‐PATH CACHING MECHANISMS
Authors: Cohen William W.
Published: April 2007

Much research in machine learning has been focused on the problem of symbol‐level learning (SLL), or learning to improve the performance of a program given examples of its behavior on typical inputs. A common approach to symbol‐level learning is to use some sort of mechanism for saving and later reusing the solution paths used to solve previous search problems. Examples of such mechanisms are macro‐operator learning, explanation‐based learning, and chunking. However, experimental evidence that these mechanisms actually improve performance is inconclusive. This paper presents a formal framework for analysis of symbol‐level learning programs, and then uses this framework to investigate a series of solution‐path caching mechanisms which provably improve performance. The analysis of these mechanisms is illuminating in many respects; in particular, in order to obtain positive results, it is necessary to use a novel representation for a set of solution paths, and also to apply certain unusual optimizations to a set of solution paths. Several of the predictions made by the model have been confirmed by recently published experiments.
CONCEPTUAL SCAFFOLDING: A SPATIALLY FOUNDED MEANING REPRESENTATION FOR METAPHOR COMPREHENSION
Authors: Veale Tony , Keane Mark T.
Published: April 2007

Once viewed as a rhetorical and superficial language phenomenon, metaphor is now recognized to serve a fundamental role in our conceptual structuring and language comprehension processes. In particular, it is argued that certain experiential metaphors based upon intuitions of spatial relations are inherent in the conceptual organization of our most abstract thoughts. In this paper we present a two‐stage computational model of metaphor interpretation which employs a spatially founded semantics to broadly characterize the meaning carried by a metaphor in terms of a conceptual scaffolding, an interim meaning structure around which a fuller interpretation is fleshed out over time. We then present a semantics for the construction of conceptual scaffolding which is based upon core metaphors of collocation, containment and orientation. The goal of this scaffolding is to maintain the intended association of ideas even in contexts in which system knowledge is insufficient for a complete interpretation. This two‐stage system of scaffolding and elaboration also models the common time lapse between initial metaphor comprehension and full metaphor appreciation. Several mechanisms for deriving elaborative inference from scaffolding structures, particularly in cases of novel or creative metaphor, are also presented. While the system developed in this paper has significant practical application, it also demonstrates that core spatial metaphors clearly play a central role in metaphor comprehension.
CONVERSATION ACTS IN TASK‐ORIENTED SPOKEN DIALOGUE
Authors: Traum David R. , Hinkelman Elizabeth A.
Published: April 2007

A linguistic form's compositional, timeless meaning can be surrounded or even contradicted by various social, aesthetic, or analogistic companion meanings. This paper addresses a series of problems in the structure of spoken language discourse, including turn‐taking and grounding. It views these processes as composed of fine‐grained actions, which resemble speech acts both in resulting from a computational mechanism of planning and in having a rich relationship to the specific linguistic features which serve to indicate their presence. The resulting notion of Conversation Acts is more general than speech act theory, encompassing not only the traditional speech acts but turn‐taking, grounding, and higher‐level argumentation acts as well. Furthermore, the traditional speech acts in this scheme become fully joint actions, whose successful performance requires full listener participation. This paper presents a detailed analysis of spoken language dialogue. It shows the role of each class of conversation acts in discourse structure, and discusses how each class can be processed and recognized. Conversation acts, it will be seen, better account for the success of conversation than speech act theory alone. They also provide a pragmatic view of meaning in which the literal/non‐literal distinction is simply irrelevant.
MERGING SEPARATELY GENERATED PLANS WITH RESTRICTED INTERACTIONS
Authors: Yang Qiang , Nau Dana S. , Hendler James
Published: April 2007

Generating action sequences to achieve a set of goals is a computationally difficult task. When multiple goals are present, the problem is even worse. Although many solutions to this problem have been discussed in the literature, practical solutions focus on the use of restricted mechanisms for planning or the application of domain dependent heuristics for providing rapid solutions (i.e., domain‐dependent planning). One previously proposed technique for handling multiple goals efficiently is to design a planner or even a set of planners (usually domain‐dependent) that can be used to generate separate plans for each goal. The outputs are typically either restricted to be independent and then concatenated into a single global plan, or else they are merged together using complex heuristic techniques. In this paper we explore a set of limitations, less restrictive than the assumption of independence, that still allow for the efficient merging of separate plans using straightforward algorithmic techniques.

In particular, we demonstrate that for cases where separate plans can be individually generated, we can define a set of limitations on the allowable interactions between goals that allow efficient plan merging to occur. We propose a set of restrictions that are satisfied across a significant class of planning domains. We present algorithms that are efficient for special cases of multiple plan merging, propose a heuristic search algorithm that performs well in a more general case (where alternative partially ordered plans have been generated for each goal), and describe an empirical study that demonstrates the efficiency of this search algorithm.
THE TYPICALITY OF PHASE TRANSITIONS IN SEARCH
Authors: WILLIAMS COLIN , HOGG TAD
Published: April 2007

Search is fundamental to artificial intelligence (AI) and numerous sophisticated search methods have been developed. We present a general, simple model of search processes and use it to analytically determine some typical behavior when applied to large problems. In particular, this identifies abrupt changes in overall search cost as small improvements are made in the underlying method. We also examine the robustness of this model's predictions in a range of more realistic cases. More generally, we introduce a criterion for determining when average case results reflect typical behavior which allows the method developed here to be used for investigating other large‐scale behaviors of complex AI systems.
THE COMPUTATIONAL COMPLEXITY OF THE UNIVERSAL RECOGNITION PROBLEM FOR PARALLEL MULTIPLE CONTEXT‐FREE GRAMMARS
Authors: Kaji Yuichi , Nakanishi Ryuichi , Seki Hiroyuki , Kasami Tadao
Published: April 2007

A number of grammatical formalisms have been proposed to describe the syntax of natural languages, and the universal recognition problems for some of those classes of grammars have been studied. A universal recognition problem for a class Q of grammars is the one to decide, taking a grammar G ∈ G and a string ui as an input, whether G can generate w or not. In this paper, the computational complexities of the universal recognition problems for parallel multiple context‐free grammars, multiple context‐free grammars, and their subclasses are discussed.
LOGICAL EMBEDDED PUSH‐DOWN AUTOMATA IN TREE‐ADJOINING GRAMMAR PARSING
Authors: Johnson Mark
Published: April 2007

This paper extends the “parsing as deduction” approach to tree‐adjoining grammars by showing how a TAG recognition problem can be reduced to a Datalog deduction problem, and presents an SLD selection rule that makes the proof search correspond to a top‐down parse using the original grammar. Just as in the DCG extension of context‐free grammars, this approach permits nodes to be labeled with firsl‐order terms (rather than only atomic symbols). Finally the paper discusses implementation matters, and describes how the control rule can be efficiently implemented in Prolog.
HEAD‐CORNER PARSING FOR TAG
Authors: van Noord Gertjan
Published: April 2007

This paper describes a bidirectional head‐corner parser for (unification‐based versions of) lexicalized tree‐adjoining grammars.
A SEMANTIC HEAD‐DRIVEN GENERATION SYSTEM FOR FEATURE STRUCTURE TREE‐ADJOINING GRAMMARS
Authors: Kikui Gen‐ichiro
Published: April 2007

This paper describes a natural language generation system developed for a spoken language translation system. Our system employs Feature‐structure‐based Tree Adjoining Grammar (FTAG) for generation knowledge representation. Each elementary tree of our grammar is paired with a semantic feature structure which is consistent with semantics defined in Head‐driven Phrase Structure Grammar. Feature structures attached to nodes of elementary trees are unrestricted. Thus our formalism allows HPSG style phrase structure description as well as TAG style description. The advantage of our generation knowledge representation is the ability of incorporating HPSG style “core” grammar and TAG style case‐based grammar.

The system generates a syntactic tree by combining elementary trees so as to satisfy an input semantic structure. The generation algorithm is an application of a semantic head‐driven generation. To carry out an adjoining operation. an elementary tree with an adjunction node is dynamically split at the adjunction node during generation.
METABANK: A KNOWLEDGE‐BASE OF METAPHORIC LANGUAGE CONVENTIONS
Authors: Martin James H.
Published: April 2007

The frequent and conventional use of nonliteral language has been a major stumbling block for natural language processing systems since the early machine translation efforts. Metaphor, metonymy, and indirect speech acts are among the most troublesome phenomena. Recent computational efforts addressing these problems have taken an approach that emphasizes the use of systematic knowledge about nonliteral language conventions. We are currently engaged in an effort to supply this knowledge in the case of conventional metaphor. We are constructing MetaBank: an empirically derived and theoretically motivated knowledge‐base of English metaphorical conventions. This article describes our three‐part approach to the construction of MetaBank: the collection of on‐line textual resources and databases of linguistic generalizations, the development of a methodology for analyzing these resources, and the construction of a knowledge‐base based on the preceding analyses.
REASONING WITH BACKGROUND KNOWLEDGE–A THREE‐LEVEL THEORY
Authors: Zadrozny Wlodek
Published: April 2007

We address the problem of reasoning in cases when knowledge bases containing background knowledge are understood not as sets of formulas (rules and facts) but as collections of partially ordered theories. In our system, the usual, two‐part logical structures, consisting of a metalevel and an object level, are augmented by a third level–a referential level. The referential level is a partially ordered collection of theories; it encodes background knowledge. As usual, current situations are described on the object level, and the metalevel is a place for rules that can eliminate some of the models permitted by the object level and the referential level. As a logic of reasoning the system generalizes the standard model of a rational agent: deducing actions and deriving new information about the world from a logical theory–its knowledge base. It is a natural logical system in which priorities on the possible readings of predicates, not special rules of inference, are the main source of nonmonotonicity. We introduce a theory forming operator PT(x) to exploit the priorities, and we investigate its basic logical properties. Then we show how such a system can be augmented by metarules. Although this paper concentrates on basic logical properties of the new theory, this formalism has already been applied to model a number of natural language phenomena such as the notion of text coherence, Gricean maxims, vagueness, and a few others. The paper also briefly compares it with the model of background knowledge of CYC, as proposed by Lenat and Guha.
CORRECTING REAL‐WORD SPELLING ERRORS USING A MODEL OF THE PROBLEM‐SOLVING CONTEXT
Authors: Ramshaw Lance A.
Published: April 2007

This paper explores the application of a rich model of pragmatic context to the problem of identifying and correcting real‐word spelling errors. Results suggest that such a model can be useful for generating and ranking a list of possible corrections according to their contextual relevance. In the domain of expert consultation discourse, a mode! of pragmatic context must represent not only the user's domain plans, but also the problem‐solving processes that explore alternative plans, refining and instantiating the intended plan, and the connections between those problem‐solving moves and their resulting discourse manifestations. In the model presented, metaplans are used to represent these problem‐solving and discourse levels, while heuristics that take into account the user's problem‐solving strategies and world knowledge serve to rank the relative likelihood of different possible next queries. An implementation of this model has been used to suggest pragmatically coherent interpretations that can be matched against a partial parse of the input in order to generate possible corrections for real‐word spelling errors.
EXPLOITING CAUSAL STRUCTURE TO CONTROL RETRIEVAL AND REFITTING DURING PLAN REUSE
Authors: Kambhampati Subbarao
Published: April 2007

The ability to reuse existing plans to solve new planning problems can enable a domain‐independent planner to improve its average case efficiency by exploiting the problem distribution and avoiding repetition of planning effort. The pay‐off from plan reuse, however, crucially depends on finding effective solutions to two important underlying control problems: (i) controlling the retrieval of an appropriate plan and mapping to be reused in a new situation, and (ii) controlling the modification (refitting) of the retrieved plan so as to minimize perturbation to the applicable parts of the plan. This paper is concerned with the development of efficient domain‐independent solutions to these two problems. For the retrieval, it provides a domain independent similarity metric that utilizes the plan causal dependency structure to estimate the utility of reusing a given plan in a new problem situation. For the refitting, it presents a minimum‐conflict heuristic, again based on the causal dependency structure of the plan, to conservatively control the modification. The paper also discusses the implementation and evaluation of these strategies within the PRIAR plan modification framework.
LEARNING BAYESIAN BELIEF NETWORKS: AN APPROACH BASED ON THE MDL PRINCIPLE
Authors: Lam Wai , Bacchus Fahiem
Published: April 2007

A new approach for learning Bayesian belief networks from raw data is presented. The approach is based on Rissanen's minimal description length (MDL) principle, which is particularly well suited for this task. Our approach does not require any prior assumptions about the distribution being learned. In particular, our method can learn unrestricted multiply‐connected belief networks. Furthermore, unlike other approaches our method allows us to trade off accuracy and complexity in the learned model. This is important since if the learned model is very complex (highly connected) it can be conceptually and computationally intractable. In such a case it would be preferable to use a simpler model even if it is less accurate. The MDL principle offers a reasoned method for making this trade‐off. We also show that our method generalizes previous approaches based on Kullback cross‐entropy. Experiments have been conducted to demonstrate the feasibility of the approach.
ABDUCTION and EXPLANATION‐BASED LEARNING: CASE STUDIES IN DIVERSE DOMAINS
Authors: O'Rorke Paul
Published: April 2007

This paper presents a knowledge‐based learning method and reports on case studies in different domains. The method integrates abduction and explanation‐based learning. Abduction provides an improved method for constructing explanations. The improvement enlarges the set of examples that can be explained so that one can learn from additional examples using traditional explanation‐based macro learning. Abduction also provides a form of knowledge level learning. Descriptions of case studies show how to set up abduction engines for tasks in particular domains. The case studies involve over a hundred examples taken from diverse domains requiring logical, physical, and psychological knowledge and reasoning. The case studies are relevant to a wide range of practical tasks including natural language understanding and plan recognition; qualitative physical reasoning and postdiction; diagnosis and signal interpretation; and decision making under uncertainty. The descriptions of the case studies include an example, its explanation, and discussions of what is learned by macro‐learning and by abductive inference. The paper discusses how to provide and represent the domain knowledge and meta‐knowledge needed for abduction and search control. The main conclusion is that abductive inference is important for learning. Abduction and macro‐learning are complementary and synergistic.
VAGUENESS AND UNCERTAINTY: A ROUGH SET PERSPECTIVE
Authors: Pawlak Zdzislaw
Published: April 2007

Vagueness and uncertainty have attracted the attention of philosophers and logicians for many years. Recently, AI researchers contributed essentially to this area of research. Fuzzy set theory and the theory of evidence are seemingly the most appealing topics. On this note we present a new approach, based on the rough set theory, for looking to these problems. The theory of rough sets seems a suitable mathematical tool for dealing with problems of vagueness and uncertainty. This paper is a modified version of the author's lecture titled “An inquiry into vagueness and uncertainty,” which was delivered at the AI Conference in Wigry (Poland), 1994.
THE USEFULNESS OF A MACHINE LEARNING APPROACH TO KNOWLEDGE ACQUISITION
Authors: Grzymala‐Busse Dobroslawa M. , Grzymala‐Busse Jerzy W.
Published: April 2007

This paper presents results of experiments showing how machine learning methods arc useful for rule induction in the process of knowledge acquisition for expert systems. Four machine learning methods were used: ID3, ID3 with dropping conditions, and two options of the system LERS (Learning from Examples based on Rough Sets): LEM1 and LEM2. Two knowledge acquisition options of LERS were used as well. All six methods were used for rule induction from six real‐life data sets. The main objective was to lest how an expert system, supplied with these rule sets, performs without information on a few attributes. Thus an expert system attempts to classify examples with all missing values of some attributes. As a result of experiments, it is clear that all machine learning methods performed much worse than knowledge acquisition options of LERS. Thus, machine learning methods used for knowledge acquisition should be replaced by other methods of rule induction that will generate complete sets of rules. Knowledge acquisition options of LERS are examples of such appropriate ways of inducing rules for building knowledge bases.
ESTIMATING DBLEARN'S POTENTIAL FOR KNOWLEDGE DISCOVERY IN DATABASES
Authors: Hamilton Howard J. , Fudger David R.
Published: April 2007

We propose a procedure for estimating DBLEARN's potential for knowledge discovery, given a relational database and concept hierarchies. This procedure is most useful for evaluating alternative concept hierarchies for the same database. The DBLEARN knowledge discovery program uses an attribute‐oriented inductive‐inference method to discover potentially significant high‐level relationships in a database. A concept forest, with at most one concept hierarchy for each attribute, defines the possible generalizations that DBLEARN can make for a database. The potential for discovery in a database is estimated by examining the complexity of the corresponding concept forest. Two heuristic measures are defined based on the number, depth, and height of the interior nodes. Higher values for these measures indicate more complex concept forests and arguably more potential for discovery. Experimental results using a variety of concept forests and four commercial databases show that in practice both measures permit quite reliable decisions to be made; thus, the simplest may be most appropriate.
ROUGH SET REDUCTION OF ATTRIBUTES AND THEIR DOMAINS FOR NEURAL NETWORKS
Authors: Jelonek Jacek , Krawiec Krzysztof , Slowiński Roman
Published: April 2007

This paper presents an empirical study of the use of the rough set approach to reduction of data for a neural network classifying objects described by quantitative and qualitative attributes. Two kinds of reduction are considered: reduction of the set of attributes and reduction of the domains of attributes. Computational tests were performed with five data sets having different character, for original and two reduced representations of data. The learning time acceleration due to data reduction is up to 4.72 times. The resulting increase of misclassification error does not exceed 11.06%. These promising results let us claim that the rough set approach is a useful tool for preprocessing of data for neural networks.
PRIMEROSE: PROBABILISTIC RULE INDUCTION METHOD BASED ON ROUGH SETS AND RESAMPLING METHODS
Authors: Tsumoto S. , Tanaka H.
Published: April 2007

Automated knowledge acquisition is an important research issue in machine learning. Several methods of inductive learning, such as ID3 family and AQ family, have been applied to discover meaningful knowledge from large databases and their usefulness is assured in several aspects. However, since their methods are of a deterministic nature and the reliability of acquired knowledge is not evaluated statistically, these methods are ineffective when applied to domains essentially probabilistic in nature, such as medical domains. Extending concepts of rough set theory to a probabilistic domain, we introduce a new approach to knowledge acquisition, which induces probabilistic rules based on rough set theory (PRIMEROSE) and develop a program that extracts rules for an expert system from a clinical database, using this method. The results show that the derived rules almost correspond to those of the medical experts.
QUANTIFICATION OF UNCERTAINTY IN CLASSIFICATION RULES DISCOVERED FROM DATABASES
Authors: Xiang Y. , Wong S. K. M. , Cercone N.
Published: April 2007

We apply rough set constructs to inductive learning from a database. A design guideline is suggested, which provides users the option to choose appropriate attributes, for the construction of data classification rules. Error probabilities for the resultant rule are derived. A classification rule can be further generalized using concept hierarchies. The condition for preventing overgeneralization is derived. Moreover, given a constraint, an algorithm for generating a rule with minimal error probability is proposed.
AN EPISTEMIC LOGIC WITH QUANTIFICATION OVER NAMES
Authors: Haas Andrew R.
Published: April 2007

Sentential theories of belief hold that propositions (the things that agents believe and know) are sentences of a representation language. To analyze quantification into the scope of attitudes, these theories require a naming map a function that maps objects to their names in the representation language. Epistemic logics based on sentential theories usually assume a single naming map, which is built into the logic. I argue that to describe everyday knowledge, the user of the logic must be able to define new naming maps for particular problems. Since the range of a naming map is usually an infinite set of names, defining a map requires quantification over names. This paper describes an epistemic logic with quantification over names, presents a theorem‐proving algorithm based on translation to first‐order logic, and proves soundness and completeness. The first version of the logic suffers from the problem of logical omniscience; a second version avoids this problem, and soundness and completeness are proved for this version also.
PLANNING TO FIND THE REFERENTS OF NOUN PHRASES
Authors: Haas Andrew R.
Published: April 2007

Finding the referent of a definite noun phrase is a classic problem in natural language processing. Most work assumes that when a program begins to analyze an utterance, it already has the knowledge it needs for identifying referents. If a robot accepts commands in natural language, this assumption may not hold. Suppose a user says, “Go get the book on the table in room 3,” but the robot has never been in room 3, so it lacks the knowledge it needs to identify the referent of “the book on the table in room 3.” To gain this knowledge, the robot must travel to room 3 and search. This article describes a simulated robot that accepts commands in English and actively searches for the referents of definite descriptions.
KNOWLEDGE‐BASED FEATURE DISCOVERY FOR EVALUATION FUNCTIONS
Authors: Fawcett Tom E.
Published: April 2007

Since Samuel's work on checkers over thirty years ago, much effort has been devoted to learning evaluation functions. However, all such methods are sensitive to the feature set chosen to represent the examples. If the features do not capture aspects of the examples significant for problem solving, the learned evaluation function may be inaccurate or inconsistent. Typically, good feature sets are carefully handcrafted and a great deal of time and effort goes into refining and tuning them. This paper presents an automatic knowledge‐based method for generating features for evaluation functions. The feature set is developed iteratively: features are generated, then evaluated, and this information is used to develop new features in turn. Both the contribution of a feature and its computational expense are considered in determining whether and how to develop it further.

This method has been applied to two problem‐solving domains: the Othello board game and the domain of telecommunications network management. Empirical results show that the method is able to generate many known features and several novel features and to improve concept accuracy in both domains.
LEARNING OF RESOURCE ALLOCATION STRATEGIES FOR GAME PLAYING
Authors: Markovitch Shaul , Sella Yaron
Published: April 2007

Human chess players exhibit a large variation in the amount of time they allocate for each move. Yet, the problem of devising resource allocation strategies for game playing has not received enough attention. In this paper we present a framework for studying resource allocation strategies. We define allocation strategy and identify three major types of strategies: static, semi‐dynamic, and dynamic. We then describe a method for learning semi‐dynamic strategies from self‐generated examples. We present an algorithm for assigning classes to the examples based on the utility of investing extra resources. The method was implemented in the domain of checkers, and experimental results show that it is able to learn strategies that improve game‐playing performance.
A PLANNING APPROACH TO DECLARER PLAY IN CONTRACT BRIDGE
Authors: Smith S. J. J. , Nau D. S. , Throop T. A.
Published: April 2007

Although game‐tree search works well in perfect‐information games, it is less suitable for imperfect‐information games such as contract bridge. The lack of knowledge about the opponents’ possible moves gives the game tree a very large branching factor, making it impossible to search a significant portion of this tree in a reasonable amount of time.

This paper describes our approach for overcoming this problem. We represent information about bridge in a task network extended to represent multi‐agency and uncertainty. Our game‐playing procedure uses this task network to generate game trees in which the set of alternative choices is determined not by the set of possible actions, but by the set of available tactical and strategic schemes.

We have tested this approach on declarer play in the game of bridge, in an implementation called Tignum 2. On 5000 randomly generated notrump deals, Tignum 2 beat the strongest commercially available program by 1394 to 1302, with 2304 ties. These results are statistically significant at the α= 0.05 level. Tignum 2 searched an average of only 8745.6 moves per deal in an average time of only 27.5 seconds per deal on a Sun SPARCstation 10. Further enhancements to Tignum 2 are currently underway.
PERFECT RECALL AND PRUNING IN GAMES WITH IMPERFECT INFORMATION1
Authors: Blair Jean R. S. , Mutchler David , van Lent Michael
Published: April 2007

Games with imperfect information are an interesting and important class of games. They include most card games (e.g., bridge and poker) as well as many economic and political models. Here we investigate algorithms for findi ng the simplest form of a solution (a pure‐strategy equilibrium point) to imperfect information games expressed in their extensive (game tree) form. We introduce to the artificial intelligence community a classic algorithm, due to Wilson, that solves one‐player games with perfect recall. Wilson's algorithm, which we call iMP‐minimax, runs in time linear in the size of the game‐tree searched. In contrast to Wilson's result, Koller and Meggido have shown that finding a pure‐strategy equilibrium point in one‐player games without perfect recall is NP‐hard. Here, we provide another contrast to Wilson's result–we show that in games with perfect recall but more than one player, finding a pure‐strategy equilibrium point, given that such an equilibrium point exists, is NP‐hard.

Our second contribution is to present a pruning technique for Wilson's IMP‐minimax algorithm to make the latter more tractable. We call this new algorithm IMP‐alpha‐beta. We provide a theoretical framework (model) and analyze IMP‐alpha‐beta in that model. IMP‐alpha‐beta is of direct value for one‐player, perfect‐recall games. It also has strong potential for other imperfect information games, as it is a natural (but as yet untested) heuristic in those cases.
ON TEMPORAL DEDUCTIVE DATABASES
Authors: Orgun Mehmet A.
Published: April 2007

This article introduces a temporal deductive database system featuring a logic programming language and an algebraic front‐end. The language, called Temporal DATALOG, is an extension of DATALOG based on a linear‐time temporal logic in which the flow of time is modeled by the set of natural numbers. Programs of Temporal DATALOG are considered as temporal deductive databases, specifying temporal relationships among data and providing base relations to the algebraic front‐end. The minimum model of a given Temporal DATALOG program is regarded as the temporal database the program models intensionally. The algebraic front‐end, called TRA, is a point‐wise extension of the relational algebra upon the set of natural numbers. When needed during the evaluation of TRA expressions, slices of temporal relations over intervals can be retrieved from a given temporal deductive database by bottom‐up evaluation strategies.

A modular extension of Temporal DATALOG is also proposed, through which temporal relations created during the evaluation of TRA expressions may be fed back to the deductive part for further manipulation. Modules therefore enable the algebra to have full access to the deductive capabilities of Temporal DATALOG and to extend it with nonstandard algebraic operators. This article also shows that the temporal operators of TRA can be simulated in Temporal DATALOG by program clauses.
EFFICIENT TEMPORAL REASONING IN THE CACHED EVENT CALCULUS
Authors: Chittaro L. , Montanari A.
Published: April 2007

This article deals with the problem of providing Kowalski and Sergot's event calculus, extended with context dependency, with an efficient implementation in a logic programming framework. Despite a widespread recognition that a positive solution to efficiency issues is necessary to guarantee the computational feasibility of existing approaches to temporal reasoning, the problem of analyzing the complexity of temporal reasoning programs has been largely overlooked. This article provides a mathematical analysis of the efficiency of query and update processing in the event calculus and defines a cached version of the calculus that (i) moves computational complexity from query to update processing and (ii) features an absolute improvement of performance, because query processing in the event calculus costs much more than update processing in the proposed cached version.
Rational Underdevelopment*
Authors: Desmet Klaus , Ortuño Ortín Ignacio
Published: April 2007

We propose a two‐region two‐sector model of uneven development, where technological change benefits either the lagging or the leading region. In this framework interregional transfers may lead to persistent underdevelopment; by raising wages, transfers reduce the chance of the backward region adopting a new technology and taking off. Due to uncertainty about which region benefits from technological change, the backward region may rationally choose to remain underdeveloped, while the advanced region continues to pay transfers. The model provides a rationale for cases, such as Italy's Mezzogiorno, where the same rich region subsidizes the same poor region on a continuous basis.
Estimating Mortality in War‐Time Iraq: A Controversial Survey with Important Lessons for Students
Authors: De Maio Fernando
Published: April 2007

In teaching introductory quantitative methods in sociology, I have used a controversial survey of mortality in Iraq before and after the 2003 invasion to highlight to students the power of simple questionnaires, the role of ambiguity in statistics and the place of politics in the framing of statistical results. This brief report summarizes Roberts et al.'s (2004) estimate that the invasion of Iraq resulted in 98,000 (95% CI = 8000–194,000) deaths, as well as the intriguing reaction that the survey received in the press. Statistics teachers should find the Roberts et al. study to be an effective way to introduce students to more controversial – and political – aspects of statistical research.
The inclusion record of fluid evolution, crack healing and trapping from a heterogeneous system during rapid cooling of pegmatitic veins (Dronning Maud Land; Antarctica)
Authors: ENGVIK A. K. , STÖCKHERT B.
Published: April 2007

Granitoid (pegmatite and aplite) veins in metamorphic rocks and intrusive syenites of central Dronning Maud Land, Antarctica, are flanked by conspicuous light‐coloured alteration halos, which represent the damage zone of fracture propagation. The damage zone is characterized by a high density of sealed or healed microcracks, about 1 order of magnitude above background. Fluid inclusions along healed microcracks in quartz of both pegmatite and alteration halos are inspected by optical and scanning electron microscopy, and their composition is analysed by microthermometry and quadrupole mass spectrometry. The similar inclusion record in the granitoid vein and in the damaged host rock indicates the derivation of the fluids from the hydrous melt phase. The aqueous inclusions bear abundant daughter crystals, mainly silicates, and may represent a hydrous melt. The volatile composition is variable in the system H2O–CO2, with mostly subordinate amounts of N2. Phase separation with partitioning of CO2 into the fluid phase coexisting with the hydrous melt, and possibly immiscibility in the subsolidus range, govern fluid evolution during cooling. The variable CO2/N2 ratio suggests mixing with fluids from an external source in the host rock and vigorous circulation at an early stage of high transient permeability. Experiments have shown that healing of microcracks at high temperatures is a matter of hours to weeks, hence similar in time scale to the cooling of the cm‐ to dm‐thick granitoid veins. In this case, rapid cooling and concomitant crack healing in a system undergoing phase separation causes a broad compositional variability of the inclusions due to necking down, and the underpressure developing in closed compartments precludes a meaningful thermobarometric interpretation.
Gap‐junction blocker carbenoxolone differentially enhances NMDA‐induced cell death in hippocampal neurons and astrocytes in co‐culture
Authors: Zündorf Gregor , Kahlert Stefan , Reiser Georg
Published: April 2007

The beneficial or detrimental role of gap junction communication in the pathophysiology of brain injury is still controversial. We used co‐cultures of hippocampal astrocytes and neurons, where we identified homocellular astrocyte–astrocyte and heterocellular astrocyte–neuron coupling by fluorescence recovery after photobleaching, which was decreased by the gap junction blocker carbenoxolone (CBX). In these cultures, we determined the cell type‐specific effects of CBX on the excitotoxic damage caused byN‐methyl‐d‐aspartate (NMDA). We determined in both astrocytes and neurons the influence of CBX, alone or together with NMDA challenge, on cytotoxicity using propidium iodide labeling. CBX alone was not cytotoxic, but CBX treatment differentially accelerated the NMDA‐induced cell death in both astrocytes and neurons. In addition, we measured mitochondrial potential using rhodamine 123, membrane potential using the oxonol dye bis(1,3‐diethylthiobarbituric acid)trimethine oxonol, cytosolic Ca2+level using fura‐2, and formation of reactive oxygen species (ROS) using dihydroethidium. CBX alone induced neither an intracellular Ca2+rise nor a membrane depolarization. However, CBX elicited a mitochondrial depolarization in both astrocytes and neurons and increased the ROS formation in neurons. In contrast, NMDA caused a membrane depolarization in neurons, coinciding with intracellular Ca2+rise, but neither mitochondrial depolarization nor ROS production seem to be involved in NMDA‐mediated cytotoxicity. Pre‐treatment with CBX accelerated the NMDA‐induced membrane depolarization and prevented the repolarization of neurons after the NMDA challenge. We hypothesize that these effects are possibly mediated via blockage of gap junctions, and might be involved in the mechanism of CBX‐induced acceleration of excitotoxic cell death, whereas the CBX‐induced mitochondrial depolarization and ROS formation are not responsible for the increase in cytotoxicity. We conclude that both in astrocytes and neurons gap junctions provide protection against NMDA‐induced cytotoxicity.
Dexamethasone suppresses monocyte chemoattractant protein‐1 production via mitogen activated protein kinase phosphatase‐1 dependent inhibition of Jun N‐terminal kinase and p38 mitogen‐activated protein kinase in activated rat microglia
Authors: Zhou Yan , Ling Eng‐Ang , Dheen S. Thameem
Published: April 2007

Microglial cells release monocyte chemoattractant protein‐1 (MCP‐1) which amplifies the inflammation process by promoting recruitment of macrophages and microglia to inflammatory sites in several neurological diseases. In the present study, dexamethasone (Dex), an anti‐inflammatory and immunosuppressive drug has been shown to suppress the mRNA and protein expression of MCP‐1 in activated microglia resulting in inhibition of microglial migration. This has been further confirmed by the chemotaxis assay which showed that Dex or MCP‐1 neutralization with its antibody inhibits the microglial recruitment towards the conditioned medium of lipopolysaccharide (LPS)‐treated microglial culture. This study also revealed that the down‐regulation of the MCP‐1 mRNA expression by Dex in activated microglial cells was mediated via mitogen‐activated protein kinase (MAPK) pathways. It has been demonstrated that Dex inhibited the phosphorylation of Jun N‐terminal kinase (JNK) and p38 MAP kinases as well as c‐jun, the JNK substrate in microglia treated with LPS. The involvement of JNK and p38 MAPK pathways in induction of MCP‐1 production in activated microglial cells was confirmed as there was an attenuation of MCP‐1 protein release when microglial cells were treated with inhibitors of JNK and p38. In addition, Dex induced the expression of MAP kinase phosphatase‐1 (MKP‐1), the negative regulator of JNK and p38 MAP kinases in microglial cells exposed to LPS. Blockade of MKP‐1 expression by triptolide enhanced the phosphorylation of JNK and p38 MAPK pathways and the mRNA expression of MCP‐1 in activated microglial cells treated with Dex. In summary, Dex inhibits the MCP‐1 production and subsequent microglial cells migration to the inflammatory site by regulating MKP‐1 expression and the p38 and JNK MAPK pathways. This study reveals that the MKP‐1 and MCP‐1 as novel mediators of biological effects of Dex may help developing better therapeutic strategies for the treatment of patients with neuroinflammatory diseases.
“Missing Pieces”—A Study of Postpartum Feelings
Authors: Affonso Dyanne D.
Published: April 2007

ABSTRACT: A study of postpartal women revealed components of their childbirth experience have been perceived to be missing. Behavioral manifestations and situations which make women vulnerable to encountering “missing pieces” are described. Suggestions are made to help women reconstruct the childbirth experience into a meaningful whole.
Congenital Malformation: Teratogenic Foods and Additives
Authors: Streitfeld Pamela Port
Published: April 2007

ABSTRACT: The principles and research problems of teratology as related to foods and additives are reviewed. A report is made of the medical literature on teratogenicity of caffeine, nitrosamines, fungal metabolites (aflatoxins), potato blight, artificial sweeteners, Red dye no. 2, and alcohol. Some research problems in teratogenicity of foods and additives are discussed.
MOM Survey: Maternity Options for Mothers—What Do Women Want in Maternity Care?
Authors: Scaer Roberta , Korte Diana
Published: April 2007

ABSTRACT: As part of planning a new maternity wing of a Boulder, Colorado hospital, a telephone interview survey of 645 women who delivered within one year at this hospital was made to determine their preferences for 49 different options in maternity care. The sample was divided into 210 women chosen at random, 230 from La Leche League groups, and 205 women from prepared childbirth classes. The most important areas of concern to these new mothers were similar in all three groups and revolved around maintaining family closeness and obtaining help from hospital staff rather than desire for new or different facilities. Proposals resulting from this study were for the new maternity service to provide 1) combined labor‐delivery‐recovery rooms; 2) most post‐partum rooms to be private; 3) father unrestricted in visiting throughout; 4) sibling visitation; 5) inservice training for medical and nursing staff in childbirth and breastfeeding techniques; 6) family‐centered cesarean births; 7) alternative birth arrangement with early discharge.
A Study of Timing of First Solid Foods: Comparison of Breast‐ and Bottlefeeding Mothers
Authors: Auerbach Kathleen G.
Published: April 2007

ABSTRACT: A study of the timing of first solid foods in the infant diet reveals significant differences, with bottlefeeding mothers more likely to add solid foods prior to the infant's third month than breastfeeding mothers. In addition, the type of food used was related to the timing of its introduction, with bottlefeeding mothers more likely than breastfeeding women to use commercially prepared baby foods rather than home‐prepared foods. Although recommendations by established pediatric societies caution against the too‐early introduction of solid foods at the expense of the amount of milk received, these recommendations have not yet filtered down to a number of parents, especially those who bottlefeed their infants.