Data encodings and their costs

Summary This paper is devoted to developing and studying a precise notion of the encoding of a logical data structure in a physical storage structure, that is motivated by considerations of computational efficiency. The development builds upon the notion of an encoding of one graph in another. The cost of such an encoding is then defined so as to reflect the structural compatibility of the two graphs, the (externally specified) costs of implementing the host graph, and the (externally specified) set of intended usage patterns of the guest graph. The stability of the constructed framework is demonstrated in terms of a number of results; the faithfulness of the formalism is argued in terms of a number of examples from the literature; and the tractability of the model is hinted at by several results and by further references to the literature.     

Recognition of handwritten musical notes by a modified Neocognitron

A neural network for recognition of handwritten musical notes, based on the well-known Neocognitron model, is described. The Neocognitron has been used for the what pathway (symbol recognition), while contextual knowledge has been applied for the where (symbol placement). This way, we benefit from dividing the process for dealing with this complicated recognition task. Also, different degrees of intrusiveness in learning have been incorporated in the same network: More intrusive supervised learning has been implemented in the lower neuron layers and less intrusive in the upper one. This way, the network adapts itself to the handwriting of the user. The network consists of a 13×49 input layer and three pairs of simple and complex neuron layers. It has been trained to recognize 20 symbols of unconnected notes on a musical staff and was tested with a set of unlearned input notes. Its recognition rate for the individual unseen notes was up to 93%, averaging 80% for all categories. These preliminary results indicate that a modified Neocognitron could be a good candidate for identification of handwritten musical notes.     

Crypt-equivalent algebraic specifications

Summary Equivalence is a fundamental notion for the semantic analysis of algebraic specifications. In this paper the notion of crypt-equivalence is introduced and studied w.r.t. two loose approaches to the semantics of an algebraic specification T: the class of all first-order models of T and the class of all term-generated models of T. Two specifications are called crypt-equivalent if for one specification there exists a predicate logic formula which implicitly defines an expansion (by new functions) of every model of that specification in such a way that the expansion (after forgetting unnecessary functions) is homologous to a model of the other specification, and if vice versa there exists another predicate logic formula with the same properties for the other specification. We speak of first-order crypt-equivalence if this holds for all first-order models, and of inductive crypt-equivalence if this holds for all term-generated models. Characterizations and structural properties of these notions are studied. In particular, it is shown that first order crypt-equivalence is equivalent to the existence of explicit definitions and that in case of positive definability two first-order crypt-equivalent specifications admit the same categories of models and homomorphisms. Similarly, two specifications which are inductively crypt-equivalent via sufficiently complete implicit definitions determine the same associated categories. Moreover, crypt-equivalence is compared with other notions of equivalence for algebraic specifications: in particular, it is shown that first-order cryptequivalence is strictly coarser than abstract semantic equivalence and that inductive crypt-equivalence is strictly finer than inductive simulation equivalence and implementation equivalence.     

The dynamic clusters method in nonhierarchical clustering

Given a finite setE R ⁿ, the problem is to find clusters (or subsets of similar points inE) and at the same time to find the most typical elements of this set. An original mathematical formulation is given to the problem. The proposed algorithm operates on groups of points, called samplings (samplings may be called multiple centers or cores); these samplings adapt and evolve into interesting clusters. Compared with other clustering algorithms, this algorithm requires less machine time and storage. We provide some propositions about nonprobabilistic convergence and a sufficient condition which ensures the decrease of the criterion. Some computational experiments are presented.     

A Dialogue with C. West Churchman

In 1996, the author attended a seminar on ethics given by C. West Churchman at the University of California, Berkeley. During that year, the author also interviewed Churchman several times regarding the future direction of information sciences in general and the information systems research field in particular. This article is a compilation of the seminar and the interviews. It is set in the context of both Churchman's earlier and his current views of a global god, good, kindness, and caring. C. West Churchman holds that global ethics should lead to the study and design of information systems to solve large and difficult problems of the humankind such as poverty, crime and disease. His Global Ethical Management (GEM) of information sciences translates into abandoning the current goals and boundaries of the information sciences fields and changing what constitutes valid research to globally ethical endeavors.     

