Rapid Prototyping of Robust Language Understanding Modules for Spoken Dialogue Systems

Language understanding (LU) modules for spoken dialogue systems in the early phases of their development need to be (i) easy to construct and (ii) robust against various expressions. Conventional methods of LU are not suitable for new domains, because they take a great deal of effort to make rules or transcribe and annotate a sufficient corpus for training. In our method, the weightings of the Weighted Finite State Transducer (WFST) are designed on two levels and simpler than those for conventional WFST-based methods. Therefore, our method needs much fewer training data, which enables rapid prototyping of LU modules. We evaluated our method in two different domains. The results revealed that our method outperformed baseline methods with less than one hundred utterances as training data, which can be reasonably prepared for new domains. This shows that our method is appropriate for rapid prototyping of LU modules.

Introduction
The language understanding (LU) of spoken dialogue systems in the early phases of their development should be trained with a small amount of data in their construction. This is because large amounts of annotated data are not available in the early phases. It takes a great deal of effort and time to transcribe and provide correct LU results to a Figure 1: Relationship between our method and conventional methods large amount of data. The LU should also be robust, i.e., it should be accurate even if some automatic speech recognition (ASR) errors are contained in its input. A robust LU module is also helpful when collecting dialogue data for the system because it suppresses incorrect LU and unwanted behaviors. We developed a method of rapidly prototyping LU modules that is easy to construct and robust against various expressions. It makes LU modules in the early phases easier to develop.
Several methods of implementing an LU module in spoken dialogue systems have been proposed. Using grammar-based ASR is one of the simplest. Although its ASR output can easily be transformed into concepts based on grammar rules, complicated grammars are required to understand the user's utterances in various expressions. It takes a great deal of effort to the system developer. Extracting con- Figure 2: Example of WFST for LU cepts from user utterances by keyword spotting or heuristic rules has also been proposed (Seneff, 1992) where utterances can be transformed into concepts without major modifications to the rules. However, numerous complicated rules similarly need to be manually prepared. Unfortunately, neither method is robust against ASR errors.
To cope with these problems, corpus-based (Sudoh and Tsukada, 2005;He and Young, 2005) and Weighted Finite State Transducer (WFST)-based methods (Potamianos and Kuo, 2000;Wutiwiwatchai and Furui, 2004) have been proposed as LU modules for spoken dialogue systems. Since these methods extract concepts using stochastic analysis, they do not need numerous complicated rules. These, however, require a great deal of training data to implement the module and are not suitable for constructing new domains.
Here, we present a new WFST-based LU module that has two main features. 1. A statistical language model (SLM) for ASR and a WFST for parsing that are automatically generated from the domain grammar description.
2. Since the weighting for the WFST is simpler than that in conventional methods, it requires fewer training data than conventional weighting schemes.
Our method accomplishes robust LU with less effort using SLM-based ASR and WFST parsing. Figure 1 outlines the relationships between our method and conventional schemes. Since rule-or grammarbased approaches do not require a large amount of data, they take less effort than stochastic techniques.
However, they are not robust against ASR errors. Stochastic approaches, on the contrary, take a great deal of effort to collect data but are robust against ASR errors. Our method is an intermediate approach that lies between these. That is, it is more robust than rule-or grammar-based approaches and takes less effort than stochastic techniques. This characteristic makes it easier to rapidly prototype LU modules for a new domain and helps development in the early phases.

Related Work and WFST-based Approach
A Finite State Transducer (FST)-based LU is explained here, which accepts ASR output as its input. Figure 2 shows an example of the FST for a video recording reservation domain. The input, ε, means that a transition with no input is permitted at the state transition. In this example, the LU module returns the concept [month=2, day=22] for the utterance "It is February twenty second please".
Here, a FILLER transition in which any word is accepted is appropriately allowed between phrases. In Figure 2, 'F' represents 0 or more FILLER transitions. A FILLER transition from the start to the end is inserted to reject unreliable utterances. This FILLER transition enables us to ignore unnecessary words listed in the example utterances in Table 1. The FILLER transition helps to suppress the insertion of incorrect concepts into LU results. However, many output sequences are obtained for one utterance due to the FILLER transitions, because the utterance can be parsed with several paths. We used a WFST to select the most appropriate path from several output sequences. The path with the highest cumulative weight, w, is selected in a WFST-based LU. In the example in Table 2, the concept [month=2, day=22] has been selected, because its cumulative weight, w, is 2.0, which is the highest.
The weightings of conventional WFST-based approaches used an n-gram of concepts (Potamianos and Kuo, 2000) and that of word-concept pairs (Wutiwiwatchai and Furui, 2004). They obtained the n-grams from several thousands of annotated utterances. However, it takes a great deal of effort to transcribe and annotate a large corpus. Our method enables prototype LU modules to be rapidly constructed that are robust against various expressions with SLM-based ASR and WFST-based parsing. The SLM and WFST are generated automatically from a domain grammar description in our toolkit. We need fewer data to train WFST, because its weightings are simpler than those in conventional methods. Therefore, it is easy to develop an LU module for a new domain with our method.

Domain Grammar Description
A developer defines grammars, slots, and concepts in a domain in an XML file. This description enables an SLM for ASR and parsing WFST to be automatically generated. Therefore, a developer can construct an LU module rapidly with our method. Figure 3 shows an example of a description.
A definition of a slot is described in keyphrase-class tags and its keyphrases and  February and 2 are defined as one of the phrases and values for the slot month. A grammar is described in a sequence of terminal and non-terminal symbols. A non-terminal symbol represents a class of keyphrases, which is defined in keyphrase-class. It begins with an asterisk "*" in a grammar description in sentence tags. Symbols that can be skipped are enclosed by brackets []. The FILLER transition described in Section 2 is inserted between the symbols unless they are enclosed in brackets [] or braces {}. Braces are used to avoid FILLER transitions from being inserted. For example, the grammar in Figure  3 accepts "It is February twenty second please." and "It is twenty second, OK?", but rejects "It is February." and "It, uhm, is February twenty second.".
A WFST for parsing can be automatically generated from this XML file. The WFST in Figure 2 is generated from the definition in Figure 3. Moreover, we can generate example sentences from the grammar description. The SLM for the speech recognizer is generated with our method by using many example sentences generated from the defined grammar.

Weighting for ASR Outputs on Two Levels
We define weights on two levels for a WFST. The first is a weighting for ASR outputs, which is set to select paths that are reliable at a surface word level. The second is a weighting for concepts, which is used to select paths that are reliable on a concept level. The weighting for concepts reflects correctness at a more abstract level than the surface word level. The weighting for ASR outputs consists of two categories: a weighting for ASR N-best outputs and one for accepted words. We will describe the definitions of these weightings in the following subsections.

Weighting for ASR N-Best Outputs
The N-best outputs of ASR are used for an input of a WFST. Weights are assigned to each sentence in ASR N-best outputs. Larger weights are given to more reliable sentences, whose ranks in ASR N-best are higher. We define this preference as where w i s is a weight for the i-th sentence in ASR N-best outputs, β is a coefficient for smoothing, and score i is the log-scaled score of the i-th ASR output. This weighting reflects the reliability of the ASR output. We set β to 0.025 in this study after a preliminary experiment.

