We present the first large scale corpus for entity resolution in email conversations (CEREC).The corpus consists of 6001 email threads from the Enron Email Corpus containing 36,448 email messages and 38,996 entity coreference chains.The annotation is carried out as a two-step process with minimal manual effort.Experiments are carried out for evaluating different features and performance of four baselines on the created corpus.For the task of mention identification and coreference resolution, a best performance of 54.1 F1 is reported, highlighting the room for improvement.An in-depth qualitative and quantitative error analysis is presented to understand the limitations of the baselines considered.

This paper investigates the problem of entity resolution for email conversations and presents a seed annotated corpus of email threads labeled with entity coreference chains. Characteristics of email threads concerning reference resolution are first discussed, and then the creation of the corpus and annotation steps are explained. Finally, performance of the current state-of-the-art deep learning models on the seed corpus is evaluated and qualitative error analysis on the predictions obtained is presented.

This paper describes an accurate framework for carrying out multi-lingual discourse segmentation with BERT (Devlin et al., 2019). The model is trained to identify segments by casting the problem as a token classification problem and jointly learning syntactic features like part-of-speech tags and dependency relations. This leads to significant improvements in performance. Experiments are performed in different languages, such as English, Dutch, German, Portuguese Brazilian and Basque to highlight the cross-lingual effectiveness of the segmenter. In particular, the model achieves a state-of-the-art F-score of 96.7 for the RST-DT corpus (Carlson et al., 2003) improving on the previous best model by 7.2%. Additionally, a qualitative explanation is provided for how proposed changes contribute to model performance by analyzing errors made on the test data.

This paper presents a semantic logic-based approach to determine textual similarity. Three logic form transformations taking into account semantic structure of sentences are proposed. Logic proofs are obtained using an adapted resolution step that drops predicates when a proof cannot be found with standard resolution. Features are extracted from proofs and combined using supervised machine learning to obtain the final similarity scores. Experimental results show that taking into account semantic relations to determine textual similarity yields performance improvements with respect to both baselines and third-party state-of-the-art systems. Specific sentence pairs that benefit from considering semantic relations are discussed. Detailed results provide empirical evidence that either proof direction offers a strong baseline although considering both is beneficial, and that ignoring concepts that are not an argument of a semantic relation is not sound.

This paper presents a methodology to infer implicit semantic relations from verbargument structures.An annotation effort shows implicit relations boost the amount of meaning explicitly encoded for verbs.Experimental results with automatically obtained parse trees and verb-argument structures demonstrate that inferring implicit relations is a doable task.

Abstract This paper introduces a model for capturing the meaning of negated statements by identifying the negated concepts and revealing the implicit positive meanings. A negated sentence may be represented logically in different ways depending on what is the scope and focus of negation. The novel approach introduced here identifies the focus of negation and thus eliminates erroneous interpretations. Furthermore, negation is incorporated into a framework for composing semantic relations, proposed previously, yielding a richer semantic representation of text, including hidden inferences. Annotations of negation focus were performed over PropBank, and learning features were identified. The experimental results show that the models introduced here obtain a weighted f-measure of 0.641 for predicting the focus of negation and 78 percent accuracy for incorporating negation into composition of semantic relations.

This paper presents a novel approach to determine textual similarity.A layered methodology to transform text into logic forms is proposed, and semantic features are derived from a logic prover.Experimental results show that incorporating the semantic structure of sentences is beneficial.When training data is unavailable, scores obtained from the logic prover in an unsupervised manner outperform supervised methods.

Abstract This paper presents a method for the composition of at-location with other semantic relations. The method is based on inference axioms that combine two semantic relations yielding another relation that otherwise is not expressed. An experimental study conducted on PropBank, WordNet, and eXtended WordNet shows that inferences have high accuracy. The method is applicable to combining other semantic relations and it is beneficial to many semantically intense applications.

This paper presents a semiautomatic method for generating commonsense axioms. The method relies on three metarules that process a few commonsense rules referring to some concept properties. The proposed algorithm searches automatically in Extended WordNet for all concepts that have a given property and generates axioms linking those concepts with the seed commonsense rule. The results show that using 27 commonsense rules, the algorithm generated 2596 axioms of which 98% were validated by human. The generation of commonsense axioms is useful to many natural language applications that require reasoning.

