Document Re-ranking via Wikipedia Articles for Definition/Biography Type Questions

In this paper, we propose a document re-ranking approach based on the Wikipedia articles related to the specific questions to re-order the initial retrieved documents to improve the precision of top retrieved documents in Chinese information retrieval for question answering (IR4QA) system where the questions are definition or biography type. On one hand, we compute the similarity between each document in the initial retrieved results and the related Wikipedia article. On the other hand, we do clustering analysis for the documents based on the K-Means clustering method and compute the similarity between each centroid of the clusters and the Wikipedia article. Then we integrate the two kinds of similarity with the initial ranking score as the last similarity value and re-rank the documents in descending order with this measure. Experiment results demonstrate that this approach can improve the precision of the top relevant documents effectively.

Introduction
It is reported that most of the information system users are accustomed to browse the top returned search results only (iProspect, 2004), so they hope the top ranking documents are highly relevant. In order to meet the information need, it is necessary and significant to improve the precision of top retrieved documents. Currently, document re-ranking has become one of the main streams to improve the precision of top retrieved documents. After document reranking, it is expected that more relevant documents appear in the higher rankings.
In information retrieval system, users often submit the query which is a short description by natural language, and they decides the relevance of document not based on existence of query terms, but semantics of query terms in documents. If the IR system just simply checks the existence of query terms in documents without considering the context of documents, it often causes term mismatch and declines the performance greatly (Salton and McGill, 1983). So the important problem in automatic document re-ranking is the relevance measure of document and query. The strategies, such as query expansion, latent semantic indexing (LSI) and mutual information, have been proposed to solve this problem. And it has been proved that these approaches can improve the performance of the retrieval system effectively. Geetha and Kannan (2007) put forward another approach to solve this problem. When the initial results are returned, the user can choose a document of interest as the seed document and initiate the re-ranking algorithm by which documents are re-ranked based on its similarity distance from the seed document. This algorithm helps users to re-rank documents based on seed document as a query. But it needs the interaction of users.
In this paper, we make use of the related Wikipedia articles to calculate the Wiki-Document and Wiki-Cluster similarities to adjust the ranking score for document re-ranking to solve the problem mentioned above.
As we know, Wikipedia 1 is a multilingual, web-based, free-content encyclopedia project, and each of its article provides information to explain the term of the article title. We can make use of the related Wikipedia article as the "seed" document of a query, without choosing the seed documents manually, mentioned by Geetha and Kannan. We calculate the similarity distance between the seed document and each document in the initial retrieved results, named Wiki-Document similarity.
In the IR4QA task of 7 th NTCIR, we look on the question as the query. The whole Wikipedia article states like the definition of its title, so we just take the specific type of questions, the definition/biography type 2 into consideration. As the name implies, the definition/biography type questions are the ones about definitions of terms or biographies of persons, such as "What is the Nobel Prize?", "Who is Osama bin Laden?".
Many researchers have made efforts on how to apply clustering to get better retrieved results. The document clustering based approach is now a typical one of document re-ordering, which is based on the assumption that cluster related documents should be more similar to each other and the content similar documents may appear in the same category with greater possibility (van Rijsbergen, 1979). Document clustering approach assigns documents to automatically created clusters, based on the degree of association between documents and clusters. But this is inappropriate to calculate the similarity of the query and the document since query consists of only a few terms for obtaining statistically meaningful frequency-vector and clusters.
In order to apply the document clustering analysis for document re-ranking, we also make use of the related Wikipedia article as a question. When the initial ranking documents are divided into clusters, we can calculate the similarity between the question-related Wikipedia article and the document cluster, instead of the question and document cluster, named Wiki-Cluster similarity, to regulate the ranking score.
The remainder of this paper is organized as follows. Section 2 reviews related works. Section 3 introduces the proposed document re-ranking approach using Wikipedia article. Section 4 then presents experiment results. Finally, Section 5 concludes the paper. document re-ranking method that uses the distances between documents for modifying initial relevance weights. Yang et al. (2004Yang et al. ( , 2005 used query terms which occur in both query and top N (N<=30) retrieved documents to re-rank documents.
Many research efforts have been made on how to apply clustering to get better retrieved results. Lee et al. (2001) proposed a model of information retrieval system that is based on a document re-ranking method using document clusters mentioned above. Anick and Vaithyanathan (1997) exploited the synergy between document clustering and phrasal analysis for the purpose of automatically constructing a context-based retrieval system. In their system, a context consists of two components, cluster of logical related articles (its extension) and a small set of salient concepts, represented by words and phrases and organized by the cluster's key terms (its intension). The Scatter/Gather system (Hearst and Pedersen, 1996) was a clusterbased document to browsing method, as an alternative to ranked titles for the organization and viewing of retrieved results. All of their experiments show that the clustering methods can enhance the performance of the IR systems.

System Architecture
For each question, the related question/query term will be submitted to the system to get a relevant Wikipedia article from the Wikipedia articles index, which will be explained in detail in the following section for each document. Then the Wikipedia article and the initial retrieved documents are input into the document re-ranking module. This module will compute the Document-Wiki similarity and the Wiki-Cluster similarities. When these two similarities are gained, they are combined with the initial score to generate the last similarity score. Then, documents are descending ordered by the last score and the final ranking documents are returned to users.
The system architecture is illustrated in Figure 1.

Wikipedia Resource Processing
For a question of definition/biography type, we want to get the related pages of the Wikipedia article which the title is the key term of the question. For example, if the question is "What is the Nobel Prize?", we would like to obtain the text content of the page which the title is "Nobel Prize". It is feasible that searching online by submit the key terms in the question to the Wikipedia search portal while the retrieval system is running. But the retrieval rate is closely depending on the performance of the network. For the sake of reducing the retrieval time, we download the compressed xml format files on the related Wikipedia site, extract text content of each article and index them to the local disk for the later retrieval. Due to the Wikipedia resources are on the local disks, the retrieval rate will be greatly improved than searching the information online.
There are several types of files contain different content on Wikipedia site. Now we only take the current pages file into consideration. This type of files contains current versions of article content. According to different time duration, different files are preserved on the site. In our experiments, we download the latest file. When the pages are revised, we can download it again and re-index them to keep the up-to-date information.

Wiki-Document Similarity
For each document in the initial retrieved results, we will calculate the similarity with the related Wikipedia article, the Wiki-Document Similarity. There are several models to compute the similarity. We choose the well-known Vector Space Model (VSM). After the text contents of each document including the Wikipedia articles are segmented by a Chinese segmentor ICTCLAS 3 , documents are represented by a vector in vector space where each dimension of vector is a word. We use the tf*idf values as the weighting scheme for the words. The same document representation and the weighting strategy for words will also be used for calculating the following Wiki-Cluster Similarity. So the similarity of document d in the initial retrieved results with the Wikipedia article can be computed by the following equation.

Wiki-Cluster Similarity
The clustering analysis hopes to divide the similar documents into the same cluster, and then uses the correlation of the question and the cluster information to regulate the sorting score. It is likely to that the document A gains high relevant score when it contains the key terms of the question while document B gets low score for it doesn't contain these key terms although its content is related to the question. When A and B have similar contents as they contain other same terms, they would be grouped into the same cluster. So when the cluster has high similarity with the question, the document B can get higher similarity score to enhance the ranking position based on the correlation of the cluster.
Several document clustering approaches to cluster document set have been put forward. K-Means and hierarchical clustering are the two typical ones. Here we make use of the K-Means cluster method (Ren et al., 2006) to do the clustering analysis and assign the cluster similarity score for each document. The process is listed as follows.
1) Create the vectors of the Wikipedia article and each of the documents in the initial results. 2) Utilize the K-means algorithm to do clustering analysis for the documents in results and calculate the centroid of each cluster.  When do the K-Means clustering, we set the number of the cluster K according to the number of the initial retrieval result documents. Following is the formula to initialize this parameter. ( Where N is the total number of the result documents for a question, n is the experimental determined parameter which is taken as the average documents number of all the clusters. In our experiments, n is set to 5, and N is 50.

Document Re-ranking
We combine the similarity ( , ) Sim q d between each document and the question in the initial results with the Wiki-Document similarity and the Wiki-Cluster similarity. The formula is displayed as follows.
(4) Where ( ) Sim d implies the final similarity of document d . α , β and γ are parameters to adjust the different importance to each of the similarities and assigned to 0.6, 0.3 and 0.1 respectively in our following experiments,.
When the last similarity is calculated, the documents are re-ranked by descending order of this measure and the final results are returned to users.

Experiment Results
We evaluate the proposed document re-ranking approach based on related Wikipedia articles on Simplified Chinese document collections for the 7 th NTCIR ACLIA/IR4QA task which are from Xinhua Chinese and Lianhe Zaobao between the year 1998 and 2001. The total number of the documents is 539,062.
In question set of the 7 th NTCIR ACLIA/IR4QA task, there are four types of question and totally 98 questions. There are two different fields to describe one question, title and narrative, and we only choose the title field to represent the question in the experiments. In this paper, we select 36 definition/biography questions, which can obtain related articles on the Wikipedia site. The questions and the Wikipedia articles are all in Simplified Chinese.
The initial retrieved results are generated by the approach put forward by Liu et al. (2008) and we select the top 100 documents in the results for the further re-ranking.
We mainly use the P@N evaluation criterion to analyze our experiments. Two kinds of relevant measures, relax relevant and rigid relevant, are concerned. The rigid relevant means the document is highly relevant or relevant with a question, and relax relevant denotes the document is highly relevant or relevant partially with a question. Table 1 lists the baseline results, representing the initial results, and the re-ranking results, obtained by using our reranking approach. Other groups of data such as P@20 and P@30 are also displayed in the table with the measure of relax and rigid respectively. From the groups of the relax measure and the rigid measure, we can see that the improvement of rigid measure are better than the relax measure when evaluating with different P@N. Figure 2 below shows the improvements in measure of rigid P@10 for each question. The xaxis denotes the No. of each question.  Figure 2, we can see that most of the questions are better in rigid P@N measure after re-ranking while a few of them are worse, such as Question 22 and 36. Look into the two Wikipedia articles related to these two questions, we find that there are some redundant contents, such as the development history of the term, which takes up long length of the whole document. The terms in this content may be irrelevant with the question so it declines the precision. So, we can conclude that the content of the Wikipedia articles have great impact on the re-ranking results.

Conclusions
In this paper, we put forward a re-ranking approach via question related Wikipedia article for the definition/biography type question. We make use of the related Wikipedia articles to calculate the Wiki-Document and Wiki-Cluster similarities to adjust the ranking score. The experiments show that our approach can improve the top precision for the IR4QA system. The improvement of P@N in rigid measure is higher than the relax measure where the rigid from 12.6% to 42.6% and the relax measure from 5.14% to 13.0% with different P@N evaluations.
The re-ranking approach in this paper is applied to specific type of questions for the convenient acquisition of the whole article content from the Wikipedia. But the content of some articles does not well state the related terms as the seed document. If we choose these articles, it may decline the retrieval precision. There are other free encyclopedia resources such as the Baidu encyclopedia. We may integrate some of these encyclopedias to generate the model answers to be used as a seed document.


extfieldsofstudy:
Computer Science
Mathematics

text:
A comparison and combination of segmental and fixed-frame signal representations in NMF-based word recognition

Segmental and fixed-frame signal representations were compared in different noise conditions in a weakly supervised word recognition task using a non-negative matrix factorization (NMF) framework. The experiments show that fixed-frame windowing results in better recognition rates with clean signals. When noise is introduced to the system, robustness of segmental signal representations becomes useful, decreasing the overall word error rate. It is shown that a combination of fixed-frame and segmental representations yields the best recognition rates in different noise conditions. An entropy based method for dynamically adjusting the weight between representations is also introduced, leading to near-optimal weighting and therefore enhanced recognition rates in varying SNR conditions.

Introduction
Structural characteristics of signal representations are an important aspect in all pattern discovery and speech recognition tasks. There are numerous different methods for describing speech signals that use different types of signal transformations, including, e.g., FFT, cepstra and LP-coefficients. These approaches describe local spectral properties of the signal as feature frames at a specific point in time. However, it is well known that also the way that temporal aspects of the signal are included in the analysis is important. Most approaches in speech recognition, including state-of-the-art HMMs, use fixed-frame windowing where the chosen features are extracted from approximately 20-25 ms long windows at fixed temporal intervals, e.g., every 10 milliseconds (see Gales and Young, 2008).
Speech signals, however, have a very special temporal structure, which can be described in terms of hierarchically organized linguistically motivated units like utterances, words, syllables and phones. This structure has to exist in the speech signal in order for the receiver to be able to decode it. For example, human listeners are able to locate and segment phone-like segments in speech signal, although the reliability and accuracy of the location of phone-phone boundaries is often quite inaccurate (+/-20 ms at best). Phone structure, or at least phone-like units, can then also be detected automatically using automatic segmentation algorithms that often use information about spectral changes in the signal in order to provide hypotheses about possible phone-boundary locations. These phone-like segments can then be described with chosen features to next levels of processing instead of fixed windowing, or the phone boundary information can be utilized in processing of fixed frame representations as was done in this study to form segmental representations. The way that temporal information is embedded in the feature stream has important implications for the next steps in the processing of the signals.
The aim of this paper is to present findings from comparison of fixed-frame and segmental based vector quantized representations of the speech signal in a NMF-based word learning and recognition task ( Van hamme, 2008a;Van Hamme, 2008b;Ten Bosch et al., 2008), where a weakly supervised speech recognition system is trained with these two types of signal representations and then tested in word recognition accuracy.

Properties of signal representations
In theory, the use of temporal segmental information should have several advantages. It synchronizes the feature stream to phonetically meaningful units in speech and the features can be extracted from desired temporal locations aligned with each segment. Phonetic synchrony facilitates the co-occurrence of subsequent phonetic units in temporally coherent manner (or at fixed lags in NMF) as the temporal deviations resulting from, e.g., different speaking rates or badly aligned windows are removed. This may aid pattern discovery methods, including NMF, in detection of recurring patterns (see Stouten et al., 2008). Segmental knowledge can be also used for compression of the feature data describing the signal, since each segment can be represented with a fixed number of features that incorporate all essential aspects of a segment. Segmental descriptions have the potential of being more robust in noisy situations when compared to fixedframe representations, as they can integrate spectral information over large temporal units.
The use of fixed frame representations, on the other hand, has several advantages, too. It provides a stable stream of information about the speech signal without being affected by the underlying signal content. For example, in situations where a segmentation algorithm misses transitions from phone to another and therefore leads to deletions in the label sequence, the fixed frame representation provides systematical information of the spectral content in the transient signal. Temporal resolution of fixed frames is also good if the window step size is sufficiently small, which means that the quantized label sequences can describe short-term details in the signal whereas segmental information is often an 'average' description of the content of a detected phone-like unit.

Algorithms used in experiments 2.1 Signal representations
For the experiments, fixed-frame signal representations were first created using vector quantization (VQ) and then segmental information was utilized to derive segmental version of the representations. The signals were first preemphasized and then MFCC-features were extracted every 10 ms. Quantization of the signal frames was performed using codebooks created by k-means algorithm: one codebook for static MFCCs, one for Δ-, and one for ΔΔ-coefficients. Corresponding VQ codebook sizes were 150, 150 and 100 labels, respectively. Each codebook was used as a separate input stream to the system. Segmental information was provided using a blind segmentation algorithm that tracks sudden changes in the spectral content of the signal using cross-correlation of spectral frames. The algorithm detects approximately 75 % of the segmental boundaries defined in a manually annotated reference of a test-set in the TIMIT corpus (with maximum deviation of ± 20 ms; Räsänen, 2007). Segmental representations were created using the information about segmental boundaries to group fixed-frame representation into segments, and then compressing these groups of VQ labels in each stream into overall descriptions of the segments. In order to do this, a number of labels had to be chosen to represent each segment according to some decision criteria. Preliminary experiments indicated that the best method for picking up N labels for each segment was to take the mode of labels (the most frequent label) inside each of the N pre-defined sub-segment. This smoothens out small variability inside segments and picks only the most dominant label for the chosen subsegment. When one label was chosen to represent a segment, the mode was taken from labels between 5 % and 95 % of the entire segment duration. In case of two labels per segment, the segment was divided to two sub-segments from 5 % to 45 % and from 55 % to 95 % of segment duration and modes were taken from these sub-segments. In case of three labels, corresponding sub-segment ranges were from 5 % to 40 %, from 30 % to 70 %, and from 60 % to 95 % in terms of segment duration.

Word-learning algorithm
The utilized non-negative matrix factorization (NMF) algorithm for word recognition is described in detail in the work of (Van hamme 2008a). The NMF in general is a mathematical technique to decompose a complex high-dimensional datamatrix as a product of two lower-dimensional matrices (see Lee and Seung, 2001). It has shown to be a powerful language-learning algorithm, capable of acquiring and robustly detecting at least a dozen keywords (see Van hamme, 2008a;Ten Bosch et al., 2008;Van hamme, 2008b).
The idea of the method is as follows. Firstly, speech utterances are converted to a vectorized form by accumulating the co-occurrences of labels from a single stream (statics, velocity and acceleration) in the signal at different time offsets (lags) and putting them in a histogram. The histograms determined on the different label streams can be concatenated into a single highdimensional vector. This representation, which is called the Histogram of Acoustic Co-occurrences (Van hamme 2008a), is very convenient for performing NMF, due to the non-negativeness of its elements and the fact that it is by approximation entirely composed of non-negative subparts, namely the HAC-representations of the words constituting the original utterances. Concretely, the NMF algorithm can be written as: V ≈ W H (1) in which V is a matrix, each column of which is the HAC-representation of an utterance from the input data. The columns of W contain nonnegative parts that make up the data, and the columns of H contain the extent to which each of these parts is present in each utterance. If the inner dimension (i.e. the number of columns in W) of the factorization is cleverly chosen, typically a bit higher than the total number of different words to be learned in the data, the non-negative parts contained in the columns of W will approximately model the HAC-representations of those words after convergence (Van hamme, 2008a; Van hamme, 2008b).
Given an utterance from the test set, W can be used to calculate an activation level for each trained word. If our objective is to detect one single keyword in the utterances of the test set, the answer for each utterance will consist of the word that is maximally activated by this utterance.

Material
A corpus recorded as a part of the ACORNS project 1 was used. The chosen subset of the corpus (UK Y1) consists of 4000 English utterances spoken by four different native English speakers (two males). The sentences in the material simulate linguistic input to infants less than one year of age. Each utterance contains a keyword surrounded by 1 http://www.acorns-project.org a carrier sentence (total 11 different keywords: bath,book,bottle,car,daddy,mommy,nappy,shoe,telephone,Angus,Ewan). Each utterance is also paired with a meta-tag that indicates the presence of a keyword in the utterance. This simulates a multimodal information source in a situation where there is an object of interest in the environment and the learning agent is paying attention to it, making it possible to model acoustic content in association to some other information source. The training material consisted of 2999 randomly selected utterances and the test material of the remaining 1000 utterances (one signal was removed due to an apparent recording problem). In the evaluation, the algorithm had to provide most likely keyword for each utterance that was then compared to the manual annotation.

Baseline experiments
After training the system with the 2999 utterances in the training material using 10 ms fixed-frame VQ-labels, a baseline result of 0.1 % WER was obtained for word recognition. When information about segmental boundary locations was utilized, keyword recognition accuracy depended on the amount of labels used for describing each segment. WER of 3.2 % was obtained using 1 label per segment. Interestingly, with two labels, only WER of 3.3 % was obtained after profuse experimenting with parameters, whereas for three labels the WER decreased to 2.8 %, being slightly below one label condition.
While it is not exactly clear why the error rate does not decrease when two labels are used instead of one, a possible explanation may be that the cooccurrence of labels becomes disturbed when the mode of labels is chosen from relatively large temporal areas that mainly represent left and right phone transitions (from the previous phone to the current phone and from the current phone to the next phone), whereas selecting one label per segment smoothens out these left and right transitions into one overall segmental description. However, transitional information should be still somewhat systematic at least for those phones that are not in the beginning or at the end of the word that is being modeled. Despite this, it may be that one overall description is better than two more context dependent descriptions, since counting cooccurrences of context-dependencies of adjacent phones may be more sensitive to variations in, e.g., speaking rate and long-range phonetic context.
In case of three labels per segment, the segmental description contains both left and right context and a sort of "locus" description from the middle of each segment that seems to carry important information regarding the underlying phonetic content. This is still significantly worse than the 0.1 % WER baseline with fixed frame representation.
This concludes that the compression to segmental level descriptions loses some fine details in the speech signal that are meaningful in order to differentiate between words. Three labels per segment yields the best recognition results for segmental based signal representations but falls still far behind fixed frame accuracies.
However, using only one label per segment has a noteworthy impact on computational complexity of further processing, since the signal representation is compressed into approximately 1/11 (9.1 %) of the original 10 ms fixed-frame size. The accuracy with this approach is almost as good as with three labels per segment, but due to data reduction, it speeds up execution of the NMF algorithm greatly.

Introducing noise
In order to see how well the representations and NMF perform in noise, two different types of noise were introduced to the system: 1) white noise added to the acoustic input, and 2) artificial noise added to the already quantized label sequences. In these experiments, the fixed frame signal representations were compared with segmental labels with one label per segment (mode of fixed frame symbols inside the segment).
In the first noise condition, five levels of (white Gaussian) noise were added to the acoustic input before signal quantization. Corresponding signalto-noise ratios were baseline level (set to 60 dB for visualization purposes), 40 dB, 30 dB, 20 dB, and 10 dB, mean noise level being computed over each utterance, including small silent portions in the beginning and in the end of the signals. For the remaining of this paper, this type of noise shall be called acoustic white noise (AWN).
The second type of noise, which shall be called channel noise (CN), was introduced to the recognition process by directly scrambling the label sequences at random indices. A manually defined percentage of labels were changed to a random label from the VQ codebook (using a uniform distribution). Five levels of SNR 2 were used: ∞, 22dB, 8.5dB, 0dB, and -8.5dB (SNR = 10log([1-p scrambled ]/p scrambled ), where p ! " [0,1]).
This type of scrambling simulates noise originating from somewhere inside the system, e.g., by errors in the transmission channel, and can be used to examine the nature of representations needed for reliable pattern discovery.
It was also of interest whether fixed frame and segmental representations would contain complementary information. Therefore activations of keyword representations in NMF were combined together with a formula: ! act combined = " # act fixed + (" $1) # act segmental (2) where ! " # [0,1] and act fixed and act segmental are word activations caused by fixed-frame input and segmental input, respectively.
In addition, reliability of segmentation in noisy conditions is also a central issue in this type of comparison. Boundary detection accuracy of the used segmentation algorithm has been found reasonably robust at least down to 0 dB SNR, however leading to increase in over-segmentation rate as the noise becomes more dominating (still approximately 75 % of boundaries are correctly detected at SNR = 20 dB with less than 10 % of over-segmentation; Räsänen, in preparation). In order to confirm these findings in word recognition experiments instead of previous comparison to reference annotation, the segmentation was also performed in parallel with both noisy input and clean input to see differences between these two situations.

