8016894
Induction by Enumeration
Induction by enumeration has a clear interpretation within the numerical paradigm of inductive discovery (i.e., the one pioneered by E. M. Gold (1967, Inform. and Control 10, 447-474)). The concept is less easily interpreted within the first-order paradigm discussed by K. T. Kelly (1996, "The Logic of Reliable Inquiry," Oxford Univ. Press, New York) and E. Martin and D. Osherson (1998, "Elements of Scientific Inquiry," MIT Press, Cambridge, MA), in which the scientist's data amount to the basic diagram of a structure. We formulate two kinds of enumerative induction that are appropriate to the first-order paradigm and analyze their potential for discovery. Among other results, it is shown that one form of enumerative induction achieves maximum inductive competence. 2001 Elsevier Science.
7592429
On the Convergence of Incremental Knowledge Base Construction
Ripple Down Rules is a practical methodology to build knowledge-based systems, which has proved successful in a wide range of commercial applications. However, little work has been done on its theoretical foundations. In this paper, we formalise the key features of the method. We present the process of building a correct knowledge base as a discovery scenario involving a user, an expert, and a system. The user provides data for classification. The expert helps the system to build its knowledge base incrementally, using the output of the latter in response to the last datum provided by the user. In case the system’s output is not satisfactory, the expert guides the system to improve its future performance while not affecting its ability to properly classify past data. We examine under which conditions the sequence of knowledge bases constructed by the system eventually converges to a knowledge base that faithfully represents the target classification function. Our results are in accordance with the observed behaviour of real-life systems.
2402100
Input-Dependence in Function-Learning
In the standard literature on inductive inference, a learner sees as input the course of values of the function to be learned. In the present work, it is investigated how reasonable this choice is and how sensitive the model is with respect to variations like the overgraph or undergraph of the function. Several implications and separations are shown and for the basic notions, a complete picture is obtained. Furthermore, relations to oracles, additional information and teams are explored.
39139980
On Sufficient Conditions for Learnability of Logic Programs from Positive Data
Shinohara, Arimura, and Krishna Rao have shown learnability in the limit of minimal models of classes of logic programs from positive only data. In most cases, these results involve logic programs in which the "size" of the head yields a bound on the size of the body literals. However, when local variables are present, such a bound on body literal size cannot directly be ensured. The above authors achieve such a restriction using technical notions like mode and linear inequalities. The present paper develops a conceptually clean framework where the behavior of local variables is controlled by nonlocal ones. It is shown that for certain classes of logic programs, learnablity from positive data is equivalent to limiting identification of bounds for the number of clauses and the number of local variables. This reduces the learning problem finding two integers. This cleaner framework generalizes all the known results and establishes learnability of new classes.
38643151
Learning from Each Other
Since its inception, the field of machine learning has seen the advent of several learning paradigms, designed to frame the issues central to the learning activity, provide effective learning methods, and investigate the power and limitations inherent to the process of successful learning. In this article, we propose a formalization that underlies the key concepts of many such paradigms and discuss their relevance to scientific discovery, with the aim of assessing what scientists can expect from machines designed to assist them in their quest for the discovery of valid laws. We illustrate the formalization on several variations of a card game, and highlight the differences that paradigms impose on learners, as well as the assumptions they make on the nature of the learning process. We then use the formalization to describe a multi-agent interaction protocol, that has been inspired by these paradigms and that has been validated recently on some groups of agents. Finally, we propose extensions to this protocol.
37212285
Quantification over names and modalities
34573352
A Vision System on Chip for Industrial Control
This paper describes the building of an original vision system on chip. Our smart sensor performs motion detection and pattern recognition with only one single line of pixels. The maximum cross-correlation number is processed by the processors network. A peculiar methodology was defined to tackle the sensor’s processing part design. Relying on our architectural synthesis tool GAUT, it leads to an optimal matching between the application specifications, the sensor’s architecture and the processor’s. The elementary processor’s architecture is detailed. Its CMOS VLSI implementation is sketched, as well as the sensor’s analog part and the light to byte conversion. The circuit’s final structure and floorplan are outlined. Its performances are exhibited.
40556746
Intégration de la synthèse mémoire dans l'outil de synthèse d'architecture GAUT Low Power
The systems supporting signal and image applications process large amount of data. That involves an intensive use of the memory which becomes the bottleneck of systems. Memory limits performances and represents a significant proportion of total consumption. In the development high level synthesis tool called GAUT Low Power, we are interested in the synthesis of the memory unit. In this work, we integrate the data storage and data transfert to constraint the high level synthesis of the datapath's execution unit.
7274427
Low Power Synthesis Methodology with Data Format Optimization Applied on a DWT
In modern VLSI circuits, power consumption has become a design criteria as well as speed and silicon area or gate count. To guide the designer implementing complex applications with real time constraint on dedicated circuits, we present a High Level Synthesis methodology that provides a Register Transfer Level description of an ASIC, from a behavioral description of an algorithm; this complete methodology uses basic techniques such as selection, assignment or scheduling specified for power optimization, associated with a new approach based on data format optimization. Actually, instead of the usual 32-bit floating-point format, it is power efficient to use a fixed-point format provided overflow and computation noise problems are solved. The application of our method on an usual DSP example (the DWT) shows a power reduction of more than 60%.
11623202
A memory aware behavioral synthesis tool for real-time VLSI circuits
We introduce a new approach to take into account the memory architecture and the memory mapping in the Behavioral Synthesis of Real-Time VLSI circuits. We formalize the memory mapping as a set of constraints for the thesis, and defined a Memory Constraint Graph and an accessibility criterion to be used in the scheduling step. We use a memory mapping file to include those memory straints in our HLS tool GAUT. Our scheduling algorithm exhibits a relatively low complexity that permits to tackle complex designs in a reasonable time. Several experiments are performed to demonstrate the efficiency of our method, and to compare GAUT with an industrial behavioral synthesis tool. We finally show how to explore, with the help of GAUT, a wide range of solutions, and to reach a good tradeoffs between time, power-consumption, and area.
15848153
Memory aware HLS and the implementation of ageing vectors
We introduce a new approach to take into account the memory architecture and the memory mapping in behavioral synthesis. We formalize the memory mapping as a set of constraints for the synthesis, and defined a memory constraint graph and an accessibility criterion to be used in the scheduling step. We present a new strategy for implementing signals (ageing vectors). We formalize the maturing process and explain how it may generate memory conflicts over several iterations of the algorithm. The final compatibility graph indicates the set of valid mappings for every signal. Several experiments are performed with our HLS tool GAUT. Our scheduling algorithm exhibits a relatively low complexity that permits to tackle complex designs in a reasonable time.