Weighting for Accepted Words
Weights are assigned to word sequences that have been accepted by the WFST. Larger weights are given to more reliable sequences of ASR outputs at the surface word level. Generally, longer sequences having more words that are not fillers and more reliable ASR outputs are preferred. We define these preferences as the weights: The word(const.) gives a constant weight to all accepted words. This means that sequences with more words are simply preferred.
The word(#phone) takes the length of each accepted word into consideration. This length is measured by its number of phonemes, which are normalized by that of the longest word in the vocabulary. The normalized values are denoted as l(W ) (0 < l(W ) ≤ 1). By adopting word(#phone), the length of sequences is represented more accurately. We also take the reliability of the accepted words into account as word(CM). This uses confidence measures  for a word, W , in ASR outputs, which are denoted as CM (W ). The θ w is the threshold for determining whether word W is accepted or not. The w w obtains a negative value for an unreliable word W when CM (W ) is lower than θ w . This represents a preference for longer and more reliable sequences.

Weighting for Concepts
In addition to the ASR level, weights on a concept level are also assigned. The concepts are obtained from the parsing results by the WFST, and contain several words. Weights for concepts are defined by using the measures of all words contained in a concept.
We prepared three kinds of weights for the concepts: 1. cpt(const.): w c = 1.0,

cpt(avg):
3. cpt(#pCM(avg)): where W is a set of accepted words, W , in the corresponding concept, and #W is the number of words in W . The cpt(const.) represents a preference for sequences with more concepts.
The cpt(avg) is defined as the weight by using the CM (W ) of each word contained in the concept. The cpt(#pCM(avg)) represents a preference for longer and reliable sequences with more concepts. The θ c is the threshold for the acceptance of a concept.   Figure 4: Example of LU with WFST

Calculating Cumulative Weight and Training
The LU results are selected based on the weighted sum of the three weights in Subsection 4.3 as The LU module selects an output sequence with the highest cumulative weight, w i , for 1 ≤ i ≤ N .
Let us explain how to calculate cumulative weight w i by using the example specified in Table 3. Here, word(CM) and cpt(#pCM(avg)) are selected as parameters. The sum of weights in this table for accepted words is α w (4.1 − 5θ w ), when the input sequence is "No, it is February twenty second.". The sum of weights for concepts is α c (1.335 − 2θ c ) because the weight for "month=2" is α c (0.81 − θ c ) and the weight for "day=22" is α c (0.525 − θ c ). Therefore, cumulative weight w i for this input sequence is w i s + α w (4.1 − 5θ w ) + α c (1.335 − 2θ c ). In the training phase, various combinations of parameters are tested, i.e., which weightings are used for each of ASR output and concept level, such as N = 1 or 10, coefficient α w,c = 1.0 or 0, and threshold θ w,c = 0 to 0.9 at intervals of 0.1, on the training data. The coefficient α w,c = 0 means that a corresponding weight is not added. The optimal pa-rameter settings are obtained after testing the various combinations of parameters. They make the concept error rate (CER) minimum for a training data set. We calculated the CER in the following equation: CER = (S + D + I)/N , where N is the number of concepts in a reference, and S, D, and I correspond to the number of substitution, deletion, and insertion errors. Figure 4 shows an example of LU with our method, where it rejects misrecognized concept [car:FIT], which cannot be rejected by keyword spotting.

Experimental Conditions
We discussed our experimental investigation into the effects of weightings in Section 4. The user utterance in our experiment was first recognized by ASR. Then, the i-th sentence of ASR output was input to WFST for 1 ≤ i ≤ N , and the LU result for the highest cumulative weight, w i , was obtained.
We used 4186 utterances in the video recording reservation domain (video domain), which consisted of eight different dialogues with a total of 25 different speakers. We also used 3364 utterances in the rent-a-car reservation domain (rent-a-car domain) of eight different dialogues with 23 different speakers. We used Julius 1 as a speech recognizer with an SLM. The language model was prepared by using example sentences generated from the grammars of both domains. We used 10000 example sentences in the video and 40000 in the rent-a-car domain. The number of the generated sentences was determined empirically. The vocabulary size was 209 in the video and 891 in the rent-a-car domain. The average ASR accuracy was 83.9% in the video and 65.7% in the rent-a-car domain. The grammar in the video domain included phrases for dates, times, channels, commands. That of the rent-a-car domain included phrases for dates, times, locations, car classes, options, and commands. The WFST parsing module was implemented by using the MIT FST toolkit (Hetherington, 2004).

Performance of WFST-based LU
We evaluated our method in the two domains: video and rent-a-car. We compared the CER on test data, which was calculated by using the optimal settings for both domains. We evaluated the results with 4fold cross validation. The number of utterances for training was 3139 (=4186*(3/4)) in the video and 2523 (=3364*(3/4)) in the rent-a-car domain.
The baseline method was simple keyword spotting because we assumed a condition where a large amount of training data was not available. This method extracts as many keyphrases as possible from ASR output without taking speech recognition errors and grammatical rules into consideration. Both grammar-based and SLM-based ASR outputs are used for input in keyword spotting (denoted as "Grammar & spotting" and "SLM & spotting" in Table 4). The grammar for grammar-based ASR was automatically generated by the domain description file. The accuracy of grammar-based ASR was 66.3% in the video and 43.2% in the rent-a-car domain. Table 4 lists the CERs for both methods. In keyword spotting with SLM-based ASR, the CERs were improved by 5.2 points in the video and by 22.2 points in the rent-a-car domain compared with those with grammar-based ASR. This is because SLMbased ASR is more robust against fillers and un-1 http://julius.sourceforge.jp/ known words than grammar-based ASR. The CER was improved by 3.4 and 6.9 points by optimal weightings for WFST. Table 5 lists the optimal parameters in both domains. The α c = 0 in the video domain means that weights for concepts were not used. This result shows that optimal parameters depend on the domain for the system, and these need to be adapted for each domain.

Performance According to Training Data
We also investigated the relationship between the size of the training data for our method and the CER.
In this experiment, we calculated the CER in the test data by increasing the number of utterances for training. We also evaluated the results by 4-fold cross validation. Figures 5 and 6 show that our method outperformed the baseline methods by about 80 utterances in the video domain and about 30 utterances in the rent-a-car domain. These results mean that our method can effectively be used to rapidly prototype LU modules. This is because it can achieve robust LU with fewer training data compared with conventional WFST-based methods, which need over several thousand sentences for training.

Conclusion
We developed a method of rapidly prototyping robust LU modules for spoken language understanding. An SLM for a speech recognizer and a WFST for parsing were automatically generated from a domain grammar description. We defined two kinds of weightings for the WFST at the word and concept levels. These two kinds of weightings were calculated by ASR outputs. This made it possible to create an LU module for a new domain with less effort because the weighting scheme was relatively simpler than those of conventional methods. The optimal parameters could be selected with fewer training data in both domains. Our experiment re-  vealed that the CER could be improved compared to the baseline by training optimal parameters with a small amount of training data, which could be reasonably prepared for new domains. This means that our method is appropriate for rapidly prototyping LU modules. Our method should help developers of spoken dialogue systems in the early phases of development. We intend to evaluate our method on other domains, such as database searches and question answering in future work.


extfieldsofstudy:
Computer Science
Medicine

s2fieldsofstudy:
Computer Science
Biology

text:
Brainlab: A Python Toolkit to Aid in the Design, Simulation, and Analysis of Spiking Neural Networks with the NeoCortical Simulator

Neuroscience modeling experiments often involve multiple complex neural network and cell model variants, complex input stimuli and input protocols, followed by complex data analysis. Coordinating all this complexity becomes a central difficulty for the experimenter. The Python programming language, along with its extensive library packages, has emerged as a leading “glue” tool for managing all sorts of complex programmatic tasks. This paper describes a toolkit called Brainlab, written in Python, that leverages Python's strengths for the task of managing the general complexity of neuroscience modeling experiments. Brainlab was also designed to overcome the major difficulties of working with the NCS (NeoCortical Simulator) environment in particular. Brainlab is an integrated model-building, experimentation, and data analysis environment for the powerful parallel spiking neural network simulator system NCS.

INTRODUCTION
Spiking neural network simulator software systems continue to grow in speed and capacity (see Brette et al., 2007 for a recent survey). The complexity and size of the models simulated on these systems also continue to grow, threatening to overwhelm the ability of the experimenter to build the models, conduct parameterized experiments, and analyze the huge amounts of resulting data. The simulators themselves are generally extremely effi cient but minimalist tools written in low-level programming languages that are diffi cult to understand and modify by any but a few dedicated experts. Tools beyond the simulators themselves are needed to help the experimenter cope with the complexity of the experiments.
In our work with one such powerful spiking neural network simulator called NCS 1 (the NeoCortical Simulator, described briefl y in the Section "NCS") we encountered these general complexity barriers. Our work was also hampered by problems specifi c to working with NCS, most notably the necessity of preparing network models for simulation using NCS's restrictive neural modeling interface, the .in fi le format. We confronted all these problems together by creating a unifi ed Python toolkit called Brainlab 2 , which has greatly eased the burden of organizing and conducting our experiments in general, and working with NCS in particular.
The fundamental proposition of Brainlab is this: For the tasks of complex neuroscience model-building, experimentation, and analysis, nothing short of a full-fl edged programming language will suffi ce. No neural model fi le format or restricted special purpose programming language for modeling will ultimately suffi ce for day to day work. And as long as a real programming language will be needed to hold the whole experimental enterprise together, good single-processor simulation performance through the use of vectorized processing provided by the NumPy library, and it can also manage multiple jobs in parallel on a cluster computer system, but splitting a single large simulation onto multiple compute nodes is not supported. The Topographica 11 project provides standalone Python tools intended for exploring higher-level neural abstractions like sheets and projections from neural area to area. Though not primarily intended for investigations that require detailed simulation of individual neurons, Topographica can be interfaced to lower-level simulators like NEURON and GENESIS. Topographica is one of the older Python neuroscience tool packages, with an initial public release in late 2005.
Perhaps because NCS has a fraction of the number of users of some other simulators (e.g. NEURON and GENESIS), Brainlab has attracted comparatively little attention. Brainlab merited brief mention in a recent survey of major spiking neural net simulator packages (Brette et al., 2007). Brainlab was unnoticed by another recent survey of interoperability of neuroscience software (Cannon et al., 2007) though Python interfaces to other spiking neural network simulators (e.g. NEURON's and NEST's) were described there in some detail.

BRAINLAB MOTIVATION, DESIGN, AND IMPLEMENTATION
In this section, we will fi rst describe enough about NCS so that a reader will understand the problems we faced designing a system to interface to and control it. Next we will describe the broad features we wanted to include in our toolkit, and how we wanted the fi nished system to appear to the user for modeling, simulation, and analysis. Then we will describe in detail how we actually confronted the problems interfacing to NCS, to implement the Brainlab system.

NCS
The development history of NCS is recounted elsewhere (Drewes, 2005b). In its current evolution, NCS is a parallel (MPI-based) spiking neural network simulator written in C/C++ that can perform very large discrete-time simulations with a reasonably high degree of biological realism. Simulations with a million neurons and a billion synapses have been accomplished. NCS allows for neuron models that include detailed and customizable ion channel and cell membrane voltage dynamics, but for effi ciency the stereotypical action potential voltage and postsynaptic conductivity waveforms are templated rather than generated dynamically. NCS supports multi-compartment cells but often large scale simulations are done using single compartment models. A good recent comparison of NCS with other spiking neural network simulators, including some discussion of maximum simulation sizes, is Brette et al. (2007).

THE NCS INPUT FILE (THE .in FILE)
NCS reads a description of a neural network model and other simulation parameters from a plain text fi le whose fi lename is supplied to NCS as a command line argument. For our purposes here it is not necessary to go into great detail about the format of this fi le, but we do wish to describe it generally in order to explain some of the shortcomings of working with it. This input fi le, hereafter called a .in fi le after the convention of using .in as a fi lename extension for such fi les, contains a variable number of subsections. Each subsection starts with a line that contains the name of the subsection (which must be one of a limited number of keywords permitted by the system) and ends with a line that contains END_ with the section name appended. The fi rst subsection in a .in fi le is the BRAIN section. In the BRAIN section of the fi le are defi ned global features that affect the entire simulation. For example, a line beginning with JOB defi nes a job name for the simulation. Some subsections can be repeated (for example, a COLUMN or LAYER), and then each is assigned a unique text identifi er within the fi le. The fi le format allows other portions of the fi le to reference these named objects, to create additional instances of them, but no structural or other signifi cant variation in a defi ned object is permitted. The .in format defi nition permits no looping constructs or macro substitutions. Other sections of the .in fi le defi ne connections between these objects, with references to the text names of the objects being connected. Because of these restrictions, NCS .in fi les tend to be quite long even for fairly simple networks, and they tend to be prone to syntactical error or internal referential inconsistency when edited manually.
Other neural simulator systems acquired programming languages (e.g. Hoc for NEURON) to avoid the limitations of a fl at input fi le format like NCS's. NCS never went this far, though there were several attempts to elaborate the .in fi le with macros, loops and other features. None of these efforts for NCS were widely used or reached the generality of a true programming language. Many NCS users eventually created custom text processing programs in other programming languages (like MATLAB) that would emit .in fi les. But writing special-purpose macro processors to create .in fi les is time consuming work that generally cannot be reused on later projects, and MATLAB is not a particularly good text processing tool. The experimentation process was either not automated or automated with external custom scripts, making the whole process cumbersome and systematic model parameter search diffi cult. Data fi le management was typically done manually using ftp type tools.
One other unusual aspect of NCS deserves mention: it imposes a notion of the cortical column and the cortical layer as structural elements, and this requirement is refl ected in the structure of the NCS input fi le. Even if an NCS user wishes to simply simulate two connected cells, or a homogeneous collection of cells for a study of, say, synfi re chains, he must defi ne those cells within an NCS LAYER text block, and that in turn within an NCS COLUMN text block. This introduces additional complication for the simplest simulations.

NCS USAGE
NCS is optimized for large cluster computer systems (Beowulf clusters). A common usage pattern is as follows: A user typically fi rst prepares an input fi le in the .in fi le format in a text editor, specifying the neuron, synapse, channel, and network model. This fi le is copied across a network to the cluster computer and NCS is invoked there with the fi le as a command line argument. Reports are written to the cluster computer's disks during the simulation run, which can last from a few seconds to days. Data analysis is then performed on the cluster computer if the data set is very large, or the data is copied back to the user's workstation for data analysis 11 http://topographica.org/Home/index.html if that is feasible. The experimenter then makes some adjustments to the model and tries again.

BRAINLAB MOTIVATION AND DESIGN GOALS
Faced with the powerful but diffi cult to use NCS simulator, we set about to design a toolkit that would offer the following: 1. An interactive shell for simple experimentation with NCS, making NCS a more suitable educational tool for learning the behavior of spiking neural networks and also a more convenient platform for experienced users to explore the behavior of new cell or network elements. 2. A convenient platform for parameterized control of sets of NCS experiments. 3. A convenient platform for scripted regression testing of NCS itself, with fl exible output validation. 4. Scripted, algorithmic generation of neural network models rather than NCS's native static fi le specifi cation of networks. 5. Convenient, integrated, graphical on-line reporting and plotting of spiking, current, and voltage activity of cells, synapses, and channels. 6. Convenient, integrated, on-line three-dimensional plotting of neural network architecture for expository and diagnostic purposes. 7. Experimental support for higher-level abstractions than those provided natively in NCS (for example support for areas, composed of arrays of columns, and a variety of distinct areato-area synaptic connection patterns), and a fl exible environment to add new ones. 8. Support for lower-level abstractions too unwieldy to reasonably manage in native NCS (for example, columns where all cells are enumerated and independently, rather than just statistically, addressable). 9. A container for a standard and extensible library of NCS network building blocks (for example channels, cell types, columns, spike templates), where all components are guaranteed to interoperate, utilize consistent naming conventions, and may be manipulated programmatically as variable objects rather than text chunks. 10. A more convenient, higher-level, object-oriented representation of neural networks that hides many complexities and inconveniences inherent in NCS's native .in fi le format. 11. A convenient environment in which to convert a neural network description into a chromosomal representation suitable for use with a genetic algorithm. 12. A convenient environment in which to access NCS's realtime stimulus input capabilities, especially for robotic interface applications (see Goodman et al., 2008 for more information on using NCS in robotics). 13. The ability to conveniently extend many of these capabilities without recourse to coding in NCS's native compiled programming environment (the C/C++ language).

WHY PYTHON?
When we selected Python as the language for Brainlab, Python was not yet in wide use in neuroscience, and it was also in the midst of a seemingly endless reorganization of its vector processing math support libraries. Nevertheless, there were hopeful signs of building momentum for Python as a scientifi c platform, and the base language was so appealing in several respects that we selected Python as the language for our project.
Python is an open source, cross platform programming language. The base Python language is constantly being extended and made more powerful by hundreds of developers working together across the world. In addition to the base language, there are dozens of external packages in various states of development, from polished to prototype. These packages gradually move into the base distribution as they mature and if they are of suffi ciently wide interest.
Python is ordinarily compiled into bytecode automatically and the bytecode is then interpreted in a runtime virtual machine. This is essentially the same approach used by Java, though the compilation generally requires an explicit step with Java. Compilation to bytecode results in code execution that is generally faster than ordinary interpreted code. Python is dynamically typed, making programming extremely convenient. Built in datastructures like lists, dictionaries (hashes), and arrays help make Python programs very concise. The clean syntax makes programs easy to understand. Python has a well deserved reputation as an extremely clean and easy to read and understand language.
At the time we selected it, Python already had a growing set of support library packages for scientifi c computation. These have since matured. Some of these packages are used in Brainlab, including: • Matplotlib 12 , a MATLAB-like plotting package • PyOpenGL 13 , OpenGL bindings for Python • NumPy 14 , MATLAB-style array processing • SciPy 15 , a set of scientifi c tools for Python, including pseudo random number generators and transforms

BRAINLAB TO NCS INTERFACE FOR NETWORK MODELING
When we were designing the Python to NCS interface for the fi rst version of Brainlab, there were already a number of ways to interface Python to a C/C++ application. Of these, one approach we considered seriously was to create a Python module out of the NCS C/C++ program with fairly simple and standardized wrapper code using standard techniques 16 . The wrapped C code could then be included into a Python program with the import command. With this approach the Python program would be in charge from the beginning, and it could selectively make normal looking Python function calls into the wrapped C code to actually perform the NCS simulation and other functions. How would the network, cell, synapse, and other neural network parameters be communicated to NCS? A reasonable approach would be to defi ne a new abstract network modeling interface using highlevel Python facilities, perhaps a Python Object class for a Cell, a Synapse, and so on, that allows these objects to be created and interconnected. This Python-based model could then be converted directly to the internal in-memory representation of network models of NCS, called the GCList, through a new function provided by the imported NCS python module. This function, being in the C/C++ side of things, would have full access to the memory structures, memory allocation, and cluster-distribution routines that NCS itself uses to convert the .in fi le representation into the GCList representation for simulation, merely bypassing the fi le parsing NCS normally uses to build its internal network representation. However this tightly integrated approach would have a number of disadvantages. Such a Brainlab system would have to be at least recompiled with every new release of NCS. But there would be more complications than just that. While the NCS .in fi le representation is part of the NCS documentation and is fairly stable, the internal GCList representation does not have a publicly documented interface. The GCList interface changes over time, and when it changes, corresponding detailed C/C++ changes would then have to be made in the NCS/Python module for import. A possibly larger documentation burden also would be placed on Brainlab to describe the new model-building interface.
We opted instead to try to achieve our design goals with a much looser Brainlab-NCS interface for modeling and simulation. We left NCS as a completely separate programming project and did not even try to integrate more tightly with it than its existing published modeling (.in fi le) and invocation (command line) interface. So Brainlab would have to provide a convenient and powerful Pythonic network modeling interface to the user, since that was a primary design goal, but it would also have to emit a properly formatted .in fi le for use by NCS on the back-end. The approach we took to model-building in Brainlab is depicted in Figure 1.
The BRAIN, CELL, LAYER, and other sections of the NCS .in fi le are each implemented in Brainlab as a Python object class. The __repr__() method for each object is overridden so that printing an object results in text for that object in a format suitable for inclusion in the NCS .in fi le. In the case of a lower-level object, this method just prints out the object itself, but does not print any other objects that are referenced by the object being printed. The BRAIN object's __repr__() method, however, fi rst recursively traverses the entire tree of objects referenced from the BRAIN object and a list is composed for each type of referenced object. Once all referenced objects have been collected together, the entire NCS .in fi le is printed, starting with the BRAIN section, and proceeding to all of the other sections of the .in fi le in the conventional order.
The lower-level classes are implemented as nested classes within the BRAIN class. Note that they are not derived subclasses, but rather nested classes. Derived subclasses are appropriate where the subclass has most of the aspects of the superclass but some additional features. In Brainlab the nested classes are not logically subclasses of the BRAIN since they do not share the same characteristics as the super-object but are merely contained by it.

FIGURE 1 | Brainlab's approach to building neural network models for NCS.
A script using the Brainlab brain.py module allocates objects of special modeling object classes (BRAIN, CELL, SYNAPSE, etc.) defi ned in brain.py. These objects each contain a Python dictionary called parms containing (name, value) pairs. Each such name corresponds exactly to an NCS character string parameter name for that record type within the .in fi le. Each value contains either the literal value desired for that parameter, or a Python object that will later be dereferenced and substituted with an appropriate text name for the text section representing that object in the resulting NCS .in fi le. The lower-level objects can be inserted into the higher-level objects through direct manipulation of the parms dict, but generally they are added there implicitly through the brain.py module's helper functions such as BRAIN.AddColumn(). The value of the highest level container object, the BRAIN object, is determined by the overridden __repr__() function, which converts the in-memory model representation into the text .in representation, in the manner described in the text. The result is a Python character string which is a suitable input fi le for the NCS program. However, the lower-level classes do need access to the component type libraries that are stored with the BRAIN class. If the lowerlevel objects were entirely separate classes, they would not have convenient access to the component type libraries. By making the lower-level classes nested within the BRAIN class, they do have that access.
We chose to map many of the modeling details of Brainlab directly onto the underlying NCS implementation, rather than providing a completely new modeling interface. This primarily means that we preserve NCS's text character string names for various neural parameters of the cells, synapses, channels, and so on. This eases the documentation burden on Brainlab since we can refer directly to the NCS's documentation on many points. Furthermore, it makes keeping Brainlab up to date with respect with NCS very easy. Whenever NCS adds support for a new parameter within an existing modeling object, it is usually a simple matter to add it to the permitted parameter list of the appropriate class in brain.py and that is the end of it. (When NCS adds entirely new types of objects, as is occasionally done, there is a bit more work, but even still it is usually just a matter of intelligently cloning an existing object to a new name and making a few changes.) The overall mechanism of .in fi le emission through recursive application of __repr__()'s to discovered objects starting at the top-level BRAIN extends quite easily.
The simple strategies of creating a Python object class for each .in fi le section, with automatic conversion from object to text through the __repr__() method, combined with the ability to reference one object from another, achieved all our design goals for a Pythonic modeling interface to NCS. The modeling power achieved by combining these few concepts in this way should not be underestimated.

BRAINLAB TO NCS INTERFACE FOR SIMULATION
Once the internal Pythonic neural network model is constructed inside the top-level BRAIN object, it can be simulated by invoking the BRAIN's Run() method. Since we elected to keep an armslength interface between Brainlab and NCS, the invocation of NCS is done through the use of a popen() call, as follows. First, Brainlab determines through invocation options or a standard confi guration .rc fi le whether the NCS process is to be invoked locally, or on a remote compute server (typically a cluster). The .in fi le generated from the __repr__() method of the top-level BRAIN object is stored in a disk fi le locally, then propagated to the remote compute server using ssh 17 (secure shell) if necessary. Other support fi les, such as input stimulus patterns, are likewise generated and propagated as needed. Next, the NCS invocation command is constructed, again with appropriate references to remote servers with ssh, and then this command is executed using popen(). Brainlab monitors the realtime progress of the command as NCS reports the progress of the run through the fi le descriptors of the popen(). If an error condition is detected in the output, Brainlab either throws a Python exception, or an error code to the caller. When Brainlab detects that a run has completed, it constructs additional commands to retrieve output fi les from the remote compute server, as needed.
We felt it was essential to support all three stages of operationmodel-building, simulation, and analysis -completely within the control of the Python Brainlab environment. This permits selfcontained and reproducible experiments, in the form of Python Brainlab scripts. This also opens up the possibility of parameterized model search with feedback from model performance affecting parameters of the next iteration, or even the use of genetic programming techniques for parameter search, all within a Brainlab script.

BRAINLAB'S MODULE ORGANIZATION
Brainlab itself is implemented as two main Python modules, brainlab.py and brain.py. The brain.py module contains the parts of the system concerned with building a neural model using Python classes supplied by the module and other normal Python facilities, and then automatically converting this model to a format understandable to NCS (a .in fi le). The brainlab.py module contains support functions for invoking an NCS simulation on a model either locally or remotely on a remote cluster, and analyzing and documenting the results using plotting and other functions.
In addition to these two main modules, an optional module called netplot is available. This module can take a model built using the core BRAIN class of brain.py and convert it into a threedimensional depiction using the model's architecture and hints provided during model construction. The three-dimensional depiction can be examined and explored interactively on a workstation or saved in a number of graphics fi le formats. The PyOpenGL 18 package is used for the actual rendering.

BRAINLAB USAGE BUILDING MODELS WITH BRAINLAB
In Brainlab, every brain model is an instance of a new Python object class called BRAIN. Once the brainlab library itself is brought into a Python program with the import command, creating a brain object is by the usual Python means: import brainlab b = brainlab.BRAIN() The variable b then refers to the newly created, and initially empty, brain model. When a BRAIN object is created, it contains a default set of commonly used types of neural network modeling components. (There are initially no instances of these types in the brain model.) These component types can be directly instantiated and then used for construction of network models, or they can be modifi ed in place and then used in a model, or they can be copied to new types with different names and then the copies can be modifi ed and instantiated for use in a model. The component types are contained in Python dictionaries (hashes), and the keys of the dictionary are simply the text names of the components. These building blocks are automatically included within a Python dictionary called libs in each BRAIN instance. There can be multiple libraries of parts within a BRAIN. The library provided with the class is given the key name standard, and is itself a dictionary. In this dictionary are subdictionaries for the different types of neural modeling components, such as channels (accessed with the chantypes dictionary key), cell types (accessed with the celltypes key), synapse facilitation and depression profi les (under the sfds key), and more as listed below.
The following interactive Python session shows how to view these different library components and shows how one could modify the negative Hebbian learning window duration parameter within the standard Hebbian learning profi le: The Section "Usage Example: RAIN Network" contains another example of creating components based on the included standard library.
An NCS .in fi le contains a number of text blocks, with each block consisting of a number of parameter keywords on the left and their values to the right. The values can be of several types. In the example above, the numbers for the NEG_HEB_WINDOW are a mean and standard deviation. During model initialization, NCS assigns that parameter to a random value from a normal distribution with the mean and standard deviation requested. For other parameters, such as the RSE_INIT parameter of the synapse object, two numeric values specify a minimum and a maximum of a range. In the case of the LEARNING parameter in the example above, the value for a parameter is a text label that references another block defi ned within the fi le. The NCS documentation details each parameter and its expected values. In some cases, Brainlab allows commonly used and frequently modifi ed parameter values to be changed in Brainlab function calls. For example, when specifying a synaptic connection, the probability of the connection and the conductance speed values can be set directly using the prob= and speed= keyword arguments to the Brainlab AddConnect() method. In all cases however, NCS parameters can be set by modifying a dictionary value in the appropriate parms dictionary of the object with the key set to the text name of the NCS parameter name. This approach gives convenience to the programmer while allowing quick access to new NCS parameters as they are added to the system, by simply adding a keyword to a list in the Python class defi nition for that object.
In NCS, cells cannot exist on their own but rather only as part of a higher-level structure called a column. A column is composed of one or more layers, which in turn is composed of one or more groups of cells. Brainlab has COLUMN, LAYER, and CELL objects that correspond to these structures. A Brainlab script can build a column up from cell groups and layers, or instead use a convenience function that will add a pre-built column in a single step. The following Brainlab function adds to the model an instance of an ordinary column populated with a single cell: Additional optional parameters to the function can specify a cell type to use (other than the default), spatial coordinates for the cell, and more.
At this point the Brainlab script typically makes connections between the cells or cell groups. Brainlab functions such as AddConnect() are used for this. The Python variables for the objects are used as the point of contact for connection. An example of this is given in the Sections "Usage Example: Hebbian Learning" and "Usage Example: RAIN Network". Report requests are also added to the brain at this time.

SIMULATING MODELS WITH BRAINLAB
Once the BRAIN object is created, simply printing it with the Python print command causes Brainlab to emit a complete, properly formatted .in fi le containing all the information added to the brain by the modeler. If desired, this fi le can be examined and manually submitted for simulation by NCS. This approach is occasionally useful for debugging purposes, but in practice it is seldom necessary to view the generated .in fi le directly. Instead, the modeler can simply leave the underlying .in fi le mechanism hidden and evoke an NCS simulation directly on the model using the brainlab Run() function on the brain: brainlab.Run (b, nprocs = 32) In this example the simulation is evoked remotely on 32 processors. The .in fi le that results from the model is created by Brainlab behind the scenes, copied over to the compute cluster automatically by Brainlab, and the simulation results are fetched on demand as the data analysis portion of the Brainlab program requires them.
Brainlab is designed primarily to run on the user's workstation, and send jobs across a network to be simulated on a different computer (or cluster). There are several reasons for this focus. The user has more control over the software installed on a personal workstation than on a typical group or departmental compute server or Beowulf cluster, where it may be more diffi cult to get installed the libraries necessary to run Brainlab. Often data will be analyzed repeatedly, displayed and analyzed in a variety of ways, and that is best done on a personal workstation so that specialized tools are guaranteed to be available and also so that other users of the simulation environment will not be affected. Also typically a personal workstation will have high-performance display hardware that will work more effi ciently with extensive graphing, perhaps in three dimensions.
Brainlab can also be confi gured to run directly on the machine where NCS also does the simulation. With modern highperformance multi-core CPUs this is a good option for smaller exploratory simulations.
The encapsulation of the model construction, simulation, and data analysis loop within a single program, a Python Brainlab script, makes automatic model parameter search easier. In some of our work we have defi ned a mapping from artifi cial chromosome to neural network model, and used a standard Python genetic algorithm package to do a fi tness search for the best functioning model (Drewes et al., 2004).

DATA ACCESS, ANALYSIS, AND PLOTTING WITH BRAINLAB
Brainlab provides a few convenience functions for loading, processing, and plotting standard NCS reports. In combination with the SciPy and Matplotlib packages, modelers can do sophisticated mathematical analyses and create complex graphics for view or publication. Effi cient access to very large datasets is available to the modeler through Python's hdf5 interface, pytables. With the PyOpenGL libraries, Brainlab provides some limited threedimensional plotting tools for viewing network models.
We will mention a few of the more commonly used Brainlab data access and plotting routines here. The Brainlab LoadReport() function returns a NumPy array containing all the data captured from a requested NCS report. The data to be loaded can be limited by time range or by range of cells. The returned data can then be processed further in the Brainlab program using the wide range of Python or NumPy tools. The Brainlab function LoadSpikeData() returns a list of just the spike times for a given range of cells for a given time. The ReportPlot() function gives a simple visual representation of continuous NCS report data (often voltages or currents) on screen or into a graphical fi le. Brainlab makes extensive use of the Matplotlib library for the actual generation of the plots.
Brainlab handles remotely invoking a simulation on a compute cluster, and it also simplifi es accessing the resulting NCS report fi les. The same Brainlab LoadReport() function works whether the fi le data was captured remotely or on the local workstation. Brainlab also tries to use knowledge about the simulation environment to be effi cient about management of report fi les. For example, rather than copying large report fi les across a network from the compute cluster to the workstation for processing, Brainlab can in some cases invoke itself remotely on the compute cluster for report processing, and then only copy back the much smaller amount of data that is the result of the processing. The programmer generally does not need to be aware, for either simulation or analysis, that the computation was done remotely. Figure 2 is a sample compound plot, generated using Brainlab convenience functions and the Matplotlib library, from the Hebbian learning simulation detailed in the Section "Usage Example: Hebbian Learning". Refer to Drewes (2005b) for further 2D and 3D Brainlab plot examples.

USAGE EXAMPLE: RAIN NETWORK
In this section, we give an example of how Brainlab is used to create a type of model that our lab has called RAIN (Recurrent Asynchronous Irregular Network). This type of asynchronous, irregularly fi ring network with persistent activity is similar to the models investigated by Vogels and Abbott (2005) and it is also a benchmark model used in the Brette et al. (2007) review of neural simulator systems. Our network has 4000 leaky integrate-and-fi re neurons, 80% excitatory and 20% inhibitory. Each neuron is defi ned as a single compartment model with a time constant, τ = 20 μσ, g leak = 5 ns, and E leak = -60 mV. The neuron will generate an action potential and the membrane potential will reset to the clamped resting potential for 5 ms whenever the membrane potential crosses the threshold at −50 mV. The excitatory neurons differ from the inhibitory ones with a depolarization-activated, noninactivating potassium channel (I m current), which is responsible for the adaptation of fi ring rate of cortical pyramidal cells (Yamada et al., 1998). Both excitatory and inhibitory type synapses are simulated as conductance changes with instantaneous jump at maximal value and exponential decays, i.e., a presynaptic event generates a synaptic conductance change of g , which decays according to the following equation: The synaptic time constants are 5 and 10 ms, and quantal conductances are 5 and 50 nS for excitatory and inhibitory synapses, respectively. All synapses are created with synaptic delay chosen from a normal distribution with a mean of 1 ms and standard deviation of 1 ms.
Neurons were randomly connected by a probability of 2% by conductance-based synapses (Gupta et al., 2000). For outbound inhibitory connections, we incorporate the diversity of GABAergic interneurons. The experiment performed by Gupta et al. (2000) indicates that GABAergic synapses in neocortical layers II to IV have three statistically distinct types of synapses, where each type has particular temporal dynamics of synaptic transmission. The synapses were modeled according to the concepts of the refractoriness of the release process (Markram et al., 1998)  Next we create an new inhibitory synapse profi le called InhSyn1 that is based on the Brainlab standard profi le called I. The facilitation and depression profi le just created is then embedded into the new synapse type. Note that some extraneous parameters inherited from the default profi le are also deleted at this time, and note that the reference to the facilitation and depression profi le is made to the newly-created variable, rather than the text string name of the profi le (though Brainlab supports either, the former is generally easier and less error prone): We omit the section of Brainlab code that creates the cells themselves, but the procedure is similar: a basic cell type is copied from the Brainlab library and a few parameters are selectively modifi ed. The variables returned from the Brainlab function that creates the cells groups are stored in a Python list. So e[0] references the fi rst group created, e[1] the second group created, and so on.
Brainlab provides a single, general AddConnect(from, to) method that can make connections at all three connection levels supported by NCS (within-layer, between-layer, and betweencolumn). The modeler does not need to pay attention to NCS's distinction between these three levels of connection if this is not desired, and this encapsulation can hide much complexity from the user. Furthermore, connections can conveniently be made in Brainlab using the Python variables assigned to the created objects, rather than their underlying .in fi le text names (which the modeler can basically ignore). In our example of a 4000 neurons network, we do divide the network into fi ve cell groups, so that it could be distributed to fi ve computational nodes. The three types of inhibitory synapses connect to both inhibitory and excitatory neurons in the network: The short-term dynamics of inhibitory synapses not only maximize the synaptic diversity, but potentially constrain the functional impact of different interneurons on the long-term dynamics which exist among the excitatory neurons. To incorporate this idea into the model, we also include the spike timing dependent plasticity (STDP) within each cell group (Song et al., 2000). The Brainlab code for these connections is as follows: for i in range (0, 4) Even the fairly simple RAIN network example shown above results in a multi-thousand line .in fi le for NCS. The more concise, programmatic representation of the model in Brainlab makes it easier to create and also easier for others to quickly understand the true structure of the model.

DISCUSSION
We have shown elements of the design, implementation, and usage of Brainlab, a Python toolkit that leverages the strengths of Python to provide a more powerful and convenient interface to the NCS network simulator. We integrated Brainlab to NCS loosely, in a way that required no source code changes to NCS whatsoever. We were able to design a Pythonic neural modeling interface that can automatically convert an object representation into NCS's cumbersome .in representation. For simulation, we also integrate Brainlab loosely with NCS, using Python's sub-process management and standard operating system level tools like ssh for remove invocation as necessary.
Our approach gives us simplicity of implementation and ease of long-term maintainability, with no signifi cant performance penalties on simulations, yet still extends to NCS all the considerable power and fl exibility of Python and its numerical, graphical, special format fi le access, and other support packages.


extfieldsofstudy:
Computer Science
Economics

text:
Query-based sentence fusion is better defined and leads to more preferred results than generic sentence fusion

We show that question-based sentence fusion is a better deﬁned task than generic sentence fusion (Q-based fusions are shorter, display less variety in length, yield more identical results and have higher normalized Rouge scores). Moreover, we show that in a QA setting, participants strongly prefer Q-based fusions over generic ones, and have a preference for union over intersection fusions.

Introduction
Sentence fusion is a text-to-text generation application, which given two related sentences, outputs a single sentence expressing the information shared by the two input sentences (Barzilay and McKeown 2005). Consider, for example, the following pair of sentences: 1 (1) Posttraumatic stress disorder (PTSD) is a psychological disorder which is classified as an anxiety disorder in the DSM-IV.
(2) Posttraumatic stress disorder (abbrev. PTSD) is a psychological disorder caused by a mental trauma (also called psychotrauma) that can develop after exposure to a terrifying event. * Thanks are due to Ed Hovy for discussions on the Rouge metrics and to Carel van Wijk for statistical advice. The dataset described in this paper (2200 fusions of pairs of sentences) is available upon request. This research was carried out within the Deaso project (http://daeso.uvt.nl/). 1 All examples are English translations of Dutch originals.
Fusing these two sentences with the strategy described by Barzilay and McKeown (based on aligning and fusing the respective dependency trees) would result in a sentence like (3).
(3) Posttraumatic stress disorder (PTSD) is a psychological disorder. Barzilay and McKeown (2005) argue convincingly that employing such a fusion strategy in a multidocument summarization system can result in more informative and more coherent summaries.
It should be noted, however, that there are multiple ways to fuse two sentences. Besides fusing the shared information present in both sentences, we can conceivably also fuse them such that all information present in either of the sentences is kept, without any redundancies. Marsi and Krahmer (2005) refer to this latter strategy as union fusion (as opposed to intersection fusion, as in (3)). A possible union fusion of (1) and (2) would be: Posttraumatic stress disorder (PTSD) is a psychological disorder, which is classified as an anxiety disorder in the DSM-IV, caused by a mental trauma (also called psychotrauma) that can develop after exposure to a terrifying event. Marsi and Krahmer (2005) propose an algorithm which is capable of producing both fusion types. Which type is more useful is likely to depend on the kind of application and information needs of the user, but this is essentially still an open question.
However, there is a complication. Daumé III & Marcu (2004) argue that generic sentence fusion is an ill-defined task. They describe experimental data showing that when participants are given two consecutive sentences from a single document and are asked to fuse them (in the intersection sense), different participants produce very different fusions. Naturally, if human participants cannot reliably perform fusions, evaluating automatic fusion strategies is always going to be a shaky business. The question is why different participants come to different fusions. One possibility, which we explore in this paper, is that it is the generic nature of the fusion which causes problems. In particular, we hypothesize that fusing two sentences in the context of a preceding question (the natural setting in QA applications) results in more agreement among humans. A related question is of course what the results would be for union fusion. Will people agree more on the unions than on the intersections? And is the effect of a preceding question the same for both kinds of fusion? In Experiment I, below, we address these questions, by collecting and comparing four different fusions for various pairs of related sentences, both generic and question-based ones, and both intersection and union ones.
While it seems a reasonable hypothesis that question-based fusions will lead to more agreement among humans, the really interesting question is which fusion strategy (if any) is most appreciated by users in a task-based evaluation. Given that Experiment I gives us four different fusions per pair of sentence, an interesting follow-up question is which leads to the best answers in a QA setting. Do participants prefer concise (intersection) or complete (union) answers? And does it matter whether the fusion was question-based or not? In Experiment II, we address these questions via an evaluation experiment using a (simulated) medical questionanswering system, in which participants have to rank four answers (resulting from generic and questionbased intersection and union fusions) for different medical questions.

Experiment I: Data-collection
Method To collect pairs of related sentences to be fused under different conditions, we proceeded as follows. As our starting point we used a set of 100 medical questions compiled as a benchmark for evaluating medical QA systems, where all correct answers were manually retrieved from the available text material. Based on this set, we randomly selected 25 questions for which more than one answer could be found (otherwise there would be nothing to fuse), and where the first two answer sentences shared at least some information (otherwise intersection fusion would be impossible).
Participants were 44 native speakers of Dutch (20 women) with an average age of 30.1 years, none with a background in sentence fusion research. Experiment I has a mixed between-within subjects design. Participants were randomly assigned to either the intersection or the union condition, and within each condition they first had to produce 25 generic and then 25 question-based fusions. In the latter case, participants were given the original question used to retrieve the sentences to be fused.
The experiment was run using a web-based script. Participants were told that the purpose of the experiment was merely to gather data, they were not informed about our interest in generic vs question based fusion. Before participants could start with their task, the concept of sentence fusion (either fusion or intersection, depending on the condition) was explained, using a number of worked examples. After this, the actual experiment started.
Results First consider the descriptive statistics in Table 1. Naturally, intersection fusion leads to shorter sentences on average than union fusion. More interestingly, question (Q)-based fusions lead to significantly shorter sentences than their generic counterparts (intersection t = 9.1, p < .001, union: t = 6.1, p < .001, two-tailed). Also note that  the variation among participants decreases in the Qbased conditions (lower standard deviations). This suggests that participants in the Q-based conditions indeed show less variety in their fusions than participants in the generic conditions. This is confirmed by the number of identical (i.e., duplicated) fusions, which is indeed higher in the Q-based conditions, although the difference is only significant for intersections (χ 2 (1) = 51.3, p < .001).
We also computed average Rouge-1, Rouge-SU4 and Rouge-SU9 scores for each set of fusions, to be able to quantify the overlap between participants in the various conditions. One complication is that these metrics are sensitive to sentence-length (longer sentences are more likely to contain overlapping words than shorter ones), hence in Table 2 we report on Rouge scores that are normalized with respect sentence length. The resulting picture is surprisingly consistent: Q-based fusion on all three metrics results in higher normalized Rouge scores, where the difference is generally small in the case of union, and rather substantial for intersection.

Experiment II: Evaluation
The previous experiment indicates that Q-based fusion is indeed a better-defined summarization task than generic fusion, in this experiment we address the question which kind of fusion participants prefer in a QA application.
Method We selected 20 from the 25 questions used in Experiment I, for which we made sure that the fusions in the four categories resulted in sentences with a sufficiently different content. For each question, one representative sentence was selected from the 22 fusions produced by participants in Experiment I, for each of the four categories (Q-based intersection, Q-based union, Generic intersection and Generic union). This

Fusion type
Mean Rank Q-Based Union 1.888 Q-Based Intersection 2.471 Generic Intersection 2.709 Generic Union 2.932 Table 4: Mean rank from 1 (= "best") to 4 (="worst") as a function of fusion type.
representative sentence was the most frequent result for that particular category. When no such sentence was present for a particular task, a random selection was made. Participants were 38 native speakers of Dutch (17 men), with an average age of 39.4 years. None had participated in Experiment I and none had a background in sentence fusion research. Participants were confronted with the selected 20 questions, one at a time. For each question, participants saw four alternative answers (one from each category). Figure 3 shows one question, with four different fusions derived by participants from example sentences (1) and (2). Naturally, the labels for the 4 fusion strategies were not part of the experiment. Participants were asked to rank the 4 answers from "best" (rank 1) to "worst" (rank 4), via a forced choice paradigm (i.e., they also had to make a choice if they felt that two answers were roughly as good). Experiment II had a within-subjects design, which means that all 38 participants ranked the answers for all 20 questions.
Results Table 4 gives the mean rank for the four fusion types. To test for significance, we performed a repeated measures Analysis of Variance (ANOVA) with fusion type and question as the independent variables and average rank as the dependent variable. A main effect was found of fusion type (F (3, 111) = 20.938, p < .001, η 2 = .361).
What is PTSD? Generic Intersection Posttraumatic stress disorder (PTSD) is a psychological disorder.
Q-based Intersection PTSD stands for posttraumatic stress disorder and is a psychological disorder.

Generic Union
Posttraumatic stress disorder (PTSD) is a psychological disorder, which is classified as an anxiety disorder in the DSM-IV, caused by a mental trauma (also called psychotrauma) that can develop after exposure to a terrifying event.
Q-based Union PTSD (posttraumatic stress disorder) is a psychological disorder caused by a mental trauma (also called psychotrauma) that can develop after exposure to a terrifying event. Pairwise comparisons using the Bonferroni method show that all comparisons are statistically significant (at p < .001) except for the one between Generic Intersection and Generic Union. Thus, in particular: Q-based union is ranked significantly higher than Q-based intersection, which in turn is ranked significantly higher than both Generic union and intersection (whose respective ranks are not significantly different). The ANOVA analysis also revealed a significant interaction between question and type of fusion (F (57, 2109) = 7.459, p < .001, η 2 = .168). 2 What this means is that relative ranking varies for different questions. To better understand this interaction, we performed a series of Friedman tests for each question (the Friedman test is a standard nonparametric test for ranked data). The Friedman analyses revealed that the overall pattern (Q-based union > Q-based intersection > Generic Union / Intersection) was found to be significant for 13 out of the 20 questions. For four of the remaining seven questions, Q-based union ranked first as well, while for two questions Q-based intersection was ranked as the best answer. For the remaining question, there was no significant difference between the four fusion types.

Conclusion and discussion
In this paper we have addressed two questions. First: is Q-based fusion a better defined task than generic fusion? Here, the answer seems to be "yes": Qbased fusions are shorter, display less variety in length, result in more identically fused sentences 2 Naturally, there can be no main effect of question, since there is no variance; the ranks 1-4 are fixed for each question. and have higher normalized Rouge scores, where the differences are larger for intersection than for union. Inspection of the fused sentences reveals that there is simply more potential variation on the word level (do I select this word from one input sentence or from the other?) for union fusion than for intersection fusion. Second: which kind of fusion (if any) do users of a medical QA system prefer? Here a consistent preference order was found, with rank 1 = Q-based union, rank 2 = Q-based Intersection, rank 3/4 = Generic intersection / union. Thus: participants clearly prefer Q-based fusions, and prefer more complete answers over shorter ones.
In future research, we intend to collect new data with different questions per sentence pair, to find out to what extent the question and its phrasing drive the fusion process. In addition, we will also let sentences from different domains be fused, based on the hypothesis that fusion strategies may differ across domains.


extfieldsofstudy:
Computer Science
Mathematics

text:
Construction of Z4-linear Reed-Muller codes

New quaternary Plotkin constructions are given and are used to obtain new families of quaternary codes. The parameters of the obtained codes, such as the length, the dimension and the minimum distance are studied. Using these constructions new families of quaternary Reed-Muller codes are built with the peculiarity that after using the Gray map the obtained Z4-linear codes have the same parameters and fundamental properties as the codes in the usual binary linear Reed-Muller family. To make more evident the duality relationships in the constructed families the concept of Kronecker inner product is introduced.

Introduction
In [13] Nechaev introduced the concept of Z 4 -linearity of binary codes and later, in [7], Hammons, Kumar, Calderbank, Sloane and Solé showed that several families of binary codes are Z 4 -linear. In [7] it is proved that the binary linear Reed-Muller code RM (r, m) is Z 4 -linear for r = 0, 1, 2, m − 1, m and is not Z 4 -linear for r = m − 2 (m ≥ 5). In a subsequent work, Hou, Lahtonen and Koponen [8], proved that RM (r, m) is not Z 4 -linear for 3 ≤ r ≤ m − 2.
In [7] it is introduced a construction of codes, called QRM(r, m), based on Z 4 -linear codes, such that after doing modulo two we obtain the usual binary linear Reed-Muller (RM ) codes. In [2,3] such family of codes is studied and their parameters are computed as well as the dimension of the kernel and rank. In [16] a kind of Plotkin construction was used to build a family of additive Reed-Muller codes and also in [19] it was used a Plotkin construction to obtain a sequence of quaternary linear Reed-Muller like codes. In both last quoted constructions, the images of the obtained codes under the Gray map are binary codes with the same parameters as the binary linear RM codes. Moreover, on the other hand, in [5,9,10,14] were classified all the non-equivalent Z 2 Z 4 -linear extended 1-perfect codes and their duals, the Z 2 Z 4 -linear Hadamard codes. It is a natural question to ask for the existence of families of quaternary linear codes such that, after the Gray map, the corresponding Z 4 -linear codes have the same parameters as the well known family of binary linear RM codes. In these new families, like in the usual RM (r, m) family, the code with (r, m) = (1, m) should be a Hadamard code and the code with (r, m) = (m − 2, m) should be an extended 1-perfect code.
It is well known that an easy way to built the binary RM family of codes is by using the Plotkin construction [12]. So, it seems a good matter of study to try to generalize the Plotkin construction to the quaternary linear codes and try to obtain new families of codes which contain the above mentioned Z 2 Z 4linear Hadamard codes and Z 2 Z 4 -linear extended 1-perfect codes and fulfill the same properties from a parameters point of view (length, dimension, minimum distance, inclusion and duality relationship) than the binary RM family.
In this paper we begin by studying the Z 4 -linear case and we organize it in the following way. In Section 2 we introduce the concept of quaternary code and give some constructions that could be seen as quaternary generalizations of the well known binary Plotkin construction. In Section 3, we construct several families of Z 4 -linear Reed-Muller codes and prove that they have similar parameters as the classical binary RM codes but they are not linear. In Section 4, we discuss the concept of duality for the constructed Z 4 -linear Reed-Muller codes and, finally, in Section 5 we give some conclusions and further research in the topic.

Constructions of quaternary codes 2.1 Quaternary codes
Let Z 2 and Z 4 be the ring of integers modulo two and modulo four, respectively. Let Z n 2 be the set of all binary vectors of length n and Z N 4 be the set of all quaternary vectors of length N . Any non-empty subset C of Z n 2 is a binary code and a subgroup of Z n 2 is called a binary linear code. Equivalently, any non-empty subset C of Z N 4 is a quaternary code and a subgroup of Z N 4 is called a quaternary linear code. In general, any non-empty subgroup C of Z α 2 × Z β 4 is an additive code.
The Hamming weight w H (u) of a vector in Z n 2 is the number of its nonzero coordinates. The Hamming distance d(u, v) between two vectors u, v ∈ Z n 2 is d(u, v) = w H (u − v). For quaternary codes it is more appropriate to use the Lee metric [11]. In Z 2 the Lee weight coincides with the Hamming weight, but in Z 4 the Lee weight of their elements is w L (0) = 0, w L (1) = w L (3) = 1, and w L (2) = 2. The Lee weight w L (u) of a vector in Z N 4 is the addition of the Lee weight of all the coordinates. The Lee distance d L (u, v) between two vectors is the usual Gray map, so φ(v 1 , . . . , v β ) = (ϕ(v 1 ), . . . , ϕ(v β )), and ϕ(0) = (0, 0), ϕ(1) = (0, 1), ϕ(2) = (1, 1), ϕ(3) = (1, 0). We will use the symbols 0, 1 and 2 for the all zeroes, the all ones and the all twos vectors, respectively (by the context it will be always clear we speak about the binary vectors 0, 1 or quaternary, it will also be clear the length of the vectors).
Hamming and Lee weights, as well as Hamming and Lee distances, can be generalized, in a natural way, to vectors in Z α 2 × Z β 4 by adding the corresponding weights (or distances) of the Z α 2 part and the Z β 4 part. Since C is a subgroup of Z α 2 ×Z β 4 , it is also isomorphic to an abelian structure like Z γ 2 × Z δ 4 . Therefore, we have that |C| = 2 γ 4 δ and the number of order two codewords in C is 2 γ+δ . We call such code C an additive code of type (α, β; γ, δ) and the binary image C = Φ(C) a Z 2 Z 4 -linear code of type (α, β; γ, δ). In the specific case α = 0 we see that C is a quaternary linear code and its binary image is called a Z 4 -linear code. Note that the binary length of the binary code The minimum Hamming distance d of a Z 2 Z 4 -linear code C is the minimum value of d(u, v), where u, v ∈ C and u = v. Notice that the Hamming distance of a Z 2 Z 4 -linear code C coincides with the Lee distance defined in the additive code C = Φ −1 (C). From now on, when we work with distances it must be understood that we deal with Hamming distances in the case of binary codes or Lee distances in the case of additive codes.
Although C could not have a basis, it is appropriate to define a generator matrix for C as where B 2 is a γ × α matrix; Q 2 is a γ × β matrix; B 1 is a δ × α matrix and Q 1 is a δ × β matrix. Matrices B 1 , B 2 are binary and Q 1 , Q 2 are quaternary, but the entries in Q 2 are only zeroes or twos. Two additive codes C 1 and C 2 both of the same length are said to be monomially equivalent, if one can be obtained from the other by permuting the coordinates and multiplying by −1 of certain coordinates. Additive codes which differ only by a permutation of coordinates are said to be permutation equivalent.
For Z 2 Z 4 -linear codes is usual to use the following definition of inner product in Z α 2 × Z β 4 that we will call the standard inner product [18,4]: where u, v ∈ Z α 2 × Z β 4 . We can also write the standard inner product as where J N = 2I α 0 0 I β , N = α + β, is a diagonal matrix over Z 4 . Note that when α = 0 the inner product is the usual one for vectors over Z 4 and when β = 0 it is twice the usual one for vectors over Z 2 .
For α = 0 and N = β = 2 i , i = 1, 2, 3, . . ., we can define the inner product in an alternative way. Let K 2 = 1 0 0 3 be a matrix over Z 4 and define where denotes the Kronecker product of matrices. We call the Kronecker inner product the following: The additive dual code of C, denoted by C ⊥ , is defined in the standard way as for all v ∈ C} or, using the Kronecker inner product The definition and notations will be the same for the Z 4 -duality obtained by using the standard inner product or the Kronecker inner product and the difference will be clear from the context.
Note that u, v ⊗N = u·K N ·v t = u, v·K N . Hence, both additive dual codes by using the standard inner product or the Kronecker inner product, respectively, are monomially equivalent and so they have the same weight distribution. For both inner products, the additive dual code C ⊥ is also an additive code, that is a subgroup of Z α 2 ×Z β 4 . Its weight enumerator polynomial is related to the weight enumerator polynomial of C by the MacWilliams identity [6]. The corresponding binary code Φ(C ⊥ ) is denoted by C ⊥ and called the Z 2 Z 4 -dual code of C. In the case α = 0, the code C ⊥ is also called the quaternary dual code of C and C ⊥ the Z 4 -dual code of C. Notice that C and C ⊥ are not dual in the binary linear sense but the weight enumerator polynomial of C ⊥ is the McWilliams transform of the weight enumerator polynomial of C. Given an additive code C of type (α, β, γ, δ) it is known the type of the additive dual code ( [4] for additive codes with α = 0 and [7] for additive codes with α = 0).
In the present paper, as we will see later, the duality concept using the Kronecker inner product will make more visible the property that if a code C belongs to a family of Reed-Muller codes then its dual code belongs to the same family.
From now on, we focus our attention specifically to additive codes with α = 0, so quaternary linear codes such that after the Gray map they give rise to Z 4 -linear codes. Given a quaternary linear code of type (0, β; γ, δ), we will write (N ; γ, δ) to say that α = 0 and β = N .

The Plotkin construction
In this section, we show that the well-known binary Plotkin construction can be generalized to quaternary linear codes.
Let A and B be two quaternary linear codes of types (N ; γ A , δ A ) and (N ; γ B , δ B ) and minimum distances d A , d B , respectively. Given u ∈ Z N 4 define supp(u) ⊂ {1, . . . , N } as the set of nonzero coordinates of vector u.
Definition 1 (Plotkin Construction) Given two quaternary linear codes A and B, we define a quaternary linear code as It is easy to see that if G A and G B are generator matrices of A and B, respectively, then the matrix is a generator matrix of the code PC(A, B).

Proposition 2
The quaternary linear code PC(A, B) defined using the Plotkin construction is of type (2N ; γ, δ), where γ = γ A + γ B and δ = δ A + δ B ; the binary length is n = 4N ; the size is 2 γ+2δ and the minimum distance is d = min{2d A , d B }.
Proof: The type, the binary length and the size of PC(A, B) can be easily computed from the definition of the code. The minimum distance can be established as in the binary case [12] but, by completeness, we include the proof. Let us consider any vector u ∈ PC(A, B) such that u = (u 1 |u 1 + u 2 ), where u 1 ∈ A and u 2 ∈ B. Since PC(A, B) is a quaternary linear code, it is enough to prove that the weight w L (u) is not less than d. If If u 2 = 0, by using the triangle inequality we immediately obtain Hence d ≥ min{2d A , d B }. The equality holds because taking the specific vectors u 1 ∈ A with minimum weight d A and u 2 ∈ B with minimum weight d B we obtain w L (u 1 |u 1 ) = 2d A and w L (0|v 2 ) = d B .

The quaternary Plotkin construction
A useful generalization of the above construction to obtain quaternary linear codes is the following construction, called the quaternary Plotkin construction. Such construction was used, for example, in [10] for the classification of all Z 4 -linear Hadamard codes.

Definition 3 (Quaternary Plotkin Construction) Given two quaternary linear codes A and B, we define the quaternary linear code
It is easy to see that if G A and G B are generator matrices of A and B, then the matrix is a generator matrix of the code QP(A, B).

Proposition 4 The quaternary linear code QP(A, B) given in Definition 3 is of type
Proof: The type, the binary length and the size of QP(A, B) can be easily computed from the definition of the code. To check the minimum distance of QP(A, B) let us consider any vector u ∈ QP(A, B). Vector u can be represented by u = (u 1 |u 1 |u 1 |u 1 ) + (0|u 2 |2u 2 |3u 2 ), where u 1 ∈ A and u 2 ∈ B. Since QP(A, B) is a quaternary linear code it is enough to show that the weight of u is at least d. If The equality holds taking a vector u 1 ∈ A of minimum weight. For It is easy to see that if G A , G B , G C and G D are generator matrices of A, B, C and D, then the matrix is a generator matrix of the code DP(A, B, C, D).

Proposition 6
The quaternary linear code DP(A, B, C, D) given in Defini- the binary length is n = 8N ; the size is 2 γ+2δ and the minimum distance is Proof: The type, the binary length and the size of the code DP(A, B, C, D) can be easily computed from the definition.
To check the minimum distance of the code DP(A, B, C, D) let us consider any vector u from this code. It can be represented as u = (u 1 |u 1 |u 1 |u 1 ) + (0|u 2 |2u 2 |3u 2 ) + (0|0|u 3 |u 3 ) + (0|0|0|u 4 ), where u 1 ∈ A, u 2 ∈ B, u 3 ∈ C and u 4 ∈ D. Since DP(A, B, C, D) is a quaternary linear code it is enough to show that the weight of u is, at least, d.
If u 2 = 0 then we can write u = (u 1 |u 1 |u 1 |u 1 ) + (0|0|u 3 |u 3 + u 4 ) so that u ∈ PC((A|A), PC(C, D)), where (A|A) is the code generated by (G A |G A ). Using Proposition 2 we obtain Note that in case B = C the bound is tight because d B = d C and the minimum distance d = min{4d A , 2d C , d D } can be obtained taking specific vectors from A, C or D.

The BQ-Plotkin construction
We slightly change the construction given in Definition 5 in order to obtain a tight bound for the minimum distance. We call this new construction the BQ-Plotkin construction.
Let A, B and C be three quaternary linear codes of types (N ; γ A , δ A ), (N ; γ B , δ B ), (N ; γ C , δ C ), with minimum distances d A , d B and d C , respectively.
Definition 7 (BQ-Plotkin Construction) Let G A , G B and G C be generator matrices of the quaternary linear codes A, B and C, respectively. We define a new code BQ(A, B, C) as the quaternary linear code generated by where G ′ B is the matrix obtained from G B after switching twos by ones in their γ B rows of order two andĜ B is the matrix obtained from G B after removing their γ B rows of order two.
Proof: The type, the length and the size of BQ(A, B, C) can be easily computed from the definition of the code.
If u 2 = 0 then by using the same arguments as in Proposition 6 we have If u 2 = 0 then we distinguish two cases. If u 4 = 0 then Using twice the triangle inequality, the case u 4 = 0 easily gives But the equality holds after the following considerations.
Taking the specific vector u 1 ∈ A with minimum weight d A we obtain w L (u 1 |u 1 |u 1 |u 1 ) = 4d A .
Taking the specific vector u 4 ∈ C with minimum weight d C we obtain w L (0|0|0|u 4 ) = d C .

Quaternary Reed-Muller codes
The usual binary linear RM family of codes is one of the oldest and interesting family of codes. The codes in this family are easy to decode and their combinatorial properties are of great interest to produce new optimal codes. For any integer m ≥ 1 the family of binary linear RM codes is given by the sequence RM (r, m), where 0 ≤ r ≤ m. The code RM (r, m) is called the r-th order binary linear Reed-Muller code of length n = 2 m and it is true that Let 0 ≤ r ≤ m, m ≥ 1. Following [12] the RM (r, m) code of order r can be constructed by using the Plotkin construction in the following way: It is important to note that if we fix m, once we know the sequence RM (r, m) for all 0 ≤ r ≤ m, then it is easy to obtain the new sequence RM (r, m + 1) by using the Plotkin construction (3).
Moreover, the codes in the RM family fulfill the basic properties summarized in the following theorem: In the recent literature [7,20,2,3] several families of quaternary linear codes have been proposed and studied trying to generalize the RM codes. However, when we take the corresponding Z 4 -linear codes, they do not satisfy all the properties in Theorem 9. This last requirement is the main goal of the present work, to construct new families of quaternary linear codes such that, after the Gray map, we obtain Z 4 -linear codes with the parameters and properties quoted in Theorem 9. The result of the present paper generalizes the results in [19].

The family of RM(r, 1) codes
We begin by considering the trivial case of m = 1, that is, the case of codes of binary length n = 2 1 . The quaternary linear Reed-Muller code RM(0, 1) is the repetition code with only one nonzero codeword (the vector with only one quaternary coordinate of value 2). This quaternary linear code is of type (1; 1, 0). The code RM(1, 1) is the whole space Z 1 4 , so a quaternary linear code of type (1; 0, 1).
These two codes, RM(0, 1) and RM(1, 1), after the Gray map, give binary codes with the same parameters of the corresponding binary codes RM (r, 1) and with the same properties described in Theorem 9. In this case, when m = 1, not only these codes have the same parameters, but they have the same codewords.
We will refer to these codes as RM 0 (0, 1) and RM 0 (1, 1), respectively, as it is shown in Table 1. In each entry of this table there are the parameters (γ, δ) of the corresponding code of type (N ; γ, δ).
Since we will need an specific representation for these codes in Table 1, we will agree in using further the following matrices as the generator matrices for each one of them. The generator matrix of RM 0 (0, 1) is G 0 (0, 1) = 2 and the generator matrix of RM 0 (1, 1) is G 0 (1, 1) = 1 .

Plotkin and BQ-Plotkin constructions
The first important point is to apply the Plotkin construction to quaternary linear Reed-Muller codes.
For m = 3, it is well known that there exist two Z 4 -linear Hadamard codes [10]. So, our goal is to construct two families of quaternary linear Reed-Muller codes as it is shown in Table 3. The codes in the first row of Table 3 can be obtained due to the Plotkin construction from the codes of Table 2. But, the codes in the second row can not be obtained by using only the Plotkin construction. It is in this case that we need to exploit the new BQ-Plotkin construction as we will see later in this section.
Constructions of additive codes with the parameters of the binary linear Reed-Muller codes by using only the Plotkin construction were initiated in [16,19].   the codes generated by G ′ i andĜ i , respectively, such that for i = 1, 2, 3 it is true that
Proof: It is straightforward to see that the Plotkin construction fulfills the properties.
For the BQ-Plotkin construction the property (i) is clear from Definition 7. Now, the generator matrix ofBQ(A i+2 , A i+1 , A i ) has the following form: Using the properties (ii) and (iii) for the matrices using the properties (ii) and (iii) for the matrices G i , G i+1 , G i+2 we obtain the property (iii) for BQ(A i+2 , A i+1 , A i ) and i = 1.
Finally, the generator matrix of BQ(A i+2 , A i+1 , A i ) has the form Using the properties (ii), (iii) and (iv) for the matrices G i , G i+1 , G i+2 we obtain the property (iv) for BQ(A i+2 , A i+1 , A i ) and i = 1.  Proof: The type (4N ; γ s r,m , δ s r,m ) of the code RM s (r, m) and the minimum distance can be computed from Proposition 8.
Proof: All the rows in matrix G s (m − 1, m) are vectors of even weight. So, to prove that this matrix generates RM s (m − 1, m) we only need to check if the dimension is the adequate.
We will prove, by induction on m ≥ 1, that γ s m−1,m = 1 and δ s m−1,m = 2 m−1 − 1. The claim is trivially true for m = 1 and m = 2 using the matrices defined in section 3.1 and in (4). Suppose the claim is true for m ≥ 2.  Using Theorems 10 and 12 we can construct the RM codes in the two rows of Table 3. We do not write the generator matrices for codes RM 0 (r, 3) because they can be directly obtained from the respective codes for m = 2 by using the Plotkin construction. For the codes in the family RM 1 (r, 3) we present the generator matrices as a direct application of Theorem 12: and the remaining code RM 1 (3, 3) in the family is the whole space Z 2 2 4 . All these codes, after the Gray map, give binary codes with the same parameters as the codes RM (r, 3) and with the same properties described in Theorem 9. In the case m = 3, like in the case m = 2 not only these codes have the same parameters, but they have the same codewords. This is not in this way for all the other values m > 3. Now, from Table 3 and by using the Plotkin construction we can construct the two families of the codes RM s (r, 4) for s = 0, 1, as it is shown in Table 4. Note that the family of codes RM 1 (r, 4) also can be obtained using the BQ-Plotkin construction from the family of codes RM 0 (r, 2) in Table 2.
Note that RM 0 (r, 5) only can be obtained applying the Plotkin construction, RM 2 (r, 5) only can be obtained applying the BQ-Plotkin construction, but RM 1 (r, 5) can be obtained by using the Plotkin or the BQ-Plotkin construction.
In general, for m > 1, the code RM 0 (r, m) can be only obtained applying the Plotkin construction. As it is proved in Theorems 10 and 12 the constructed families of RM codes satisfy the same properties we stated for binary linear Reed-Muller codes in Theorem 9 except for the duality. In the following Section we will discuss this topic.
Notice that, after the Gray map, the constructed RM families of quaternary linear Reed-Muller codes have not only the same parameters as the usual binary linear family of RM codes, but also the characteristic properties of codes RM s (1, m) and RM s (m − 2, m) as it is stated in the following proposition.

Duality
For the usual binary linear RM codes we know that the codes RM (r, m) and RM (m − r − 1, m) are dual to each other. The families of RM codes have the same property if we use the Kronecker inner product to define the Z 4 -duality.
Throughout this section the notion of duality will be related to the Kronecker inner product defined in (2).
We begin by studying the duality properties for the family of RM codes obtained by using the BQ-Plotkin construction, that is, we are going to prove the duality relationships for the family of codes RM s (r, m), m odd, s = m−1 2 , constructed from the family RM s−1 (r, m − 2).
Basically, we will prove this fact by induction but, previously, we need two technical lemmas. We will use G s (r, m) to refer to the generator matrix of code RM s (r, m); the matrices G ′ s (r, m),Ĝ s (m − r − 1, m) will have the meaning that we introduced in Definition 7 and RM ′ s (r, m),R M s (m − r − 1, m) will be the codes generated by G ′ s (r, m) andĜ s (m − r − 1, m), respectively.
Lemma 17 Let u, v ∈ Z N 4 be any two vectors such that u = (u 1 |u 2 ) and Proof: Straightforward from the Kronecker inner product definition. Proof: We proceed by induction on m beginning with m = 3. Using (9) it is easy to see that the assertion is true for m = 3.
For the case when r is odd the statement is trivially true, since there is nothing to proof. Indeed, from Lemma 15, γ s r,m = 0 and so G ′ s (r, m)\Ĝ s (r, m) = ∅. Hence, along this proof we can take r as an even integer. Now, for m > 3 and 0 < r ≤ m − 2, assume by induction hypothesis that for all x ∈ G ′ s−1 (r, m − 2)\Ĝ s−1 (r, m − 2) and y ∈R M s (m − r − 3, m − 2) is x, y ⊗N/4 = 0.
Finally, we prove the statement for r = 0; r = m − 1 and r = m. For r = 0, we proceed by induction. Case m = 3 is trivially true taking into account (9). We have u ∈ G ′ s (0, m)\Ĝ s (0, m) and so u is the all ones vector u = (1, 1, . . . Proof: Since |RM s (r, m)| · |RM s (m − r − 1, m)| = 2 m , it suffices to prove that for every u ∈ G s (r, m) and v ∈ G s (m − r − 1, m) we have u, v ⊗N = 0. We proceed by induction on m. The claim is trivially true for m = 1. Now, for m > 1 and 0 ≤ r ≤ m, assume by induction hypothesis that for all x ∈ G s−1 (r, m − 2) and y ∈ G s−1 (m − r − 3, m − 2) it is true that x, y ⊗N/4 = 0.

Conclusion
New constructions based on quaternary linear codes has been proposed such that, after doing a Gray map, the obtained Z 4 -linear codes fulfill the same properties and fundamental characteristics as the binary linear RM codes. Apart from the parameters characterizing each code an important property which remains in these new presented families is that the first order RM code is, under the Gray map, a Z 4 -linear Hadamard code and the (m − 2)-th order RM code, after the Gray map, is a Z 4 -linear extended perfect code, like in the usual binary case. So the families of codes obtained in the paper, after the Gray map, contain the families of Z 4 -linear extended perfect and Z 4 -linear Hadamard codes introduced in [9,10]. Moreover, it is important to note that, after defining the Kronecker inner product, the codes RM(r, m) and RM(m − r − 1, m) are dual each other like in the binary linear case.
There are several questions and subjects related to this work where would be of great interest to go deeply. The first one is about the generalization of the constructions of RM codes to the case of general additive codes, so the case of additive codes with α = 0. It is known from [5] that there exist Z 2 Z 4 -linear perfect and Hadamard codes (which are not Z 4 -linear) and these could be the starting point of the new families. Other questions of interest are related to uniqueness (up to equivalence) of the codes in a given family of RM codes, weight distribution, etc.