US 6,301,577 B1Grant

Similar document retrieval method using plural similarity calculation methods and recommended article notification service system using similar document retrieval method

Issue Date:2001-10-09

•9 Claims

•11 Drawing Sheets

Abstract

A similar document retrieval method capable of realizing an improved retrieval performance. In this similar document retrieval method for retrieving similar documents of a reference document from a plurality of retrieval target documents, similarities of each one of the plurality of retrieval target documents with respect to the reference document are calculated by using each one of two or more similarity calculation methods separately, and the similar documents of the reference document are retrieved by carrying out a discrimination analysis with respect to each one of a plurality of similarities calculated by using each one of the two or more similarity calculation methods separately.

Metadata

Assignee

KDD Corporation

Inventors

Kazunori Matsumoto
Kazuo Hashimoto
Shigeki Muramatsu

Application Information

Application Number:US 09/668,718

Filing Date:2000-09-22

Priority Date:1999-09-22

Art Unit:7

Classifications

IPC:

G06F 1730

Field of Search:

707 5707 1707 2707 3707 6707 10707104345327706 14706 45

Patent Drawings (11 sheets)

Description

Background of the Invention

[0002] 1. Field of the Invention

[0003] The present invention relates to a method for retrieving similar documents of a reference document from a plurality of retrieval target documents, and a recommended article notification service system utilizing the similar document retrieval method.

[0004] 2. Description of the Background Art

[0005] The well known retrieval models for retrieving similar documents include a vector space model such as tf·idf and a probabilistic model in which a similarity with respect to a retrieval requested document is expressed by a ratio of a relevant document probability and an non-relevant document probability with respect to a retrieval request. An example of the probabilistic model is disclosed in Iwayama et al.: “Hierarchical Bayesian Clustering for Automatic Text Classification”, Proceedings of IJCAI-95, pp. 1322-1327, 1995, for example. When the vector space model and the probabilistic model are compared, the probabilistic model has a clearer meaning with respect to a value of the similarity (distance), and the probabilistic model is expected to have a superior precision at a time of clustering as shown by Iwayama et al. mentioned above, so that the probabilistic model is considered superior.

[0006] FIG. 1 is a graph showing a distribution of similar documents and dissimilar documents in the case where the similarities of a plurality of target documents are calculated in order to retrieve similar documents with respect to a given reference document, using the probabilistic model of Iwayama et al. In FIG. 1, the horizontal axis represents the similarity while the vertical axis represents a relative frequency, and black rectangle marks indicate a plot of the similarities of similar documents while white rectangle marks indicate a plot of the similarities of dissimilar documents. Note that this distribution was calculated using 10,000 target documents extracted from the Published Japanese Patent Applications between 1993 and 1999, with respect to 21 retrieval requests. Also, the comprehensive similarity Judgment for these 10,000 Published Japanese Patent Applications with respect to each retrieval request was made by experts.

[0007] As shown in FIG. 1, in the high similarity region such as a region with the similarity not greater than −1.0, there are hardly any dissimilar document so that the similar documents and the dissimilar documents can be separated almost completely. It can be seen that a distribution of the similar documents is flatter and more widespread compared with a distribution of the dissimilar documents. For this reason, there are many portions where the separation from the dissimilar documents is not realized very well because of the low similarities of some similar documents.

[0008] In the similar document retrieval using the probabilistic model of Iwayama et al. that is considered as a superior probabilistic model, the result of retrieval experiments using Iwayama et al's similarity measure can be analyzed in detail to reveal that, as can be seen in a graph of FIG. 5, the similar documents with relatively high similarities can be appropriately separated from the dissimilar documents, but there are many dissimilar documents at somewhat lower similarities so that the similar documents and the dissimilar documents coexist there, and they lowers the overall retrieval precision so that it is difficult to obtain the sufficient retrieval precision.

Summary of the Invention

[0009] It is therefore an object of the present invention to provide a similar document retrieval method capable of realizing an improved retrieval performance by combining two or more similarities calculated by two or more different methods.

[0010] It is another object of the present invention to provide a recommended article notification service system utilizing this similar document retrieval method.

[0011] According to one aspect of the present invention there is provided a similar document retrieval method for retrieving similar documents of a reference document from a plurality of retrieval target documents, comprising the steps of: calculating similarities of each one of the plurality of retrieval target documents with respect to the reference document by using each one of two or more similarity calculation methods separately; retrieving the similar documents of the reference document by carrying out a discrimination analysis with respect to each one of a plurality of similarities calculated by using each one of the two or more similarity calculation methods separately.

[0012] According to another aspect of the present invention there is provided a recommended article notification service system for delivering mails describing recommended articles to users through Internet, comprising: a profile generation unit configured to generate a profile of each user; a recommended article selection unit configured to select the recommended articles from a plurality of articles in accordance with the profile of each user, by utilizing a similar document retrieval method, where the similar document retrieval method retrieves the recommended articles by calculating similarities of each one of the plurality of articles with respect to the profile of each user by using each one of two or more similarity calculation methods separately, and carrying out a discrimination analysis with respect to each one of a plurality of similarities calculated by using each one of the two or more similarity calculation methods separately; and a delivery unit configured to deliver a Web mail containing information of the recommended articles to each user through the Internet.

