JP5530469B2 - Natural language analysis processing apparatus, method, and program - Google Patents

Description

  The present invention relates to a natural language analysis processing device, method, and program, and more particularly, to a natural language analysis processing device, method, and program for performing natural language analysis processing including a plurality of stages of language analysis processing on an input document.

  Natural language is a language normally used by humans, such as Japanese and English. A technique for grammatically and semantically analyzing a document described in a natural language has an academic significance from a linguistic viewpoint, for example, to understand the origin and structure of the language. In recent years, various services have been developed mainly on the web that automatically analyze grammatically and semantically documents generated by humans and use the results. For example, services such as a translation site, a reputation analysis site for people and products, and a summary site for a specific event correspond to this. In these services, digitized documents generated by humans are grammatically and semantically analyzed in the system, and the actual services are provided by using them. In this sense, grammatical and semantic analysis of natural language is the core technology of these services, and has come to occupy a very important position in the information processing field.

  Natural language analysis includes everything from surface analysis such as word breaks and part-of-speech estimation to more advanced analysis such as estimation of dependency relationships between words and clauses. For example, there are “sentence breaks” that estimate sentence breaks from documents, “word breaks” that estimate word breaks, part-of-speech assignment that estimates word part-of-speech, and dependency analysis that estimates the relationship between words and clauses. . Examples of these are shown in FIG.

  Language analysis problems such as part-of-speech assignment and dependency analysis are classified as problems with “interdependence”. This is because, for example, in the problem of determining the part of speech of a word, when determining the part of speech of a word, there is a relationship in which the part of speech to be given to the target word is determined by the surrounding parts of speech and the surrounding parts of speech. And surrounding parts of speech are also problems that depend on the part of speech before and after that. If there is a rule that part of speech B should not appear after a part of speech A, there is no guarantee that a result satisfying this rule will be obtained if the part of speech of each word is estimated independently. In other words, when the part-of-speech of individual words is estimated independently, it is not always possible to obtain such consistency as a whole. In particular, considering problems such as sentence breaks, word breaks, part-of-speech estimation, and dependency analysis in a batch, the problem of searching for the best output is very difficult because it is a very complicated problem. It can be said that it is a problem.

  In order to solve these problems, a method of estimating an output using an algorithm such as history-based sequential analysis (so-called stack decoding), dynamic programming, integer programming, etc. is widely used (Non-Patent Document 1). -Non-patent document 3).

  The history-based sequential analysis method is a method for performing the next estimation using the estimation results obtained immediately before (see FIG. 9). Compared with the method of solving the problem independently, the output consistency can be maintained. However, since this is a method of determining the next analysis result by believing in the previous analysis result, if there is an error in the previous analysis result, the analysis will continue according to the error, and the propagation of the error will continue. The problem of happening is known.

  As a method for solving this problem, a method based on dynamic programming (see FIG. 10) and a method based on integer programming have come to be used. Since this is a method for selecting the best output as a whole, there is no problem of an analysis error in the middle compared to the history-based sequential analysis method. On the other hand, the amount of calculation for selecting the best output as a whole has a drawback that it is very large compared to the sequential analysis method.

Joakim Nivre. Algorithms for deterministic incremental dependency parsing.Computational Linguistics, 2008. F. Sha and F. Pereira. Shallow Parsing with Conditional Random Fields. Proc. Of HLT / NAACL, 2003. Dan Roth, Wen-tau Yih Global Inference for Entity and Relation Identification via a Linear Programming Formulation Introduction to Statistical Relational Learning, 2007.

  For example, a system is assumed in which a word break, phrase break, sentence break, part of speech assignment (dictionary lookup), and inter-phrase dependency relation assignment are collectively applied to a Japanese document. As a service that uses the grammatical and semantic analysis results of such documents, a site that analyzes the reputation of people and products on the web, a translation site, etc. can be considered.

  In such a system, it is usually complicated to perform all processing at once, so conventionally, 1, sentence break, 2, word break + part of speech assignment (commonly called morphological analysis), 3, phrase break, 4 The process is applied step by step in the order of dependency analysis. That is, the process at each stage receives the process result of the previous stage as input and performs the process. Such a sequential processing method is generally called a “pipeline method”. Therefore, here again, the conventional method of handling each stage of processing as an input of the next stage of processing is called a “pipeline method”. The pipeline method has a problem that when there is an error in the processing result of the previous stage, there is no framework for correcting the error, and therefore error propagation is likely to occur because the error causes a later analysis. In addition, it is difficult to operate an analysis system in consideration of information that can be used across stages of processing. Actually, it is often possible to improve the analysis accuracy by using such complex information, so it is considered a drawback of the pipeline method. These are the same causes as the disadvantages found in history-based sequential analysis in one stage.

  In other words, even if global optimization methods such as dynamic programming and integer programming are used for processing at each stage, after all the same disadvantages as the history-based sequential analysis method in terms of pipeline processing. Will occur.

  Of course, it is possible to apply a method of performing overall optimization such as dynamic programming or integer programming to a system that performs such a plurality of analyzes simultaneously. However, the calculation amount becomes too large, and it is difficult to apply as it is in practice.

  The present invention has been made in view of the above circumstances, and provides a natural language analysis processing apparatus, method, and program capable of accurately performing natural language analysis processing while suppressing an increase in the amount of calculation. Objective.

In order to achieve the above object, a natural language analysis processing apparatus according to a first invention performs a natural language analysis process including a plurality of types of natural language analysis processes on an input document including at least one sentence. In each of the plurality of types of natural language analysis processes, the problem of performing the natural language analysis process on the input document is a problem of units greater than or equal to a character unit previously defined for the natural language analysis process. Sub-problem generating means for decomposing into sub-problems and generating the set of sub-problems, S (N is a natural number of 2 or more) calculation nodes for performing the natural language analysis processing, and the partial problem generating means For the set of subproblems generated by the above, each subproblem is composed of an arbitrary subset for the whole set of subproblems so that they belong to at least two groups Creating S groups and assigning them to the S computation nodes, wherein each of the S computation nodes is for the sub-problem of the group assigned by the group creation means. A partial decomposition updating means for updating a solution of each partial problem of the subset based on a constraint condition in which the solutions of the partial problems belonging to the two or more groups match with respect to the subset of the entire set; and the partial decomposition update Synchronizing means for notifying other sub-problems solutions of the sub-set updated by the means to other computing nodes, and obtaining the solutions of the sub-problems of the sub-set notified from the other computing nodes; Solution of each partial problem of the subset of the other computation node acquired by the synchronization means, and each part of the subset updated by the partial decomposition update means Based on the solution of the problem, for each subproblem, the constraint condition update means for updating the constraint parameter that is a solution when matching the solution of the subproblem according to the constraint condition, and the value of the constraint parameter converges Until it is determined whether or not the value of the constraint parameter has converged, and the convergence determination that repeats the update by the partial update means, the notification and acquisition by the synchronization means, and the update by the constraint condition update means Means.

