21813971
Membership Functions for Spatial Proximity
Formalising nearness has been the subject of extensive work, resulting in many membership functions based on absolute distance metrics, relative distance metrics, and combinations of those. The possible strengths and weaknesses of these functions have been discussed and argued at length, but strangely enough, no experiment seems to have been conducted to assess the merits and shortcomings of competing approaches. Conducting such experiments can be expected not only to provide an objective evaluation of the various measures that have been proposed, but also to suggest new measures that outperform all those being analysed. This paper fulfills these expectations, and gives further evidence that fuzzy logic provides fruitful and powerful methods to formalise qualitative reasoning and capture fundamental qualitative notions. The proposed fuzzy membership functions can be directly used in qualitative reasoning about spatial proximity in Geographic Information Systems, which are becoming more and more important in software development for diverse purposes such as Tourist Information Systems or property development.
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.
37212285
Quantification over names and modalities
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.
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.
5876918
A Methodology for Efficient Space-Time Adapter Design Space Exploration: A Case Study of an Ultra Wide Band Interleaver
This paper presents a solution to efficiently explore the design space of communication adapters. In most digital signal processing (DSP) applications, the overall architecture of the system is significantly affected by communication architecture, so the designers need specifically optimized adapters. By explicitly modeling these communications within an effective graph-theoretic model and analysis framework, we automatically generate an optimized architecture, named Space-Time AdapteR (STAR). Our design flow inputs a C description of input/output data scheduling, and user requirements (throughput, latency, parallelism...), and formalizes communication constraints through a resource constraints graph (RCG). The RCG properties enable an efficient architecture space exploration in order to synthesize a STAR component. The proposed approach has been tested to design an industrial data mixing block example: an ultra-wideband interleaver.
18182574
SoftExplorer: Estimation, Characterization, and Optimization of the Power and Energy Consumption at the Algorithmic Level
We present SoftExplorer, a tool to estimate and analyze the power and energy consumption of an algorithm from the C program. The consumption of every loop is analyzed, and the influence of the data mapping is characterized. Several models of processor are available, from the simple RISC ARM7 to the very complex VLIW DSP TI-C67. Cache misses, pipeline stalls, and internal / external memory accesses are taken into account. We show how to analyze and optimize the power and energy consumption, and how to choose a processor and its operating frequency, for a MPEG-1 decoder. We also explain how to find the best data mapping for a DSP application.
996478
A Co-Design Methodology for Telecommunication Systems: A Case Study of an Acoustic Echo Canceller
The acoustic echo cancellation with large adaptive filters is a computationally intensive problem and needs real time cost effective solution. To deal with these challenges, designers have increasingly turned to mixed Hardware/Software (HW/SW) implementation of echo canceller algorithms. This paper presents a co-design methodology and environment for both hardware and software modules. We describe how High Level Synthesis (HLS) tools like GAUT and SYNDEX can be efficiently used for rapid prototyping of heterogeneous architecture based on DSP TMS320C40 and ASIC. The HW/SW interface synthesis task is especially discussed since it constitutes a key issue of the whole design. As an illustration, we present a mixed implementation of the GMDF alpha algorithm, an adaptive filter well suited to acoustic echo cancellation, on both ASIC and TMS320C40 DSP.
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.
5563691
Synchronization processor synthesis for latency insensitive systems
In this paper we present our contribution in terms of synchronization processor for a SoC design methodology based on the theory of the latency insensitive systems (LIS) of Carloni et al. (2001). Our contribution consists in IP encapsulation into a new wrapper model whose speed and area are optimized and synthetizability guaranteed. The main benefit of our approach is to preserve the local IP performance when encapsulating them and reduce SoC silicon area.