[0013] According to another aspect of the present invention there is provided a method for providing a recommended article notification service for delivering mails describing recommended articles to users through Internet, comprising: generating a profile of each user; selecting the recommended articles from a plurality of articles in accordance with the profile of each user, by utilizing a similar document retrieval method, where the similar document retrieval method retrieves the recommended articles by calculating similarities of each one of the plurality of articles with respect to the profile of each user by using each one of two or more similarity calculation methods separately, and carrying out a discrimination analysis with respect to each one of a plurality of similarities calculated by using each one of the two or more similarity calculation methods separately; and delivering a Web mail containing information of the recommended articles to each user through the Internet.

[0014] Other features and advantages of the present invention will become apparent from the following description taken in conjunction with the accompanying drawings.

Brief Description of the Drawings

[0015] FIG. 1 is a graph showing a distribution of similar documents and dissimilar documents according to a conventional probabilistic model of Iwayama et al.

[0016] FIG. 2 is a graph showing a distribution of similar documents and dissimilar documents in a two dimensional feature space according to the present invention.

[0017] FIG. 3 is a graph showing a part of the graph of FIG. 2 in enlargement along with lines representing two exemplary linear discriminant functions.

[0018] FIG. 4 is a flow chart showing a processing procedure of a similar document retrieval method according to the first embodiment of the present invention.

[0019] FIG. 5 is a flow chart showing a processing procedure for calculating a linear discriminant function to be used in the processing procedure of FIG. 4.

[0020] FIG. 6 is a diagram showing a table of average precision obtained for various combinations of similarities according to different models, in the second embodiment of the present invention.

[0021] FIG. 7 is a diagram showing one exemplary display layout of contents to be delivered in a mail magazine service according to the third embodiment of the present invention.

[0022] FIG. 8 is a diagram showing another exemplary display layout of contents to be delivered in a mail magazine service according to the third embodiment of the present invention.

[0023] FIG. 9 is a diagram showing an exemplary display of an article selected by a user on the display layout of FIG. 7 or FIG. 8 in a mail magazine service according to the third embodiment of the present invention.

[0024] FIG. 10 is a block diagram showing an exemplary basic configuration of a mail magazine service system according to the third embodiment of the present invention.

[0025] FIG. 11 is a diagram showing an exemplary module configuration for forming the mail magazine service system of FIG. 10 by using a group of programs.

Detailed Description of the Preferred Embodiments

[0026] Referring now to FIG. 2 to FIG. 5, the first embodiment of a similar document retrieval method according to the present invention will be described in detail.

[0027] In the similar document retrieval method of the first embodiment, the multinomial distribution model is used in addition to the probabilistic model of Iwayama et al., such that the retrieval performance is improved by combining the similarity calculated by utilizing the probabilistic model of Iwayama et al. and the similarity calculated by utilizing the multinomial distribution model.

[0028] First, the principle of the similar document retrieval method of the first embodiment will be described with references to FIG. 2 and FIG. 3.

[0029] FIG. 2 shows a graph of a distribution of similar documents and dissimilar documents in a two-dimensional feature space formed by the similarity in the probabilistic model of Iwayama et al. and the similarly in the multinomial distribution model as feature quantities, that was obtained for each retrieval request, where the horizontal axis represents the similarity in the multinomial distribution model while the vertical axis represents the similarity in the probabilistic model of Iwayama et al. Also, in FIG. 3, black rectangle marks indicate the similarities of similar documents with respect to a reference document while white rectangle marks indicate the similarities of dissimilar documents with respect to a reference document.

[0030] FIG. 3 shows an enlarged view of a part of FIG. 2 centered around a portion containing many similar documents indicated by the black rectangle marks. As shown in FIG. 3, if a line 100 at the similarity in the probabilistic model of Iwayama et al. equal to −1.2 is used as a border, i.e., a threshold line, for discriminating the similar documents and the dissimilar documents, FIG. 3 indicates the retrieval result in which documents below this threshold line 100 are the similar documents while documents above this threshold line 100 are the dissimilar documents.

[0031] In FIG. 3, there are altogether 33 documents below the threshold line 100 of the similarity in the probabilistic model of Iwayama et al. equal to −1.2 that are judged as similar documents, which include 11 similar documents indicated by the black rectangle marks, i.e., correct documents, and 22 dissimilar documents indicated by the white rectangle marks, i.e., incorrect documents.

[0032] Namely, in the case of utilizing only the similarity in the probabilistic model of Iwayama et al., the documents judged as similar documents will contain more actually dissimilar documents than actually similar documents, so that it can be seen that the retrieval performance is rather poor.

[0033] In order to improve the retrieval performance further, the similar document retrieval method of the present invention combines the similarity in the multinomial distribution model with the similarity in the probabilistic model of Iwayama et al., and to this end, a combined threshold line 200 shown in FIG. 3 will be used as a threshold line for a combination of the similarity in the probabilistic model of Iwayama et al. and the similarity in the multinomial distribution model.

