INFORMATION PROCESSING APPARATUS, NON-TRANSITORY COMPUTER-READABLE STORAGE MEDIUM, AND INFORMATION PROCESSING METHOD

An information processing apparatus includes a processor to execute a program; and a memory to store multiple retrieval target sentences including multiple retrieval target tokens and similarity determination information indicating whether combinations of the respective retrieval target tokens and respective retrieval tokens have high similarity or low similarity, the retrieval target tokens each being a smallest unit having a meaning, the retrieval tokens each being a smallest unit having a meaning and being included in a retrieval sentence. The memory stores the program which, when executed by the processor, performs processes of calculating inter-token similarity for the combinations indicated to have high similarity in the similarity determination information, and setting the inter-token similarity to a predetermined value for the combinations indicated to have low similarity in the similarity determination information, to calculate inter-sentence similarity between the retrieval sentence and the respective retrieval target sentences.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to an information processing apparatus, a non-transitory computer-readable storage medium, and an information processing method.

2. Description of the Related Art

The wide use of personal computers and the Internet has led to an increase in the volume of electronic documents accessible by users. There is a need for an efficient document retrieval technique for finding desired documents in such a large volume of documents.

In order to process the meaning of a natural language in document retrieval, it is useful to represent tokens, which are each a smallest unit of a character or a character string having a meaning, by vectors indicating the meanings of the corresponding tokens.

A method of giving one vector to one token is a mainstream technique; however, such a technique cannot eliminate the ambiguity in the meaning of a token having multiple meanings depending on context. Therefore, a technique is proposed for acquiring a vector of a token that allows the context to be considered.

In document retrieval, it is necessary to measure with high accuracy the similarity in meaning between a retrieval query that is a retrieval sentence input for retrieval and a retrieval target sentence that is a target of retrieval. In measuring the similarity with high accuracy, it is useful to calculate the inter-token similarity between tokens of the retrieval query and the retrieval target sentence.

For example, Non-patent Literature 1 describes a method of calculating the inter-sentence similarity by selecting the tokens having the highest similarity to tokens xiincluded in a retrieval query x from tokens Yjkincluded in retrieval target sentences Yj, and using a value obtained by averaging the inter-token similarities φ(xi,Yjk) calculated for the combinations of the i words.

SUMMARY OF THE INVENTION

In calculating the inter-sentence similarity, it is necessary to calculate the similarity in all combinations of all tokens included in the retrieval query and all tokens included in the retrieval target sentences, and this results in an enormous amount of calculation, which makes practical application difficult.

For example, when one vector representation is given to one token, every similarity between the tokens can be preliminarily calculated and stored as data in a lookup table or the like so that the calculation of similarity can be omitted at the time of retrieval. However, when vector representations of tokens that allow the context in which the tokens appear to be considered are used, the meaning of each token varies depending on the context, and thus the similarity between the tokens cannot be calculated in advance.

Accordingly, an object of at least one aspect of the invention is to reduce the load of calculating similarities for document retrieval.

An information processing apparatus according to an aspect of the invention includes a retrieval-target storage unit configured to store multiple retrieval target sentences including multiple retrieval target tokens, the retrieval target tokens each being a smallest unit having a meaning; a similarity-determination-information storage unit configured to store similarity determination information indicating whether combinations of the respective retrieval target tokens and respective retrieval tokens have high similarity or low similarity, the retrieval tokens each being a smallest unit having a meaning and being included in a retrieval sentence; and an inter-sentence-similarity calculation unit configured to calculate inter-token similarity for the combinations indicated to have high similarity in the similarity determination information, and sets the inter-token similarity to a predetermined value for the combinations indicated to have low similarity in the similarity determination information, to calculate inter-sentence similarity between the retrieval sentence and the respective retrieval target sentences.

A program according to an aspect of the invention causes a computer to function as a retrieval-target storage unit configured to store multiple retrieval target sentences including multiple retrieval target tokens, the retrieval target tokens each being a smallest unit having a meaning; a similarity-determination-information storage unit configured to store similarity determination information indicating whether combinations of the respective retrieval target tokens and respective retrieval tokens have high similarity or low similarity, the retrieval tokens each being a smallest unit having a meaning and being included in a retrieval sentence; and an inter-sentence-similarity calculation unit configured to calculate inter-token similarity for the combinations indicated to have high similarity in the similarity determination information, and sets the inter-token similarity to a predetermined value for the combinations indicated to have low similarity in the similarity determination information, to calculate inter-sentence similarity between the retrieval sentence and the respective retrieval target sentences.

An information processing method includes calculating inter-sentence similarities between multiple retrieval target sentences including multiple retrieval target tokens and a retrieval sentence including multiple retrieval tokens, the retrieval target tokens each being a smallest unit having a meaning, the retrieval tokens each being a smallest unit having a meaning; calculating inter-token similarity for combinations indicated to have high similarity in the similarity determination information indicating whether the combinations of the retrieval target tokens and the retrieval tokens have high similarity or low similarity, and sets the inter-token similarity to a predetermined value for the combinations indicated to have low similarity in the similarity determination information, to calculate the inter-sentence similarities between the retrieval sentence and the respective retrieval target sentences.