Experiments with acoustic white noise
The system, including VQ codebook and NMF representations, was first trained using clean speech and then tested in word recognition with VQ-labels produced at different levels of AWN. Figure 1 displays the results at different SNR levels. As can be seen, the results are very similar for both representations at SNR = 40 dB, but as the SNR goes further down, the segmental representation of the signal performs significantly better than the fixed 10 ms frames approach. Increasing and varying the lag parameter of NMF Figure 1: Word-error rates as a function of SNR for fixed frames labels every 10 ms, segmental labels (one label per phone-like segment) and these two combined in case of acoustic white noise. Combination of these representations has complementary value and increases the recognition accuracy. did not affect the WER significantly from the original 50 ms and 90 ms lags in fixed-frame condition.
When word model activations from both representations are combined using eq. 2, WER further decreases, suggesting that they contain complementary information at all noise levels (alpha optimized separately for each SNR level). Figure 2 displays the word-error rates for combined representations at different SNR levels as a function of alpha, both with segmentation performed in noise (solid lines) and with clean speech (dashed lines).
As the fixed frame representation performs better at low noise levels, the optimal alpha for these levels is rather high. However, as soon as the SNR starts to drop, the optimal alpha starts to decrease fast. At very high noise levels the Figure 3: Word-error rates in channel noise as a function of SNR for fixed frames labels every 10 ms, segmental labels (one label per phone-like segment) and these two combined. Combination of these representations has complementary value and increases the recognition accuracy.
segmental descriptions seem to degrade badly and alpha shifts back towards fixed frames. This was found to be due to fact that at very high noise levels the vector quantization process tends to attract most of the feature vectors into a handful of 'noise-like' clusters. As these labels start to become the majority in the utterance related sequences, taking the mode of labels for all segments results in same (noise) symbols representing most of the segments. However, the overall recognition rates at 10 dB are extremely poor with all values of alpha. Figure 2 also shows that the difference between blind segmentation performed in clean and noisy speech is not being significantly affected by the increase of noise all the way down to SNR = 20 dB. Only at SNR of 10 dB the degradation of segmentation quality becomes clearly visible in terms of recognition rate. This suggests that the information about segmental boundaries can be considered reliable at moderate white noise levels.