[0034] This combined threshold line 200 can be expressed as y=−0.00055x−1.7, where y stands for a value along the vertical axis and x stands for a value along the horizontal axis in FIG. 3. Note that, in this notation, the above described threshold line 100 can be expressed as y=−1.2.

[0035] In the similarity distribution shown in FIG. 3, when this combined threshold line 200 of y=−0.00055x−1.7 is used, documents above this combined threshold line 200 will be judged as dissimilar documents, while documents below this combined threshold line 200 will be judged as similar documents. In FIG. 3, there are altogether 20 documents below the combined threshold line 200 that are judged as similar documents, which include 11 similar documents indicated by the black rectangle marks, i.e., correct documents, and 9 dissimilar documents indicated by the white rectangle marks, i.e., incorrect documents.

[0036] Thus, it can be seen from this result that, in the similar document retrieval method of the present invention which utilizes both the similarity in the probabilistic model of Iwayama et al. and the similarity in the multinomial distribution model, the number of actually dissimilar documents contained in the documents judged as similar documents is significantly reduced from 22 to 9 compared with the conventional method of utilizing only the similarity in the probabilistic model of Iwayama et al., so that the retrieval performance is considerably improved.

[0037] As described, the present invention carries out the retrieval by judging similar documents by combining both the similarity in the probabilistic model of Iwayama et al. and the similarity in the multinomial distribution model. Note that the above described combined threshold line 200 of y=−0.00055x−1.7 is called a linear discriminant function.

[0038] Next, with reference to FIG. 4, the processing procedure for the similar document retrieval method of the first embodiment based on the above principle will be described.

[0039] In the processing of FIG. 4, a reference document and a plurality of retrieval target documents are entered (steps S11, S13) in order to retrieval documents similar to the reference document from the plurality of retrieval target documents. Then, the similarity of each one of the plurality of retrieval target documents with respect to the entered reference document is calculated by the similarity calculation utilizing the probabilistic model of Iwayama et al. and the similarity calculation utilizing the multinomial distribution model as described above (step S15).

[0040] In this similarity calculation of the step S15, the similarity P_i(c|d_x) of the retrieval target document c with respect to the reference document d_xis calculated in the similarity calculation utilizing the probabilistic model of Iwayama et al. as follows.

P_{i} (c | d_{x}) = P (c) \sum_{t} \frac{P (t | c) P (t | d_{x})}{P (t)}

[0041] where:

[0042] P(t|d_x): An appearance probability of a term t in d_x,

[0043] P(t|c): An appearance probability of a term t in c,

[0044] P(t): An appearance probability of a term t in all retrieval target documents, and

[0045] P(c): A probability for d_xto be contained in documents to be used as c (which will be set equal to 1 in the following).

[0046] Also, the similarity P_m(c|d_x) of the retrieval target document c with respect to the reference document d_xis calculated in the similarity calculation utilizing the multinomial distribution model as follows.

\begin{matrix} P_{m} (c | d_{x}) = {}_{N}C_{n (t1)} \times {}_{N - n (t1)}C_{n (t2)} \times \dots \times {P (t_{1} | c)}^{n (t1)} \times {P (t_{2} | c)}^{n (t2)} \times \dots \\ = \frac{N_{x}!}{n_{x} (t_{1})! \times n_{x} (t_{2})! \times \dots \times {P (t_{1} | c)}^{n (t1)} \times \dots} \end{matrix}

[0047] where:

[0048] N_x: A sum of the number of appearances of all terms in d_x, and

[0049] n_x(t_i): The number of appearances of a term t_iin d_x.

[0050] Also, both in the probabilistic model of Iwayama et al. and the multinomial distribution model, regardless of how P(c|d_x) is calculated, the similarity Sim(d_x, d_y) between a document d_xand a document d_yis calculated as follows.

Sim (d_{x}, d_{y}) = \frac{P ({d_{x}, d_{y}} | d_{x}) \cdot P ({d_{x}, d_{y}} | d_{y})}{P ({d_{x}} | d_{x}) \cdot P ({d_{y}} | d_{y})}

[0051] This gives the posterior probability by which the document d_xand the document d_yare correct when a cluster (document set) obtained by merging the document d_xand the document d_yis retrieved.

[0052] Next, each one of a plurality of similarities P_i(c|d_x) according to the probabilistic model of Iwayama et al. and a plurality of similarities P_m(c|d_x) according to the multinomial distribution model calculated at the step S15 is normalized (step S17), because they use different measures.

[0053] Then, the linear discrimination is carried out as a discrimination analysis with respect to these normalized similarities P_i(c|d_x) according to the probabilistic model of Iwayama et al. and normalized similarities P_m(c|d_x) according to the multinomial distribution model (step S19). This linear discrimination is carried out using the linear discriminant function y=−0.00055x−1.7 of the combined threshold line 200 described above, for example. Namely, in the linear discrimination utilizing this linear discriminant function y=−0.00055x−1.7, the retrieval target document c having the similarities P_i(c|d_x) and P_m(c|d_x) above the linear discriminant function y=−0.00055x−1.7 in the distribution shown in FIG. 3 will be judges as dissimilar to the reference document d_x(step S21).