Abstract An important problem in knowledge discovery from text is the automatic extraction of semantic relations. This paper addresses the automatic classification of thesemantic relationsexpressed by English genitives. A learning model is introduced based on the statistical analysis of the distribution of genitives' semantic relations in a corpus. The semantic and contextual features of the genitive's noun phrase constituents play a key role in the identification of the semantic relation. The algorithm was trained and tested on a corpus of approximately 20,000 sentences and achieved an f-measure of 79.80 per cent for of-genitives, far better than the 40.60 per cent obtained using a Decision Trees algorithm, the 50.55 per cent obtained using a Naive Bayes algorithm, or the 72.13 per cent obtained using a Support Vector Machines algorithm on the same corpus using the same features. The results were similar for s-genitives: 78.45 per cent using Semantic Scattering, 47.00 per cent using Decision Trees, 43.70 per cent using Naive Bayes, and 70.32 per cent using a Support Vector Machines algorithm. The results demonstrate the importance of word sense disambiguation and semantic generalization/specialization for this task. They also demonstrate that different patterns (in our case the two types of genitive constructions) encode different semantic information and should be treated differently in the sense that different models should be built for different patterns.

This paper describes an algorithm for propagating verb arguments along lexical chains consisting of WordNet relations. The algorithm creates verb argument structures using VerbNet syntactic patterns. In order to increase the coverage, a larger set of verb senses were automatically associated with the existing patterns from VerbNet. The algorithm is used in an in-house Question Answering system for re-ranking the set of candidate answers. Tests on factoid questions from TREC 2004 indicate that the algorithm improved the system performance by 2.4%.

This paper presents a novel methodology to improve large vocabulary continuous speech recognizer (LVCSR) hypotheses using additional phonetic, lexical, syntactic and semantic knowledge. Such additional higher level knowledge sources are unavailable during the LVCSR decoding due to the various constraints placed on the successful deployment of such information sources. This paper focuses on the extraction of WER improvements from the LVCSR n-best list using the additional higher level knowledge sources as the nucleus of a reranking mechanism. We illustrate the improvements obtained for the conversational speech transcription task and also for the directed dialog speech utterance transcription task in a grammar tuning application

This paper presents a procedure to efficiently create and tune context free grammars for directed dialog speech applications using only spoken test user utterances. We present a procedure to transcribe utterances with improved accuracy by post-processing the ASR n-best lists with higher level knowledge sources and additional information from the application prompt. We then present a semantic categorizer for the transcriptions, a statistical filtering mechanism for modifying the grammars and, a mechanism to raise an alarm condition in case of large in-flow of errors. We also illustrate the importance of additional improvements gained by using the semantic classification strength in a feedback loop to the transcription mechanism

Summary form only given. Text-based Question Answering technology has made significant progress in the last few years. Cellular phones are now shipping with integrated web browsers. It is clear the next step is to integrate voice input and output with Question Answering systems to alleviate the keyword bottleneck of cellular phones. This talk presents some issues specific to designing VAQA systems. It is possible to integrate state-of-the-art question answering and automatic speech recognition in such a way that the performance of the combined system is better than the individual components.

An important problem in knowledge discovery from text is the automatic extraction of semantic relations. This paper presents a supervised, semantically intensive, domain independent approach for the automatic detection of part-whole relations in text. First an algorithm is described that identifies lexico-syntactic patterns that encode part-whole relations. A difficulty is that these patterns also encode other semantic relations, and a learning method is necessary to discriminate whether or not a pattern contains a part-whole relation. A large set of training examples have been annotated and fed into a specialized learning system that learns classification rules. The rules are learned through an iterative semantic specialization (ISS) method applied to noun phrase constituents. Classification rules have been generated this way for different patterns such as genitives, noun compounds, and noun phrases containing prepositional phrases to extract part-whole relations from them. The applicability of these rules has been tested on a test corpus obtaining an overall average precision of 80.95% and recall of 75.91%. The results demonstrate the importance of word sense disambiguation for this task. They also demonstrate that different lexico-syntactic patterns encode different semantic information and should be treated separately in the sense that different clarification rules apply to different patterns.

This paper describes a novel framework for interactive question-answering (Q/A) based on predictive questioning. Generated off-line from topic representations of complex scenarios, predictive questions represent requests for information that capture the most salient (and diverse) aspects of a topic. We present experimental results from large user studies (featuring a fully-implemented interactive Q/A system named FERRET) that demonstrates that surprising performance is achieved by integrating predictive questions into the context of a Q/A dialogue.