According to at least one aspect of the present invention, the load of calculating similarity for document retrieval can be reduced.

DETAILED DESCRIPTION OF THE INVENTION

First Embodiment

FIG. 1is a block diagram schematically illustrating the configuration of a document retrieval apparatus100, or information processing apparatus according to the first embodiment.

The document retrieval apparatus100includes a retrieval target database (hereinafter referred to as a retrieval target DB)101, a retrieval-target context-sensitive representation generating unit102, an information generating unit103, a retrieval-query input unit106, a tokenizer107, a retrieval-query context-sensitive representation generating unit108, a similar-token-table storage unit110, an inter-sentence-similarity calculation unit111, and a retrieval-result output unit112.

The information generating unit103includes a data structure converting unit104, a search database (hereinafter referred to as a search DB)105, and a similar-token-table generating unit109.

The retrieval target DB101is a retrieval-target storage unit that stores retrieval target sentences and retrieval-target token sequences corresponding to the retrieval target sentences. The retrieval-target token sequence is a sequence of multiple tokens, and one retrieval-target token sequence constitutes one sentence. Note that a token is a smallest unit having a meaning and is a character or a character string. The tokens included in a retrieval-target token sequence are also referred to as retrieval target tokens. It is presumed that the retrieval target DB101stores multiple retrieval target sentences and multiple retrieval-target token sequences corresponding to the retrieval target sentences.

In the following, a document retrieval task of retrieving an article corresponding to a retrieval query is considered as an example. Specifically, a task is considered in which the article “Holidays are as follows: summertime holiday . . . ” corresponding to the retrieval query “When does summer vacation start and end?” is retrieved from multiple articles. Here, the multiple articles are the multiple retrieval target sentences.

In such a case, the retrieval-target token sequence may be in a two-dimensional sequence format, as illustrated inFIG. 2. In the example of the retrieval-target token sequence illustrated inFIG. 2, the p-th article is stored in the p-th row, and the q-th retrieval target token counted from the beginning of the p-th article is stored in the p-th row and q-th column. InFIG. 2, a retrieval target token is a character or a character string surrounded by double quotations.

The retrieval-target context-sensitive representation generating unit102acquires retrieval-target token sequences from the retrieval target DB101. The retrieval-target context-sensitive representation generating unit102then generates a retrieval-target context-sensitive representation sequence in which retrieval-target context-sensitive representations, which are the context-sensitive representations of all retrieval target tokens included in the acquired retrieval-target token sequences, are arrayed. The generated retrieval-target context-sensitive representation sequence is provided to the data structure converting unit104and the inter-sentence-similarity calculation unit111. Here, the context-sensitive representations are vectors, and the retrieval-target context-sensitive representations are retrieval target vectors.

For example, the retrieval-target context-sensitive representation generating unit102is a retrieval-target-vector generating unit that generates retrieval target vectors, or vectors corresponding to the meanings of the retrieval target tokens included in retrieval-target token sequences. Here, the retrieval-target context-sensitive representation generating unit102identifies the meanings of the retrieval target tokens depending on the context of the retrieval target sentences corresponding to retrieval-target token sequences including the retrieval target tokens, and generates retrieval target vectors indicating the determined meanings.

Specifically, the retrieval-target context-sensitive representation generating unit102identifies the meanings depending on the context of the respective retrieval target tokens included in the retrieval-target token sequences. The retrieval-target context-sensitive representation generating unit102then arrays multidimensional vectors indicating the determined meanings in accordance with the respective sequences of the retrieval target tokens to generate the retrieval-target context-sensitive representation sequence.

The retrieval-target context-sensitive representation sequence may be in a two-dimensional sequence format, for example, as illustrated inFIG. 3. In the retrieval-target context-sensitive representation sequence illustrated inFIG. 3, the p-th piece of text is stored in the p-th row, and a vector, or context-sensitive representation, corresponding to the q-th retrieval target token counted from the beginning of the p-th article is stored in the p-th row and q-th column.

Note that a known method may be used for identifying the context-sensitive representations corresponding to the retrieval target tokens. For example, the following literature describes a method of acquiring a vector representation of a token that allows the context in which the token appears to be considered.

The data structure converting unit104acquires the retrieval-target context-sensitive representation sequence from the retrieval-target context-sensitive representation generating unit102. The data structure converting unit104then converts the acquired retrieval-target context-sensitive representation sequence into a search data structure. The generated search data structure is stored in the search DB105.

The search data structure may be selected from any known data structure in accordance with the algorithm of the k-approximate nearest neighbor search to be used. For example, when approximate nearest neighbor search (ANN) is used as the algorithm for the k-approximate nearest neighbor search, a data structure of a k-d tree may be selected. If locality sensitive hashing (LSH) is used as the algorithm of the k-approximate nearest neighbor search, the mapping results by a hash function may be selected as the data structure. Here, an example will be described in which ANN is used as the algorithm of the k-approximate nearest neighbor search, and the data structure of a k-d tree is used as the search data structure.

Note that these algorithms are described in the following literature.

The search DB105stores the search data structure converted by the data structure converting unit104.