[0054] Next, with reference to FIG. 5, the processing for calculating the linear discriminant function utilized in the linear discrimination as the discrimination analysis of the step S19 in the processing of FIG. 1 will be described. This calculation of the linear discrimination function is carried out by the learning.

[0055] In the learning processing of FIG. 2, learning data are entered first (step S31). In this learning data input, the similarity according to the probabilistic model of Iwayama et al. and the similarity according to the multinomial distribution model of each one of the similar documents that are known to be similar to the reference document and the dissimilar documents that are known to be dissimilar to the reference document are entered as the learning data.

[0056] Then, these entered learning data are normalized (step S33), and the learning of the linear discriminant function using these normalized learning data is carried out (step S35) to calculate the linear discriminant function (step S37). The linear discriminant function so calculated is y=−0.00055x−1.7 described above, for example, and the linear discrimination at the step S19 of FIG. 1 is carried out using such a linear discriminant function.

[0057] Note that the first embodiment has been described for the case where the linear discrimination is used as the discrimination analysis, but the discrimination analysis is not necessarily limited to this case, and can be also realized by utilizing a neural network, a vector quantization, or a learning vector quantization (LVQ), for example.

[0058] Also, the first embodiment has been described for the case of carrying out the retrieval processing by combining two different similarities according to the probabilistic model of Iwayama et al. and the multinomial distribution model, but more than two different similarities can be combined if desired. Also, the similarity calculation is not necessarily limited to that utilizing the probabilistic model of Iwayama et al. and the multinomial distribution model, and any other model that can calculate the similarity can be used, but the probabilistic model of Iwayama et al. is currently regarded as having the best performance so that it is preferable to use this model.

[0059] Referring now to FIG. 6, the second embodiment of a similar document retrieval method according to the present invention will be described in detail.

[0060] In the case of extracting the similar documents with respect to a document given as a retrieval request from the retrieval target documents, the similarity is calculated using the discriminant function in the first embodiment. However, in practice, the similarity distribution may vary in a sophisticated way for each retrieval request, so that the discriminant function used in judging the similar documents may become inappropriate depending on the retrieval request. Namely, the discriminant function for discriminating relevant documents and non-relevant documents in the similar document retrieval can be different for different retrieval request documents.

[0061] For this reason, in the second embodiment, a distribution of the similarities (feature quantities) with respect to a given retrieval request is obtained by a pilot search once, then a linear transformation is applied to this distribution in such a way that the similarity distribution resembles the standard distribution model as much as possible, and then an optimal discriminant function with respect to the standard model is applied to the similarity distribution after this linear transformation.

[0062] More specifically, in the second embodiment, the following quantities are defined as a preparation.

[0063] Standard models: M₁, M₂, . . .

[0064] Retrieval request document set used in M_i: Q=[q₁, q₂, . . . , q_m}

[0065] Retrieval target documents: D={d₁, d₂, . . . , d_N}

[0066] Similarity measures: X, Y, Z, . . .

[0067] Similarity between q_iand d_jusing similarity measures X, Y . . . : SimX(q_i,d_j), SimY(q_i,d_j), . . . which will be denoted hereafter as: X_i,j=SimX(q_i,d_j), Y_i,j=SimY(q_i,d_j)≡Y_i,j, etc.

\underset{(in the two-dimensional case)}{Transformation matrix for q :} T (q) = (\begin{matrix} a_{q} & b_{q} & c_{q} \\ d_{q} & e_{q} & f_{q} \end{matrix})

[0068] Optimal transformation matrix for q: {overscore (T(q))}

[0069] Similarity distribution in original space: (q_i)={(X_i,1,Y_i,1), (X_i,2,Y_i,2), . . . }

[0070] Similarity distribution in transformed space: ′(q_i)={X′_i,1,Y′_i,1), (X′_i,2,Y′_i,2), . . . }

where (\begin{matrix} X_{i, j}^{'} \\ Y_{i, j}^{'} \end{matrix}) = \overline{T (q_{i})} (\begin{matrix} \begin{matrix} X_{i, j} \\ Y_{i, j} \end{matrix} \\ 1 \end{matrix})

[0071] Reference vector set (execution result of SOM (Self-Organizing Map)): R={r₁, r₂, . . . }

[0072] Then, the standard models are produced. In this standard model production, the standard models M_i(i=1, 2, . . . ) are repeatedly produced by the following procedure.

[0073] (1) ′=φ

[0074] (2) Repeat the following for q_j(j=1, 2, . . . ).

[0075] 1. Go to 7, if j≠1.

2. \overline{T (q_{1})} = (\begin{matrix} \frac{1}{σ_{X} (q_{1})} & 0 & \frac{μ_{X} (q_{1})}{σ_{X} (q_{1})} \\ 0 & \frac{1}{σ_{Y} (q_{1})} & \frac{μ_{Y} (q_{1})}{σ_{X} (q_{1})} \end{matrix})