Automatic image annotation is the task of automatically assigning words to an image that describe the content of the image. Machine learning approaches have been explored to model the association between words and images from an annotated set of images and generate annotations for a test image. The paper proposes methods to use a hierarchy defined on the annotation words derived from a text ontology to improve automatic image annotation and retrieval. Specifically, the hierarchy is used in the context of generating a visual vocabulary for representing images and as a framework for the proposed hierarchical classification approach for automatic image annotation. The effect of using the hierarchy in generating the visual vocabulary is demonstrated by improvements in the annotation performance of translation models. In addition to performance improvements, hierarchical classification approaches yield well to constructing multimedia ontologies.

This paper presents a perspective imaging model that is able to eliminate image deformations caused by non-linear lens distortion and to detect the location of the optical center respectively. By using a calibration pattern it can detect the optical center by tracking the optical rays generated by 3D points that have the same representation on the image plane. Calibration pattern is also used in order to generate normalized virtual screens on which captured images are back projected, thus eliminating the deformations. Experimental results for single viewpoint omni-directional cameras demonstrate the effectiveness of our method.

This paper presents an in-depth analysis of a state-of-the-art Question Answering system. Several scenarios are examined: (1) the performance of each module in a serial baseline system, (2) the impact of feedbacks and the insertion of a logic prover, and (3) the impact of various retrieval strategies and lexical resources. The main conclusion is that the overall performance depends on the depth of natural language processing resources and the tools used for answer finding.

This paper presents an in-depth analysis of a state-of-the-art Question Answering system. Several scenarios are examined: (1) the performance of each module in a serial baseline system, (2) the impact of feedbacks and the insertion of a logic prover, and (3) the impact of various lexical resources. The main conclusion is that the overall performance depends on the depth of natural language processing resources and the tools used for answer finding.

This paper introduces DISK, a distributed Java Virtual Machine for networks of heterogenous workstations. Several research issues are addressed. A novelty of the system is its object-based, multiple-writer memory consistency protocol (OMW). The correctness of the protocol and its Java compliance is demonstrated by comparing the nonoperational definitions of release consistency, the consistency model implemented by OMW, with the Java Virtual Machine memory consistency model (JVMC), as defined in the Java Virtual Machine Specification. An analytical performance model was developed to study and compare the design trade-offs between OMW and the lazy invalidate release consistency (LI) protocols as a function of the number of processors, network characteristics, and application types. The DISK system has been implemented and running on a network of 16 Pentium III computers interconnected by a 100 Mbps Ethernet network. Experiments performed with two applications: parallel matrix multiplication and traveling salesman problem confirm the analytical model.

The problem of question/answering (Q/A) is to find answers to open-domain questions by searching large collections of documents. Unlike information retrieval systems very common today in the form of Internet search engines, Q/A systems do not retrieve documents, but instead provide short, relevant answers located in small fragments of text. This enhanced functionality comes with a price: Q/A systems are significantly slower and require more hardware resources than information retrieval systems. This paper proposes a distributed Q/A architecture that enhances the system throughput through the exploitation of interquestion parallelism and dynamic load balancing and reduces the individual question response time through the exploitation of intraquestion parallelism. Inter and intraquestion parallelism are both exploited using several scheduling points: one before the Q/A task is started and two embedded in the Q/A task. An analytical performance model is introduced. The model analyzes both the interquestion parallelism overhead generated by the migration of questions and the intraquestion parallelism overhead generated by the partitioning of the Q/A task. The analytical model indicates that both question migration and partitioning are required for a high-performance system.

This paper presents an open-domain textual Question-Answering system that uses several feedback loops to enhance its performance. These feedback loops combine in a new way statistical results with syntactic, semantic or pragmatic information derived from texts and lexical databases. The paper presents the contribution of each feedback loop to the overall performance of 76% human-assessed precise answers.

WordNet is a rich source of world knowledge from which formal axioms can be derived. In this paper we present a method for transforming the WordNet glosses into logic forms and further into axioms. The transformation of WordNet glosses into logic forms is useful for theorem proving and other applications. The paper demonstrates the utility of the WordNet axioms in a question answering system to rank and extract answers.