A model for pattern perception with musical applications part I: Pitch structures as order-preserving maps

The initial five papers of this series on pattern perception treat first, the perception of pitch in musical contexts and then, the perception of timbre and speech. Each sound is considered to be embedded in a context consisting of those sounds which surround it or coincide with it. The apprehension of a musical pattern depends upon the perceptibility of certain relations between, and properties of, its parts (e.g. motifA is similar to motifB or G is the tonic). It is hypothesized that, because of the limitations of short term memory, the perception of specific relations and properties requires that certain mental reference frames be extracted from the various contexts. However, a reference frame which supports the perception of any specified relation may be extracted from only very few of all possible contexts. The choices of musical materials in both Western and non-Western music are shown to avoid precisely such difficulties. When they are not avoided, distortions of perception are predicted and methods for experimental verification are suggested. This theory is then applied to suggest new materials for the composition of both microtonal and tonecolor music. This is done in a manner which exposes the correspondence between each choice of musical materials and those musical properties and relations whose perception is (or is not) thereby supported.This first paper discusses the relation between the ability to perceive relative sizes of musical intervals and the choice of reference frame from a given musical context.     

A Philosophical Approach to the Concept of Data Model: Is a Data Model, in Fact, a Model?

The design of the database is crucial to the process of designing almost any Information System (IS) and involves two clearly identifiable key concepts: schema and data model, the latter allowing us to define the former. Nevertheless, the term model is commonly applied indistinctly to both, the confusion arising from the fact that in Software Engineering (SE), unlike in formal or empirical sciences, the notion of model has a double meaning of which we are not always aware. If we take our idea of model directly from empirical sciences, then the schema of a database would actually be a model, whereas the data model would be a set of tools allowing us to define such a schema.The present paper discusses the meaning of model in the area of Software Engineering from a philosophical point of view, an important topic for the confusion arising directly affects other debates where model is a key concept. We would also suggest that the need for a philosophical discussion on the concept of data model is a further argument in favour of institutionalizing a new area of knowledge, which could be called: Philosophy of Engineering.     

Effects of computers on Japanese schools

In this paper I consider how the computer can or should be accepted in Japanese schools. The concept of teaching in Japan stresses learning from a long-term perspective. Whereas in the instructional technology, on which the CAI or the Tutoring System depends, step-by-step attainments in relatively short time are emphasized. The former is reluctant in using the computer, but both share the Platonic perspective which are goal-oriented. However, The Socratic teacher, who intends to activate students' innate disposition to be better, would find another way of teaching and use of the computer.     

The effects of a “distinct window” screen design on computer-mediated group decision making

An experiment was performed to test a distinct-window conferencing screen design as an electronic cue of social status differences in computer-mediated group decision-making. The screen design included one distinct window to symbolize high-status, and two nondistinct windows to symbolize low-status. The results indicated that the distinct-window screen design did produce status affects in groups of peers making decisions on judgmental problems. Randomly assigned occupants of the distinct window had greater influence on group decisions and member's attitudes than occupants of nondistinct windows.The authors would like to thank Shyam Kamadolli and Phaderm Nangsue, the programmers who developed the software used in this experiment. We would also like to thank the editor and our three anonymous reviewers for exceedingly helpful comments on an earlier draft of this article.     

Where does the end begin? Problems in musico-cognitive modeling

Research with computer systems and musical grammars into improvisation as found in the tabla drumming system of North India has indicated that certain musical sentences comprise (a) variable prefixes, and (b) fixed suffixes (or cadences) identical with those of their original rhythmic themes. It was assumed that the cadence functioned as a kind of target in linear musical space, and yet experiments showed that defining what exactly constituted the cadence was problematic. This paper addresses the problem of the status of cadential patterns, and demonstrates the need for a better understanding and formalization of ambiguity in musico-cognitive processing. It would appear from the discussion that the cadence is not a discrete unit in itself, but just part of an ever-present underlying framework comprising the entire original rhythmic theme. Improvisations (variations), it is suggested, merely break away from and rejoin this framework at important structural points. This endorses the theory of simultaneity. However, the general cognitive implications are still unclear, and further research is required to explore musical ambiguity and the interaction of musical, linguistic, and spatio-motor grammars.     