A natural language analysis processing method according to a second invention includes a sub-problem generating means, S calculation nodes (S is a natural number of 2 or more), and a group creating means for an input document including at least one sentence. a natural language analysis processing method in natural language analysis processing apparatus for natural language analysis processing including a plurality of types of natural language analysis processing, by the partial problems generating means, for each of the natural language analysis processing of the plurality of types, wherein The problem of performing the natural language analysis processing on the input document is decomposed into sub-problems that are problems of units greater than or equal to a character unit predefined for the natural language analysis processing, and the set of the partial problems is generated, With respect to the set of partial problems generated by the partial problem generating means by the group creating means, each partial problem belongs to at least two or more groups. As described above, S groups composed of arbitrary subsets of the entire subset of the subproblems are created and assigned to the S computation nodes, and the natural language analysis processing is performed by the S computation nodes. And performing the natural language analysis processing by each of the S computation nodes is performed on the subset of the partial problem of the group assigned by the group creating unit by the partial decomposition updating unit. The solution of each partial problem of the subset is updated based on a constraint condition that the solutions of the partial problems belonging to two or more groups match, and the subset of the subset updated by the partial decomposition update means is synchronized by a synchronization means Not only the solution of each subproblem is notified to other computing nodes, but also the solution of each subproblem of the subset notified from the other computing node is obtained. A solution for each subproblem of the subset of the other computation node acquired by the synchronization means by the constraint condition updating means, and a solution for each subproblem of the subset updated by the partial decomposition update means, For each subproblem, update the constraint parameter that is a solution when matching the solution of the subproblem according to the constraint, and whether or not the value of the constraint parameter has converged by the convergence determination means Until the value of the constraint parameter is converged, the update by the partial decomposition update unit, the notification and acquisition by the synchronization unit, and the update by the constraint condition update unit are repeated.

As described above, according to the first and second inventions, the problem of performing a plurality of types of natural language analysis processing is divided into a set of subproblems to create a group, and subproblems belonging to two or more groups Based on the constraint conditions with which the solutions match, in each computation node, the solution is updated for a subset of the assigned subproblem, and the constraint parameter is updated using the solution of the subproblem obtained from another computation node. By repeating this until convergence, an increase in the amount of calculation can be suppressed and natural language analysis processing can be performed with high accuracy.

A natural language analysis processing apparatus according to a third invention is a natural language analysis processing apparatus that performs a natural language analysis process including a plurality of types of natural language analysis processes on an input document including at least one sentence, the plurality of types of for each of the natural language analysis processing, the problem of performing natural language analysis processing, and decompose the subproblem a predefined character units or more units problem for the natural language analysis processing on the input document, the A sub-problem generating means for generating a set of sub-problems, S calculation nodes (S is a natural number of 2 or more) for performing the natural language analysis process, and the sub-problem generated by the sub-problem generating means Create S groups of arbitrary subsets for the entire set of subproblems so that each subproblem belongs to at least two groups. Group creating means for assigning to the S computing nodes, constraint condition updating means, and convergence judging means, each of the S computing nodes being the portion of the group assigned by the group creating means Partial decomposition updating means for updating a solution of each subproblem of the subset based on a constraint condition that the solutions of the subproblems belonging to the two or more groups match with respect to a subset of the whole set of problems. The constraint condition update means matches the solutions of the subproblems according to the constraint conditions for each partial problem based on the solutions of the partial problems of the subset updated by the partial decomposition update means of each computation node. Updating the constraint parameter, which is a solution when performing the determination, the convergence determination means determines whether or not the value of the constraint parameter has converged, To a value of approximately condition parameter is determined to have converged, updating by the portion degradation updating means of each computing node, and repeating the updating by the constraint condition update unit.

A natural language analysis processing method according to a fourth invention includes a sub-problem generating means, S calculation nodes (S is a natural number of 2 or more), a group creating means, a constraint condition updating means, and a convergence determining means, A natural language analysis processing method in a natural language analysis processing apparatus for performing natural language analysis processing including a plurality of types of natural language analysis processing on an input document including at least one sentence, wherein the plurality of types for each of the natural language analysis processing, the problem of performing natural language analysis processing, and decompose the subproblem a predefined character units or more units problem for the natural language analysis processing on the input document, the A set of subproblems is generated, and each subproblem is generated for the set of subproblems generated by the subproblem generating means by the group creating means. Create S groups composed of arbitrary subsets for the entire set of subproblems so as to belong to at least two groups and assign them to the S computation nodes, and by the S computation nodes, Performing the natural language analysis process, updating by the constraint condition updating unit, and determining by the convergence determination unit, and performing the natural language analysis process by each of the S computation nodes includes partial decomposition update Means for a subset of the subset assigned to the group by the group creation means based on a constraint condition that the solutions of the subproblems belonging to the two or more groups match. Updating the solution of each subproblem, wherein the constraint condition updating means is connected to the partial decomposition updating means of each computation node. Based on the solution of each subproblem of the subset updated in this way, for each subproblem, update the constraint parameter, which is a solution when matching the solution of the subproblem according to the constraint, and determine the convergence The means determines whether or not the value of the constraint parameter has converged, and updates by the partial decomposition update means for each calculation node until it is determined that the value of the constraint parameter has converged, and the constraint condition update Repeat update by means.