The problem of question/answering (Q/A) is to find answers to open-domain questions by searching a large collection of documents. Unlike Internet search engines, Q/A systems provide short, relevant answers to questions. Due to the complex natural language processing involved that is CPU intensive, and the retrieval of large number of documents that is disk intensive, the time performance of sequential Q/A systems is rather slow. This paper presents the design and performance analysis of a distributed state-of-the-art Q/A system. The design is modular and parallelism is dynamically exploited at inter and intra-question levels. Several schedule points are used to balance the load. An analytical performance model is given backed up by experimental results.

This paper presents the architecture, operation and results obtained with the LASSO Question Answering system developed in the Natural Language Processing Laboratory at SMU. To find answers, the system relies on a combination of syntactic and semantic techniques. The search for the answer is based on a novel form of indexing called paragraph indexing. A score of 55.5% for short answers and 64.5% for long answers was achieved at the TREC-8 competition.

Many natural language processing tasks, such as word sense disambiguation, knowledge acquisition, information retrieval, use semantically tagged corpora. Till recently, these corpus-based systems relied on text manually annotated with semantic tags; but the massive human intervention in this process has become a serious impediment in building robust systems. In this paper, we present AutoASC, a system which automatically acquires sense tagged corpora. It is based on (1) the information provided in WordNet, particularly the word definitions found within the glosses and (2) the information gathered from Internet using existing search engines. The system was tested on a set of 46 concepts, for which 2071 example sentences have been acquired; for these, a precision of 87% was observed.

Selecting the most appropriate sense for an ambiguous word in a sentence is a central problem in Natural Language Processing. In this paper, we present a method that attempts to disambiguate all the nouns, verbs, adverbs and adjectives in a text, using the senses provided in WordNet. The senses are ranked using two sources of information: (1) the Internet for gathering statistics for word-word cooccurrences and (2) WordNet for measuring the semantic density for a pair of words. We report an average accuracy of 80% for the first ranked sense, and 91% for the first two ranked senses. Extensions of this method for larger windows of more than two words are considered.

This paper presents a possible solution for the text inference problem-extracting information unstated in a text, but implied. Text inference is central to natural language applications such as information extraction and dissemination, text understanding, summarization, and translation. Our solution takes advantage of a semantic English dictionary available in electronic form that provides the basis for the development of a large linguistic knowledge base. The inference algorithm consists of a set of highly parallel search methods that, when applied to the knowledge base, find contexts in which sentences are interpreted. These contexts reveal information relevant to the text. Implementation, results, and parallelism analysis are discussed.

This paper presents an inferential system based on abductive interpretation of text. Inference to the best explanation is performed by the recognition of the most economic semantic paths produced by the propagation of markers on a very large linguistic knowledge base. The propagation of markers is controlled by their intrinsic propagation rules, devised from plausible semantic relation chains. An interpretation is inferred whenever two markers collide. Using a very large knowledge base, our inferential system aims at producing interpretations accountable for common sense reasoning. The novelty is that the inference rules model a large variety of implications, as suggested by the knowledge base relations. Textual implicatures are recognized as pragmatic inferences.

This paper presents a parallel natural language processing system implemented on a marker-passing parallel AI computer, the Semantic Network Array Processor (SNAP). Our system uses a memory-based parsing approach in which parsing is viewed as a memory search process. Linguistic information is stored as phrasal patterns in a semantic network knowledge base distributed over the memory of the parallel computer. Parsing is performed by recognizing and linking phrasal patterns that reflect a sentence interpretation. This is achieved by propagating markers over the distributed network. We have developed a system capable of processing newswire articles from a particular domain. The paper presents the structure of the system, the memory-based parsing method used, and the performance results obtained.>

The paper presents an automatic acquisition of linguistic patterns that can be used for knowledge based information extraction from texts. In knowledge based information extraction, linguistic patterns play a central role in the recognition and classification of input texts. Although the knowledge based approach has been proved effective for information extraction on limited domains, there are difficulties in construction of a large number of domain specific linguistic patterns. Manual creation of patterns is time consuming and error prone, even for a small application domain. To solve the scalability and the portability problem, an automatic acquisition of patterns must be provided. We present the PALKA (Parallel Automatic Linguistic Knowledge Acquisition) system that acquires linguistic patterns from a set of domain specific training texts and their desired outputs. A specialized representation of patterns called FP structures has been defined. Patterns are constructed in the form of FP structures from training texts, and the acquired patterns are tuned further through the generalization of semantic constraints. Inductive learning mechanism is applied in the generalization step. The PALKA system has been used to generate patterns for our information extraction system developed for the fourth Message Understanding Conference (MUC-4).>