The retrieval-query input unit106is a retrieval input unit that accepts input of a retrieval query, or retrieval sentence. The retrieval query includes multiple tokens. The tokens included in the retrieval query are also referred to as retrieval tokens.

For example, the retrieval-query input unit106accepts input of a question such as “When does the summer vacation start and end?” as a retrieval query.

The tokenizer107acquires the retrieval query from the retrieval-query input unit106. The tokenizer107is a token identifying unit that identifies retrieval query tokens in the acquired retrieval query and generates a retrieval-query token sequence in which the retrieval query tokens are arrayed. The generated retrieval-query token sequence is provided to the retrieval-query context-sensitive representation generating unit108. Note that the tokens included in the retrieval-query token sequence are also referred to as retrieval query tokens.

For example, the tokenizer107uses any known technique such as morphological analysis to identify tokens, which are the smallest units having meanings, in the retrieval query and arrays the identified tokens to generate a retrieval-query token sequence.

FIG. 4is a schematic diagram illustrating an example of a retrieval-query token sequence.

In the example illustrated inFIG. 4, the r-th token of the retrieval query is stored as the r-th element of the retrieval-query token sequence.

The retrieval-query context-sensitive representation generating unit108acquires the retrieval-query token sequence from the tokenizer107. The retrieval-query context-sensitive representation generating unit108then generates a retrieval-query context-sensitive representation sequence including arrayed retrieval-query context-sensitive representations, which are context-sensitive representations of retrieval query tokens, or all tokens included in the acquired retrieval-query token sequence. The generated retrieval-query context-sensitive representation sequence is provided to the similar-token-table generating unit109and the inter-sentence-similarity calculation unit111. Here, the retrieval-query context-sensitive representations are retrieval vectors.

For example, the retrieval-query context-sensitive representation generating unit108is a retrieval-vector generating unit that generates retrieval vectors, or vectors corresponding to the meanings of the retrieval tokens. Here, the retrieval-query context-sensitive representation generating unit108identifies the meanings of the retrieval tokens depending on the context of the retrieval sentence and generates retrieval vectors indicating the identified meanings.

Specifically, the retrieval-query context-sensitive representation generating unit108identifies the meanings depending on the context of the respective retrieval query tokens included in the retrieval-query token sequence. The retrieval-query context-sensitive representation generating unit108can array multidimensional vectors indicating the identified meanings in accordance with the sequence of the respective retrieval query tokens to generate a retrieval-query context-sensitive representation sequence. Note that a known method may be used for identifying the context-sensitive representations corresponding to the retrieval query tokens, as in the retrieval-target context-sensitive representations described above.

FIG. 5is a schematic diagram illustrating an example of a retrieval-query context-sensitive representation sequence.

In the example illustrated inFIG. 5, a vector, or context-sensitive representation corresponding to the r-th token of the retrieval query is stored as the r-th element of the retrieval-query context-sensitive representation sequence.

The similar-token-table generating unit109acquires the retrieval-query context-sensitive representation sequence from the retrieval-query context-sensitive representation generating unit108and acquires the search data structure from the search DB105. The similar-token-table generating unit109generates a similar token table serving as similarity determination information indicating whether the similarity of each combination of a retrieval target token and a retrieval query token is relatively high or low, from the acquired retrieval-query context-sensitive representation sequence and search data structure. The generated similar token table is stored in the similar-token-table storage unit110.

For example, the similar-token-table generating unit109may determine whether the similarity is relatively high or low for the respective combinations of the retrieval target tokens and the retrieval query tokens through a known search method that is more efficient than a brute-force search in which the similarity for all combinations of the retrieval target tokens and the retrieval query tokens is calculated to use the calculated similarity for determining whether the similarity is relatively high or not. For example, the similar-token-table generating unit109may search for k retrieval target tokens having high similarity relative to a certain retrieval query token by using the k-approximate nearest neighbor search to search for k neighboring points (where k is an integer of one or more). The similar-token-table generating unit109may set the k searched tokens to be tokens having relatively high similarity and set the remaining retrieval target tokens to be tokens having relatively low similarity. Note that a known technique such as ANN or LSH may be used as the algorithm of the k-approximate nearest neighbor search.

FIG. 6is a schematic diagram illustrating an example of a similar token table.

The example illustrated inFIG. 6is a lookup table showing that when the above-mentioned retrieval query “summer vacation is . . . ” is input, the similarity between each token included in the retrieval query and each token included in all retrieval target sentences is relatively high or low in the retrieval target sentences.

In the example illustrated inFIG. 6, the rows represent retrieval query tokens, and the columns represent retrieval target tokens. The circle symbol indicates that the similarity is relatively high, and the cross symbol indicates that the similarity is relatively low. For example, for the retrieval query token “summer,” the similarity to the retrieval target tokens “holiday” and “summertime” are relatively high in the tokens included in all of the retrieval target sentences.

Since the k-approximate nearest neighbor search algorithm can be applied to the generation of the similar token table, there is an advantage in that the calculation amount can be reduced.