As described above, according to the third and fourth aspects of the present invention, the problem of performing a plurality of types of natural language analysis processing is decomposed into a set of subproblems to create a group, and subproblems belonging to two or more groups Based on the constraint conditions with which the solutions match, at each computation node, the solution is updated for a subset of the assigned subproblem, and the constraint parameter is updated using the subproblem solution updated at each computation node. By repeating this until convergence, an increase in the amount of calculation can be suppressed and natural language analysis processing can be performed with high accuracy.

  A program according to a fifth aspect is a program for causing a computer to function as each means of the natural language analysis processing apparatus.

  As described above, according to the natural language analysis processing device, method, and program of the present invention, it is possible to obtain an effect that natural language analysis processing can be performed with high accuracy while suppressing an increase in calculation amount.

It is a figure for demonstrating the method to produce the group of a minimum subproblem. It is the schematic which shows the structure of the natural language analysis processing apparatus which concerns on the 1st Embodiment of this invention. It is a flowchart which shows the content of the natural language analysis processing routine in the calculation node of the natural language analysis processing apparatus which concerns on the 1st Embodiment of this invention. It is the schematic which shows the other example of a structure of the natural language analysis processing apparatus which concerns on the 1st Embodiment of this invention. It is the schematic which shows the structure of the natural language analysis processing system which concerns on the 3rd Embodiment of this invention. It is the schematic which shows the structure of the language analysis control apparatus which concerns on the 3rd Embodiment of this invention. It is the schematic which shows the structure of the language analyzer which concerns on the 3rd Embodiment of this invention. It is a figure which shows the example of word break, part-of-speech tagging, specific expression extraction, phrase break, and dependency between phrases. It is a figure which shows the history-based sequential analysis method in a prior art. It is a figure which shows the example of the analysis based on the dynamic programming in a prior art.

  Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.

[First Embodiment]
<Outline of the invention>
In the present invention, it is proposed in Non-Patent Document 4 (Andre FT Martins, Mario AT Figueiredo, Pedro MQ Aguiar, Noah A. Smith, Eric P. Xing An Augmented Lagrangian Approach to Constrained MAP Inference Proc. Of ICML, 2011.). The DD-ADMM method is used to address the issue of global optimization. DD-ADMM is a method of solving a large problem that you want to solve by dividing it into small subproblems. The point is that each divided problem can be solved independently of each other, and there is an advantage that calculation is relatively easy. At this time, when the problem is divided, an overlapping part is created in each problem, and the whole consistency is maintained by giving a restriction that the analysis results of the overlapping part must all match. This makes it possible to obtain a solution to a large problem that is actually desired to be solved by solving a set of divided sub-problems.

  As an example, a system is assumed that performs word break, phrase break, sentence break, part of speech assignment (dictionary lookup), and inter-phrase dependency relation assignment for an input document (Japanese). Conventionally, the processing at each stage, such as 1, sentence break, 2, word break + part-of-speech assignment (generally called morphological analysis), 3, clause break, 4, dependency analysis, etc. Receive as input. That is, processing is performed as follows.

・ Input: A document is input to the system ・ Process 1 [Input]: Receives the document input to the system ・ Process 1: Estimate sentence breaks for the input document ・ Process 1 [Output]: For the input document・ Process 2 [Input]: Receive the document output from Process 1 ・ Process 2: Estimate part of speech at the same time as word break ・ Process 2 [Output]: Sentence for input document Outputs a document with delimiters, word breaks, and parts of speech ・ Process 3 [Input]: Receives the document output from Process 2 ・ Process 3: Estimate phrase break ・ Process 3 [Output]: Sentence for input document Output a document with delimiters, word breaks, phrase breaks, and parts of speech ・ Process 4 [Input]: Receive the document output from Process 3 ・ Process 4: Estimate the dependency relationship between phrases ・ Process 4 [Output] : Sentence breaks, word breaks, phrase breaks, part of speech, and dependency relations between phrases for the input document・ Output: Outputs a document with sentence breaks, word breaks, phrase breaks, part of speech, and dependency relations between phrases for the input document.

  On the other hand, in the present invention, the five types of processing in the above example are performed in a single framework.

・ Input: A document is input to the system ・ Process [Input]: Receives a document input to the system ・ Process: Sentence delimiter, word delimiter, phrase delimiter, part of speech, and dependency relation between phrases are estimated collectively Process [Output]: Outputs a document with sentence breaks, word breaks, phrase breaks, part of speech, and dependency relations between phrases for the input document.Output: sentence breaks, word breaks, phrase breaks for input documents, Output a document with part-of-speech and sentence dependency

  As a feature of the present invention, there is a process of creating a group of several minimum sub-problems together for a pre-defined minimum sub-problem. The entire process is performed by repeating the process of determining the solution, there is a process that maintains the consistency of the results processed independently in each group, and when the solution of each group matches the final solution There is a process to obtain. These features are described below.

  First, in the conventional pipeline method, the optimization problem expressed by the following equation (1) is repeatedly solved.

The above expression (1) represents an optimization problem related to the i∈ {1,..., I} -th language analysis process when there are, for example, I stages in the natural language analysis process. At this time, let X _{i be} the input of the i-th language analysis processing problem, and Y _{i be} the output of the i-th language analysis processing problem. In the case of the pipeline method, it can be said that y _i-1 obtained by the _i− 1th language analysis processing is used as a part of the input x _i of the _ith language analysis processing.

  In the present invention, the minimum unit of processing is determined in advance as a basic idea. The minimum unit of processing corresponds to what can be defined as the smallest problem in defining a problem in each stage of processing, and is different for each stage and is a unit of character units or more. For example, in the case of word delimiters, the problem of estimating whether each character is delimited or not is the smallest problem unit. Similarly, in the case of clause breaks and sentence breaks, the problem of estimating whether each character becomes a clause or a sentence break can be considered as the smallest unit of the problem. In addition, if it is a problem of part-of-speech assignment, the problem of selecting a part-of-speech suitable for one character is the minimum unit. Since the problem of the minimum unit corresponds to the part of the problem to be solved, the problem of the minimum unit is referred to as “minimal subproblem”. Here, the index of the minimal subproblem is represented by r. Also, let R denote the set of indices for all the minimal subproblems. Therefore, the problem to be solved is composed of | R |