Experiments with channel noise
When noise is introduced directly to label sequences after quantization, the situation changes significantly as the noise affects only some of the quantized frames. The results show that the qualities of both representations start to degrade in a fairly similar manner as the SNR increases (figure 3), fixed frame representation being more effective all the way down to SNR = -8.5 dB. Increasing the number of lags or varying the lag lengths did not decrease the WER significantly from the original 50 ms and 90 ms lags in fixed frame conditions or 1, 2, 3, 4, and 5 segments in segmental conditions. A value for alpha was again optimized for each SNR level separately by finding the value resulting in the minimum WER. Figure 4 shows the recognition rates at different noise levels and with different values of alpha.
A combination of the two different representations yields again the best recognition results, suggesting that the information about larger scale units (speech segments) can aid in the recognition process when the input is distorted. Next we will consider how this combination can be performed automatically when the signal conditions change.

Automatic weighting of representations 4.1 Alpha in acoustic white noise
It was shown that combining fixed frame and segmental information is useful when noise is introduced to the system. But how does the system know how to weight small details (fixed frames) or larger units (segments), i.e., how can it automatically find a proper value for alpha in varying conditions when word-error rates are not available for optimization? One method is to build a SNR dependent model for alpha so that value of alpha can be adjusted based on signal conditions. For on the fly estimation of SNR of the input, entropy is computed from the sequential label input X:  where n is the number of labels in the codebook and p is the probability distribution function of X that describes the frequency proportion of each symbol in the input. By measuring the entropy in different noise conditions, it is possible to find a mapping between SNR and the optimal alpha values. For white noise, entropy measured in the baseline SNR condition sets a maximum value for the entropy range, where H(X) = 1 would be obtained if signal content was entirely random (note that base of the logarithm is the size of the codebook). Figure 5 shows both entropy and the optimal alpha value as a function of SNR in the AWN condition. As the amount of noise increases, the entropy decreases as the noise-like clusters in the codebook start to become more probable.
By taking entropy estimates and optimal alpha values for the test signals at several noise levels, a good estimate for alpha can be described as a 2 nd order polynomial function of entropy of the input sequences.
! " = a 2 H 2 + a 1 H + a 0 The coefficients a 2 , a 1 , and a 0 of the equation will depend on the used codebook, and therefore it is necessary to estimate entropy and WER values as a function of noise level and define these parameters in the development/training phase of the system. For VQ codebooks of size 150/150/100 (static, Δ, and ΔΔ labels) used in the experiments, a 2 = 12.07, a 1 = -16.1, and a 0 = 5.4 were obtained. The parabolic fit to the data used in the experiments is extremely good (correlation > 0.999; figure 6) and therefore recognition rates are basically identical between entropy-based and manually optimized alpha, and are not therefore plotted separately (see fig. 3 for the results). In practice some deviation between these two may occur if the alpha is adjusted on the fly, depending on the temporal length of input used for estimating the entropy.