InFIG. 6, for ease of explanation, retrieval query tokens are stored in the rows, and retrieval target tokens are stored in the columns; however, here, retrieval context-sensitive representations (i.e., retrieval vectors) corresponding to retrieval query tokens are stored in the rows, and retrieval-target context-sensitive representations (i.e., retrieval target vectors) corresponding to the retrieval target tokens are stored in the columns.

As described above, the data structure converting unit104, the search DB105, and the similar-token-table generating unit109constitute the information generating unit103that generates a similar token table, or similarity determination information.

The information generating unit103searches the multiple points indicated by multiple retrieval target vectors for at least one neighboring point located in the vicinity of one point indicated by one retrieval vector of the multiple retrieval vectors, determines that the at least one combination of the retrieval token corresponding to the point indicated by the one retrieval vector and the at least one retrieval target token corresponding to the at least one neighboring point has high similarity, and determines that the at least one combination of the one retrieval token and the at least one retrieval target token corresponding to the at least one point other than the at least one neighboring point has low similarity, to generate a similar token table. Here, the information generating unit103searches for at least one neighboring point by using a search method more efficient than a brute-force search for calculating all distances between the point corresponding to one retrieval vector and multiple points corresponding to multiple retrieval target vectors.

The similar-token-table storage unit110is a similarity-determination-information storage unit for storing a similar token table serving as similarity determination information.

The similar token table indicates whether combinations of retrieval target tokens and retrieval tokens have high or low similarity.

The inter-sentence-similarity calculation unit111acquires the similar token table from the similar-token-table storage unit110, acquires the retrieval-target context-sensitive representation sequence from the retrieval-target context-sensitive representation generating unit102, and acquires the retrieval-query context-sensitive representation sequence from the retrieval-query context-sensitive representation generating unit108. The inter-sentence-similarity calculation unit111calculates the inter-sentence similarity, or the similarity between the retrieval query and the retrieval target sentences from the acquired similar token table, retrieval-target context-sensitive representation sequence, and retrieval-query context-sensitive representation sequence. The calculated inter-sentence similarity is provided to the retrieval-result output unit112.

Here, the inter-sentence-similarity calculation unit111calculates the inter-token similarity of the combinations that are indicated to have high similarity in the similar token table, and sets the inter-token similarity to a predetermined value for the combinations that are indicated to have low similarity in the similar token table, thereby reducing the calculation load for the calculation of the inter-sentence similarity. Note that when the inter-sentence-similarity calculation unit111calculates the inter-token similarity, the inter-token similarity is set such that the smaller the distance between a point indicated by one retrieval target vector of multiple retrieval target vectors and a point indicated by one retrieval vector of multiple retrieval vectors, the higher the similarity of the combination of the retrieval target vector and the retrieval vector. The inter-sentence-similarity calculation unit111then identifies the maximum values of the inter-token similarity in the combinations of the respective retrieval tokens and the respective retrieval target tokens included in one of the multiple retrieval target sentences, and calculates the inter-sentence similarity between the retrieval sentence and the one retrieval target sentence on the basis of the average of the identified maximum values.

The calculation of the inter-sentence similarity will now be explained.

The inter-sentence similarity may be calculated by using any inter-token similarity. For example, the inter-sentence similarity may be calculated by using the maximum alignment method described in the above-mentioned Non-patent Literature 1.

First, the calculation of inter-sentence similarity by a general maximum alignment method will be described, and then accelerated calculation of the inter-sentence similarity according to the first embodiment will be described.

In the calculation of the inter-sentence similarity by the general maximum alignment method, the token having the highest inter-token similarity to each retrieval query token xiincluded in a retrieval query x is selected from retrieval target tokens Y, included in a retrieval target sentence Yj. Then, the inter-sentence similarity is calculated by the average value obtained by averaging the inter-token similarities φ(xi,Yjk) calculated for the selected i=|x| retrieval target tokens.

The calculation of the inter-sentence similarity by a maximum alignment method is formulated as in the following expression (1), where the inter-sentence similarity between a retrieval query x and the j-th retrieval target sentence Yjis s(x,Yj).

Here, xidenotes the i-th retrieval query token of the retrieval query x, Yjdenotes the k-th retrieval target token of the retrieval target sentence Yj, and p(xi,Yjk) denotes the inter-token similarity between the retrieval query token xiand the retrieval target token Yjk. For inter-token similarity, the distance (e.g., the cosine similarity of a context-sensitive representation) between the vector of a retrieval query token and the vector of a retrieval target token is used.

In the maximum alignment method, the inter-sentence similarity between a retrieval query and each retrieval target sentence is calculated on the basis of the above concept.

This corresponds to obtaining the inter-sentence similarity s between the retrieval query and all of the retrieval target sentences and generating the inter-sentence similarity S(x,Y) between the retrieval query and each retrieval target sentence, as indicated in the following expression (2).

Here, the j-th element of S(x,Y) is the inter-sentence similarity between the retrieval query x and the retrieval target sentence Yj.

Next, the expression of the above-mentioned maximum alignment method is modified.

A similarity matrix A(i) consisting of a retrieval query token xiand all retrieval target tokens is defined by the following expression (3).

Here, the similarity matrix A(i) is a matrix of the type indicated by the following expression (4).