This paper presents a parallel approach for utilizing contextual knowledge to improve spoken language understanding. The method emphasizes a hierarchically-structured knowledge base and a memory-based parsing technique. Within this paradigm, several levels of knowledge sources including contextual knowledge arc efficiently combined. An ambiguity resolution scheme utilizing the preceding discourse context and the situational context was implemented on a parallel computer using a marker-passing scheme. The experiments on the parallel computer for an Air Traffic Control (ATC) domain show an 86% sentence recognition accuracy with about 6% improvement compared with the system not utilizing the contextual knowledge.

It has been shown that implicit covering algorithms are effective for learning concepts from preclassified training examples. In this paper, we show that by making these covering algorithms explicit, concepts with lower error rates can be learned. Experimental results are reported for three real domains.>

Article Free Access Share on PALKA: a system for lexical knowledge acquisition Authors: Jun-Tae Kim Department of Electrical Engineering-Systems, University of Southern California, Los Angeles, CA Department of Electrical Engineering-Systems, University of Southern California, Los Angeles, CAView Profile , Dan I. Moldovan Department of Electrical Engineering-Systems, University of Southern California, Los Angeles, CA Department of Electrical Engineering-Systems, University of Southern California, Los Angeles, CAView Profile Authors Info & Claims CIKM '93: Proceedings of the second international conference on Information and knowledge managementDecember 1993 Pages 124–131https://doi.org/10.1145/170088.170116Published:01 December 1993Publication History 3citation551DownloadsMetricsTotal Citations3Total Downloads551Last 12 Months8Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Reference is an important phenomenon in natural language, and it has been addressed by many researchers. Though a local focus constitutes an important information used in reference resolution, the previous focusing approaches fail to resolve some references due to several problems. The authors present a marker-passing algorithm and some experimental results. Reference resolution is carried out based on the premise that the most active concept which is acceptable syntactically and semantically as a referent is the referent. By defining the activeness of each concept and propagating activeness to related concepts, these problems are avoided. Referability is defined based on constraints and activeness and is used to compute the referent. This model has been implemented on SNAP (Semantic Network Array Processor) simulator, and it shows a 90.2% success rate in various definite references on a set of 100 news articles.

Presents a parallel approach for integrating speech and natural language understanding. The method emphasizes a hierarchically-structured knowledge base and memory-based parsing techniques. Processing is carried out by passing multiple markers in parallel through the knowledge base. Speech specific problems such as insertion, deletion, substitution, and word boundary detection have been analyzed and their parallel solutions are provided. Results on the SNAP-1 multiprocessor show an 80% sentence recognition rate for the Air Traffic Control (ATC) domain. Furthermore, speed-up of up to 15-fold is obtained from the parallel platform which provides response times of a few seconds per sentence for the ATC domain.>

Frame-based systems or semantic networks have been generally used for knowledge representation. In such a knowledge representation system, concepts in the knowledge base are organized based on the subsumption relation between concepts, and classification is a process of constructing a concept hierarchy according to the subsumption relationships. Since the classification process involves search and subsumption test between concepts, classification on a large knowledge base may become unacceptably slow, especially for real-time applications. In this paper, a massively parallel classification and property retrieval algorithm on a marker passing architecture is presented. The subsumption relation is first defined by using the set relationship, and the parallel classification algorithm is described based on that relationship. In this algorithm, subsumption test between two concepts is done by parallel marker passing and multiple subsumption tests are performed simultaneously. To investigate the performance of the algorithm, time complexities of sequential and parallel classification are compared. Simulation of the parallel classification algorithm was performed using the SNAP (Semantic Network Array Processor) simulator, and the influence of several factors on the execution time is discussed.>

The semantic network array processor (SNAP) is a specialized, highly parallel architecture for knowledge representation and reasoning. The instruction set has been carefully designed to reflect the requirements of semantic network processing. SNAP is a marker propagation architecture, where the passing of markers between cells plays a fundamental role. The movement of markers between cells is controlled by a set of propagation rules. Various reasoning mechanisms were implemented using these propagation rules. A simulator was developed, and knowledge processing examples, such as inheritance, recognition, and classification, were tested. By comparing the simulation results with the same examples run on the Connection Machine, it was found that SNAP outperforms the Connection Machine over a broad range of knowledge processing examples by a factor of 1000 or more.>