Alpha in channel noise
Entropy based alpha estimation can also be used in channel noise situation. In contrast to AWN, the entropy now increases as SNR decreases since labels at random locations become replaced with random labels. A reasonably good fit between entropy and alpha values can be obtained with a 1 st order polynomial using eq. 4. However, even a more straightforward approach to select a proper alpha exists. It can be grossly approximated from figure 4 that the valleys of the curves are located in the middle section of the alpha range. Fixing α to 0.5 is then a trivial and computationally efficient method to combine information from both temporal resolutions in both clean sequences and noisy sequences. Weighting segmental and fixed frame information equally in all conditions leads to nearly same recognition accuracy as in optimized situation. Figure 7 displays results from the recognition task in channel noise as was performed previously, now also including results with entropy based alpha estimation and the manually defined α. The difference between recognition rates using optimal alpha values and alphas estimated from the input entropy are small. However, having fixed alpha of 0.5, that is, weighting the segmental and fixed frame information equally, leads to even better accuracy than the entropy based estimation. This suggests that this type of noise that does not take into account the spectral content of the speech, but uniformly affects entire quantized sequences, can be compensated by equally weighting fixed frame and segmental sized representations with NMF.

Discussion about noise experiments
An important finding here is that the information from larger temporal scales seems to become more and more important as the signal-to-noise ratio becomes worse (figures 2,4,5). Changes in the SNR of the input can be approximated with entropy after it is known how the entropy behaves at different levels of noise. This information can be then used to adjust the weight between scales dynamically.
When noise is introduced to the acoustic signal before vector quantization (e.g., external noise source), the quality of quantized labels suffers greatly as the spectral structure of the input becomes dominated by the noise, biasing the NMF word activations towards specific word models. It seems that integrating temporal information over phone-like speech segments helps to form more systematic representations than treating each small time-scale unit as a meaningful event in the presence of external (white) noise. Combining these two representation leads to better recognition accuracy than using either of them alone.
If noise is introduced directly to label sequences after quantization, weighting of small-and largescale temporal information equally at all noise levels is much more straightforward and leads to similar or even better results than dynamic entropy estimation. It may be so that the balance between activations emerging in NMF representations on different temporal scales is automatically adjusted by the ambiguity of the incoming patterns at each scale, since this type of noise does not bias the representations in any specific direction (except towards general randomness). When small-scale (more detailed) patterns match well with the smallscale representations, they dominate large-scale information in activation levels due to richness of information. When the small-scale patterns are distorted, previously learned large-scale patterns in the memory start to become more dominant. This linear weighting of cues has an interesting relation to perceptual processing in humans, where such summation of different cues embedded in the input takes place in, e.g., vision (Bruce et al., 2003;Oruc et al., 2003).