Note that |Y| denotes the total number of retrieval target sentences, and |Yj| denotes the number of retrieval target tokens included in the j-th retrieval target sentence.

Note that for the row l satisfying the following expression (5), the inter-token similarity p cannot be calculated because no retrieval target tokens correspond to the (|Yl|+1)-th and subsequent rows. Therefore, zero-padding processing may be performed to fill the inter-token similarity with zero.

The maximum value max of the similarity then is defined by the following expression (6).

In such a case, the inter-sentence similarity S(x,Y) between the retrieval query and each retrieval target sentence can be modified as in the following expression (7).

As indicated by the expression (7), it is necessary to obtain the similarity matrix A(i) to obtain the inter-sentence similarity S(x,Y) between the retrieval query x and each retrieval target sentence Y.

However, the calculation amount for obtaining the similarity matrix A(i) is O(|x|Σj|Yj|). Therefore, there has been a problem in that when the volume of the retrieval target sentences is large, the calculation amount of Σj|Yj| is enormous, which is not a practical calculation amount.

Accordingly, the inter-sentence-similarity calculation unit111according to the first embodiment speeds up the calculation of the inter-sentence similarity.

In the maximum alignment method before the speed-up, the values of the inter-token similarity between the retrieval query tokens and all of the retrieval target tokens are compared relatively for each retrieval target sentence, and the maximum values are acquired, to acquire the maximum value max of the inter-token similarity between a retrieval query token xiand a retrieval target sentence Yjas indicated by the expression (6).

However, in the document retrieval task, if a value of inter-token similarity is relatively high in one retrieval target sentence but relatively low in all retrieval target sentences, the possibility of this inter-token similarity affecting the inter-document similarity is low.

Accordingly, when the inter-token similarity is relatively low in all retrieval target sentences, the inter-sentence-similarity calculation unit111skips the calculation of this inter-token similarity (for example, approximates it to zero) to speed up the calculation of the inter-document similarity.

Specifically, the inter-sentence-similarity calculation unit111approximates the similarity matrix A(i) as indicated by the following expression (8).

where γ(xi,Yjk) is specified by the following expression (9).

Here, Simset(xi) is a function that returns a set of retrieval target tokens Yjkof which the value in the fields in the row of a retrieval query token xiin the similar token table is the circle symbol.

For example, in the example illustrated inFIG. 6, in the row of the retrieval query token “summer,” the retrieval target tokens “holiday” and “summertime” are returned by Simset (xi).

The retrieval-result output unit112acquires the inter-sentence similarity from the inter-sentence-similarity calculation unit111and acquires the retrieval target sentences from the retrieval target DB101. The retrieval-result output unit112sorts the retrieval target sentences in accordance with the inter-sentence similarity and outputs the sorted retrieval target sentences as the retrieval result.

Here, any method of sorting such as ascending or descending order of inter-sentence similarity may be selected for the sort.

FIG. 7is a block diagram schematically illustrating the hardware configuration implementing the document retrieval apparatus100.

As illustrated inFIG. 7, the document retrieval apparatus100can be implemented by a computer190including a memory191, a processor192, an auxiliary storage device193, a mouse194, a keyboard195, and a display device196.

Specifically, a portion or the entirety of the retrieval-target context-sensitive representation generating unit102, the data structure converting unit104, the tokenizer107, the retrieval-query context-sensitive representation generating unit108, the similar-token-table generating unit109, the inter-sentence-similarity calculation unit111, and the retrieval-result output unit112described above can be implemented by the memory191and the processor192, such as a central processing unit (CPU), that executes the programs stored in the memory191. Such programs may be provided via a network or may be recorded and provided on a recording medium. That is, such programs may be provided as, for example, program products.

The retrieval target DB101, the search DB105, and the similar-token-table storage unit110can be implemented by the processor192using the auxiliary storage device193. However, the auxiliary storage device193does not necessarily have to be present in the document retrieval apparatus100, and an auxiliary storage device present in a cloud may be used via a communication interface (not illustrated). Note that the similar-token-table storage unit110may be implemented by the memory191.

The retrieval-query input unit106can be implemented by the processor192using the mouse194and the keyboard195serving as input devices and the display device196. Note that the mouse194and the keyboard195function as input units, and the display device196functions as a display unit.

FIG. 8is a flowchart illustrating processing by the retrieval-target context-sensitive representation generating unit102.

First, the retrieval-target context-sensitive representation generating unit102acquires a retrieval-target token sequence from the retrieval target DB101(step S10).

The retrieval-target context-sensitive representation generating unit102then identifies the meanings of all retrieval target tokens included in the acquired retrieval-target context-sensitive representation sequence depending on context, and arrays retrieval-target context-sensitive representations (i.e., retrieval target vectors) indicating the identified meanings in accordance with the acquired retrieval-target token sequence, to generate a retrieval-target context-sensitive representation sequence (step S11).

The retrieval-target context-sensitive representation generating unit102then provides the generated retrieval-target context-sensitive representation sequence to the data structure converting unit104and the inter-sentence-similarity calculation unit111(step S12).

FIG. 9is a flowchart illustrating processing by the data structure converting unit104.