Next, considering one document as one input, word breaks and part-of-speech tagging are defined by a set of minimal subproblems. Therefore, the solution space of these problems is represented by a set Y of vectors. One output obtained when an input is given is represented by a vector z∈Y. Here, the solution of the minimal sub-problem corresponds to one element z _i of the vector.

  Next, in the present invention, a group is composed of several minimal subproblems, and the problem is expressed by a set of groups. At this time, each group can include the minimum subproblem in an overlapping manner. How to create a group is arbitrary, but it should satisfy the following two points. The first point is to form a group so as to cover the entire problem to be solved, and the second point is that each local subproblem belongs to a plurality of groups. Here, one created group is considered as one partial problem for the whole problem. Therefore, one group solves as one optimization problem. It should be noted that the subset of the minimal subproblems belonging to the group can include those relating to multiple stages of language analysis processing.

Here, it is assumed that S groups are created. Let Y _s be a subspace of the solution space included in the sth group. That is, Y _s ⊆Y. At this time, let z _s (r) be the solution of the rth minimal subproblem included in the sth group.

  An example of creating a group is shown in FIG.

Let R _s be the set of indices of the minimal subproblems included in the sth group. Next, R⊆∪ the ^{_{R s s = 1 S R '}} s, and, R _s = R' be the set to be _s .andgate.R. Although this is not a minimal subproblem, there is an auxiliary subproblem that is effective in solving the entire problem. That is, here, the index included in the set corresponding to R ′ _s \ R is not a minimal subproblem but corresponds to an index of an auxiliary subproblem effective in solving the problem.

For the output obtained in the sth group, let f _s be the function that calculates the goodness of the output. Here, the value calculated under the assumption that the larger the value of f _s (z _s ) is, the better the output is. At this time, the whole problem for performing the natural language analysis processing can be formulated as an optimization problem shown in the following equation (2).

Here, z _s is a set of solutions of the minimal subproblem included in the group s. Z is the total set of z _s (r). This optimization problem into S groups independently a problem of selecting the best a partial solution that seems at output z _s (r) for the minimum subproblem each group is responsible, partial solution of each group u This corresponds to solving as a constraint condition that it matches the vector of (r). The point of this formulation lies in the part of the constraint condition z _s (r) = u (r), and in each group s, the value of z _s (r) is all u ( This means that the condition for the solution is to match r). In other words, in each group, the solution z _s (r) is determined independently, but can be limited to a solution that can be consistent as a whole by the constraint condition z _s (r) = u (r). Using this constraint equation and Lagrangian relaxation, the objective function shown in the following equation (3) for optimization is obtained.

Next, it is described in Non-Patent Document 5 (Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning, 2011.) As shown, the augmented Lagrangian term P / 2 (z _s (r) −u (r)) ² is added and the problem is transformed into a quadratic form as shown in equation (4) below. To make the problem easier to solve.

This is consistent with the problem with the optimal value. Further, in order to simplify the subsequent expression expansion, λ _s (r) = − ρα _s (r) is set, and the following expression (5) is obtained.

<System configuration>
The natural language analysis processing apparatus 100 according to the first embodiment of the present invention receives a document given as an object of the natural language analysis process as an input, and receives the result of the natural language analysis process including a plurality of stages of language analysis processes. Output. The natural language analysis processing apparatus 100 is configured by a computer including a CPU, a RAM, and a ROM that stores a program for executing a natural language analysis processing routine to be described later, and functionally as described below. It is configured. As shown in FIG. 2, the natural language analysis processing apparatus 100 includes an input unit 10, a calculation unit 20, and an output unit 30.

  The input unit 10 receives an input document. The input unit 10 receives the number of calculation nodes S and the parameter ρ input manually.

The calculation unit 20 includes a minimal subproblem generation unit 21, a group creation unit 22, and S calculation nodes 23 ₁ to 23 _S. In addition, when showing arbitrary calculation nodes among the calculation nodes 23 ₁ to 23 _S , they are referred to as calculation nodes 23.

  For each stage of the language analysis process, the minimal partial problem generation unit 21 defines a problem for performing the language analysis process at the stage for the input document input by the input unit 10 in advance for the language analysis process at the stage. Break down into minimal subproblems and generate a set of minimal subproblems at all stages

The group creation unit 22 selects S groups of subsets of the subproblems so that each local subproblem belongs to at least two groups with respect to the set of local subproblems generated by the local subproblem generation unit 21. It is created and assigned to _S computing nodes 23 ₁ to 23 _S. In addition, the group creation unit 22 notifies the input parameter ρ to each of the _S computation nodes 23 ₁ to 23 _S.

Each of the _S calculation nodes 23 ₁ to 23 _S includes a parameter update unit 31, a partial decomposition update unit 32, a synchronization unit 33, a constraint condition update unit 34, and a convergence determination unit 35. Each S parameter update unit 31, partial decomposition update unit 32, synchronization unit 33, constraint condition update unit 34, and convergence determination unit 35 exist, but the processing units having similar functions are the same number. It represents.

The parameter updating unit 31 updates the Lagrange undetermined multiplier α _s (r) for the subset of the minimal subproblems included in the group assigned by the group creating unit 22 as described below.

(Update of Lagrange multiplier _s α (r))
As the first process, the parameter updating unit 31 updates the Lagrange undetermined multiplier α _s (r) for each minimal subproblem r included in the group assigned to the computation node 23 _s .

When z and u are fixed, the direction of the optimum value of α _s (r) is α of the objective function L _ρ (z, u, α) shown in the above equation (5) as shown in the following equation (6). _s (r) is the gradient direction.

  From the relationship of the above equation (6), the update equation shown in the following equation (7) is obtained.

The parameter updating unit 31 updates the Lagrange undetermined multiplier α _s (r) according to the above equation (7) for each minimal subproblem r. Since the update formula (7) can be calculated independently by each calculation node 23, it is not necessary to communicate with other calculation nodes 23.

As will be described below, the partial decomposition update unit 32 solves each minimal subproblem solution z _s (in the calculation node 23 _s) for a subset of the minimal subproblem r included in the group assigned by the group creation unit 22. Update r).

(Update of solution z _s (r) for each minimal subproblem)

At the time of the iterative calculation k (k is a variable for managing the number of iterations), when α and u are fixed, the optimal solution for each z _s (r) is the above (5) as shown in the following equation (8). The problem is to find z _s (r) that maximizes the objective function L (z, u, α) shown in the equation.

Here, it is assumed that f _s is expressed by the following equation (9).

Here, θ _s (r) represents a score regarding r in the group s, and this value is given from the outside. In other words, it is treated as a constant in this optimization.

  If only the term related to the solution z is extracted from the above equation (5) according to the definition, the following equation (10) is obtained.

  The calculation of equation (8) can also be calculated for each group s. That is, for each calculation node 23, the partial decomposition update unit 32 may solve the maximization problem expressed by the following equation (12) for each minimal subproblem r included in the assigned group.

The synchronization unit 33 notifies α _s (r) and z _s (r) updated this time in the computation node 23 to all computation nodes 23 _i other than itself. Further, the synchronization unit 33 receives α _s (r) and z _s (r) updated this time notified from all the other computation nodes 23 _i . By this processing, each computation node 23 can acquire the values of α _s (r) and z _s (r) possessed by all the computation nodes 23 _s .

The constraint condition update unit 34 uses α _s (r) and z _s (r) received from all the other computation nodes 23 _s to match the solution of the minimal subproblem according to the constraint condition as follows. The parameter u (r) indicating the solution is updated.

When z and α are fixed, the optimal solution for u is that the partial differential value for u _s (r) becomes 0 with respect to the objective function L (z, u, α) shown in the above equation (5). . From the relationship, the following relational expressions (13) and (14) are obtained.

That is, u means the sum of the average of z _s (r) and the average of α _s (r), and all α _s (r) and z _s (r) are used to update the parameter u (r). is necessary.

Therefore, the constraint condition update unit 34 uses the values of α _s (r) and z _s (r) possessed by all of the acquired calculation nodes 23 _s to determine all the minimal subproblems r according to the above equation (14). Update the parameter u (r) for each.

  U (r) is obtained independently at each computation node 23. It should be noted that each computation node 23 independently obtains u (r), but the obtained u (r) matches in all computation nodes 23. As a processing method, a process may be performed in which u (r) is calculated by one arbitrary calculation node 23 and then notified to each calculation node 23. However, in that case, it is necessary to wait for the other calculation nodes until the calculation of the selected calculation node 23 ends and the result is notified. In the present embodiment, a case will be described as an example in which the same calculation is performed in each calculation node 23.

  The convergence determination unit 35 determines whether the obtained parameter u of the constraint condition has converged to an optimum value.

Two small positive real numbers ε ₁ and ε ₂ are given, and it is determined that they converge to the optimum value when the following equations (15) and (16) are satisfied (see Non-Patent Document 5).

  In the convergence determination, if it has not converged to the optimum value, k = k + 1 is set and the process returns to the parameter updating unit 31. If it is determined that the value has converged to the optimum value, the iterative process is terminated.

  Similarly to u (r), the convergence determination process may be performed by any one calculation node 23 and the result may be notified to the whole. However, since synchronous processing is required, in this embodiment, a case will be described as an example where convergence is also individually determined in all the computation nodes 23, and the processing is terminated if it is determined that convergence has occurred. The result of this convergence determination is always the same at all the computation nodes, so the result is the same even if the determination is made individually.

  The convergence determination unit 35 combines the solutions u (r) of the respective minimal sub-problems r obtained when it is determined that the convergence has been achieved to the optimum value, and generates a result of a plurality of stages of language analysis processing. As a result of processing, the output unit 30 outputs the result. In this embodiment, the case where the result of the natural language analysis process is output from any one calculation node 23 has been described as an example. However, the result of the natural language analysis process is output from all the calculation nodes 23. May be. When generating the actual ranking, the search score is calculated using the above equation (2) as in the conventional method.

<Operation of natural language analysis processing device>
Next, the operation of the natural language analysis processing apparatus 100 according to the present embodiment will be described. First, when an input document to be subjected to natural language analysis processing is input to the natural language analysis processing device 100, the natural language analysis processing device 100 performs natural language analysis processing on the input document by the minimal partial problem generation unit 21. The problem is decomposed into minimal subproblems at each stage of the language analysis processing, and a set of minimal subproblems at all stages is generated. Then, the group creation unit 22 creates S groups for the generated set of minimal subproblems and assigns them to _S computation nodes 23 ₁ to 23 _S.

Then, the natural language analysis processing routine shown in FIG. 3 is executed by each calculation node 23 of the natural language analysis processing apparatus 100. In the following, a case where it is executed by the computation node 23 _s will be described.

First, in step S101, an initial value 1 is set for a variable k indicating the number of iterations, and each Lagrange undetermined multiplier α _s ⁰ (r) for each subset of the minimal subproblem r of the assigned group s is assigned to each minimal subproblem. An appropriate value (for example, 0) is given to each of the solution z _s ⁰ (r) and the parameter u _s ⁰ (r) of the constraint condition for initialization.

In step S102, the parameter update unit 31 performs Lagrange undetermined multiplier α _s ⁰ (r) initialized in step S101, the solution z _s ⁰ (r) of each local subproblem, and the parameter u _{s of the} constraint condition. ⁰ (r), or Lagrange undetermined multiplier α _s ^k-1 (r) updated last time, solution z _s ^k-1 (r) of each local subproblem, and constraint parameter u _s ^k-1 (r) Based on the above, the Lagrange undetermined multiplier α _s ^k (r) for each of the minimal subproblems r in the group s is updated according to the above equation (7).

In the next step S103, the Lagrangian undetermined multiplier α _s ^k (r) updated in step S102 by the partial decomposition update unit 32 and the solution z _s ⁰ (r) of each local subproblem initialized in step S101. ), or based on previous solutions updated each minimum subproblem z _s ^k-1 (r), (12) in accordance with equation, the solution to each of the minimum partial problems r in the group s z _s ^k (r) Update.