Conclusions
The use of segmental representations instead of fixed 10 ms frames degrades the recognition accuracy noticeably with clean speech. The magnitude of difference between these two is slightly surprising, as there are supposed to be several advantages of using segmental information, as was discussed in the introduction. However, it was found out that the segmental information is helpful in noisy conditions, adding robustness to the recognition decisions and therefore reducing the word-error rates. The weighting between segmental and fixed frame information can be estimated by utilizing entropy measure to the vector quantized labels. Parameters for this adaptive process have to be estimated in advance with well-defined input so that approximate entropy values for clean speech and several noise levels can be obtained.
In case of uniformly distributed random channel noise, simply using constant equal weight for both small and large temporal scales results in nearly optimal results. This may be because the strength of activation of internal representations in NMF at different temporal scales seems to follow the amount of previously learned structure available at these scales. This has striking similarity to theories of linear summation of cues from different scales of processing. Why this type of self-adjustment does not occur in case of AWN is not certain, but it may be due to the fact that the noise in quantization input changes the process systematically (reducing entropy). As such, it biases activations of internal representations towards a specific set of words instead of uniformly impeding all internal representations.


Rfuzzy framework

Fuzzy reasoning is a very productive research field that during the last years has provided a number of theoretical approaches and practical implementation prototypes. Nevertheless, the classical implementations, like Fril, are not adapted to the latest formal approaches, like multi-adjoint logic semantics. Some promising implementations, like Fuzzy Prolog, are so general that the regular user/programmer does not feel comfortable because either representation of fuzzy concepts is complex or the results difficult to interpret. In this paper we present a modern framework, Rfuzzy, that is modelling multi-adjoint logic. It provides some extensions as default values (to represent missing information, even partial default values) and typed variables. Rfuzzy represents the truth value of predicates through facts, rules and functions. Rfuzzy answers queries with direct results (instead of constraints) and it is easy to use for any person that wants to represent a problem using fuzzy reasoning in a simple way (by using the classical representation with real numbers).

Introduction
One of the reasoning models that is more useful to represent real situations is fuzzy reasoning. Indeed, world information is not represented in a crisp way. Its representation is imperfect, fuzzy, etc., so that the management of uncertainty is very important in knowledge representation. There are multiple frameworks for incorporating uncertainty in logic programming: fuzzy set theory [5,38,32], -probability theory [8,16,20,25,26], -multi-valued logic [7,11,12,15,17,29], -possibilistic logic [6,36,37] ⋆⋆ This work is partially supported by the project DESAFIOS -TIN 2006-15660-C02-02 from the Spanish Ministry of Education and Science and project PROMESAS -S-0505/TIC/0407 from the Madrid Regional Government.
Despite of the multitude of theoretical approaches to this issue, few of them resulted in actual practically usable tools. Since Logic Programming is traditionally used in Knowledge Representation and Reasoning, we argue it is perfectly well-suited to implement a fuzzy reasoning tool as ours.

Fuzzy Approaches in Logic Programming
The result of introducing Fuzzy Logic into Logic Programming has been the development of several fuzzy systems over Prolog. These systems replace the inference mechanism of Prolog, SLD-resolution, with a fuzzy variant that is able to handle partial truth. Most of these systems implement the fuzzy resolution introduced by Lee in [18], as the Prolog-Elf system [10], the FRIL Prolog system [2] and the F-Prolog language [19]. However, there is no common method for fuzzifying Prolog, as has been noted in [28].
Some of these Fuzzy Prolog systems only consider the predicates' fuzziness whereas other systems consider fuzzy facts or fuzzy rules. There is no agreement about which fuzzy logic should be used. Most of them use min-max logic (for modelling the conjunction and disjunction operations) but other systems just use Lukasiewicz logic [13].
Furthermore, logic programming is considered a useful tool for implementing methods for reasoning with uncertainty in [38].
There is also an extension of constraint logic programming [3], which can model logics based on semiring structures. This framework can model min-max fuzzy logic, which is the only logic with semiring structure.
Another theoretical model for fuzzy logic programming without negation has been proposed by Vojtas in [35], which deals with many-valued implications.

Fuzzy Prolog
One of the most promising fuzzy tools for Prolog was the "Fuzzy Prolog" system [33,9]. The most important advantages against the other approaches are: 1. A truth value will be a finite union of sub-intervals on [0, 1]. An interval is a particular case of union of one element, and a unique truth value is a particular case of having an interval with only one element. 2. A truth value is propagated through the rules by means of an aggregation operator. The definition of this aggregation operator is general and it subsumes conjunctive operators (triangular norms [14] like min, prod, etc.), disjunctive operators [31] (triangular co-norms, like max, sum, etc.), average operators (averages as arithmetic average, quasi-linear average, etc) and hybrid operators (combinations of the above operators [27]). 3. Crisp and fuzzy reasoning are consistently combined [24]. Fuzzy Prolog adds fuzziness to a Prolog compiler using CLP(R) instead of implementing a new fuzzy resolution, as other former fuzzy Prologs do. It represents intervals as constraints over real numbers and aggregation operators as operations with these constraints, so it uses Prolog's built-in inference mechanism to handle the concept of partial truth.

Motivation and RFuzzy Approach
Over the last few years several papers have been published by Medina et al. ([22,23,21]) about multi-adjoint programming, which describe a theoretical model, but no means of serious implementations apart from promising prototypes [1].
Indeed, that was the reason for developing Fuzzy Prolog [9]. Fuzzy Prolog is a very expressive tool which allows the user 1 to program almost everything, but we have to pay for this expressiveness. The cost is a complex syntax difficult to understand.
The motivation for developing Rfuzzy is mainly focused on reducing this complex syntax. This reduction is based on three ideas: 1. Use real numbers instead of intervals between real numbers to represent truth values. Fuzzy Prolog answers to user queries are intervals like it will rain (tonight, [0,1]). This is a bit difficult to understand by normal users. Truth value of this example is between 0 and 1, and this means that program can not conclude anything about the predicate truth value. 2. Whenever it is possible, do not answer user queries using constraints. A Fuzzy Prolog answer to an user query can be a constraint, like it will rain (tomorrow, [X, Y]), X > 0, X < 1, Y > 0, Y < 1. The meaning of this example is exactly the same as the meaning of the previous one, but it is slightly more difficult to understand it. 3. Truth value variables do not need to be coded. Taking care of variables to manage the predicates truth value introduces errors and makes the code illegible, without giving us any advantage.
Rfuzzy uses real numbers to represent truth values and its replies are never constraints. Besides, it is able to distinguish between crisp and fuzzy predicates and it manages the introduction of truth value variables, so the user does not need to take care of them. Truth variables are always introduced at the end of the predicate arguments list, so it can be seen as some syntactic sugar. We explain this in subsection 2.6.
From the point of view of expressiveness, we can remark that RFuzzy offers to the user the ability to define types, general and conditioned default values and truth value representations by means of facts, functions or rules. Besides, it implements multi-adjoint logic with representation of the concept of credibility of the rules, so it is one of the first tools that are actually modelling multi-adjoint logic 2 .