First, the data structure converting unit104acquires the retrieval-target context-sensitive representation sequence from the retrieval-target context-sensitive representation generating unit102(step S20).

Next, the data structure converting unit104converts the acquired retrieval-target context-sensitive representation sequence into a search data structure used for searching retrieval target tokens having relatively high similarity to the retrieval query tokens through a search method more efficient than a brute-force search (step S21).

The data structure converting unit104then provides the resulting search data structure to the search DB105(step S22). Note that the search DB105stores the provided search data structure.

FIG. 10is a flowchart illustrating processing by the tokenizer107.

The tokenizer107acquires a retrieval query from the retrieval-query input unit106(step S30).

The tokenizer107then identifies retrieval query tokens, which are the smallest units having meanings, in the acquired retrieval query, and generates a retrieval-query token sequence by arraying the identified retrieval query tokens in accordance with the retrieval query (step S31).

The tokenizer107then provides the generated retrieval-query token sequence to the retrieval-query context-sensitive representation generating unit108(step S32).

FIG. 11is a flowchart illustrating processing by the retrieval-query context-sensitive representation generating unit108.

First, the retrieval-query context-sensitive representation generating unit108acquires the retrieval-query token sequence from the tokenizer107(step S40).

The retrieval-query context-sensitive representation generating unit108then identifies the respective meanings of all retrieval target tokens included in the acquired retrieval-query context-sensitive representation sequence depending on context, and arrays context-sensitive representations indicating the identified meanings (hereinafter, also referred to as retrieval-query context-sensitive representations), or vectors (hereinafter, also referred to as retrieval query vectors) in accordance with the acquired retrieval-query token sequence, to generate a retrieval-query context-sensitive representation sequence (step S41).

The retrieval-query context-sensitive representation generating unit108then provides the generated retrieval-query context-sensitive representation sequence to the similar-token-table generating unit109and the inter-sentence-similarity calculation unit111(step S42).

FIG. 12is a flowchart illustrating processing by the similar-token-table generating unit109.

The similar-token-table generating unit109also acquires the search data structure from the search DB105(step S51).

The similar-token-table generating unit109then searches all of the retrieval-target context-sensitive representations for retrieval-target context-sensitive representations having relatively higher similarity to all of the retrieval-query context-sensitive representations included in the retrieval-query context-sensitive representation sequence by using a search method more efficient than a brute-force search in the search data structure, to generate a similar token table indicating whether the similarity between each of the retrieval-query context-sensitive representations and each of the retrieval-target context-sensitive representations is high or low (step S52).

The similar-token-table generating unit109then provides the generated similar token table to the similar-token-table storage unit110to store the similar token table in the similar-token-table storage unit110(step S53).

FIG. 13is a flowchart illustrating processing by the inter-sentence-similarity calculation unit111.

First, the inter-sentence-similarity calculation unit111acquires the similar token table from the similar-token-table storage unit110(step S60).

The inter-sentence-similarity calculation unit111also acquires the retrieval-query context-sensitive representation sequence from the retrieval-query context-sensitive representation generating unit108(step S61).

The inter-sentence-similarity calculation unit111also acquires the retrieval-target context-sensitive representation sequence from the retrieval-target context-sensitive representation generating unit102(step S62).

The inter-sentence-similarity calculation unit111then refers to the similar token table to calculate the inter-token similarity for the combinations of the retrieval query tokens and retrieval target tokens that are determined to have high similarity and to set the combinations determined to have low similarity to be a predetermined value (e.g., zero), and thereby calculates the inter-token similarity between the retrieval target sentences and the retrieval query (step S63).

The inter-sentence-similarity calculation unit111then provides the calculated inter-sentence similarity to the retrieval-result output unit112(step S64).

FIG. 14is a flowchart illustrating processing by the retrieval-result output unit112.

First, the retrieval-result output unit112acquires the inter-sentence similarity from the inter-sentence-similarity calculation unit111(step S70).

The retrieval-result output unit112then rearranges the retrieval target sentences in accordance with the acquired inter-sentence similarity to generate a retrieval result that can identify at least the retrieval target sentence having the highest inter-sentence similarity (step S71). Note that the retrieval-result output unit112may acquire the retrieval target sentences from the retrieval target DB101.

The retrieval-result output unit112then displays the generated retrieval result on, for example, the display device196illustrated inFIG. 7, to output the retrieval result (step S72).

As described in the first embodiment above, since the inter-token similarity between tokens determined not to have high similarity can be set to a predetermined value when the inter-sentence similarity is calculated, the calculation load of the inter-sentence similarity can be reduced.

Second Embodiment

FIG. 15is a block diagram schematically illustrating the configuration of a document retrieval apparatus200, or an information processing apparatus according to the second embodiment.

The document retrieval apparatus200includes a retrieval target DB101, a retrieval-target context-sensitive representation generating unit202, an information generating unit103, a retrieval-query input unit106, a tokenizer107, a retrieval-query context-sensitive representation generating unit108, a similar-token-table storage unit110, an inter-sentence-similarity calculation unit111, a retrieval-result output unit112, and an ontology DB213.