[0076] 3. Obtain ′(q₁) by:

(\begin{matrix} X_{1, k}^{'} \\ Y_{1, k}^{'} \end{matrix}) = \overline{T (q_{1})} (\begin{matrix} \begin{matrix} X_{1, k} \\ Y_{1, k} \end{matrix} \\ 1 \end{matrix}) (1 ≦ k ≦ N)

[0077] 4. =′(q₁)

[0078] 5. Obtain the reference vector set R_iby executing SOM with respect to .

[0079] 6. Return to 1.

[0080] 7. Optimize R_jby using T(q_j).

[0081] 8. Obtain ′(q_j) by:

(\begin{matrix} X_{j, k}^{'} \\ Y_{j, k}^{'} \end{matrix}) = \overline{T (q_{j})} (\begin{matrix} \begin{matrix} X_{j, k} \\ Y_{j, k} \end{matrix} \\ 1 \end{matrix}) (1 ≦ k ≦ N)

[0082] 9. =+′(q_j)

[0083] 10. Obtain the reference vector set R_iby executing SOM (self-Organizing Map) with respect to .

[0084] 11. Return to 1.

[0085] After the standard models are produced as in the above, the following processing is carried out with respect to a new retrieval request (q).

[0086] (1) The pilot search with respect to the retrieval target document set D={d₁, d₂, . . . , d_N} is carried out using the retrieval request document q, so as to obtain X_q,1, X_q,2, . . . , X_q,N; Y_q,1, Y_q,2, . . . , Y_q,N.

[0087] (2) The optimal transformation matrix in the case of using the reference vector of each model is obtained, and set the optimal transformation matrix for a model with the smallest distortion as the optical transformation matrix T(q).

[0088] (3) ′(q) is obtained by:

(\begin{matrix} X_{q, i}^{'} \\ Y_{q, i}^{'} \end{matrix}) = \overline{T (q)} (\begin{matrix} \begin{matrix} X_{q, i} \\ Y_{q, i} \end{matrix} \\ 1 \end{matrix}) (1 ≦ i ≦ N)

[0089] (4) Documents of the retrieval target document set are ranked according to the discrimination function of the model with the smallest distortion and ′(q)

[0090] Namely, in the similar document retrieval method of the second embodiment, when two different similarity calculation methods are to be utilized, for example, one retrieval request q for which the similarity distribution is standard is determined first, and the similarity between this retrieval request q and each one of the retrieval target documents d1, d2, . . . is separately calculated using each similarity calculation method. The similarities between the retrieval request q and the retrieval target document d_iobtained by respective methods are denoted as X(q, d_i) and Y(q, d_i). At this point, the similarity distribution in the original space is expressed as described above.

[0091] This similarity distribution is transformed into the similarity distribution in the transformed space described above by using the transformation matrix T(q) described above with respect to each point (X_i, Y_i). This similarity distribution after the transformation will be denoted as ′(q).

[0092] In general, it is difficult to express ′(q) analytically, so that a set of reference vectors R={r₁, r₂, . . . } is obtained by applying the vector quantization method for expressing ′(q) discretely, and these reference vectors are used as parameters of the standard model.

[0093] With respect to a new retrieval request q, the similarity distribution (q) is obtained by calculating the similarities with respect to all the retrieval target documents d1, d2, . . . for each similarity calculation method. Here, the transformation matrix T(q) is adjusted such that the similarity distribution (q) obtained by applying the transformation matrix T(q) to the obtained similarity distribution will resemble the standard distribution ′(q) as much as possible.

[0094] Next, FIG. 6 shows a table summarizing the result of average precision obtained for various cases of using the similarity according to the probabilistic model of Iwayama et al. (denoted as simI) and the similarity according to the multinomial distribution model (denoted as simM) either singly or in combination.

[0095] In FIG. 6, there are three cases of combining simI and simM, in which the content of the normalization processing is different, including (1) the case where a standard transformation using mean and variance for all retrieval requests as axes is applied to each retrieval request (where the same transformation is carried out for all the retrieval requests), (2) the case where a standard linear transformation is applied to each axis independently according to mean and variance for each retrieval request, and (3) the case where the optimal linear transformation is applied for each retrieval request.

[0096] It can be seen from FIG. 6 that the precision in the case of not carrying out the adaptation for each retrieval request (the case of simI+simM (each axis independent, same transformation) in FIG. 6) can be lower than the precision in the case of using only the similarity according to the probabilistic model of Iwayana et al. (the case of simI in FIG. 6). However, the average precision is improved both in the case of applying the standard linear transformation to each axis independently according to mean and variance for each retrieval request (the case of simI+simM (each axis independent, for each retrieval request) in FIG. 6) and the case of applying the optimal linear transformation for each retrieval request (the case of simI+simM (distortion minimized) in FIG. 6).

[0097] This implies that the retrieval precision can be improved by carrying out the linear transformation with respect to the similarity distribution in such a way that the similarity distribution resembles the standard model as much as possible, at a time of normalizing the feature quantities.