Choosing reference classes and building provisional models

A well-known problem in default logic is the ability of naive reasoners to explain bothg and ¬g from a set of observations. This problem is treated in at least two different ways within that camp.One approach is examination of the various explanations and choosing among them on the basis of various explanation comparators. A typical comparator is choosing the explanation that depends on the most specific observation, similar to the notion of narrowest reference class.Others examine default extensions of the observations and choose whatever is true in any extension, or what is true in all extensions or what is true in preferred extensions. Default extensions are sometimes thought of as acceptable models of the world that are discarded as more knowledge becomes available.We argue that the notions of specificity and extension lack clear semantics. Furthermore, we show that the problems these ideas were supposed to solve can be handled easily within a probabilistic framework.     

A note on dimensions and factors

In this short note, we discuss several aspectsof dimensions and the related constructof factors. We concentrate on those aspectsthat are relevant to articles in this specialissue, especially those dealing with the analysisof the wild animal cases discussed inBerman and Hafner's 1993 ICAIL article. We reviewthe basic ideas about dimensions,as used in HYPO, and point out differences withfactors, as used in subsequent systemslike CATO. Our goal is to correct certainmisconceptions that have arisen over the years.     

Rapid Concept Learning for Mobile Robots

Concept learning in robotics is an extremely challenging problem: sensory data is often high-dimensional, and noisy due to specularities and other irregularities. In this paper, we investigate two general strategies to speed up learning, based on spatial decomposition of the sensory representation, and simultaneous learning of multiple classes using a shared structure. We study two concept learning scenarios: a hallway navigation problem, where the robot has to induce features such as opening or wall. The second task is recycling, where the robot has to learn to recognize objects, such as a trash can. We use a common underlying function approximator in both studies in the form of a feedforward neural network, with several hundred input units and multiple output units. Despite the high degree of freedom afforded by such an approximator, we show the two strategies provide sufficient bias to achieve rapid learning. We provide detailed experimental studies on an actual mobile robot called PAVLOV to illustrate the effectiveness of this approach.     

A class of high performance Maekawa-type algorithms for distributed systems under heavy demand

Summary Distributed Mutual Exclusion algorithms have been mainly compared using the number of messages exchanged per critical section execution. In such algorithms, no attention has been paid to the serialization order of the requests. Indeed, they adopt FCFS discipline. Conversely, the insertion of priority serialization disciplines, such as Short-Job-First, Head-Of-Line, Shortest-Remaining-Job-First etc., can be useful in many applications to optimize some performance indices. However, such priority disciplines are prone to starvation. The goal of this paper is to investigate and evaluate the impact of the insertion of a priority discipline in Maekawa-type algorithms. Priority serialization disciplines will be inserted by means of agated batch mechanism which avoids starvation. In a distributed algorithm, such a mechanism needs synchronizations among the processes. In order to highlight the usefulness of the priority based serialization discipline, we show how it can be used to improve theaverage response time compared to the FCFS discipline. The gated batch approach exhibits other advantages: algorithms are inherently deadlock-free and messages do not need to piggyback timestamps. We also show that, under heavy demand, algorithms using gated batch exchange less messages than Maekawa-type algorithms per critical section excution. Roberto Baldoni was born in Rome on February 1, 1965. He received the Laurea degree in electronic engineering in 1990 from the University of Rome La Sapienza and the Ph.D. degree in Computer Science from the University of Rome La Sapienza in 1994. Currently, he is a researcher in computer science at IRISA, Rennes (France). His research interests include operating systems, distributed algorithms, network protocols and real-time multimedia applications. Bruno Ciciani received the Laurea degree in electronic engineering in 1980 from the University of Rome La Sapienza. From 1983 to 1991 he has been a researcher at the University of Rome Tor Vergata. He is currently full professor in Computer Science at the University of Rome La Sapienza. His research activities include distributed computer systems, fault-tolerant computing, languages for parallel processing, and computer system performance and reliability evaluation. He has published in IEEE Trans. on Computers, IEEE Trans. on Knowledge and Data Engineering, IEEE Trans. on Software Engineering and IEEE Trans. on Reliability. He is the author of a book titled Manufactoring Yield Evaluation of VLSI/WSI Systems to be published by IEEE Computer Society Press.This research was supported in part by the Consiglio Nazionale delle Ricerche under grant 93.02294.CT12This author is also supported by a grant of the Human Capital and Mobility project of the European Community under contract No. 3702 CABERNET     