The findings of a workshop, the goals of which were to identify applications, research problems, and designs of high performance computing and communications (HPCC) systems for supporting applications are discussed. In computer vision, the main scientific issues are machine learning, surface reconstruction, inverse optics and integration, model acquisition, and perception and action. In speech and natural language processing (SNLP), issues were identified statistical analysis in corpus-based speech and language understanding, search strategies for language analysis, auditory and vocal-tract modeling, integration of multiple levels of speech and language analyses, and connectionist systems. In AI, important issues that need immediate attention include the development of efficient machine learning and heuristic search methods that can adapt to different architectural configurations, and the design and construction of scalable and verifiable knowledge bases, active memories, and artificial neural networks.>

The Semantic Network Array Processor (SNAP) is a parallel architecture for knowledge representation and reasoning that uses the marker-propagation paradigm. The primary application areas of SNAP are natural language understanding and speech processing. A first-generation SNAP-1 system has been designed and constructed using an array of 144 digital signal processors organized as 32 multiprocessing clusters with dedicated communication units, a tiered synchronization scheme, and multiported memory network. Issues in the design, performance, and scalability of a marker-propagation architecture are addressed.>

The semantic network array processor (SNAP), a highly parallel architecture targeted to artificial intelligence applications, and in particular natural language understanding, is presented. The knowledge is represented in a form of the semantic network. The knowledge base is distributed among the elements of the SNAP array, and the processing is performed locally where the knowledge is stored. A set of powerful instructions specific to knowledge processing is implemented directly in hardware. SNAP is packaged into 256 custom-designed chips assembled on four printed circuit boards and can store a 16 K node semantic network. SNAP is a marker propagation architecture in which the movement of markers between cells is controlled by propagation rules. Various reasoning mechanisms are implemented with these marker propagation rules.>

Article Free Access Share on The SNAP-1 parallel AI prototype Authors: R. F. DeMara Parallel Knowledge Processing Laboratory, Department of Electrical Engineering Systems, University of Southern California, Los Angeles, California Parallel Knowledge Processing Laboratory, Department of Electrical Engineering Systems, University of Southern California, Los Angeles, CaliforniaView Profile , D. I. Moldovan Parallel Knowledge Processing Laboratory, Department of Electrical Engineering Systems, University of Southern California, Los Angeles, California Parallel Knowledge Processing Laboratory, Department of Electrical Engineering Systems, University of Southern California, Los Angeles, CaliforniaView Profile Authors Info & Claims ISCA '91: Proceedings of the 18th annual international symposium on Computer architectureApril 1991 Pages 2–11https://doi.org/10.1145/115952.115954Published:01 April 1991Publication History 9citation341DownloadsMetricsTotal Citations9Total Downloads341Last 12 Months15Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A methodology for transforming the original search space into an equivalent but minimal search space is proposed. First, the concept of dependences leads to a procedure for reduction of the search space. The search procedure using this method can produce a minimal and complete search space. It is shown that this method is applicable to parallel search as well. An added advantage of this method is that it does not exclude the use of heuristics. pi - lambda transformation is introduced to reduce the parallel search space.>

It is shown how sequential production systems can be transformed into equivalent parallel forms by performing an analysis of rule interdependence. In the parallel production system model, rules fire simultaneously and the search space is reduced from the original form. A multiprocessor called RUBIC (rule-based inference computer) was designed to implement the parallel processing model. RUBIC has a message-passing architecture. The partitioning and mapping of production systems into the multiprocessor is achieved by optimizing a performance index such that inherent parallelism is maximized and interprocessor communication is minimized.>

Airplane classification is used as an application domain to illustrate how hierarchical reasoning on large knowledge bases can be implemented. The knowledge base is organized as a two-dimensional hierarchy: one dimension corresponds to the levels of complexity often seen in computer vision, and the other dimension corresponds to the complexity of hypothesis used in the reasoning process. Reasoning proceeds top-down, from more abstract levels with fewer details toward levels with more details. Whenever possible, with the help of domain knowledge, decision is taken at a higher level, which significantly reduces processing time. A software package called RuBICS (Rule-Based Image Classification System) is described, and some examples of airplane classification are shown.>