The ontology DB213is a semantic-relation-information storage unit that stores ontology, or semantic relation information indicating the semantic relation of tokens. In the second embodiment, the ontology indicates at least one of the synonymous relation and the inclusive relation of tokens as a semantic relation.

Note that the ontology DB213can be implemented by, for example, the processor192illustrated inFIG. 7using the auxiliary storage device193.

The retrieval-target context-sensitive representation generating unit202acquires a retrieval-target token sequence from the retrieval target DB101. The retrieval-target context-sensitive representation generating unit202then refers to the ontology stored in the ontology DB213, to group the retrieval target tokens included in the acquired retrieval-target token sequence into a group that can be treated as to have the same meaning. For example, the retrieval-target context-sensitive representation generating unit202groups into one group the retrieval target tokens that are indicated by the ontology to have a synonymous relation or an inclusive relation. Specifically, the retrieval-target context-sensitive representation generating unit202groups “vacation” and “holiday” into one group because they both mean “a leave of absence,” in other words, they have a synonymous relation.

The retrieval-target context-sensitive representation generating unit202then assigns one retrieval-target context-sensitive representation to one group to generate a retrieval-target context-sensitive representation sequence. In other words, the retrieval-target context-sensitive representation generating unit202generates retrieval target vectors that are the same retrieval-target context-sensitive representations from the retrieval target tokens having identified meanings that are in a synonymous relation or an inclusive relation. For example, the retrieval-target context-sensitive representation generating unit202may set the retrieval-target context-sensitive representation of any one of the retrieval target tokens included in one group to be the retrieval-target context-sensitive representation of the group, or may set a representative value (e.g., the average value) of the retrieval-target context-sensitive representation of a retrieval target token included in one group to be the retrieval-target context-sensitive representation of the group.

FIG. 16is a flowchart illustrating processing by the retrieval-target context-sensitive representation generating unit202according to the second embodiment.

First, the retrieval-target context-sensitive representation generating unit202acquires a retrieval-target token sequence from the retrieval target DB101(step S80).

The retrieval-target context-sensitive representation generating unit202also acquires ontology from the ontology DB213(step S81).

The retrieval-target context-sensitive representation generating unit202then identifies the meanings of all retrieval target tokens included in the acquired retrieval-target context-sensitive representation sequence in accordance with context, refers to the acquired ontology to group the retrieval target tokens by the identified meanings, assigns one retrieval-target context-sensitive representation to the retrieval target tokens belonging to the group, and assigns retrieval-target context-sensitive representations corresponding to the identified meanings to the retrieval target tokens not belonging to the group, to generate a retrieval-target context-sensitive representation sequence (step S82).

The retrieval-target context-sensitive representation generating unit202then provides the generated retrieval-target context-sensitive representation sequence to the data structure converting unit104and the inter-sentence-similarity calculation unit111(step S83).

As described above, according to the second embodiment, the grouping of the retrieval target tokens reduces the number of targets to be determined whether the similarity between the retrieval query tokens and the retrieval target tokens is high by the similar-token-table generating unit109, and thereby the processing load on the similar-token-table generating unit109can be reduced.

Third Embodiment

FIG. 17is a block diagram schematically illustrating the configuration of a document retrieval apparatus300, or an information processing apparatus according to a third embodiment.

The document retrieval apparatus300includes a retrieval target DB101, a retrieval-target context-sensitive representation generating unit202, an information generating unit103, a retrieval-query input unit106, a tokenizer107, a retrieval-query context-sensitive representation generating unit108, a similar-token-table storage unit110, an inter-sentence-similarity calculation unit111, a retrieval-result output unit112, an ontology DB213, a retrieval-target dimension reducing unit314, and a retrieval-query dimension reducing unit315.

However, the retrieval-query context-sensitive representation generating unit108according to the third embodiment provides a retrieval-query context-sensitive representation sequence to the retrieval-query dimension reducing unit315and the inter-sentence-similarity calculation unit111.

The retrieval-target context-sensitive representation generating unit202and the ontology DB213according to the third embodiment are respectively the same as the retrieval-target context-sensitive representation generating unit202and the ontology DB213according to the second embodiment.

However, the retrieval-target context-sensitive representation generating unit202according to the third embodiment provides a retrieval-target context-sensitive representation sequence to the retrieval-target dimension reducing unit314and the inter-sentence-similarity calculation unit111.

The retrieval-target dimension reducing unit314acquires a retrieval-target context-sensitive representation sequence from the retrieval-target context-sensitive representation generating unit202. The retrieval-target dimension reducing unit314performs dimension compression of all retrieval-target context-sensitive representations included in the acquired retrieval-target context-sensitive representation sequence to generate low-dimensional retrieval-target context-sensitive representations having reduced dimensions (i.e., low-dimensional retrieval target vectors), and arranges the low-dimensional retrieval-target context-sensitive representations to generate a low-dimensional retrieval-target context-sensitive representation sequence having reduced dimensions. The retrieval-target dimension reducing unit314provides the generated low-dimensional retrieval-target context-sensitive representation sequence to the data structure converting unit104. Note that any known technique such as principal component analysis may be used for dimension compression.