Rfuzzy syntax
In this section we are going to describe RFuzzy's syntax. Rfuzzy defines the syntax of a new subset of Prolog predicates to work with truth values and to assign credibility to rules. The extensions that we have added to provide fuzziness of predicates are: type information, truth values (for facts, functions and rules) and default truth values.
RFuzzy shares with Fuzzy Prolog most of its nice expressive characteristics: Prolog-like syntax (based on using facts and clauses), use of any aggregation operator, flexibility of query syntax, constructivity of the answers, etc. Nevertheless, RFuzzy is simpler than Fuzzy Prolog for the user because the truth values are simple real numbers instead of the general structures of Fuzzy Prolog.

Type definition
Prolog does not have types. Prolog code are formulas and at execution time it looks for all of them to be true. To do that, it generates a Herbrand Universe and tries to substitute every variable with a Herbrand term. As we do not want programs to look for an answer infinitely, we offer the user a facility to restrict the set of possible solutions. This extension is named "types" and its syntax is shown in (1).
where set prop is a reserved word, pred is the name of the typed predicate, ar is its arity and type pred {n} is the predicate used to assure that the value given to the argument in the position n of a call to pred/ar is correctly typed. Predicate type pred {n} must have arity 1. The example below shows that the two arguments of the predicate has lower price/2 have to be of type car/1 and which individuals belong to that type.

Fact truth value
Fuzzy facts are facts to which we assign a truth value. To code them in programs we offer a special syntax, so Prolog can distinguish between normal facts and fuzzy facts. This syntax is shown in (2).
Arguments ( args ) should be ground and the truth value ( truth val ) must be a real number between 0 and 1. The example below defines that the car alfa romeo gt is an expensive car with a truth value 0.6. expensive_car(alfa_romeo_gt) value 0.6 .

Functional truth value
Fact truth value definition (see subsection 2.2) is worth for a finite (and relative small) number of individuals. As we may want to define a big amount of individuals, we need more than this.
Fuzzy truth values are usually represented using continuous functions. Fig.  1 shows an example in which the truth value function assigns the truth value of being teenager from the person's age value. A function can be defined in several ways, but the easiest one is via a sequence of ordered pairs whose first element is the fact and the second element is the truth value assigned to that fact.
Functions used to define the truth value of some group of facts are usually continuous and linear over intervals. To define those functions there is no necessity to write down the value assigned to each element in their domains. A better way to define them is by means of their inflexion points, so function values for the elements between the inflexion points are determined by means of interpolation.
RFuzzy provides the syntax for defining functions by stretches. This syntax is shown in (3). External brackets represent the Prolog list symbols and internal brackets represent cardinality in the formula notation. arg1, ..., argN should be ground terms (numbers) and truth val1, ..., truth valN should be border truth values. The truth value of the rest of the elements (apart from the border elements) is obtained by interpolation.

Rule truth value
A tool which only allows the user to define truth values through functions and facts leaks on allowing him to combine those truth values for representing more complex situations. A rule is the perfect tool to combine the truth values of facts, functions, and other rules.
Rules allow the user to combine truth values in the correct way (by means of aggregation operators, like maximum or product). Besides this combination truth value for the body of the rule, the rule can be given an overall credibility truth value.
Credibility is used to express how much we trust the rule we write. Suppose a small weather example in which we have the rule it will rain if it is cloudy and it is hot. As it might rain but it might not, we can assign the rule a credibility of 0.7. As expected, the truth value obtained from the body is combined with the credibility value of the rule to obtain a final truth value.
Rfuzzy offers the user a concrete syntax to define combinations of truth values by means of aggregation operations, and assign to that rules a credibility. This syntax extension is defined in (4). Indeed, the user can choose two aggregation operators 3 : op2 for combining the truth values of the subgoals of the rule's body and op1 for combining the previous result with the credibility of the rule.

General and Conditioned Default Truth Values
Unfortunately, information provided by the user is not complete in general. So there are many cases in which we have no information about the truth value of an individual or a set of them. Nevertheless, it is interesting not to stop a complex query evaluation just because we have no information about one or more subgoals if we can use a reasonable approximation. The solution to this problem is using default truth values for these cases. The RFuzzy extension to define a default truth value for a predicate when applied to individuals for which the user has not defined an explicit truth value is named general default truth value. Conditioned default truth value is used when the default truth value only applies to a subset of the function's domain. This subset is defined by a membership predicate which is true only when an individual belongs to the subset.
The membership predicate ( membership predicate/ar ) and the predicate to which it is applied ( pred/ar ) need to be have the same arity ( ar ). If not, an error message will be shown at compilation time.
The syntax for defining a general default truth value is shown in (5), and the syntax for assigning a conditioned default truth value is shown in (6). pred/ar is in both cases the predicate to which we are defining default values. As expected, when defining the three cases (explicit, conditioned and default truth value) only one will be given back when doing a query. The precedence when looking for the truth value goes from the most concrete to the least one.
:-default(pred/ar, truth value) => membership predicate/ar. (6) The example below shows how to assign a default truth value of 0.5 to all cars that do not have an explicit truth value nor have a default conditioned truth value. Besides, it shows how to assign a conditioned default truth value to all cars belonging to a small subset and not having an explicit truth value. This subset is determined by the membership predicate expensive type/1, and default truth value for its elements is 0.9. So lamborghini urraco is an expensive car with truth value 0.9 but vw caddy is an expensive car with truth value 0.5. Both values are default approximations because we have no direct declaration (as for alfa romeo gt that is an expensive car with a truth value 0.6 as we show above).

Doing queries with truth values
Indeed the program has to be run. When compiling, Rfuzzy adds a new argument to the arguments list of each fuzzy predicate. This argument serves for querying about the predicate truth value. It can be seen as syntactic sugar, as truth value is not part of the predicate arguments, but metadata information.
Truth value argument is added to the predicates in a uniform way: it is always a new argument at the end of the arguments list of the predicate. In the previous example we wrote expensive car/1, so to query the system we have to give the predicate two arguments instead of only one where the second one will represent the query's truth value. This can be seen in the first example of subsection 2.7.

Constructive Answers
A fuzzy tool should be able to provide constructive answers for queries. The regular (easy) questions are asking for the truth value of an element. For example, how expensive is an alfa romeo gt?
?-expensive_car(alfa_romeo_gt,V). V = 0.6 ? ; no But the really interesting queries are the ones that ask for values that satisfy constraints over the truth value. For example, which cars are very expensive?. RFuzzy provides this constructive functionality.

Applications
Rfuzzy is mainly suitable for expert systems applications. As mentioned before, its main advantages in comparison to Fuzzy Prolog are its simpler syntax, the use of real numbers instead of intervals between them and the implicit handling of truth values. Besides, it presents facts' truth values (explicit, default or conditioned default truth value), functions' truth values and rules (with or without credibility) which simplifies the user development process a lot.
Although a medical expert system development were the best example of using Rfuzzy, due to lack of space we prefer to show here one in which we decide which is the best restaurant for going out.
In the example we can see that we know the distance to all the restaurants in a crisp way. This crisp value is translated by means of low distance and low distance aux into a fuzzy one which is used into tempting restaurant to determine its truth value. This allows us to ask which is the truth value of each tempting restaurant, which restaurant is a tempting restaurant with a truth value of, for example, 0.7 or list all tempting restaurants with their truth values.
The Rfuzzy module with installation instructions and examples can be downloaded from http://babel.ls.fi.upm.es/software/rfuzzy/.