[0098] Referring now to FIG. 7 to FIG. 11, the third embodiment directed to a case of applying the similar document retrieval method of the present invention to a mail magazine service will be described in detail, as an example of a recommended article notification service system utilizing the similar document retrieval method of the present invention.

[0099] In this mail magazine service, Web based free mail accounts for mail magazine readers are provided, and mails containing titles or the like of recommended articles customized to individual registered users are delivered for the convenience of readers and the added value of the mail magazine service provider.

[0100] This mail magazine service is realized by carrying out the initial profile acquisition, the user profile management, the selection of articles to be used as contents of mails to be delivered, the display layout of contents to be delivered, and the display of the selected articles, as follows.

[0101] (a) Initial Profile Acquisition

[0102] When a reader makes a user registration for free mails, an initial profile is acquired from the user's selection of preferred article genres or topics of interest from menu/headlines presented to the user based on user's answers to an accompanying questionnaire.

[0103] (b) User Profile Management

[0104] After the mail delivery based on the initial profile, the user profile is updated whenever necessary according to the feedback information from the user as described below.

[0105] (c) Selection of Articles to be Contents of Mails to be Delivered

[0106] Articles to be recommended to each user are selected according the user profile, by using the similar document retrieval method of the present invention, in order to rank the articles to be recommended to each user by accounting for the profile information, newly arrived important articles, etc.

[0107] (d) Display Layout of Contents to be Delivered

[0108] A display layout of a Web mail containing titles of the articles to be recommended to individual user is as shown in FIG. 7, for example, where a list of articles similar to the News Update column of the top page is displayed, and special marks are attached to the recommended articles customized to individual user. The preference of the user at a time of the registration may be utilized in arranging genres.

[0109] Another exemplary display layout of contents to be delivered is as shown in FIG. 8, where (at most N sets of) titles of the recommended news for each user can be displayed in an order of their ranks determined in relation to the profile, in addition to headlines of the top news at a time of delivery.

[0110] The display layout shown in FIG. 7 requires a clever layout but it can notify other newly arrived articles as well. Also, the display layout of FIG. 8 can present the displayed contents in a neat, easy-to-read format. In either case, a result of selection including the recommended articles can be reflected into the user profile.

[0111] (e) Display of Selected Articles

[0112] A body of an article selected by the user on the display of (d) above will be displayed as shown in FIG. 9, for example.

[0113] Note that, in FIG. 9, there is provided a button for confirming addition to the profile. This may make the operation tedious, but it can make the feedback information from the user more accurate and definite. Also, as shown in a right hand side column of FIG. 9, it is also possible to display links to related articles (that are similar in contents). However, such an option presupposes a display screen to be generated separately from an ordinary article display screen.

[0114] Next, the mail magazine service system for realizing this mail magazine service will be described.

[0115] This mail magazine service requires the following features to the mail magazine service system.

[0116] (1) A mail server for providing the free account service and an application server for this mail magazine service should be provided and operated separately.

[0117] (2) No coordination with the user management by the mail server is to be incorporated. However, (a copy of) the same user information as used in the mail server is to be regularly updated also in the application server.

[0118] (3) It should be possible to acquire contents such as newly arrived articles regularly even on the application server.

[0119] (4) In the case of allowing a user to select the number of times and timings of the mail forwarding, a server configuration that can account for load balancing should be adopted.

[0120] FIG. 10 shows an exemplary basic configuration of the mail magazine service system in this embodiment. This mail service service system 100 comprises an application server 200, a mail server 300, and a WWW server 400.

[0121] The application server 200 contains article data 201, article data backup 202, a past article database 203, a latest article database 204, and a past article cluster database 205, and obtains the retrieval result 206 with respect to the article data 201 acquired from original article data 601 in an article providing WWW server 600.

[0122] The mail server 300 contains a user profile cluster database 301, and forwards mails containing forwarding data 302 to a Mailbox 501 of a free mail server 500.

[0123] The WWW server 400 contains a user database 401 according to user accounts 502 of the free mail server 500, and an access log 402.

[0124] A user terminal 700 is connected to the WWW server 400 at a time of subscription to the mail service, at a time of registration of articles of interest, and at a time of access to headlines. The user terminal 700 is connected to the free mail server 500 at a time of user account acquisition and at a time of access to the Mailbox 501. The user terminal 700 is connected to the article providing WWW server 600 at a time of access to individual articles.

[0125] FIG. 11 shows an exemplary module configuration in the case of forming the mail magazine service system of FIG. 10 by using a group of programs, including an article data classification program 801, an article data backup program 802, a user information generation program 803, a feedback program 804, a user interface program 805, an article database generation program 806, a cluster generation program 807, a cluster retrieval program 808, a retrieval program 809, a retrieval result list generation program 810, and a retrieval result forwarding program 811.

[0126] The article data classification program 801 classifies the original article data 601 into directories according to date, genre, etc., to obtain the article data 201.