The informed neuron: Issues in the use of information theory in the behavioral sciences

The concept of information is virtually ubiquitous in contemporary cognitive science. It is claimed to be processed (in cognitivist theories of perception and comprehension), stored (in cognitivist theories of memory and recognition), and otherwise manipulated and transformed by the human central nervous system. Fred Dretske's extensive philosophical defense of a theory of informational content (semantic information) based upon the Shannon-Weaver formal theory of information is subjected to critical scrutiny. A major difficulty is identified in Dretske's equivocations in the use of the concept of a signal bearing informational content. Gibson's alternative conception of information (construed as analog by Dretske), while avoiding many of the problems located in the conventional use of signal, raises different but equally serious questions. It is proposed that, taken literally, the human CNS does not extract or process information at all; rather, whatever information is construed as locatable in the CNS is information only for an observer-theorist and only for certain purposes.Blood courses through our veins, andinformation through our central nervous system.— A Neuropsychology Textbook.     

The Origins of the Translator's Workstation

The first proposals for various component tools of what is now called the translator's workstation or translator's workbench are traced back to the 1970s and early 1980s in various, often independent, proposals at different stages in the development of computers and in their use by translators.     

A formal model of atomicity in asynchronous systems

Summary We propose a generalisation of occurrence graphs as a formal model of computational structure. The model is used to define the atomic occurrence of a program, to characterise interference freeness between programs, and to model error recovery in a decentralised system.     

Design by framework completion

An object-oriented framework in essence defines an architecture for a family of applications or subsystems in a given domain. Every application in the family obeys these architectural restrictions. Such frameworks are typically delivered as collections of inter-dependent abstract classes, together with their concrete subclasses. The abstract classes and their interdependencies implicitly realize the architecture. Developing a new application reusing classes of a framework requires a thorough understanding of the framework architecture.We introduce an approach called Design by Framework Completion, in which an exemplar (an executable visual model for a minimal instantiation of the architecture) is used for documenting frameworks. We propose exploration of exemplars as a means for learning the architecture, following which new applications can be built by replacing selected pieces of the exemplar. For the piece to be replaced, the inheritance lattice around its class provides the space of alternatives, one of these classes may be suitably adapted (say, by sub-classing) to create the new replacement.Design by Framework Completion proposes a paradigm shift when designing in presence of reusable components: It enables a much simpler top-down approach for creating applications, as opposed to the prevalent search for components and assemble them bottom-up strategy. We believe that this paradigm shift is essential because components can only be fitted together if they all obey the same architectural rules that govern the framework.     

Prequential and Cross-Validated Regression Estimation

Prequential model selection and delete-one cross-validation are data-driven methodologies for choosing between rival models on the basis of their predictive abilities. For a given set of observations, the predictive ability of a model is measured by the model's accumulated prediction error and by the model's average-out-of-sample prediction error, respectively, for prequential model selection and for cross-validation. In this paper, given i.i.d. observations, we propose nonparametric regression estimators—based on neural networks—that select the number of hidden units (or neurons) using either prequential model selection or delete-one cross-validation. As our main contributions: (i) we establish rates of convergence for the integrated mean-squared errors in estimating the regression function using off-line or batch versions of the proposed estimators and (ii) we establish rates of convergence for the time-averaged expected prediction errors in using on-line versions of the proposed estimators. We also present computer simulations (i) empirically validating the proposed estimators and (ii) empirically comparing the proposed estimators with certain novel prequential and cross-validated mixture regression estimators.     

Multicriterion optimization of complex systems with parameters ranked by descending importance

A multicriterion optimization method is proposed for complex systems with parameters ranked by descending importance. This method requires weaker expert estimates for choosing an optimal alternative from the set of equally good solutions by formal specification of functional dependence between ranked parameter weights.Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 167–170, November–December, 1991.