Implementation details
RFuzzy is a logic programming language that is able to model all the extensions that are described in section 2. It is implemented as a Ciao Prolog [30] package because Ciao Prolog offers the possibility of dealing with a higher order compilation through the implementation of Ciao packages. Those packages serve as input for the "Ciao System Preprocessor" (CiaoPP) [4], a tool able to perform source-to-source transformations.
The reason beyond the implementation of Rfuzzy as a Ciao Prolog package is that the resultant code has to deal with two kinds of queries: queries in which the user asks for the truth value of an individual, and queries in which the user asks for an individual with a concrete truth value.
As can be seen in the following example, this is not an easy task.
?-A is 1, B is 2, C is A + B. Taking advantage of Rfuzzy and CLP(R) transformations, our tool compiles Rfuzzy programs into ISO Prolog programs, so the interpreter is able to work with them as it normally does. As a result, the global compilation process has two preprocessor steps: (1) the Rfuzzy program is translated into CLP(R) constraints by means of the Rfuzzy package and (2) those constraints are translated into ISO Prolog by using the CLP(R) package. Fig. 2 shows the whole process.
In the following example the predicate tempting restaurant is translated from Rfuzzy syntax into ISO Prolog syntax. In the first step, the Rfuzzy package inserts truth value variables, the inject metapredicate call (one of its arguments is the aggregation operator to be used, prod) and inserts Rfuzzy comparisons to take care at execution time that the rule's truth value is always between zero and one. In the second step, CLP(R) converts comparisons into constraints (via predicate calls). Internally, Rfuzzy package unifies and translates all the information given by the user to each predicate (Types, default values with and without condition, truth values defined in facts and rules with and without credibility) into a single predicate body. A simplified version of the skeleton used for that predicate is shown below. The skeleton has three different parts: the one which takes care of allowing only queries or answers with the expected individuals, the one which looks for a concrete truth value (it can be defined by means of a fact, a function or a rule) and the one which looks for a default truth value (conditioned or not). Predicates ending in aux do not take care on the truth value argument.

Rfuzzy package simplified skeleton
The first part is obtained from the type definitions (see 2.1), translating all types into a predicate which is called at first (Types) so we assure we only work with the expected individuals.
The second part looks for a concrete value whose arguments have to unify with the parameters the user has given. Precedence when looking for it is: The third part is only called when the second one (searching for a truth value) fails, and looks for a conditioned or default truth value.

Conclusions and Current Work
Rfuzzy offers to the users a new framework to represent fuzzy problems over real numbers. Fuzzy Prolog [34,33,9] is an existing framework for dealing with Fuzzy problems representation. Main Rfuzzy advantages over Fuzzy Prolog are a simpler syntax and the elimination of answers with constraints, and Rfuzzy is one of the first tools modelling multi-adjoint logic, as explained in subsection 1.3.
Rfuzzy syntax is simpler that Fuzzy Prolog syntax. Its fuzzy values are simple real numbers instead of intervals between real numbers, and it hides the management of truth value variables. As normal fuzzy problems do not use intervals to represent fuzziness and do not need to code an uncommon behaviour of fuzzy variables, this syntax reduction is an advantage. Programs written in Rfuzzy syntax are more legible and more easy to understand than Fuzzy Prolog programs.
Fuzzy Prolog answers to user queries are difficult to understand due to the existence of constraints. As normal replies to final users are ground terms, the programmer has to code by hand how to reach them. To eliminate those constraints and answer queries with ground terms the programmer tries to substitute variables with ground terms until one makes true all of them. Rfuzzy offers a powerful tool to deal with this task: Type definition. Type definition (see subsection 2.1) allows the user to define which terms are suitable for being substituted into a variable, so she does not have to code this behaviour again. Besides, the elimination of answers with constraints provides more human readable answers and more easy to test programs (because answers we test do not have constraints, just ground terms).
There is also an extension to introduce default truth values. As world information is sometimes incomplete, Rfuzzy offers to the user the possibility to define default truth values and default conditioned truth values (see subsection 2.5). This allows us to make inference with default truth values when we do not know anything about the truth of some fact.
Extensions added to Prolog by Rfuzzy are: Types, default truth values (conditioned or not), assignment of truth values to individuals by means of facts, functions or rules, and assignment of credibility to the rules.
Besides, the possibility to provide constructive answers to the queries increase its usage, as can be seen in subsection 2.7.
There are countless applications and research lines which can benefit from the advantages of using the fuzzy representations offered by Rfuzzy. Some examples are: Search Engines, Knowledge Extraction (from databases, ontologies, etc.), Semantic Web, Business Rules, and Coding Rules (where the violation of one rule can be given a truth value).
Current work on Rfuzzy tries to apply constructive negation to the engine. RFuzzy needs to define types in a constructive way (by means of predicates that are able to generate all their individuals by backtracking) so we cannot use constraints. Future research will be done in this line for widening the definition of types.


extfieldsofstudy:
Mathematics
Computer Science

text:
Solving the 0-1 Multidimensional Knapsack Problem with Resolution Search

We propose an exact method which combines the resolution search and branch&bound algorithms for solving the 0?1 Multidimensional Knapsack Problem. This algorithm is able to prove large?scale strong correlated instances. The optimal values of the 10 constraint, 500 variable instances of the OR-Library are exposed. These values were previously unknown.

Introduction
In this article, we present a new exact method which hybridizes the resolution search of Chvátal (1997) and a branch & bound algorithm inspired by a previous work from Vimont et al. (2008) for the 0-1 Multidimensional Knapsack Problem (01MKP). The 01MKP is a wellknown opitmization problem which can be viewed as a resource allocation model and can be stated as follows: x j ∈ {0, 1} j = 1, ..., n where n is the number of items, m is the number of knapsack constraints with capacities b i (i = 1, 2, ..., m), c ∈ N n , A ∈ N m×n and b ∈ N m . Each item j (j = 1, 2, ..., n) yields c j units of profit and consumes a given amount of resource a ij for each knapsack i. The proposed approach is centered on two main 01MKP results: (i) the consideration of a reduced costs constraint based on the reduced costs at the optimality of the problem's LPrelaxation (see Balas and Martin (1980); Oliva et al. (2001)) and (ii) the decomposition of the search space in several hyperplane where the number of items to choose is fixed at a given integer value (see Vasquez and Hao (2001); Vimont et al. (2008)). Our algorithm is self-sufficient and does not require any lower bound as starting value. We show that the structure of resolution search enables to explore partially and iteratively different subproblems (hyperplanes with a fixed number of items) while keeping completeness. This way of exploration enhances the diversification of the search and permits to improve the lower bound rapidly. For each hyperplane, this lower bound, associated with the upper bound (tighter than the classical one given by the LP-relaxation), enforces the strength of the so-called reduced costs constraint widely used in the algorithm. Roughly speaking, if we consider that the variables are sorted in decreasing order of their reduced costs (basic variables at the bottom of the list), the enumeration of the first variables is carried out by resolution search where the enumeration of the remaining variables is tackled by our specific branch & bound. Our approach proved all the optimality of all the 10 constraint, 500 variable instances. These optimal solutions were previously unknown.

Resolution search
Resolution search was proposed by Chvátal (1997) as an alternative to branch & bound for mixed 0-1 linear programming problems. This approach, based on an original exploration of the search space, uses the information brought by the fails that have occurred during the search to progressively shrink the search tree. Each time a terminal node is reached, a minimal partial instantiation of the variables responsible for the fail is identified. This partial instantiation, which corresponds also to a terminal node, is then recorded in a specific way in order to discard the corresponding subtree from the search space and to provide the next node in the exploration. The specificity of the recording mechanism allows the algorithm to preserve space memory while keeping completeness.
Globally, resolution search is composed of two main elements: (i) a set of partial instantiations (denoted path-like family F ) corresponding to fails encountered during the search and recorded as boolean clauses and (ii) an function called obstacle which uses the information brought by the family F to explore promising parts of the search space. From a partial instantiation u(F ) derived from F , which is not an already explored instantiation, obstacle performs two different phases: 1. The waxing phase which replaces step by step the free components u(F ) j = * by 0 or 1 until a terminal node (denoted u * ) is reached (a terminal node is a partial instantiation of the variables which does not lead to any improvement of the best known lower bound).
2. The waning phase which tries to find a minimal element S of {0, 1, * } n such that S ⊑ u * and S is a terminal node (formally, let u and v be two vectors of {0, 1, * } n , we call u an extension of v and we write u ⊑ v, if v j = u j whenever u j = * ).
Once the minimal element S is identified, it is recorded in a specific way as a clause in F . The structure of F enables both to guide the search toward prosimising parts of the search space and to guaranteed the completeness using the resolution / refutation principle. Indeed, if the minimal element S correspond to the instantiation ( * , * , ..., * ) then the best known solution is an optimal soltion of P . The algorithm 1. represents the function Resolution Search which takes as parameter a lower bound (LB) of the problem.