[0127] The article data backup program 802 carries out compression and backup of the article data to obtain the article data backup 202.

[0128] The user information generation program 803 generates a user list and carries out the registration and the retrieval of associated information, according to the user database 401.

[0129] The feedback program 804 provides a feedback from the access log 402 to the user profile cluster database 301.

[0130] The user interface program 805 carries out authentication, registration, deletion, and data look up by using the access log 402, the user database 401, and the retrieval result 206.

[0131] The article database generation program 806 generates the latest article database 204 and the past article database 203 from the article data 201.

[0132] The cluster generation program 807 generates the past article cluster database 205 from the past article database 203.

[0133] The cluster retrieval program 808 carries out the retrieval of past articles from the past article cluster database 205 by using the user profile cluster database 301.

[0134] The retrieval program 809 carries out the similar document retrieval according to the present invention, using the latest article database 204 and the user profile cluster database 301.

[0135] The retrieval result list generation program 810 carries out the HTML formatting and the mail creation for the retrieval result 206 obtained by the cluster retrieval program 808 or the retrieval program 809.

[0136] The retrieval result forwarding program 811 carries out the mail forwarding for the retrieval result 206 obtained by the retrieval result list generation program 810, by using the user database 401.

[0137] In these configurations, a user who wishes to use free mails acquires an account from the mail server. Among the users who acquired accounts, those users who also wish to use the mail service as an option (the number of which is estimated to be about 1,000) also register profiles such as articles of interest.

[0138] The system regularly acquires new articles, retrieves articles in accordance with the user profile, and transfers the retrieval result to the mail server. The user can make an access to the mail server whenever convenient to the user, and refer to the contents in the Mailbox.

[0139] The service mail contains headlines in the HTML format, where each article provides a link to the article providing WWW server. The user can add any favorite article to the profile, The access log with respect to articles is managed at the system side.

[0140] As described above, according to the present invention, the similar documents of the reference document are extracted by calculating the similarity of each one of a plurality of retrieval target documents with respect to a reference document using each one of two or more similarity calculation methods separately, and carrying out the discrimination analysis with respect to a plurality of similarities that are separately calculated by using these two or more similarity calculation methods, so that it is possible to improve the retrieval precision considerably, compared with the conventional similar document retrieval method utilizing only the probabilistic model of Iwayama et al., for example, in which it has been difficult to achieve a sufficient retrieval precision.

[0141] In addition, according to the present invention, the similarity calculation method according to the probabilistic model of Iwayama et al. and the similarity calculation method according to the multinomial distribution model are combined, so that it is possible to improve the retrieval precision considerably, compared with the conventional similar document retrieval method utilizing only the probabilistic model of Iwayama et al., for example, in which it has been difficult to achieve a sufficient retrieval precision.

[0142] Moreover, according to the present invention, similarities calculated for the similar documents and the dissimilar documents by each similarity calculation method are entered as learning data, the discrimination analysis is learned using these learning data, and the discrimination analysis is carried out using a discriminant function obtained by this learning, so that it is possible to carry out the discrimination analysis in good precision.

[0143] Furthermore, according to the present invention, similarities calculated for the similar documents and the dissimilar documents by different similarity calculation methods are entered as learning data, the linear discrimination analysis is learned using these learning data, and the discrimination analysis is carried out using a linear discriminant function obtained by this learning, so that it is possible to carry out the discrimination analysis in good precision.

[0144] In addition, according to the present invention, the relevancy of the document is judged after applying the linear transformation for making the similarity distribution resemble the standard model as much as possible, for each retrieval request, so that it is possible to apply the optimal linear transformation for each retrieval request and classify relevant documents and non-relevant documents accurately even when the similarity distribution varies in a sophisticated manner for each retrieval request, and therefore it is possible to improve the retrieval precision.

[0145] Also, according to the present invention, recommended articles in accordance with the profile of each user are selected from many articles, and information containing these selected recommended articles is delivered through the Internet and presented to the user, while the user profile is updated according to the selection information returned from the user as a result of user selection made on the presentation, so that articles interesting to the user will be delivered to the user and therefore the user can view the information of interest without a failure, and even when the user's interest changes, it is always possible to present appropriate information to the user according to this change.

[0146] It is to be noted that, besides those already mentioned above, many modifications and variations of the above embodiments may be made without departing from the novel and advantageous features of the present invention. Accordingly, all such modifications and variations are intended to be included within the scope of the appended claims.

Claims

What is claimed is:

1. A similar document retrieval method for retrieving similar documents of a reference document from a plurality of retrieval target documents, comprising the steps of:

calculating similarities of each one of the plurality of retrieval target documents with respect to the reference document by using each one of two or more similarity calculation methods separately, the two or more similarity calculation methods including a first similarity calculation method for calculating a similarity according to a probabilistic model in which a similarity with respect to a retrieval target document is expressed by a ratio of a relevant document probability and a non-relevant document probability with respect to a retrieval request, and a second similarity calculation method according to a multinomial distribution model;

retrieving the similar documents of the reference document by carrying out a discrimination analysis with respect to each one of a plurality of similarities calculated by using each one of the two or more similarity calculation methods separately.