In step S104, the synchronization unit 33 calculates the Lagrange undetermined multiplier α _s ^k (r) updated in step S102 and the solution z _s ^k (r) of each minimal subproblem updated in step S103 to other values. In addition to notifying the computation node 23, the updated Lagrange undetermined multiplier α _i ^k (r) and the solution z _i ^k (r) of each local subproblem are obtained from all the other computation nodes 23 _i (i = 1, ..., s-1, s + 1, ..., S).

In step S105, the constraint condition update unit 34 updates the Lagrange undetermined multiplier α _s ^k (r) updated in step S102 and the solution z _s ^k (r) of each local subproblem updated in step S103, and Based on the Lagrange undetermined multipliers α _i ^k (r) and solutions z _i ^k (r) of the respective local subproblems obtained from all the other computation nodes 23 _{i in} step S104, all the local minima are determined according to the above equation (14). Update the constraint parameters u ^k (r) for each of the subproblems r.

In the next step S106, based on the solution z _s ^k (r) of each updated minimal subproblem r in all the groups s and the updated parameter u ^k (r) of the constraint condition ( In accordance with the equations (15) and (16), it is determined whether or not all the parameters u ^k (r) of the constraint conditions have converged to the optimum values. If the above equations (15) and (16) are not satisfied, it is determined that they have not converged, the variable k is incremented by 1, and the process returns to step S102. On the other hand, if the above equations (15) and (16) are satisfied, it is determined that convergence has occurred, and the process proceeds to step S107.

In step S107, the result of the language analysis process at each stage is generated using the constraint parameter u ^k (r) finally updated in step S105, and the result of the natural language analysis process is output by the output unit 30. Output and end the natural language analysis processing routine.

  As described above, according to the natural language analysis processing apparatus according to the first embodiment, the problem of performing the multi-level language analysis processing is decomposed into a set of minimal subproblems, and a group is created. Update the Lagrange undetermined multiplier and the solution of the minimal subproblem for each subset of the minimal subproblems assigned to each computation node based on the constraints that the solutions of the minimal subproblems belonging to the group match. Using the acquired Lagrange undetermined multiplier and the solution of the minimal subproblem, it is possible to perform multi-level language analysis processing in a batch by repeating updating the constraint parameter for all the minimal subproblems until convergence. The natural language analysis process can be performed with high accuracy while suppressing an increase in the amount of calculation.

  Further, by using the present invention, it becomes possible to integrate and perform language analysis processing composed of a plurality of stages. As a result, it is possible to make it harder for the analysis of the previous stage to be affected by the error in the previous stage analysis than in the conventional cascade method, and as a result, improve the overall analysis accuracy. Is possible. In addition, it is possible to achieve total optimization with a small amount of calculation without dividing a complicated language analysis problem into each stage.

  In addition, various viewpoints can be integrated for analysis. For example, existing information such as a dictionary or partially analyzed data can be easily integrated and used. Global features can also be easily integrated. Further, since the problem is processed by dividing the problem into small units, it is easy to increase the speed by parallel processing.

In the above embodiment, the case where each calculation node 23 includes the constraint condition update unit 34 and the convergence determination unit 35 has been described as an example. However, the present invention is not limited to this. For example, as illustrated in FIG. 4, each calculation node 23 includes a parameter update unit 31 and a partial decomposition update unit 32, and the calculation unit 20 includes one constraint condition update unit 34 and one convergence determination unit 35. You may comprise. In this case, the constraint condition update unit 34 uses the Lagrange undetermined multiplier α _s ^k (r) obtained at all the computation nodes 23 _s and the solution z _s ^k (r) of each minimal subproblem to The parameter u ^k (r) is updated, and the convergence determination unit 35 determines whether the parameter u ^k (r) of the obtained constraint condition has converged to the optimum value. If the convergence is not determined in the convergence determination, the parameter u ^k (r) of the constraint condition obtained to each computation node 23 is notified, and the process returns to the process by the parameter update unit 31.

[Second Embodiment]
Next, a second embodiment will be described. In addition, about the part which becomes the structure similar to 1st Embodiment, the same code | symbol is attached | subjected and description is abbreviate | omitted.

  In the second embodiment, in the distributed parallel computing environment provided with a plurality of language analysis devices connected by a network, the parameter is updated by the distributed parallel computation by the plurality of language analysis devices. This is different from the embodiment.

<System configuration>
As shown in FIG. 5, the natural language analysis processing system 200 according to the second embodiment includes a language analysis control device 201 and S language analysis devices 202 _{1 to} 202 _S. The language analysis control device 201 and the S language analysis devices 202 _{1 to} 202 _S are connected via a network 203. In addition, when referring to any language analysis device among the language analysis devices 202 _{1 to} 202 _S , the language analysis device 202 is referred to.

  As shown in FIG. 6, the language analysis control device 201 includes an input unit 10, a calculation unit 220, and an output unit 230.

  The calculation unit 220 includes a minimal partial problem generation unit 21 and a group creation unit 22.

The group creation unit 22 creates S groups composed of subsets of the minimal subsets for the set of minimal subproblems generated by the minimal subproblem generation unit 21, and S language analysis devices via the network 203 to send to the 202 ₁ ~202 _S. Further, the group creation unit 22 transmits the input parameter ρ to each of the _S language analysis devices 202 _{1 to} 202 S via the network 203.

Each of the S language analyzers 202 _{1 to} 202 _S includes an input unit 240, a calculation unit 250, and an output unit 260, as shown in FIG.

  The input unit 240 receives a subset of minimal subproblems included in the group s transmitted from the language analysis control device 201. The input unit 240 receives information transmitted from another language analysis apparatus 202 via the network 203.

  The calculation unit 250 includes a parameter update unit 31, a partial decomposition update unit 32, a synchronization unit 33, a constraint condition update unit 34, and a convergence determination unit 35.

The parameter updating unit 31 updates the Lagrange undetermined multiplier α _s (r) for each minimal subproblem r for the subset of the minimal subproblems of the group s transmitted to the language analysis device 202.

The synchronization unit 33 transmits α _s (r) and z _s (r) updated this time by the language analysis device 202 _s to all the language analysis devices 202 other than itself through the network 203. Further, the synchronization unit 33 receives α _i (r) and z _i (r) updated this time, which are transmitted from all the other language analysis devices 202 _i . By this processing, each language analysis device 202 can acquire the values of α _s (r) and z _s (r) of all the language analysis devices 202 _s .

The constraint condition update unit 34 uses the parameters α _i (r) and z _i (r) received from all the other language analysis devices 202 _i according to the above equation (14), and parameters for the constraint conditions for each minimal subproblem r. Update u (r).

  The convergence determination unit 35 determines whether the obtained constraint condition parameter u (r) has converged to an optimum value, and uses the constraint condition parameter u (r) obtained when it is determined that the convergence has been achieved. In combination, a result of a multi-stage language analysis process is generated, and the result of the natural language analysis process is transmitted to the language analysis control apparatus 201 by the output unit 260.

<Operation of natural language analysis processing system>
Next, the operation of the natural language analysis processing system 200 according to the present embodiment will be described. First, when a document to be subjected to natural language analysis processing is input to the language analysis control device 201, the language analysis control device 201 uses the minimal partial problem generation unit 21 to perform a problem of performing natural language analysis processing on the input document. A set of minimal subproblems is generated by decomposing the minimal subproblems at each stage of the language analysis processing. Then, the group creation unit 22 creates S groups for the generated set of minimal subproblems, transmits them to the S language analysis devices 202 via the network 203, and the S language analysis devices 202. Assign to.

  Then, the natural language analysis processing routine shown in FIG. 3 is executed by each language analysis device 202.

  The result of the natural language analysis process generated by combining the finally updated constraint parameter u (r) by at least one language analysis device 202 is transmitted to the language analysis control device 201 via the network 203. The The language analysis control device 201 outputs the result of the natural language analysis processing received by the language analysis device 202 by the output unit 230.

  As described above, according to the natural language analysis processing system according to the second embodiment, a plurality of language analysis devices connected via a network perform natural language analysis processing by distributed parallel processing. Can be speeded up.

  Note that the present invention is not limited to the above-described embodiment, and various modifications and applications are possible without departing from the gist of the present invention.

  For example, although the case where the problem of performing the natural language analysis processing including the language analysis processing of a plurality of stages is decomposed into the minimum sub-problem which is the minimum unit predefined for each stage has been described as an example, the present invention is limited to this. Instead, a subproblem with a unit larger than the smallest unit may be defined and decomposed into the subproblem. For example, you may make it decompose | disassemble into the partial problem which combined several minimum partial problems which are the minimum units.

  Further, the above-described natural language analysis processing device, language analysis control device, and language analysis device have a computer system therein, but if the “computer system” uses a WWW system, a homepage can be used. It also includes the provision environment (or display environment).

  In the present specification, the embodiment has been described in which the program is installed in advance. However, the program can be provided by being stored in a computer-readable recording medium.

DESCRIPTION OF SYMBOLS 10 Input part 20 Calculation part 21 Minimal subproblem generation part 22 Group preparation part 23 Calculation node 31 Parameter update part 32 Partial decomposition update part 33 Synchronization part 34 Restriction condition update part 35 Convergence determination part 100 Natural language analysis processing apparatus 200 Natural language analysis Processing System 201 Language Analysis Control Device 202 Language Analysis Device

Claims (8)

A natural language analysis processing device that performs natural language analysis processing including a plurality of types of natural language analysis processing on an input document including at least one sentence,
For each of the plurality of types of natural language analysis processing, the problem of performing the natural language analysis processing on the input document is decomposed into partial problems that are problems in units of characters or more that are predefined for the natural language analysis processing. And subproblem generating means for generating the set of subproblems,
S computation nodes (S is a natural number of 2 or more) for performing the natural language analysis processing;
With respect to the set of subproblems generated by the subproblem generating means, S groups composed of arbitrary subsets with respect to the whole set of subproblems so that each subproblem belongs to at least two groups. Creating a group and assigning it to the S computation nodes;
Each of the S compute nodes is
For each subset of the subsets assigned to the group by the group creating means, each subset problem of the subset is based on a constraint condition in which the solutions of the subset problems belonging to the two or more groups match. Partial decomposition updating means for updating the solution of
Notifying the other calculation nodes of the solutions of the respective partial problems updated by the partial decomposition updating means, and obtaining the solutions of the respective partial problems of the subset notified from the other calculation nodes Synchronization means;
Based on the solution of each subproblem of the subset of the other computation node obtained by the synchronization means and the solution of each subproblem of the subset updated by the partial decomposition update means, , Constraint condition updating means for updating a constraint parameter that is a solution when matching the solution of the partial problem according to the constraint condition;
It is determined whether or not the value of the constraint parameter has converged, and until it is determined that the value of the constraint parameter has converged, the update by the partial decomposition update unit, the notification and acquisition by the synchronization unit, and the constraint condition A natural language analysis processing apparatus comprising: a convergence determination unit that repeats updating by the updating unit. The partial decomposition updating means, for the subset of the partial problem of the group assigned by the group creating means, the Lagrange undetermined multiplier updated last time, the solution of each partial problem of the subset, and the constraint parameter To update the Lagrangian undetermined multiplier so as to optimize a predetermined objective function value, and to use the updated Lagrange undetermined multiplier to optimize the value of the objective function, Update the solution of each subproblem of the subset,
The synchronizing means notifies the Lagrange undetermined multiplier updated by the partial decomposition updating means and the solution of each subproblem of the subset to other calculation nodes, and the Lagrange notified from the other calculation nodes. Obtain the undetermined multiplier and the solution of each subproblem of the subset,
The constraint condition update means includes the Lagrange undetermined multiplier and the solution of each partial problem of the subset obtained by the synchronization means, the Lagrange undetermined multiplier updated by the partial decomposition update means, and the The natural language analysis processing apparatus according to claim 1, wherein the constraint parameter is updated for each subproblem so that the value of the objective function is optimized based on a solution of each subproblem of the subset. A natural language analysis processing device that performs natural language analysis processing including a plurality of types of natural language analysis processing on an input document including at least one sentence,
For each of the plurality of types of natural language analysis processing, the problem of performing the natural language analysis processing on the input document is decomposed into partial problems that are problems in units of characters or more that are predefined for the natural language analysis processing. And subproblem generating means for generating the set of subproblems,
S computation nodes (S is a natural number of 2 or more) for performing the natural language analysis processing;
With respect to the set of subproblems generated by the subproblem generating means, S groups composed of arbitrary subsets with respect to the whole set of subproblems so that each subproblem belongs to at least two groups. Group creating means for creating and assigning to the S computing nodes;
Including constraint update means and convergence determination means,
Each of the S compute nodes is
For each subset of the subsets assigned to the group by the group creating means, each subset problem of the subset is based on a constraint condition in which the solutions of the subset problems belonging to the two or more groups match. A partial decomposition updating means for updating the solution of
The constraint condition update means matches the solution of the partial problem according to the constraint condition for each partial problem based on the solution of each partial problem of the subset updated by the partial decomposition update means of each computation node. Update the constraint parameter, which is the solution when
The convergence determination means determines whether or not the value of the constraint parameter has converged, and updates by the partial decomposition update means of each calculation node until determining that the value of the constraint parameter has converged, and A natural language analysis processing device that repeats updating by means of constraint condition updating. The partial decomposition updating means, for the subset of the partial problem of the group assigned by the group creating means, the Lagrange undetermined multiplier updated last time, the solution of each partial problem of the subset, and the constraint parameter To update the Lagrangian undetermined multiplier so as to optimize a predetermined objective function value, and to use the updated Lagrange undetermined multiplier to optimize the value of the objective function, Update the solution of each subproblem of the subset,
The constraint condition update means optimizes the value of the objective function based on the Lagrange undetermined multiplier updated by the partial decomposition update means of each computation node and the solution of each partial problem of the subset. The natural language analysis processing apparatus according to claim 3, wherein the constraint parameter is updated for each partial problem. A natural language analysis process including a plurality of types of natural language analysis processes for an input document including at least one sentence, including a subproblem generation unit, S (S is a natural number of 2 or more) calculation nodes, and a group creation unit A natural language analysis processing method in a natural language analysis processing apparatus for performing
For each of the plurality of types of natural language analysis processing, the partial problem generating means determines a problem of performing the natural language analysis processing on the input document in units of characters or units that are predefined for the natural language analysis processing. Break down into subproblems that are problems to generate the set of subproblems,
The set of subproblems generated by the subproblem generation means by the group creating means is composed of an arbitrary subset of the whole set of subproblems so that each subproblem belongs to at least two groups. Create S groups and assign them to the S compute nodes,
The natural language analysis processing is performed by the S calculation nodes,
Performing the natural language analysis process by each of the S computation nodes is as follows:
Based on the constraint condition that the solutions of the partial problems belonging to the two or more groups match with respect to a subset of the partial problem set of the group assigned by the group creation means by the partial decomposition update means, Update the solution of each subproblem in the subset,
The synchronization means notifies the solution of each subproblem of the subset updated by the subdivision updating means to other calculation nodes, and also notifies each subproblem of the subset notified from the other calculation node. Get the solution,
Based on the solution of each partial problem of the subset of the other computation node acquired by the synchronization means by the constraint update means and the solution of each partial problem of the subset updated by the partial decomposition update means For each subproblem, update the constraint parameter that is a solution when matching the solution of the subproblem according to the constraint,
The convergence determination means determines whether or not the value of the constraint parameter has converged, and updates by the partial decomposition update means, notification and acquisition by the synchronization means until it is determined that the value of the constraint parameter has converged And repeating the update by the constraint condition update means
Natural language analysis processing method. The partial decomposition updating means, for the subset of the partial problem of the group assigned by the group creating means, the Lagrange undetermined multiplier updated last time, the solution of each partial problem of the subset, and the constraint parameter To update the Lagrangian undetermined multiplier so as to optimize a predetermined objective function value, and to use the updated Lagrange undetermined multiplier to optimize the value of the objective function, Update the solution of each subproblem of the subset,
The synchronizing means notifies the Lagrange undetermined multiplier updated by the partial decomposition updating means and the solution of each subproblem of the subset to other calculation nodes, and the Lagrange notified from the other calculation nodes. Obtain the undetermined multiplier and the solution of each subproblem of the subset,
The constraint condition update means includes the Lagrange undetermined multiplier and the solution of each partial problem of the subset obtained by the synchronization means, the Lagrange undetermined multiplier updated by the partial decomposition update means, and the The natural language analysis processing method according to claim 5, wherein the constraint parameter is updated for each subproblem so as to optimize the value of the objective function based on a solution of each subproblem of the subset. It includes a sub-problem generating means, S calculation nodes (S is a natural number of 2 or more), a group creating means, a constraint condition updating means, and a convergence determining means, and a plurality of types of natural for an input document including at least one sentence A natural language analysis processing method in a natural language analysis processing apparatus for performing natural language analysis processing including language analysis processing,
For each of the plurality of types of natural language analysis processing, the partial problem generating means determines a problem of performing the natural language analysis processing on the input document in units of characters or units that are predefined for the natural language analysis processing. Break down into subproblems that are problems to generate the set of subproblems,
The set of subproblems generated by the subproblem generation means by the group creating means is composed of an arbitrary subset of the whole set of subproblems so that each subproblem belongs to at least two groups. Create S groups and assign them to the S compute nodes,
The natural language analysis processing is performed by the S calculation nodes,
Updated by the constraint condition update means,
Determining by the convergence determining means,
Performing the natural language analysis process by each of the S computation nodes is as follows:
Based on the constraint condition that the solutions of the partial problems belonging to the two or more groups match with respect to a subset of the partial problem set of the group assigned by the group creation means by the partial decomposition update means, Updating the solution of each subproblem of the subset,
The constraint condition update means matches the solution of the partial problem according to the constraint condition for each partial problem based on the solution of each partial problem of the subset updated by the partial decomposition update means of each computation node. Update the constraint parameter, which is the solution when
The convergence determination means determines whether or not the value of the constraint parameter has converged, and updates by the partial decomposition update means of each calculation node until determining that the value of the constraint parameter has converged, and Natural language analysis processing method that repeats the update by the constraint update means.   The program for functioning a computer as each means of the natural language analysis processing apparatus of any one of Claims 1-4.