General approach
The 01MKP is tackled by decomposing the problem in several subproblems where the number of items to choose is fixed at a given integer value. Considering that LB is a lower bound of the problem, we can define 1} n } as the set of feasible solutions strictly better than LB and consider the following problems: where 1 is the vector of dimension n with all its components equal to one andX In what follows, we note v(P ) the optimal value of a given if(try > LB) LB = try; add S to F and update F ; Solving the 01MKP by tackling separately each of the subproblems P k for k = k min , ..., k max appeared to be an interesting approach (Vasquez and Hao (2001); Vasquez and Vimont (2005); Vimont et al. (2008)) particularly because the additional constraint (1 · x = k) provides tighter upper bounds than the classical LP-relaxation. This approach takes also into consideration a constraint based on the reduced costs of the non-basic variables. Let us consider the upper bound UB = c ·x, wherex is the optimal solution of the LP-relaxation. Letc be the vector of the reduced costs and N the indexes of the non-basic variables. If we know a lower bound LB ∈ N of the problem, then each better solution x must satisfy the following constraint: (the reader is referred to Balas and Martin (1980); Oliva et al. (2001) and Vimont et al. (2008) for more details on the subject). The use of the constraint (4), also called the reduced costs constraint, is twofold: (i) it enables us to identify the unfeasibility (with respect to the constraint c · x ≥ LB + 1) of some partial solutions and (ii) it allows us to fix those variables x j with |c j | > UB − LB at their optimal valuex j . Both the tight upper bound and the good lower bound enhance the efficiency of the reduced costs constraint.
To summarize, our approach consists of decomposing the search space in several hyperplanes then solving the LP-relaxation for each one in order to generate the reduced costs constraint. The exploration is then carried out partially and iteratively for each hyperplane with resolution search until all the search space is explored.
Indeed, thanks to the structure of resolution search, P can be solved by progressively exploring each of the hyperplanes (1 · x = k, k ∈ N). Let CFamily[k] be the family of clauses associated to resolution search for the subproblem P k . At each step of the search, CFamily [k] provides all the information about the state of the search: the terminal nodes recorded at this stage and the next node to explore. It is possible to execute some iterations of resolution search at a given P k , then continue to another P k ′ and go on with the subproblem P k again without any loss of information. The algorithm 2 detail the Iterative RS algorithm which corresponds to resolution search limited to a given number of iterations and the algorithm 3 shows the hyperplane exploration using Iterative RS. This way of exploration enforces the diversification and the convergence of the search. Note that, in algorithm 3, greedy is a simple greedy function used for providing a first lower bound.

Resolution search and branch & bound combination
In this section, we detail the exploration function obstacle embedding the branch & bound algorithm.
Starting with the node u(F ) given by the path-like family F , obstacle replaces stepby-step the components * of u(F ) by 0 or 1 which constructs the node u + . If u + is a terminal node, the function provides a minimal clause S such that S ⊑ u * and S is a terminal node. Our implementation of obstacle is based on the reduced-costs constraint (4) presented in section 3. At the beginning of the procedure, the LP-relaxation of the problem is solved for each available hyperplane in order to give us the information needed for the reduced costs constraint. Then obstacle proceeds to the following steps: • The first step, called consistency phase, consists of checking the feasibility of u(F ).
Initially, we define a value gap = UB − LB. If a constraint is violated, the descent phase stops and the corresponding partial instantiation is recorded as the clause S in F . At the same time, the reduced costs constraint (4) is checked and the gap value is updated: for each non-basic variable set at the opposite of its optimal value (1 −x j ), its reduced costs (c j ) is subtracted from the gap. If it happens that gap < 0 then the current partial solution is a terminal node. In this case, S is only composed of the variables set at the opposite of their optimal value in u(F ).
• If u(F ) is feasible, we go to the next step which we call implicit waning phase. This phase consists of branching on all the remaining free variables with a reduced cost greater than gap. Those variables must be fixed at their optimal value for satisfying the reduced costs constraint (4). The branching decisions taken in this phase are just a consequence of the instantiated variables in u(F ). Consequently they can be removed from S.
• Then the algorithm starts the so-called waxing phase which consists of assigning values to free variables. The chosen strategy is to select the free variable with the greater absolute reduced cost value and to assign its optimal valuex j to it. Obviously, each time a branching is done, the feasibility of the current partial solution is verified and in case of fail, the waxing phase stops and the corresponding clause S is added to F . Note that the variables set in the implicit waning phase are still not taken into account in S.
• Once the number of remaining free variables is less than or equal to a given number spb size, the waxing phase stops and the corresponding subproblem is solved with a branch & bound algorithm. This subproblem includes the free variables with the lowest reduced cost and the basic variables. Obviously, since the branch & bound algorithm explores the whole subtree corresponding to these variables, the clause S does not contain any branching choices made during this phase. Only the branching decisions taken during the consistency phase and/or the waxing phase are considered.
• The algorithm used to enumerate the variables with the lowest reduced cost, and the basic variables, is widely inspired by a previous one published by Vimont et al. (2008). As it is represented in figure 4 (which summarizes the exploration process), this algorithm embeds a specific Depth First Search (dfs) procedure for solving small subproblems with the last 20 variables.

Computational results
Our algorithm has been experimented on the well known OR-Library set of 01MKP instances proposed by Beasley (1990). Each instance of this set is denoted cbm.n r where m is the number of constraints, n the number of variables and r the instance's number. The 01MKP OR-Library benchmark is composed of 5, 10 and 30 constraint instances and 100, 250 and 500 variables instances. There are 9 set of 30 instances with each n × m combination.
We obtained better proof time than the exact published approaches of James and Nakagawa (2005), Vimont et al. (2008) and the commercial software CPLEX 9.2, for the 10 constraint, 250 variable instances and the 5 constraint, 500 variable instances. We observed also that for the 5 constraint, 500 variable instances, the times required for obtaining the best solutions are clearly better than the ones provided by the best known heuristics on these instances (Vasquez and Vimont (2005) and Wilbaut and Hanafi (2008)). Moreover, our algorithm proved the optimality of all the cb10.500 instances. The corresponding optimal values, which were previously unknown, are exposed in table 1. The column z opt is the optimal value of the instance, opt. (h) is the time in hours required for obtaining the optimal value and proof (h) is the time in hours for proving the optimality of the value z opt . The column z opt − z corresponds to the gap between the optimal value and the previously best known solution: (vv) indicates that z was first found by Vasquez and Vimont (2005) and (wh) indicates that z was first found by Wilbaut and Hanafi (2008).

Conclusion
Although our implementation of resolution search is quite far from the original one proposed by Chvátal, especially because we have exploited specific structures of the 01MKP (hybridization with branch & bound, 1.x = k hyperplane decomposition, reduced cost constraint to generate implicitly the partial instantiations responsible for the fails, etc.), we showed that resolution search is a promising framework for designing efficient algorithms. Since the proof times are long for the 10 constraint, 500 variable instances, we plan to improve again our algorithm in order to accelerate the resolution process in the hope of maybe closing the OR-Library 01MKP benchmark by solving the 60 last 30 constraint 250/500 variable instances.