2. A method for providing a recommended article notification service for delivering mails describing recommended articles to users through Internet, comprising:

generating a profile for each user;

selecting the recommended articles from a plurality of articles in accordance with the profile of each user, by utilizing a similar document retrieval method, where the similar document retrieval method retrieves the recommended articles by calculating similarities of each one of the plurality of articles with respect to the profile of each user by using each one of two or more similarity calculation methods separately, and carrying out a discrimination analysis with respect to each one of the plurality of similarities calculated by using each one of the two or more similarity calculation methods separately, the two or more similarity calculation methods including a first similarity calculation method for calculating a similarity according to a probabilistic model in which a similarity with respect to a retrieval target document is expressed by a ratio of a relevant document probability and a non-relevant document probability with respect to a retrieval request, and a second similarity calculation method for calculating a similarity according to a multinomial distribution model; and

delivering a Web mail containing information of the recommended articles to each user through the Internet.

3. The similar document retrieval method of claim 1, wherein the discrimination analysis is carried out by using a discriminant function which is obtained by a learning using similarities of each one of known similar documents and known dissimilar documents with respect to the reference document calculated by using each one of the two or more similarity calculation methods separately as learning data.

4. The similar document retrieval method of claim 1, wherein the discrimination analysis uses a linear discriminant function.

5. The similar document retrieval method of claim 4, wherein the linear discriminant function is obtained by a learning using similarities of each one of known similar documents and known dissimilar documents with respect to the reference document calculated by using each one of the two or more similarity calculation methods separately as learning data.

6. The similar document retrieval method of claim 1, wherein the retrieving step retrieves the similar documents of the reference document by applying a linear transformation on a distribution of the similarities calculated by the calculating step for each retrieval request such that the distribution of the similarities after the linear transformation resembles a standard model as much as possible, at a time of normalizing feature quantities given by the similarities calculated by the calculating step, and carrying out the discrimination analysis for discriminating relevant documents and non-relevant documents on a space defined by the feature quantities after the linear transformation.

7. A recommended article notification service system for delivering mails describing recommended articles to users through Internet, comprising:

a profile generation unit configured to generate a profile of each user;

a recommended article selection unit configured to select the recommended articles from a plurality of articles in accordance with the profile of each user, by utilizing a similar document retrieval method, where the similar document retrieval method retrieves the recommended articles by calculating similarities of each one of the plurality of articles with respect to the profile of each user by using each one of two or more similarity calculation methods separately, and carrying out a discrimination analysis with respect to each one of a plurality of similarities calculated by using each one of the two or more similarity calculation methods separately, the two or more similarity calculation methods including a first similarity calculation method for calculating a similarity according to a probabilistic model in which a similarity with respect to a retrieval target document is expressed by a ratio of a relevant document probability and a non-relevant document probability with respect to a retrieval request, and a second similarity calculation method for calculating a similarity according to a multinomial distribution model; and

a delivery unit configured to deliver a Web mail containing information of the recommended articles to each user through the Internet.

8. The recommended article notification service system of claim 7, further comprising:

a profile update unit configured to update the profile of each user according to a selection information returned from each user as a result of each user's selection made upon presenting the information of the recommended articles to each user.

9. The recommended article notification service system of claim 8, wherein the profile generation unit generates an initial profile of each user according to information on each user's preferred article genres and topics of interest that is acquired from each user, and the profile update unit updates the initial profile of each user whenever necessary such that the profile of each user is always maintained in a state suitable for each user.

Patent Citations (10)

Patent	Date	Inventor	Cited By
US5023912	1991-06-01	Segawa	Examiner
US5550928	1996-08-01	Lu et al.	Examiner
US5625748	1997-04-01	McDonough et al.	Examiner
US5689584	1997-11-01	Kobayashi	Examiner
US5781663	1998-07-01	Sakaguchi et al.	Examiner
US5812998	1998-09-01	Tsutumi et al.	Examiner
US5907836	1999-05-01	Sumita et al.	Examiner
US5977964	1999-11-01	Williams et al.	Examiner
US5999893	1999-12-01	Lynch, Jr. et al.	Examiner
US6157921	2000-12-01	Barnhill	Examiner

Non-Patent Literature (5)

Schroder et al “Interctive Learning and Probabilistic Retrieval in Remote Sensing Image Achives”, IEEE 2000, pp. 2288-2298.Applicant
Vasconcelos et al “A Bayesian Framework for Semantic Content Characterization”, IEEE 1998, pp. 566-571.Applicant
Leistensnider et al “A Simple Probabilistic Approach to Classification and Routing”, IEEE 1997, pp. 750-754.Applicant
“Hierarchical Bayesian Clustering for Automatic Text Classification”, Iwayama, Makoto and Tokunaga, Takenobu, Proceedings of IJCAI-95, pp. 1322-1327, 1995.Applicant
Leistensnider et al “A simple probabilistic approach to classification and routing”, IEEE 1997, pp. 750-754.Examiner

Abstract