The problems in computer vision range from edge detection and segmentation at the lowest level to the problem of cognition at the highest level. This correspondence describes the organization and operation of a semantic network array processor (SNAP) as applicable to high level computer vision problems. The architecture consists of an array of identical cells each containing a content addressable memory, microprogram control, and a communication unit. The applications discussed in this correspondence are the two general techniques, discrete relaxation and dynamic programming. While the discrete relaxation is discussed with reference to scene labeling and edge interpretation, the dynamic programming is tuned for stereo.

A methodology for mapping numerical algorithms into systolic arrays is presented in this paper. This mapping is done using a transformation function which transforms the original sequential algorithm into a suitable parallel form. A program was developed to automatically generate this transformation. We consider both the case of arbitrarily large systolic arrays as well as the more realistic case of fixed-size systolic arrays requiring algorithm partitioning. An example of the algorithm is given to present the methodology and the results obtained with the program.

A technique for partitioning and mapping algorithms into VLSI systolic arrays is presented in this paper. Algorithm partitioning is essential when the size of a computational problem is larger than the size of the VLSI array intended for that problem. Computational models are introduced for systolic arrays and iterative algorithms. First, we discuss the mapping of algorithms into arbitrarily large size VLSI arrays. This mapping is based on the idea of algorithm transformations. Then, we present an approach to algorithm partitioning which is also based on algorithm transformations. Our approach to the partitioning problem is to divide the algorithm index set into bands and to map these bands into the processor space. The partitioning and mapping technique developed throughout the paper is summarized as a six step procedure. A computer program implementing this procedure was developed and some results obtained with this program are presented.

A high speed, flexible, simple and regular Discrete Fourier Transform (DFT) Array Processor architecture based on the Prime Factor Algorithm (PFA) is presented in this paper. The array processor is based only on one type of VLSI cell and can compute an N point DFT in N clock cycles throughput when N is a composit number of prime numbers. The high throughput rate is achieved with only a small number of cells. With a special indexing scheme presented in this paper, this processor can use shift registers as the system memory so that minimum global control and addressing is achieved. This array processor architecture is also highly tolerant to both semiconductor processing yield and processor defects during run time. Thus, it can be manufactured in large quantity with VLSI technology on a single wafer and used in hazardus environments With these advantages, it is very attractive to satellite, military and commercial applications.

A major problem in executing algorithms in array processors is the implementation of broadcasts without unnecessary speed-up factor degradation. We discuss when and how broadcasts can be eliminated or reduced to easily implementable sequences of reduced local broadcasts. Algorithms are modelled as a structured set of indexed computations which operate on variables associated with a referencing or indexing function. The discussion is restricted to variables with linear indexing functions and to algorithms linearly scheduled for execution in array processors. Linear indexing functions are represented as affine matricial functions of the index set of the algorithm. The linear part of such representation is a coefficient matrix denoted the indexing matrix. Linear schedules are defined as linear time-space allocation functions mapping the computations of an algorithm into time and processors. We discuss necessary and sufficient conditions for the occurrence of broadcasts in a linearly scheduled algorithm. Necessary and sufficient conditions and constructive criteria are given for selecting linear schedules for which all broadcasts are eliminated or reduced to sequences of small local broadcasts.

This correspondence is concerned with the development of algorithms for special-purpose VLSI arrays. The approach used in this correspondence is to identify algorithm transformations which modify favorably the index set and the data dependences, but perserve the ordering imposed on the index set by the data dependences. Conditions for the existance of such transformations are given for a class of algorithms. Also, a methodology is proposed for the synthesis of VLSI algorithms.

This paper studies the relation between the performances of digital filters and some inherent characteristics of the latest microprocessors. The implementation of digital filters on micro-processor(s) offers some indisputable advantages, but at the same time imposes limits on the speed, accuracy or even stability of digital filters. The approach taken here is to establish some mathematical relations between the computation time, accuracy and the order of the filter on one hand, and the addition and multiplication time, and the number of bits of the microprocessor on the other hand. Such relations lead to the feasibility study of the implementation and open the possibility of trade-offs between various parameters. Parallel processing technique implemented on multi-microprocessor structures is considered as an alternative to significantly improve the filter performances.