1-13hit |
Koji KAMMA Yuki ISODA Sarimu INOUE Toshikazu WADA
This paper presents a method for reducing the redundancy in both fully connected layers and convolutional layers of trained neural network models. The proposed method consists of two steps, 1) Neuro-Coding: to encode the behavior of each neuron by a vector composed of its outputs corresponding to actual inputs and 2) Neuro-Unification: to unify the neurons having the similar behavioral vectors. Instead of just pruning one of the similar neurons, the proposed method let the remaining neuron emulate the behavior of the pruned one. Therefore, the proposed method can reduce the number of neurons with small sacrifice of accuracy without retraining. Our method can be applied for compressing convolutional layers as well. In the convolutional layers, the behavior of each channel is encoded by its output feature maps, and channels whose behaviors can be well emulated by other channels are pruned and update the remaining weights. Through several experiments, we comfirmed that the proposed method performs better than the existing methods.
Ichiro MITSUHASHI Michio OYAMAGUCHI Kunihiro MATSUURA
The unification problem for term rewriting systems (TRSs) is the problem of deciding, for a TRS R and two terms s and t, whether s and t are unifiable modulo R. We have shown that the problem is decidable for confluent simple TRSs. Here, a simple TRS means one where the right-hand side of every rewrite rule is a ground term or a variable. In this paper, we extend this result and show that the unification problem for confluent semi-constructor TRSs is decidable. Here, a semi-constructor TRS means one where all defined symbols appearing in the right-hand side of each rewrite rule occur only in its ground subterms.
Jun YAO Shinobu MIWA Hajime SHIMADA Shinji TOMITA
Recently, a method called pipeline stage unification (PSU) has been proposed to reduce energy consumption for mobile processors via inactivating and bypassing some of the pipeline registers and thus adopt shallow pipelines. It is designed to be an energy efficient method especially for the processors under future process technologies. In this paper, we present a mechanism for the PSU controller which can dynamically predict a suitable configuration based on the program phase detection. Our results show that the designed predictor can achieve a PSU degree prediction accuracy of 84.0%, averaged from the SPEC CPU2000 integer benchmarks. With this dynamic control mechanism, we can obtain 11.4% Energy-Delay-Product (EDP) reduction in the processor that adopts a PSU pipeline, compared to the baseline processor, even after the application of complex clock gating.
Haruo YOKOTA Takashi KOBAYASHI Taichi MURAKI Satoshi NAOI
A combination of slides used in a presentation and a video recording of the circumstances of the presentation are quite useful for many applications, such as e-learning. However, to create new content from these with current authoring tools requires considerable effort for the author and the products have reduced flexibility. In this paper, we propose the preparation of a unifying function without creating new content manually. We also propose a new approach to search unified presentation manuscripts for slides matched with given keywords by considering the features peculiar to the presentation slides. We propose impression indicators to express how well a slide matches the given keywords. We also propose a system for retrieving a sequence of desired presentation slides from archives of the combined slides and video. We named the system Unified Presentation Slide Retrieval by Impression Search Engine or UPRISE. We describe the system configuration of UPRISE and the experimentation undertaken to evaluate the effect of the proposed indicators and to compare the results with those of the traditional tf.idf retrieval method.
This paper presents a Japanese Question Answering (QA) system based on a "Question Answering as Abduction" perspective. This perspective regards QA as the process of abductively explaining why a question is true based on logical contents of appropriately described textual information. This perspective is strongly inspired by Jerry Hobbs et al.'s "Interpretation as Abduction". It is also a simple conceptualization of Harabagiu et al.'s logic based QA system. We reify this concept in our QA system called SAIQA-Is. This system was designed to output only most likely answer candidates to a question. This system was participated in NTCIR QAC1. SAIQA-Is provided very good results in Task 2 and Task 3 of the QAC experiments. This results demonstrated strong feasibility and high potential of our Question Answering as Abduction approach.
A uniquely parsable unification grammar (UPUG) is a formal grammar with the following features: (1) parsing is performed without backtracking, and (2) each nonterminal symbol can have arguments, and derivation and parsing processes accompany unification of terms as in Prolog (or logic programming). We newly introduce a uniquely parallel parsable unification grammar (UPPUG) by extending the framework of a UPUG so that parallel parsing is also possible. We show that, in UPPUG, parsing can be done without backtracking in both cases of parallel and sequential reductions. We give examples of UPPUGs where a given input string can be parsed in sublinear number of steps of the length of the input by parallel reduction.
Ryuichi NAKANISHI Izumi HAYAKAWA Hiroyuki SEKI
In this paper, we propose an extension of finite state tree automaton, called tree automaton with tree memory (TTA), and also define structure composing TTA (SC-TTA) and backward deterministic TTA (BD-TTA) as subclasses of TTA. We show that the classes of yield languages accepted by TTAs, SC-TTAs and BD-TTAs are equal to the class of recursively enumerable languages, the class of languages generated by tree-to-string finite state translation systems (TSFSTSs) and the class of languages generated by deterministic TSFSTSs, respectively. As a corollary, it is shown that the yield language accepted by an SC-TTA (resp. a BD-TTA) is linear space (resp. polynomial time) recognizable.
Kazuhiro TAKADA Yuichi KAJI Tadao KASAMI
Some kind of practical problems such as security verification of cryptographic protocols can be described as a problem to accomplish a given purpose by using limited operations and limited materials only. To model such problems in a natural way, unification problems under constrained substitutions have been proposed. This paper is a collection of results on the decidability and the computational complexity of a syntactic unification problem under constrained substitutions. A number of decidable, undecidable, tractable and intractable results of the problem are presented. Since a unification problem under constrained substitutions can be regarded as an order-sorted unification problem with term declarations such that the number of sorts is only one, the results presented in this paper also indicate how the intractability of order-sorted unification problems is reduced by restecting the number of sorts to one.
Alfredo M. MAEDA Hideto TOMABECHI Jun-ichi AOE
Graph unification is doubtlessly the most expensive process in unification-based grammar parsing since it takes the vast majority of the total parsing time of natural language sentences. A parsing time overload in unification consists in that, in general, no less than 60% of the graph unifications performed actually fail. Thus one way to achieve unification time speed-up is focusing on an efficient, fast way to deal with such unification failures. In this paper, a process, prior to unification itself, capable of filtering or stopping a considerably high percentage of graphs that would fail unification is proposed. This unification-filtering process consists of comparison of signatures that correspond to each one of the graphs to be unified. Unification-filter (hereafter UF) is capable of stopping around 87% of the non-unifiable graphs before unification itself takes place. UF takes significantly less time to detect graphs that do not unify and discard them than it would take to unification to fail the attempt to unify the same graphs. As a result of using UF, unification is performed in an around 71% of the time for the fastest known unification algorithm.
Kotaro MATSUSAKA Akira KUMAMOTO
This system called COKIS automatically extracts knowledge about C functions from the UNIX on-line manual by using its description paragraph and the user can interactively inquire to the system in order to know about UNIX C functions. The idea is motivated on the one side to free users from being involved in an exhaustive knowledge acquisition in the past, and to examine problems in understanding knowledge itself on the other. We propose Memory Processor which is implemented to realize extracting knowledges from corpus and processing dialogues in the inquiry system at the same modules.
In this paper we propose a new timing optimization technique for multi-level networks by restructuring multiple nodes simultaneously. Multi-output subcircuits on critical paths are extracted and resynthesized so that the delays of the paths are reduced. The complete design space of the subcircuits is captured by Boolean relations, which allow us to perform more powerful resynthesis than previous approaches using don't cares. Experimental results are reported to show the effectiveness of the proposed technique.
Masaaki NAGATA Tsuyoshi MORIMOTO
A unification-based Japanese parser has been implemented for an experimental Japanese-to-English spoken language translation system (SL-TRANS). The parser consists of a unification-based spoken-style Japanese grammar and an active chart parser. The grammar handles the syntactic, semantic, and pragmatic constraints in an integrated fashion using HPSG-based framework in order to cope with speech recognition errors. The parser takes multiple sentential candidates from the HMM-LR speech recognizer, and produces a semantic representation associated with the best scoring parse based on acoustic and linguistic plausibility. The unification-based parser has been tested using 12 dialogues in the conference registration domain, which include 261 sentences uttered by one male speaker. The sentence recognition accuracy of the underlying speech recognizer is 73.6% for the top candidate, and 83.5% for the top three candidates, where the test-set perplexity of the CFG grammar is 65. By ruling out erroneous speech recognition results using various linguistic constraints, the parser improves the sentence recognition accuracy up to 81.6% for the top candidate, and 85.8% for the top three candidates. From the experiment result, we found that the combination of syntactic restriction, selectional restriction and coordinate structure restriction can provide a sufficient restriction to rule out the recognition errors between case-marking particles with the same vowel, which are the type of errors most likely to occur. However, we also found that it is necessary to use pragmatic information, such as topic, presupposition, and discourse structure, to rule out the recognition errors involved with topicalizing particles and sentence final particles.
Boolean unification is an algorithm to obtain the general solution of a given Boolean equation. Since a general solution provides a way to represent a complete don't care set, Boolean unification can be a powerful technique when applied to logic synthesis. In this paper we present various applications of Boolean unification to combinational logic synthesis. Three topics of combinational logic synthesis: redesign, multi-level logic minimization and minimization of Boolean relations are discussed. All these problems can be uniformly formalized as Boolean equations. Experimental results are also reported.