Note that the data structure converting unit104according to the third embodiment converts the low-dimensional retrieval-target context-sensitive representation sequence into a search data structure. The method of conversion is the same as that in the first embodiment.

The retrieval-query dimension reducing unit315acquires a retrieval-query context-sensitive representation sequence from the retrieval-query context-sensitive representation generating unit108. The retrieval-query dimension reducing unit315is a retrieval dimension reduction unit that performs dimension compression of all retrieval-query context-sensitive representations included in the acquired retrieval-query context-sensitive representation sequence to generate low-dimensional retrieval-query context-sensitive representations having reduced dimensions (i.e., low-dimensional retrieval vectors), and arranges the low-dimensional retrieval-query context-sensitive representations to generate a low-dimensional retrieval-query context-sensitive representation sequence having reduced dimensions. The retrieval-query dimension reducing unit315provides the generated low-dimensional retrieval-query context-sensitive representation sequence to the similar-token-table generating unit109. Note that any known technique such as principal component analysis may be used for dimension compression.

Note that the similar-token-table generating unit109generates a similar token table by using the low-dimensional retrieval-query context-sensitive representation sequence acquired from the retrieval-query dimension reducing unit315and the search data structure acquired from the search DB105. The generation method is the same as that in the first embodiment.

As described above, in the third embodiment, the information generating unit103generates a similar token table by using the low-dimensional retrieval-target context-sensitive representation sequence generated by the retrieval-target dimension reducing unit314and the low-dimensional retrieval-query context-sensitive representation sequence.

Specifically, the information generating unit103searches the multiple points indicated by multiple retrieval target vectors for at least one neighboring point, or at least one point located in the vicinity of a point indicated by one low-dimensional retrieval vector of multiple low-dimensional retrieval vectors, determines that the at least one combination of the retrieval token corresponding to the point indicated by the one low-dimensional retrieval vector and the at least one retrieval target token corresponding to the at least one neighboring point has high similarity, and determines that the at least one combination of the one retrieval token and the at least one retrieval target token corresponding to the at least one point other than the at least one neighboring point has low similarity, to generate a similar token table. Here, the information generating unit103searches for at least one neighboring point by using a search method more efficient than a brute-force search for calculating all distances between the point corresponding to one low-dimensional retrieval vector and multiple points corresponding to multiple low-dimensional retrieval target vectors.

A portion or the entirety of the retrieval-target dimension reducing unit314and the retrieval-query dimension reducing unit315described above can be implemented by the memory191and the processor192that executes the programs stored in the memory191, as illustrated inFIG. 7.

FIG. 18is a flowchart illustrating processing by the retrieval-target dimension reducing unit314.

The retrieval-target dimension reducing unit314then reduces the dimensions of all retrieval-target context-sensitive representations included in the acquired retrieval-target context-sensitive representation sequence to generate a low-dimensional retrieval-target context-sensitive representation sequence (step S91).

The retrieval-target dimension reducing unit314then provides the low-dimensional retrieval-target context-sensitive representation sequence to the data structure converting unit104(step S92).

FIG. 19is a flowchart illustrating processing by the retrieval-query dimension reducing unit315.

The retrieval-query dimension reducing unit315then reduces the dimensions of all retrieval-query context-sensitive representations included in the acquired retrieval-query context-sensitive representation sequence to generate a low-dimensional retrieval-query context-sensitive representation sequence (step S101).

The retrieval-query dimension reducing unit315then provides the low-dimensional retrieval-query context-sensitive representation sequence to the similar-token-table generating unit109(step S102).

As described above, in the third embodiment, even when the retrieval-target context-sensitive representations and the retrieval-query context-sensitive representations have high dimensions, the processing load on the similar-token-table generating unit109can be reduced by reducing these dimensions.

In the first to third embodiments described above, multiple retrieval target sentences and multiple retrieval-target token sequences corresponding to the multiple retrieval target sentences are stored in the retrieval target DB101; however, the first to third embodiments are not limited to such an example. For example, the retrieval target DB101may store multiple retrieval target sentences, and the retrieval-target context-sensitive representation generating unit102may use a known technique to generate corresponding retrieval-target token sequences.

In the first to third embodiments described above, the tokenizer107generates a retrieval-query token sequence; however, the first to third embodiments are not limited to such an example. For example, the retrieval-query context-sensitive representation generating unit108may use a known technique to generate a retrieval-query token sequence from a retrieval query.

Furthermore, in the first to third embodiments described above, the retrieval-target context-sensitive representation generating units102and202and the retrieval-query context-sensitive representation generating unit108generate vectors from tokens depending on context; however, the first to third embodiments are not limited to such an example. For example, a vector having a one-to-one correspondence to a token may be generated independently from context.

Even in such a case, according to the present embodiment, the calculation load of the inter-sentence similarity can be reduced without preparing a lookup table that stores inter-token similarity, which is the similarity between tokens, in advance.

The third embodiment is the same as the second embodiment except that the retrieval-target dimension reducing unit314and the retrieval-query dimension reducing unit315are added; alternatively, these components may be added to the first embodiment.

DESCRIPTION OF REFERENCE CHARACTERS