JP4494036B2 - Database generation device, data analysis device, and database search device - Google Patents

Description

  The present invention relates to database technology, and more particularly to a database generation device, a data analysis device, and a database search device.

  As a conventional data search technique, when unknown data is given, a good algorithm is known as a method for searching for data that completely matches the unknown data, and a technique for performing high-speed search has been established. For example, there are algorithms such as address mapping, hash code, binary search, binary search tree, and B-tree. If a database structure is defined based on these algorithms, a data search process that finds a match with the target data at high speed can be realized. In addition, a search specifying a search range is also possible. For example, in the database, the condition that the attribute A of the data is 100 to 200, the attribute B is 1.5 or less, and the attribute C is TRUE Technology to find all of these has been realized.

  Conventionally, a method for finding the nearest data from a database with respect to unknown data is also known. For example, as the simplest method, the nearest data can be found by calculating the distance to all data in the database. In computational geometry, processing methods for efficiently searching for the closest point using various nearest point search algorithms have been proposed. This has been put to practical use as a similar data retrieval technique in a two-dimensional space such as a map information system.

  In the pattern recognition field, a dictionary is created using learning data in advance, and the recognition process compares the input data and the dictionary by some method. If a large amount of learning data is prepared, a dictionary with good performance can be created, so that recognition processing can be performed accurately. For example, using the nearest neighbor search method, it is theoretically known that recognition errors can be minimized by increasing the learning data to the limit.

In Patent Document 1, a feature set is formed based on a feature vector composed of a plurality of elements corresponding to a model pattern, a dictionary in which the feature set is associated with a category is created, and input is performed using the dictionary. A pattern recognition apparatus for determining a pattern category is disclosed.
Japanese Patent No. 2937729

  However, it is difficult to develop a generally effective and efficient algorithm for retrieving data as close as possible to given data. The method of searching all the databases for given data has the disadvantage that the search time increases as the number of data increases. The range search of the prior art can find data that satisfies a certain condition, but is not suitable for the process of finding data that best meets the condition. Since it takes time to process candidates in order from the one closest to the condition, it becomes difficult to realize such an object when the database becomes large.

  Also, in the field of pattern recognition, if you try to perform large-scale pattern recognition processing, the learning space becomes huge, and it takes a lot of time for learning or a lot of time for recognition. Will occur. In the nearest point search algorithm, a high-speed search method for high-dimensional data has not been proposed.

  Today, there is a demand for strategically utilizing a large amount of information. In other words, there is a need for an information tool that, for given data, finds similar case data candidates from a huge amount of accumulated cases in the past and makes decisions with reference to them. A true data search can be said to be a practical search of this kind. However, in order to do so, it is necessary to perform processing for quickly finding out similar data from a large amount of data. When the scale increases, there is no known method for efficiently performing such processing.

  In general, when a high-speed similar data search is to be realized, there is a problem that it takes a lot of processing time to create such a search database in advance.

  As a theoretical algorithm that can search for similar data at high speed, there is a method that uses a huge memory space to prepare addresses that all the data values can take, but this requires time to create the database. In addition, since it requires an exponential storage space, it is not practical for a large amount of data.

  As described above, there is no known high-speed database creation method capable of searching for similar data at high speed. As a practical matter, when the database creation time is slow, if the number of data increases, it is practically impossible to realize. For example, even if the database creation time is proportional to the square of the number of data items, it takes 1 trillion units if the number of data items is 1 million.

  Under such circumstances, there is a need for a technique that can create a database at high speed and can use the database to search for similar data at high speed.

  The present invention has been made in view of these problems, and an object of the present invention is to quickly find near data from a large amount of data and to efficiently create a database capable of such high-speed data search. To provide a database generation device, a data analysis device, and a database search device. Another object is to realize a technology applicable to high-performance data mining, knowledge information processing, and pattern recognition technology.

  One embodiment of the present invention relates to a database generation apparatus. The apparatus includes a data conversion unit that converts input data using a substantially orthogonal matrix, and a distributed expression generation that generates a distributed expression of the input data by obtaining at least one neighboring point of the converted input data in a discrete space. And a dictionary generation unit that generates a dictionary using each of the at least one neighboring points in the generated distributed representation as a search key, wherein the data conversion unit is configured to input the input data using a plurality of different substantially orthogonal matrices. Is converted and given to the distributed expression generation unit, a plurality of distributed expressions are generated for the input data, and the dictionary is generated for each distributed expression. According to this configuration, a database using a large number of distributed representations of input data can be created to improve search accuracy.

  The dictionary generation unit may generate a dictionary in which identification information of a category in which the input data should be classified is associated with the search key.

  Another embodiment of the present invention also relates to a database generation apparatus. The apparatus includes a distributed representation generation unit that generates a distributed representation of the input data by obtaining at least one nearby point of the input data in a discrete space, and the at least one nearby point in the generated distributed representation. A dictionary generating unit that generates a dictionary with each as a search key, and associates the identification information of the input data with the search key and registers it in the dictionary. According to this configuration, it is possible to create a database using a distributed representation of input data and efficiently search for input data related to unknown data.

Still another embodiment of the present invention also relates to a database generation apparatus. The apparatus includes a distributed representation generation unit that generates a distributed representation of the input data by obtaining at least one nearby point of the input data in a discrete space, and the at least one nearby point in the generated distributed representation. A dictionary generating each of which is used as a search key, a dictionary generation unit for registering the search key in association with identification information of a category to which the input data should be classified, and an input whose classification destination category is known on the basis of the learning sample set of data, said to the i-th of the search key is the j-th category counts the number of times P _ij to be associated in the dictionary, it functions to increase monotonically with respect to P _ij f (P _ij ) is used to determine the addition coefficient of the score at the time of classification, and this addition coefficient is assigned to the j-th category associated with the i-th search key in the dictionary. And an addition coefficient determination unit that is registered in association with the identification information. According to this configuration, by adjusting the score addition coefficient at the time of classification, recognition by one dictionary can bring about the same effect as recognition using a large number of dictionaries, and the dictionary is stored. Thus, the storage time can be saved and the search time can be shortened.

  Yet another embodiment of the present invention relates to a data analysis apparatus. The apparatus includes a distributed representation generation unit that generates a distributed representation of the input data by obtaining at least one nearby point of the input data in a discrete space, and the at least one nearby point in the generated distributed representation. A dictionary generating each of the search keys as a search key, a dictionary generation unit that associates the identification information of the input data with the search key and registers it in the dictionary, and the identification information of the new input data in the dictionary is associated with the search key And generating an identification information pair with the identification information of the input data already registered in the search key, and storing the identification information pair in the table together with the number of appearances thereof including. According to this configuration, it is possible to detect pairs of input data that are related to each other in the process of creating a dictionary.

  Yet another embodiment of the present invention relates to a database search apparatus. The apparatus includes a dictionary using each of at least one neighboring point of registered data in a discrete space as a search key, a data conversion unit that converts input data using a substantially orthogonal matrix, and at least the input data after conversion in the discrete space. Searching the dictionary using a distributed representation generation unit that generates a distributed representation of the input data by obtaining one nearby point, and using each of the at least one nearby point in the generated distributed representation as a search key A plurality of distributed representations for the input data by the data conversion unit converting the input data using a plurality of different substantially orthogonal matrices and supplying the converted data to the distributed representation generation unit. The dictionary is searched using each of the at least one neighboring points as a search key for each distributed expression.

  The dictionary is obtained by associating the search key with a list of identification information of categories to which the registered data is classified, and the search unit is configured to store the at least one neighboring point in each distributed representation of the input data. The identification information of the category in the list hit in the search using each as a search key may be stored in a table together with the cumulative number of hits.

  Yet another embodiment of the present invention also relates to a database search apparatus. The apparatus includes a dictionary in which at least one neighboring point of registration data in a discrete space is used as a search key and a list of identification information of the registration data is associated with the search key, and at least one of input data in the discrete space. The dictionary is searched using each of the at least one neighboring point in the generated distributed representation as a search key and a distributed representation generating unit that generates a distributed representation of the input data by obtaining two neighboring points. The identification information of the registered data in the list that has been hit is stored in a table.

  The information processing apparatus may further include a calculation unit that obtains a value related to a distance between the registered data hit by the search by the search unit and the input data, and stores the value related to the distance in the table together with identification information of the registered data hit.

  Yet another embodiment of the present invention also relates to a database search apparatus. This device includes at least one neighboring point of registration data in a discrete space as a search key, and the search key includes identification information of a category to which the registration data is classified and a score addition coefficient for classification. A dictionary in which a list of pairs is associated; a discrete expression that generates a distributed representation of the input data by obtaining at least one neighboring point of the input data in a discrete space; and The dictionary is searched using each of at least one neighboring point as a search key, and the identification information of the category in the list hit is stored in the table together with the cumulative value of the addition coefficient.

  It should be noted that any combination of the above-described constituent elements and a representation of the present invention converted between a method, an apparatus, a system, a computer program, etc. are also effective as an aspect of the present invention.

  According to the present invention, it is possible to efficiently create a database and perform data search at high speed.

  Several embodiments of the present invention will be described. In the description of the embodiments, the detailed configuration and operation will be referred to as appropriate in the technical details in sections [1] to [6] described later.

Embodiment 1
FIG. 1 is a configuration diagram of nearest point search apparatus 100 according to Embodiment 1. This configuration can be realized in terms of hardware by a CPU, memory, or other LSI of any computer, and in terms of software, it can be realized by a program loaded in the memory, but here it is realized by their cooperation. Draw functional blocks. Therefore, those skilled in the art will understand that these functional blocks can be realized in various forms by hardware only, software only, or a combination thereof.

  The nearest point search device 100 according to the present embodiment is used to search for data closest to unknown data, that is, a nearest point, from a large amount of data. In the learning phase, a set of learning data is given and a database for searching for the nearest point is created. In the recognition phase, unknown data is given, and the nearest learning data is searched using the database for searching for the nearest point. The process performed by the nearest point searching apparatus 100 will be described in detail in section [2].

  The configuration of the database 70 storing the orthogonal transform unit 10, the distributed representation generation unit 20, the dictionary generation unit 30, and the closest point search dictionary 110 in the closest point search device 100 is obtained when a set of learning data is given as input data. The nearest point search dictionary 110 is created from a set of learning data, and is an example of the database generation device of the present invention.

The orthogonal transform unit 10 performs orthogonal transform on the N-dimensional input data using a random orthogonal matrix, and provides the converted input data to the distributed representation generation unit 20. Here, the orthogonal matrix is a square matrix having elements that satisfy R ^T R = E as real numbers when the transposed matrix of the N × N matrix R is expressed as ^RT . Here, E is an N-dimensional unit matrix. The linear transformation determined by the orthogonal matrix is called orthogonal transformation, and the orthogonal transformation f does not change the inner product in the metric vector space V. That is, when x and y are arbitrary vectors of V, (f (x), f (y)) = (x, y) holds. However, (,) represents the inner product. If x and y are on an N-dimensional hypersphere and the magnitude of the vector is constant, the inner product corresponds to the distance between x and y, and the orthogonal transformation f is a transformation that preserves the distance between x and y. It can be said that there is.

  The orthogonal transform unit 10 generates a plurality of types of converted input data by performing orthogonal transform on the input data using a plurality of different random orthogonal matrices, and supplies the generated data to the distributed representation generation unit 20. Since the orthogonal matrix is a matrix having N mutually orthogonal unit vectors as row vectors, in order to create a uniformly random orthogonal matrix, N uniformly orthogonal unit vectors must be created. That's fine. For this purpose, N linearly independent N-dimensional real vectors are generated at random, and each is orthogonalized by the Gram-Schmidt orthogonalization method.

  The reason why the input data is converted by a plurality of different orthogonal transforms in this way is to obtain as much quantized data as possible when the distributed representation generation unit 20 converts the input data into a discrete space for quantization. Note that the orthogonal matrix does not have to satisfy the above definition in a strict sense, and may be an approximately orthogonal matrix in which the inner product is substantially preserved after conversion. The orthogonal transform unit 10 performs processing described in [1.2.2.2], which will be described later.

  The distributed representation generation unit 20 generates a distributed representation of the input data by obtaining one or a plurality of neighboring points of the input data after the transformation by the orthogonal transformation unit 10 in a predetermined discrete space, and sends it to the dictionary generation unit 30. give. Here, it is assumed that the number of points in the discrete space is very large compared to the number of neighboring points. This quantizes the input data into one or more nearby points.

  The distributed representation generation unit 20 receives a plurality of types of input data transformed by a plurality of different orthogonal matrices from the orthogonal transform unit 10 and generates a plurality of distributed representations for one input data. Even if the distributed representation generated by the distributed representation generation unit 20 has only one neighboring point, the input data is transformed by a plurality of quantized data by converting the input data by a plurality of different orthogonal matrices. Will be. The conversion of the input data into the distributed representation by the distributed representation generation unit 20 is called distributed coding.

  Hereinafter, the distributed representation of the input data is also referred to as element representation, and in that case, the neighboring points are referred to as elements. A specific method for creating an element expression by the distributed expression generation unit 20 will be described in detail in section [1].

  The dictionary generation unit 30 generates a closest point search dictionary 110 using each element in the distributed representation of input data as a search key in the database 70, and registers the input data label in association with the search key. Since a plurality of types of distributed representations are created for one input data by conversion using a plurality of different orthogonal matrices, the dictionary generation unit 30 generates a nearest point search dictionary 110 for each of the plurality of types of distributed representations. Will do. The closest point search dictionary 110 may be divided for each distributed expression, or the closest point search dictionary 110 may be provided in which all types of distributed expressions are combined.

  The dictionary generation unit 30 performs a process of registering all input data included in the learning data set in the closest point search dictionary 110. The nearest point search dictionary 110 is a table having all elements appearing in the distributed representation of learning data as search keys, and each search key is linked with a label of learning data in a list structure. Various methods for realizing a function equivalent to the list structure may be used. The generation process of the nearest point search dictionary 110 by the dictionary generation unit 30 and the data structure of the nearest point search dictionary 110 will be described in detail in [2.2.1] to [2.2.5].

  Next, when unknown data is given as input data, data closest to the unknown data is found from the set of learning data. The configuration of the database 70 storing the orthogonal transformation unit 10, the distributed representation generation unit 20, the search unit 40, and the nearest point search dictionary 110 in the nearest point search device 100 is such that when unknown data is given as input data, The search dictionary 110 is searched for data close to unknown data, which is an example of the database search apparatus of the present invention.

  The orthogonal transform unit 10 performs orthogonal transform on the unknown data and gives the data to the distributed representation generation unit 20. At this time, the orthogonal transform unit 10 orthogonally transforms the unknown data using the same orthogonal matrix as that of the learning data, and supplies the unknown data to the distributed representation generation unit 20. The distributed representation generation unit 20 also obtains one or a plurality of neighboring points of the unknown data after the transformation by the orthogonal transformation unit 10 in the same discrete space as the learning data, and generates a distributed representation of the unknown data. As in the case of learning data, the orthogonal transform unit 10 transforms unknown data using a plurality of different orthogonal matrices, so that the distributed representation generation unit 20 generates a plurality of types of distributed representations for the unknown data.

  The search unit 40 searches the nearest point search dictionary 110 stored in the database 70 using each neighboring point (or each element) in each distributed representation of unknown data as a search key, and links to the element used as the search key. The list of learning data labels is stored, and the data labels of all the learning data in the list are stored in the nearest point candidate table 130 together with the number of appearances, and stored in the search result storage unit 80.

  The search unit 40 searches the nearest point search dictionary 110 using all the elements in the distributed representation of unknown data as search keys, and uses the data label of the obtained learning data as the data label of the nearest point candidate, and the nearest point candidate table 130. To store. At this time, if the data label is already stored in the nearest point candidate table 130, the number of appearances of the data label is cumulatively added.

  When the search unit 40 finishes searching for all elements in the distributed representation of the unknown data, the verification unit 50 refers to the nearest point candidate table 130 stored in the search result storage unit 80 and stores the latest point candidate table 130 in the nearest point candidate table 130. An evaluation value related to the distance between the learning data and the unknown data corresponding to the data label of the nearest point candidate listed in (1) is calculated. Specifically, the inner product of the learning data that is the nearest point candidate and the unknown data is calculated, and the inner product value is stored in the nearest point candidate table 130 in association with the data label of the nearest point candidate. The verification unit 50 outputs the nearest point candidate having the largest inner product as the nearest point of the unknown data.

  The verification unit 50 may calculate the inner product value for all the nearest point candidates listed in the nearest point candidate table 130, but the number of appearances of each nearest point candidate is stored in the nearest point candidate table 130. May calculate the inner product value in order from the closest point candidate having the highest number of appearances, stop the calculation in a predetermined order, and output the closest point candidate having the largest inner product value at that time as the closest point of the unknown data.

  In addition, without performing verification by the verification unit 50, the search unit 40 refers to the nearest point candidate table 130 stored in the search result storage unit 80 when the search is completed for all elements in the distributed representation of unknown data. Then, the data labels may be rearranged in descending order of the number of appearances, and the learning data corresponding to each data label may be output as a list of unknown data closest points. Further, although the accuracy is lowered, the verification unit 50 may output the learning data corresponding to the data label having the largest appearance number as the nearest point without performing the verification.

Embodiment 2
FIG. 2 is a configuration diagram of the pattern recognition apparatus 200 according to the second embodiment. The pattern recognition apparatus 200 according to the present embodiment classifies input data into categories, and is used for pattern recognition. In the learning phase, a set of input data whose classification destination category is known is given as a learning sample, and a database for pattern recognition is generated. In the recognition phase, unknown data is given and the unknown data is classified into categories using a database for pattern recognition. The processing by the pattern recognition apparatus 200 will be described in detail in section [3].

  Since the orthogonal transform unit 10 and the distributed representation generation unit 20 of the pattern recognition apparatus 200 are the same as those in the first embodiment, description thereof is omitted. The dictionary generation unit 30 creates a pattern recognition dictionary 210 using each element in the distributed representation of the input data as a search key in the database 70 and registers the search data in association with the label of the category of the input data. The dictionary generation unit 30 performs processing for registering all elements in the distributed representation of input data in the pattern recognition dictionary 210. By performing dictionary registration processing for a plurality of input data, a pattern recognition dictionary 210 having a structure in which a list of categories of input data is linked to elements is generated.

  When unknown data whose classification category is unknown is input to the orthogonal transformation unit 10, a distributed representation generation unit 20 generates a distributed representation of unknown data. The search unit 40 searches the pattern recognition dictionary 210 stored in the database 70 using each element in the distributed representation of unknown data as a search key, and all categories in the category list linked to the search key. Are stored in the category candidate table 230 together with the number of appearances, and stored in the search result storage unit 80. At this time, if the category is already stored in the category candidate table 230, the number of appearances of the category is incremented by one. This number of appearances is the category score.

  When the search unit 40 finishes searching the pattern recognition dictionary 210 using all elements in the distributed representation of unknown data as search keys, the search unit 40 outputs the category with the highest number of appearances as the category to which unknown data is classified. To do. The search unit 40 may rearrange the list of categories stored in the category candidate table 230 in descending order of the number of appearances, and output a list of a predetermined number of higher-order categories as a classification destination candidate category.

  In the above description, the score of the category hit in the search by the search unit 40 is simply counted by the number of appearances. However, an optimal addition coefficient of the category score may be calculated. The addition coefficient determination unit 35 calculates an addition coefficient for each category linked to the search key in the pattern recognition dictionary 210, and performs processing for registering a list of pairs of categories and addition coefficients in the search key. The processing for calculating the addition coefficient of the category score by the addition coefficient determination unit 35 will be described in detail in section [3.2.2].

  When the category score addition coefficient is registered in the pattern recognition dictionary 210, the search unit 40 uses the addition coefficient registered in the pattern recognition dictionary 210 to store the category in the category candidate table 230. Are cumulatively added. The search unit 40 outputs the category with the highest score as the classification category of unknown data based on the score cumulatively added by the addition coefficient.

Embodiment 3
FIG. 3 is a configuration diagram of nearest point pair search apparatus 300 according to Embodiment 3. The nearest point pair search apparatus 300 according to the present embodiment outputs two pairs of input data that are close to each other when a set of input data is given. Specific processing will be described in section [4]. To do.

  The configurations of the orthogonal transform unit 10, the distributed representation generation unit 20, and the dictionary generation unit 30 of the closest point pair search device 300 are the same as those in the first embodiment, but the closest point search dictionary generated by the dictionary generation unit 30. 110 is not used as a database for searching, but is temporarily stored in the dictionary storage unit 72 and, after being used in the analysis unit 60, is appropriately deleted for effective use of the memory capacity.

  When the new input data label is registered by the dictionary generation unit 30 in association with the search key of the nearest point search dictionary 110, the analysis unit 60 determines whether the input data label is already registered in the search key. A pair is generated between them, the pair of labels is stored in the nearest point pair candidate table 330, and stored in the analysis result storage unit 82. The nearest point pair candidate table 330 stores the number of appearances of the label pair together.

  The analysis unit 60 rearranges the list of nearest point pairs stored in the nearest point pair candidate table 330 in descending order of the number of appearances, and outputs a list of nearest point pairs within a predetermined distance.

  Note that for the nearest point pair stored in the nearest point pair candidate table 330 by the analysis unit 60, the verification unit 50 may calculate the distance between the input data of the nearest point pair, that is, the inner product. The verification unit 50 may rearrange the list of nearest point pairs stored in the nearest point pair candidate table 330 in descending order of inner product values and output a list of nearest point pairs within a predetermined distance.

  Furthermore, when it is sufficient that the nearest point pair having the closest distance is obtained as an analysis result, the checking unit 50 causes the nearest point pair to be stored each time the nearest point pair is stored in the nearest point pair candidate table 330 by the analysis unit 60. Only when the inner product value of the nearest point pair obtained up to that point is larger than the inner product value, the nearest point pair and inner product value are stored in the analysis result storage unit 82. Otherwise, the nearest point pair is discarded. May be. If a newest point pair that gives a larger inner product value than the maximum inner product value obtained up to that point is obtained, the maximum value of the inner product is updated and the new nearest point pair is stored. The nearest point pair of is deleted. As a result, without providing the nearest point pair candidate table 330, it is sufficient to store only the nearest point pair that gives the maximum inner product value obtained up to that point and the inner product value, thereby saving the memory capacity.

  The details of the technology used in the embodiment of the present invention will be described below.

[1] Element set creation method [1.1] Preparation Data is composed of numerical values, items, and the like, and is expressed in binary in the computer. Data is sometimes called a vector, a point, or the like. In the nearest point search method and pattern recognition method, data prepared in advance is referred to as learning data, learning points, learning vectors, and the like. Unknown data may be referred to as unknown input, unknown data, or the like.

[1.1.1] Data type Data represented by a computer includes binary data and real number data. This corresponds mathematically to a binary vector or a real vector. For example, a binary vector (1, 0, ₁ , 0, ₁ , 1, 0, 0) can be expressed as 101011002 and 8-bit data. Real number vectors (10.5, 30.11, 4.02, and -1.5) can be generally represented by 32-byte data in a floating-point format on a computer.

Binary space A space created by a vector whose elements can have only 0 or 1 is called a binary space, and expressed as {0, 1} ^N. A binary space vector can be represented as N-bit data in a computer.

A space formed by a vector having a combination space binary space and k elements having the value of 1 is called a combination space and expressed as _N C _k . The vector of the combination space can be expressed as N-bit data in the computer.

- real spatial element is referred to as a space to create a vector to take a real-valued real space, to be referred to as R ^N. The vector of the real number space can be expressed as N pieces of real value data in the computer. For example, if a floating point format is used, it can be expressed by N × 8 bytes.

-Factorial space 0, 1, ..., N-1 substitutions made by N integers are used as vectors, and the whole is called factorial space. Will be written. For example, the five-dimensional factorial space has 120 pieces of (0, 1, 2, 3, 4), (0, 1, 2, 4, 3), ..., (4, 3, 2, 1, 0). This is the space created by the entire vector.

A factorial space vector can be represented as N integer data. If an integer type of 4 bytes is used, it can be expressed by N × 4 bytes. However, even a smaller number of bits can be expressed. Since ceil (log ₂ N) bits are sufficient to represent integers from 0 to N−1, the factorial space vector can be represented by N × ceil (log ₂ N) bits. Here, ceil is a function for rounding up.

-Spherical space When all the vectors in space are the same size, all the vectors are on the hypersphere centered on the origin. Such a space is called a spherical space.

- a float space real space, when the magnitude of all the vectors is 1, which is referred to as unit a real space, to be denoted by E ^N.

-Discrete space When the number of vectors in the space is finite, this is called a discrete space. A vector in this space can be represented by finite length bit data.

-Space by Bipolar Value In binary space and combination space, it is also possible to take +1, -1 instead of 0, 1 as vector element values. These are spherical spaces because they are on a hypersphere centered on the origin. This can be converted into a spherical space by expanding and contracting the original space having the {0, 1} value and moving in parallel.

  Similarly, the factorial space becomes a spherical space by taking the value of the element as 2k− (N−1) instead of k = 0 to N−1. For example, (0, 1, 2, 3, 4, 5) is converted to (-5, -3, -1, +1, +3, +5).

[1.1.2] Calculation of distance Euclidean distance is used to measure the distance between two pieces of data in space. Alternatively, it may conform to the Euclidean distance. For example, a Hamming distance may be used. If the data is a point in spherical space, the distance can be measured by finding the inner product value.

[1.2] Element representation of data When a vector is expressed by a set of many vectors, each vector constituting the set is called an element, and expressing the original vector in this way is an element representation. I will call it. The element needs to have a certain small angle with the original vector. Also, the elements need to be distributed evenly to some extent.

  Each element holds part of the information of the original data in some form, and has information equivalent to or almost equivalent to the original vector as a whole.

[1.2.1] Element creation method from discrete space An example will be described.
(A)
Assume that the data type is binary data of 32 bits. For example,
0000 0000 0000 0000 0000 0000 0000 0000 (1)
And
If the distance is 1 from this data,
1000 0000 0000 0000 0000 0000 0000 0000
0100 0000 0000 0000 0000 0000 0000 0000
...
0000 0000 0000 0000 0000 0000 0000 0001
The number is 32.
By doing so, the original data can be expressed by these 32 pieces of data. This is one example of element representation. When the original vector takes an arbitrary value of 32 bits, the value of each element can take 2 ³² different values.

In addition, for the data of (1), the data with distance 2 is
1100 0000 0000 0000 0000 0000 0000 0000
1010 0000 0000 0000 0000 0000 0000 0000
...
0000 0000 0010 0000 0000 0001 0000 0000
...
0000 0000 0000 0000 0000 0000 0000 0011
496 pieces. This can also be used as an element representation.

(B)
It is also assumed that the data type is binary data of 32 bits and the number of bits = 1 is 16. For example,
1111 1111 1111 1111 0000 0000 0000 0000 (2)
And
If the distance from this data is 3 and the number of bits = 1 is 13,
1101 1011 1111 1110 0000 0000 0000 0000
There are 560 in total. This can also be used as an element representation.

(C)
It is assumed that the data type is binary data of 32 bits. For example,
1111 1110 1100 1000 0000 0001 0011 0111 (3)
And
Select 4 bits out of 32 bits and set that bit as *.
**** 1110 1100 1000 0000 0001 0011 0111
Now select bits 0-3, bits 4-7, bits 8-11, bits 12-15, bits 16-19, bits 20-23, bits 24-27, bits 28-31, and each * Then, 8 elements are created. At this time, all the bits are selected equally once. There are many variations of this method. For example, it can be expressed by a larger number of elements.

(D)
Further, it is assumed that the data is a vector of an N-dimensional factorial space. This can be represented as an N-dimensional integer vector. For example, if N = 32,
(0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24 , 25,26,27,28,29,30,31) (4)
And
When 32 bits of data are created, 1 when the number of elements is 10 or more, and 0 otherwise.
0000 0000 0011 1111 1111 1111 1111 1111
It becomes.
Also, if the number is 17 or more, 1 is set, and other values are set to 0.
0000 0000 0000 0000 0111 1111 1111 1111
It becomes.
Also, if it is 25 or more, 2 if it is 15 or more, and 1 otherwise, 0.
0000 0000 0000 0001 1111 1111 1222 2222
It becomes.
If you have a lot of things like this, it becomes an element set. In that case, it may not be said that it is evenly distributed, but it can be made substantially uniform by combining with other methods.

[1.2.2] Element creation method from real vector [1.2.2.1] Conversion of data from real vector to discrete space Assume that the data is an N-dimensional real vector. A real vector can be converted into a vector in a discrete space with the closest angle. For example, conversion from a real vector to a binary space, a combination space, a factorial space, or the like can be easily performed.

Let the real vector be v = (v _i ) (i = 0 to N−1).
1 when v _i > 0
0 when v _i ≦ 0
Then, it can be set as binary space data and can be represented by N-bit data.

By selecting the largest k of v _i (i = 0 to N−1) and setting the bit to 1 and setting the other bits to 0, the data of the combination space can be obtained. I can express.

Now, arrange in order from the largest vector elements,
v _i0 , v _i1 , v _i2 ,..., v _iN−1
(I ₀ , i ₁ ,..., I _N−1 ) is a factorial space vector, which can be represented as bit data.

In addition, it can be converted into a vector of various discrete spaces. For example, in the 24-dimensional unit real space E ²⁴ ,
When v _i > cos (84.8 °) ≈0.09063, 2
When v _i > cos (−84.8 °) ≈−0.09063, 1
0 when v _i ≦ cos (−84.8 °)
Then, this can also be represented by bit data. This data can take a value of approximately 2 ²⁴ ways. This threshold is a value that divides the surface area of the 24-dimensional hypersphere into three equal parts by a plane perpendicular to the i-axis. Any other threshold can be used for data conversion, but what value is appropriate may be selected according to the actual problem.

Further, when the N-dimensional real vector is v = (v _i ) (i = 0 to N−1), it is assumed that v _i0 > v _i1 > v _i2 >...> V _iN−1 . At this time,
a ₀ = v _i0 −v _i1
a ₁ = v _i1 −v _i2
...
a _N−2 = v _iN−2 −v _iN−1
far. Arrange them in order from the largest,
a _j0 , a _j1 , a _j2 ,..., a _jN−2
(I ₀ , i ₁ ,..., I _N−1 , j ₀ , j ₁ ,..., J _N−2 ) is a vector of a discrete space.

  These are just a few examples, and there are still many ways to convert to discrete space. It is also possible to partially combine the methods described so far. By doing so, it can be converted into a vector in a discrete space. It can be inferred that there are countless conversion methods.

  Also, a random N × N orthogonal matrix is prepared, and this is R. Multiply the N-dimensional real vector v by R to make it Rv. Then, Rv can be converted into a discrete space. Since an infinite number of random orthogonal matrices can be created, it can be said from this that there are innumerable transformations into a discrete space.

[1.2.2.2] Multiple Discrete Spaces Assume that there are multiple discrete spaces. By converting from a real vector to a vector in each space, this can be an elemental representation. However, it is desirable to select a discrete space in which elements are evenly distributed to some extent.

For example, the following method is effective. Let Q be a discrete space. A large number of uniformly random orthogonal matrices are prepared, and these are assumed to be R ₀ , R ₁ ,..., R _r−1 . Let R ₀ (Q), R ₁ (Q),..., R _r-1 (Q) be a space where R can be applied to each point on Q. Element conversion can be made by conversion from the real vector v to R ₀ (Q), R ₁ (Q),..., R _r-1 (Q). Since these elements are present at random near v, when the number is increased to some extent, the bias is reduced and it can be considered that the elements are distributed almost evenly.

[1.2.3] Neighbors in discrete space Up to now, we have explained that the original vector is converted to only one vector with the smallest angle in the discrete space. It is also possible to choose a vector.

For example, now the vector is
It is assumed that (1, 2, 4, 5, 6, 8, 9, 10, 11, 12).
The closest 16 vectors in the binary space {-1, + 1} ^N are
(1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
(-1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
(1, -1, 1, 1, 1, 1, 1, 1, 1, 1)
(-1, -1, 1, 1, 1, 1, 1, 1, 1, 1)
(1, 1, -1, 1, 1, 1, 1, 1, 1, 1)
(-1, 1, -1, 1, 1, 1, 1, 1, 1, 1)
(1, 1, 1, -1, 1, 1, 1, 1, 1, 1)
(-1, 1, 1, -1, 1, 1, 1, 1, 1, 1)
(1, -1, -1, 1, 1, 1, 1, 1, 1, 1)
(1, 1, 1, 1, -1, 1, 1, 1, 1, 1)
(-1, -1, -1, 1, 1, 1, 1, 1, 1, 1)
(-1, 1, 1, 1, -1, 1, 1, 1, 1, 1)
(1, -1, 1, -1, 1, 1, 1, 1, 1, 1)
(-1, -1, 1, -1, 1, 1, 1, 1, 1, 1)
(1, -1, 1, 1, -1, 1, 1, 1, 1, 1)
(1, 1, 1, 1, 1, -1, 1, 1, 1, 1)
It becomes. These can be found by examining the magnitude relationship of each element of the vector, the binary sum of the elements, and the sum of the three terms.

For example, examples of [1.2.1] of (b) _is equivalent to choose from 32 _{C 16} space ₃₂ C ₁₃ upper 560 close points in space.

[1.2.4] Handling when the vector is not on the hypersphere A case where the vector is not on the hypersphere will be described. Now, assume that X is an N-dimensional real vector, and every element takes a value in the range of 0.0 to 10.0. That is, a point in the hypercube.
X = (x ₀ , x ₁ ,..., X _N−1 ) 0 ≦ x _i <10.0

At this time, choose an appropriate α,
Y = (y ₀ , y ₁ ,..., Y _2N−2 , y _2N−1 )
y _2i = cos (α × xi × 2 × π / 10)
y _{2i + 1} = sin (α × xi × 2 × π / 10)
Then, Y becomes a point on the hypersphere, and it is sufficient to perform database conversion and data retrieval by performing such conversion.

  Because, for the purpose of searching for close data, it is only necessary to preserve the local distance relationship. Therefore, when X1 and X2 are close, | Y1-Y2 | ≈α | X1-X2 | It can be seen that this conversion is sufficient.

(∵)
(Cosαa-cosαb) ² + (sinαa-sinαb) ²
= 2-2 (cosαa · cosαb + sinαa · sinαb)
= 2-2cos α (ab)
= 2-2 (1-2 sin ² α (ab) / 2)
= (2 sin α (ab) / 2) ²
When α (ab) / 2 is close to 0, it can be approximated as sin α (ab) / 2≈α (ab) / 2.
(2 sin α (ab) / 2) ²
≒ (2α (ab) / 2) ²
= Α ² (ab) ²

Therefore, √Σ (y _1j −y _2j ) ² ≈α√Σ (x _1i −x _2i ) ²
∴ | Y1-Y2 | ≈α | X1-X2 |

  In this way, in the case of a general real vector, mapping may be performed so that the distance relation is roughly preserved on the hypersphere. There are many other mappings that preserve the distance relations. Various methods can be used.

[1.3] Summary The method of creating an element set from various data types has been specifically described. There are a myriad of methods for creating elements, and they can be combined in various ways.

  It is necessary to create the elements so that the angle formed from the original data is at a small position, and the entire element is distributed evenly without any deviation. By doing so, it is possible to realize a method for quickly and accurately finding data or a category close thereto from given data. Details will be described later.

[2] Nearest point search method [2.1] Exact match search When a lot of data is given in advance and certain unknown data is presented, finding a match from the data is called an exact match search. Call. Methods for realizing such functions are well known, and various methods for performing high-speed search processing have been proposed.

  For a given data set, a data structure suitable for an exact match search is constructed in advance and data is stored. This is called a database. The database may be on disk or in memory. There are various processing methods for performing an exact match search.

  Well known algorithms for performing exact match searches when a database is in memory include binary trees, hashing, binary search, linear search, and direct address reference methods. One of them, the hash method, will be briefly described.

  FIG. 4 is a diagram illustrating an example of a hash table. Suppose that there are many pairs of birth dates and names. In the hash method, a sufficiently large hash table is prepared, a hash value is calculated from the date of birth, and the date of birth and name are stored at the address of the table. Considering the case where data of a person having the same date of birth is generated, in general, a link to the date of birth and name information is stored. Keep a separate storage location for your name. In this way, when an arbitrary date of birth is given, it is possible to realize a data structure in which the name of a person whose date of birth matches the date can be checked.

  The embodiment of the present invention realizes a function of searching for close data from a large amount of data at high speed when unknown data is given by using an exact search method. In the embodiment of the present invention, data can be expressed as a vector, and Euclidean distance is used as a measure of proximity. It may be based on the Euclidean distance.

[2.2] Nearest Point Search Method The closest point search method will be described. Data prepared in advance will be referred to as learning data, learning points, learning vectors, and the like. The unknown data is called unknown input, unknown data, etc.

[2.2.1] Description of an example of the nearest point search method in the _N C _k space Assume that all data is 32 bits in binary representation, and the number of bits = 1 is 16 . It is assumed that the number of learning data is 2 ²⁰ = 1048576. Each learning data is given a name (label). _Let it be L ₀ , L ₁ ,..., L _1048575 . The learning data is assumed to be uniformly distributed at random.

  At this time, the learning data is stored in the database as follows. As shown in FIG. 6, 14 out of 16 locations where the data bit = 1 is selected, and 32-bit data with only bit = 1 is created. Since there are 120 ways to create such combinations, 120 pieces of data can be created. This is element data. A set of element data and learning data labels is stored in the database using the element as a search key. This is performed for all 1048576 learning data. FIG. 5 shows an example of a basic data structure of a nearest point search dictionary in which a learning data element is used as a search key and a list of learning data labels is linked to the element.

  When unknown data is given, the nearest point search is performed as follows. It is assumed that the unknown data is 32 bits as in the learning data, and the number of 1 bits is 16. It is assumed that unknown data is generated uniformly at random. 120 elements are created for unknown data in the same manner as for learning data. That is, 120 pieces of 32-bit data in which the number of 1 is 14 can be created.

  Search the database using the element as a key. Thereby, the label of the learning data corresponding to the matching element can be acquired. The found learning data is within 4 distances from the unknown data. That is, there is only a difference of 4 bits at most from unknown data.

By searching the database for all 120 elements of unknown data, all data within a distance of 4 can be found.
Unknown data and distance = 0 appear 120 times in 120 searches.
Unknown data and distance = 2 appear 15 times in 120 searches.
Unknown data and distance = 4 appear once in 120 searches.
Therefore, if the number of appearances is totaled for each label, the data can be ranked in the order of the closest distance.

The probability that no data is found after the search is performed, that is, the probability that there is no data within a distance of 4 from unknown data is 7.86 × 10 ⁻¹² . Therefore, there is almost no possibility that close data cannot be found. On average, 25.6 data are found. The number of searches is 120, and the total number of search hits is about 32 on average.

  In this way, when unknown data is given, information of data close thereto can be ranked and obtained accurately and at high speed.

[2.2.2] Asymmetric search In the above explanation, the types of learning data and unknown data are the same, and the element creation method is the same. However, the types of learning data and unknown data are different, and the element creation method is different. Explain that the search can be performed even if they are different.

  Now, for the learning data, the example described above is used. It is assumed that the unknown data is 32 bits, and the number of 1 bits is 17. As shown in FIG. 6, 32-bit data in which 14 of 17 bits are set to 1 is created. There are 680. This is element data. Use this to search the database. In this way, all data within a distance of 5 from unknown data can be ranked and found accurately and at high speed.

  In the above description, if the number of unknown data is 32 bits and the number of bits = 1 is 16, and the data is not found even after 120 searches, the unknown data and the data of distance 2 are create. Since there are 16 numbers with a distance of 2 and bits = 1, there are 256 by 16 × 16 = 256. For each of these, 120 elements are created and searched. This makes it possible to find even very difficult data.

[2.2.3] {0, 1} Description of an example of the nearest point search method in the case of ^N space It is assumed that the learning data is 32 bits in binary representation. It is assumed that the number of learning data is 2 ²⁰ = 1048576. The learning data is assumed to be uniformly distributed at random. A supplementary explanation about the case where the data distribution is not uniform random will be given later.

  The element creation method will be described with reference to FIG. One element is the same as the data itself. This is the 0-element. Next, there are 32 types of data that differ from the data by one bit. This is also an element. Let this be a 1-element. Next, there are 496 types of data that differ from the data by 2 bits. This is also an element. This is a 2-element. Thus, 529 elements are created.

  Here, the database is divided into three. The database 0 stores the 0-element and learning data label information. Database 1 stores 1-element and learning data label information. The database 2 stores the information on the 2-element and learning data labels. The storing method in each database has already been described.

  It is assumed that unknown data is still 32 bits and is generated uniformly at random. The search is performed as follows. First, 0-element is created and database 0 is searched. If the data is found, it is a distance = 0 from the unknown data, ie the same data as the unknown data.

  If no data is found, the database 1 is searched. If data is found here, it is data for distance = 1. If not found, the database 2 is searched. If found here, it is the data of distance = 2.

  If neither is found, 32 1-elements are created next. Then, the database 2 is searched. If data is found, it is data for distance = 3.

  If not found, 496 2-elements are created and the database 2 is searched. If data is found, it is distance = 4 data.

  If not found, 4960 data different from the unknown data by 3 bits are created. That is, it should be called a 3-element. Then, the database 2 is searched. If data is found, it is distance = 5 data.

  If not found, similarly, 4-element, 5-element, 6-element,... Are sequentially created and the database 2 is searched. Thereby, data of distance = 6, distance = 7, distance = 8... Can be found.

In this method, when there are a plurality of recent points, all of them can be listed. It is possible to estimate the number of searches when searching by the above method. For example, when the closest point to the unknown input is distance = 4, the number of searches is 1 + 1 + 1 + 32 + 496 = 531 times. The probability that the nearest point does not exist within the distance = 4 is 1.79 × 10 ⁻²⁶ . Therefore, even in the worst case, the number of searches is almost certainly guaranteed to be 531 or less. The average number of searches is about 161.2.

[2.2.4] Case of non-uniform random So far, it has been estimated that the number of searches can be reduced under the assumption that the distribution of data is uniformly random.

  A case where the distribution is not uniformly random and the distribution is biased will be described. Even if the distribution of learning data is not uniformly random, it can be assumed that the probability distribution of learning data and unknown data is equal. Such assumptions may be used in many practical cases.

  When unknown data occurs in a place where learning data is sparsely distributed, the number of searches becomes larger than that in the case of uniform randomness. On the other hand, when unknown data occurs in a place where learning data is dense, the number of searches is smaller than in the case of uniform randomness. On average in all cases of occurrence of unknown data, the number of searches in the case of uniform randomness is smaller in any distribution.

[2.2.5] E ^N 1 example of description training data closest point search method in the case of space, and a 32-dimensional real vector with unknown data. In general, this can be expressed as bit data of 256 bytes or 128 bytes in the internal representation of the computer. It is assumed that all data are normalized to a size of 1. It is assumed that the number of learning data is 2 ²⁰ = 1048576. The learning data is assumed to be uniformly distributed at random. Let the learning data be x ⁱ (i = 0 to 1048575).

A large number of random 32 × 32 orthogonal matrices are prepared. For example, 100. These are named R-0 to R-99. The learning data is multiplied by the orthogonal matrix R-0. Let this be r ₀ x ⁱ . From r ₀ x, the closest 32 points in the ₃₂ C ₉ space are selected. These can be expressed as data having 32 bits and 9 bits = 1. This is an element.

  This operation is performed on all the learning data, and the element and learning data information is stored in the database 0. The same operation is performed on all remaining orthogonal matrices, and information is stored in Database 1 to Database 99, respectively.

Next, a method for retrieving data from unknown input will be described with reference to FIG. Let x ^* be an unknown input vector. Basically, elements for unknown data are created in the same way, and labels of learning data are taken out from the database 0 to the database 99, but there are parts that are different from the search method described so far. explain.

Assume that labels L7 and L20 are found in the first element search. As shown in FIG. 8A, labels L7 and L20 are added to the searched table. Calculate the inner product of x ^* and x ⁷ , x ^* and x ²⁰ . Assume that they are 0.70, 0, and 75, respectively. As shown in FIG. 8A, first rank = L20,0.75, second rank = L7,0.70 is entered in the rank table.

Next, it is assumed that labels L3, L7, and L35 are found in the second element search.
As shown in FIG. 8B, since the label L3 is not in the searched table, it is added to the table. Then, the inner product of x ^* and x ³ is calculated, and this is 0.80. As shown in FIG. 8 (b), L3 and 0.80 are entered in the first place of the order table, and the order of the second place or less is lowered.

Since L7 is in the searched table, the inner product calculation is not performed. Since L35 is not in the searched table, it is added to the table as shown in FIG. Then, to calculate the inner product of x ^* and x ^35, which when is assumed to be 0.72, as shown in FIG. 8 (b), enters the 3-position of the ranking table, drops repeatedly following order.

  FIG. 8C shows a state where the element search operation is performed several times. As the number of searches increases, there is a higher possibility that the correct answer will be placed in the first place in the ranking table, and there is a higher possibility that the second or lower place is in the correct order.

  When element search is performed 320 times, the probability of finding the closest point is about 50%. It is about 90% for 1024 searches, and approximately 0.999 when 3200 searches are performed.

  By this method, the following functions can be realized. Inaccurate answers are acceptable, so if you want to get information about any data close to unknown input in a short time, you can stop the search in a small number of times. When there is a margin in processing time, or when you want to get an accurate answer, perform a large number of searches. The more time you spend, the more accurate you can get. As described above, the property of adaptively adjusting the processing time and accuracy is practically effective.

[2.2.6] Method for Increasing Accuracy In the method described above, means for further improving accuracy will be described. One is to change the element creation method for the learning data, that is, to generally increase the number of elements. It is also effective to increase the number of orthogonal matrices. As a disadvantage, this increases the size of the database.

  The second method is to increase the number of elements of unknown data. The method described as an asymmetric search can be used. As a demerit, this increases the processing time.

  Appropriate parameters may be selected in accordance with the actual target processing.

[2.2.7] Method for Determining General Parameters In the above description, a specific element creation method has been described by giving a specific data type, number of dimensions, and number of learning data.

  The present invention is not limited to a particular problem state, and more generally can address each unspecified problem. For this purpose, parameters such as an appropriate element creation method may be determined according to the data type, the number of dimensions, and the number of learning data. As described above, there are innumerable various methods for creating elements.

  When the data type, the number of dimensions, and the number of learning data are given and the distribution of data can be assumed, values such as data size and search time can be theoretically calculated for each element creation method. Therefore, an appropriate parameter may be selected according to the target process. In realistic application situations, the distribution type of data is often unknown. In that case, parameters can be found experimentally using actual data.

  For an actual problem, an optimum parameter may be selected according to a required search speed, search accuracy, and usable data capacity.

[3] Pattern Recognition Method According to the present invention, it has been described that the nearest point search can be performed at a high speed from a large amount of data. However, this method can also be used for pattern recognition. Pattern recognition is a problem of determining which category the data is closest to when given unknown data. The set of categories is predetermined.

  A general pattern recognition method is to obtain a large number of sets of data and category labels (called learning data, teacher signals, etc.) and use that data for highly accurate recognition. Create a data structure in advance.

[3.1] NN (Nearest Neighbor) Method The NN method stores learning data in a dictionary, and when an unknown pattern is given, searches the dictionary to identify the closest data, The category corresponding to the data is returned as an answer.

  In the NN method, it is theoretically clear that the recognition rate can be increased to the limit by storing a large amount of learning data in a dictionary. However, it is well known that when a large amount of learning data is used in a dictionary, it takes a long time to search, so that the recognition speed is slow.

  In the embodiment of the present invention, as already described, the nearest point search can be performed at a high speed for a large amount of data, so that the recognition process of the NN method can be performed at a high speed. 9 and 10 show an example of a database structure for realizing the NN method in the embodiment of the present invention. FIG. 9 shows the data structure of a nearest point search dictionary in which an element of learning data is used as a search key and a list of data labels is linked to the element. FIG. 10 shows a correspondence table between data labels and categories of learning data. The NN method can be realized by performing a nearest point search using the nearest point search dictionary of FIG. 9 and referring to the table of FIG. 10 for the found nearest point and finding a corresponding category.

[3.2] Single layer identification structure [3.2.1] Database structure By modifying the method described above, another method for realizing pattern recognition can be constructed. The information from the element to the data label is stored in the database as it is, but the category label can be stored instead of the data label.

The merits of this method will now be described. Assume that link information from a certain element e1 to a data label is as follows.
e1 → L1, L3, L6, L8
Assume that the categories (category labels) corresponding to the data are as follows.
L1 → C1
L3 → C1
L6 → C4
L8 → C1

If category labels are stored in the database instead of data labels, duplicate information can be omitted.
e1 → C1, C4
Or you may hold | maintain the number which overlaps. In that case:
e1 → C1 × 3, C4 × 1

  Such data representation has the effect of reducing the size of the database. In a state where a lot of data label information is linked from one element on average, the number of search hits is larger than the number of searches, and this increases the processing time in the case of the nearest point search. However, although the number of data of the nearest point search in the present invention can be assumed to be tens of thousands to hundreds of millions, in the case of pattern recognition, the number of categories is usually about 2 to several thousand, so the processing time There is almost no problem.

  In the pattern recognition method, as in the closest point search, what kind of element set creation method is used may be selected for each specific problem.

[3.2.2] Score calculation method In the case of pattern recognition, the score is totaled for each category, and the category with the highest score is returned as an answer. Or return a column of categories in the order of the scores. The score may be calculated by searching for elements, adding one score for the hit category, repeating it for all elements, and calculating the total score. In addition, as shown in FIG. 11, if the category label and the addition coefficient are stored in the database as a pair, the addition coefficient may be added when a search hit occurs.

[3.2.2.1] Addition coefficient determination method (a)
Assume that a link from an element to category information is as follows.
e1 → C1, C4, C8
This expression is in a form in which the addition coefficient is omitted. In this case, when the search is hit, one point is added to each of the categories C1, C4, and C8.
(B)
e1 → (C1, 0.3), (C4, 1.2), (C8, 0.5)
The category and the addition coefficient are paired and stored in the database. In this case, an addition coefficient is added for each hit category.

  In general, the recognition rate can be improved in (b), but the method (a) has the effect of reducing the database size. An appropriate method may be selected according to the actual purpose.

  The addition coefficient is determined from the learning data when creating the dictionary so that the recognition performance is maximized. There are various methods for determining the addition coefficient. An example of the method will now be described.

  It is assumed that there is a large amount of data for learning now. Assume that the number of data used in the dictionary is fixed to a certain number nL, and nL data are randomly extracted from the learning data to create a dictionary in the (a) format. Since any number of operations for extracting nL data can be performed, a large number of dictionaries can be created.

  When a single dictionary is used to calculate the score, the same is done for many dictionaries, and the scores for all dictionaries are summed up for each category. Get better. The theory of this is called ensemble learning and is theoretically explained.

  Recognizing in many dictionaries means that the addition coefficient can be adjusted and combined into one dictionary.

  When one piece of data of category C1 is arbitrarily selected from the learning data, the probability that C1 is linked to a certain element e1 is Pr ((e1, C1)).

When creating a dictionary with nL learning data, the expected value to which the score is added is 1- (1-Pr (e1, C1)) ^nL . Therefore, when it is recognized by many dictionaries, it approaches this value on average.

The probability Pr ((e _j , C _k )) is _obtained for all the elements e _j and the category C _k . Actually, the estimated value can be obtained from the learning data obtained. Then, a dictionary is ^created with 1- (1-Pr (e _j , C _k )) ^nL as an addition coefficient. Test data is prepared and the recognition rate is investigated by changing nL. By finding the nL where the recognition rate is maximized, the optimum addition coefficient can be determined.

Hereinafter, a method for estimating the probability Pr ((e _j , C _k )) and determining the addition coefficient will be described in more detail.

  Assume that there are N learning samples. This is set as the learning sample parameter. A method of estimating the probability Pij that is associated with the i-th search key and the j-th category from N learning samples will be described.

Using N learning samples, the number of times the j-th category is associated with the i-th search key is tabulated. _Let this be K _ij .

The estimated value P _ij is
P _ij = K _ij / N
Given in.
According to the law of large numbers in statistics, the larger N, the better the estimated value.

Next, a method for creating and recognizing a dictionary using this _Pij will be described. Now, M pieces are randomly extracted from the group of learning samples having the parameter N. This is a learning sample for creating a dictionary.

When a dictionary is created using M learning samples, the probability that the j-th category is associated with the i-th search key in the dictionary is 1- (1-P _ij ) ^M.

When recognition is performed using a dictionary created with M learning samples, the expected value of the score is equal when the addition coefficient is 1- (1-P _ij ) ^M.

In a dictionary created with M learning samples, P _ij is obtained from a group of parameters N when recognition is performed by scoring when the addition coefficient is 1, and the addition coefficient is 1- (1-P _ij ). ^In the case of recognition by scoring when ^{M is} assumed, the latter generally has a better recognition rate. This is an effect of simple ensemble learning. That is, in general, there is an effect that the probability that the score of the correct category is lower than the score of the other category can be lowered to the limit.

Since the expression 1- (1-P _ij ) ^M that determines the addition coefficient is a monotonically increasing function with respect to P _ij , in reality, some monotonically increasing function f (P _ij ) is used instead. As a result, the recognition rate can be improved.

Now, when the addition coefficient is 1- (1-P _ij ) ^M , when the recognition rate is changed, there is a place where a convex curve is drawn upward and takes a maximum value. Therefore, when the value of M at this time is used and the function f (P _ij ) = 1− (1−P _ij ) ^M , the most excellent recognition performance can be realized.

However, the function f is simpler,
f (P _ij ) = P _ij ,
f (P _ij ) = K _ij
Or a linear function like
f (P _ij ) = 1 (P _ij > threshold = 0.3)
= 0 (P _ij <threshold = 0.3)
A threshold function such as This has the effect of speeding up the calculation time and reducing the dictionary size.

  There are various other methods for determining the addition coefficient. Algorithms that solve various optimization problems can be applied.

[4] Nearest Point Pair Search Method The nearest point pair search is a problem of searching for two nearest points from a given point set. As a derivative of this, there is also a problem of enumerating all pairs of points within a certain distance. The application examples are listed above.

[4.1] Examples of problems dealing with mutual distances between points-Even point placement problem Given a region and the number of points, place the points in that region to maximize the distance between the nearest points problem

• Finding abnormally close data For example, when a large number of airplanes are flying, the controller must monitor to avoid being too close to each other. This corresponds to the problem of finding all nearest point pairs within a distance that is a three-dimensional space. There are practical problems and higher-dimensional problems.

Detecting Chaos As one of analysis methods for finding some kind of law from a large number of multidimensional data, it is determined whether or not the data is chaotic. The GP method (Grassberger-Procaccia algorithm) is one method of chaotic detection and is also called a correlation integration method. From a certain point, the number of points within the radius r is counted. When r is changed, the number of points within the radius r increases along a certain curve. If N-dimensional data is completely random, an N-th order curve is obtained. If it is an increase curve of a smaller order, it may be chaotic.

・ Clustering Divide a large number of points into several groups.

[4.2] Nearest Point Pair Search Algorithm The basic concept of the nearest point pair search is the same as the nearest point search method in terms of meaning. A dictionary is created from the given point set, and the nearest point is searched using the given point set for all the given point set, and finally a set of points with the shortest distance is obtained. However, the algorithm is slightly different.

[4.2.1] Example of ₃₂ C ₁₆ Space A set of data is {x _i }. It is assumed that all data is 32 bits and the number of bits = 1 is 16. From x _i, 14 out of 16 locations where bit = 1 are selected, and 32-bit data with bit = 1 is created only there. 120 data can be created. This operation is performed for all data.

Now, prepare an empty database and store the elements and data labels sequentially. 12A to 12D are views for explaining a dictionary and a closest point pair candidate table generated in the process of searching for a closest point pair.
(1) Now x ₂ is to include an element a as an element representation. At this time, the data label L2 is linked from the database location a (FIG. 12A).
(2) _{x 4} also to contain elements a. Location a is linked to L2. At this time, the pair of L2 and L4 is stored in the table. L4 is then linked to L2 in the database (FIG. 12B).
(3) _{x 5} also to contain elements a. Since links L2 and L4 can be found from the location a, (L2, L5) and (L4, L5) are stored in the table (FIG. 12 (c)). If the same table already exists, the number of appearances is recorded.

  The same processing is performed for all data. FIG. 12 (d) is a diagram showing the progress of the process. If it is performed for all the data, the table can obtain the final information of the data pair and the number of appearances.

_In the present example where 120 elements of ₃₂ C ₁₄ are created in ₃₂ C ₁₆ space, all pairs of data within a distance ≦ 4 can be listed. At this time, the number of appearances is 120 for the distance = 0, the number of appearances = 15 for the distance = 2, and the number of appearances = 1 for the distance = 4.

  In this case, it is an explanation of an algorithm of a type that finds all pairs of points within a certain distance.

[4.2.2] Example of {0, 1} ³² The data set {x _i } is 32-bit data. First, the elements of those from _{x i} distance = 0 and 1, the algorithm as described in [4.2.1], find data pairs. What can be found at this time is one with distance = 0,1,2. If the data set cannot be found, there is no nearest point pair within a distance ≦ 2.

Next, the elements of those from x _i distance = 1 and 2, the same procedure. What can be found at this time is one at distance = 2,3,4.

If the data set is not found, next, the elements of those from x _i in the distance = 2 and 3, the same procedure. What can be found at this time are those of distance = 4, 5, 6.

  In this case, the distance between the nearest points is not specified, and the algorithm is a type that always finds the answer.

[4.2.3] Example in Real Spherical Space Let {x _i } be a point set in an N-dimensional unit real spherical space. An appropriate quantization space Q is prepared. A large number of uniform random N × N orthogonal matrices are prepared. If Q is transformed by this, any number of quantization spaces can be created. In implementation, {x _i } may be converted instead of Q, but the meaning is the same.

Each x _i is multiplied by an orthogonal matrix R ₁ . Let this be r ₁ x _i . Quantize r ₁ x _i with Q. Let this be q (r ₁ x _i ). This is an element. Similarly to [4.2.1], q (r ₁ x _i ) and Li are stored in the database.

  FIGS. 13A and 13B are diagrams for explaining a dictionary generated in the process of searching for a nearest point pair and a nearest point pair candidate table storing inner product values. As shown in FIG. 13A, it is assumed that L31 and L89 are stored at the location a. At this time, the inner product (x31, x89) is calculated. As shown in FIG. 13B, the table stores a pair of points and an inner product value, although the inner product value is higher. If the purpose is to obtain a solution of only one nearest point pair, an area for storing only one pair showing the maximum inner product value may be prepared.

When the processing up to this point is completed for all x _i , the same processing is performed using another orthogonal matrix R ₂ . At that time, the information of the table obtained so far is kept as it is and used continuously.

R ₁ , R ₂ , R ₃ ,... And the number of times that are statistically sufficiently reliable. The pair of points obtained in this way having the maximum inner product is the closest point pair.

For example, let {x _i } be a point in a 20-dimensional real spherical space. Let R be a 20 × 20 orthogonal matrix. Rx ₁ and Rx ₂ may or may not be the same 20-bit data by quantizing to {0, 1} ²⁰ . The closer the distance between x1 and x2, the higher the probability of being the same. If a large number of uniform random orthogonal matrices are prepared and the number of trials is increased, the probability that one or more cases of 20-bit data with matching pairs of closest points will be very close to 1.

[4.2.4] Features of the nearest point pair search type algorithm The nearest point pair search type algorithm differs greatly from the nearest point search method and pattern recognition method in that the data area used is in the order of the number of points. It is only necessary.

Assuming that the number of points is NP, for example, if a hash table is used, the table size may be about NP × 1.5 to 2.0. On the other hand, the nearest point pair search method requires a data area proportional to 2 ²⁰ × 120 when the score is 2 ^{20 in} ₃₂ C ₁₆ space.

  In addition, an algorithm such as [4.2.3] can dynamically change the quantization space. In general, the smaller the size of | Q | is, the easier it is to find a pair of points, but many pairs are found. If Q is appropriately changed during the process, fewer pairs are found, leading to a reduction in calculation time.

[5] Embodiment As an embodiment, pattern recognition by distributed coding will be described. A model of learning / recognition method by distributed coding is constructed and given consideration. In this method, the recognition time does not depend on the number of learning samples and is a constant time. In the simplest model of this method, the learning time is proportional to the number of learning samples. Therefore, learning from a large number of samples is possible, and application to a complicated pattern recognition problem can be expected.

[5.1] Basic Principle of Pattern Recognition by Distributed Coding [5.1.1] Distributed Expression of Vector Consider a space on an N-dimensional hypersphere centered at the origin as a pattern vector space. That is, the size of an arbitrary vector on the pattern space is assumed to be constant. Now, consider that the pattern vector x is divided into a plurality of vectors. That is, by a plurality of vectors,
x = αΣe _j (j = 0,..., N _e −1) (5.1)
Consider an expression by a set of vectors {e _j } such that This is referred to as a distributed representation of x by {e _j }.

Let Q be a discrete hyperspherical space. Select the top p items that are close to x at point Q. This is called a p-neighbor point on Q of x, and is expressed as Q (x, p). A plurality of such spaces for creating neighborhood points may be prepared. Now, when Q _k (x, p _k ) is created from N _Q different spaces Q ₀ ,..., Q _NQ−1 , Σp _k points are selected as a whole.

Neighboring points are distributed around x in meaning. This is (the _{N e} = _{Σp k)} has become distributed representation of the presented x in the equation (5.1).

  In order to enhance the effect of pattern recognition described later, the space Q is selected so that | Q | is a very large number. p is a small number.

  This method implicitly uses the principle of orthogonality in a high-dimensional space and the principle that if the distribution is dense, points are statistically stable in the vicinity. One of the associative memory methods using such properties is Canelva's sparse distributed memory described in [6].

[5.1.2] Example of distributed representation In order to perform distributed representation, the original pattern vector space may be any space on the hypersphere, and there are numerous ways to select Q and p. It is in. Here is a simple example. The following symbols that define a specific space are used.

・ Binary space:
{0, 1} ^N ≡ {x | x = (x _i ), x _i ε {0, 1}, i = 0,..., N−1}
{−1, + 1} ^N ≡ {x | x = (x _i ), x _i ∈ {−1, + 1}, i = 0,..., N−1}

・ Combination space:
_N C _k ≡ {x | x∈ {0,1} ^N , | x | = k}
_N C _k ^± ≡ {x | x∈ {−1, + 1} ^N , | x | = 2k−N}

・ Floor space:
N! = {X = (x ₀ , x ₁ ,..., X _N−1 ) |
x _i ∈ {0, 1,..., N−1}, x _i ≠ x _j (i ≠ j)}
N! ^± = {x = (x ₀ , x ₁ ,..., X _N−1 ) |
x _i ε {2k−N + 1} (k = 0,..., N−1), x _i ≠ x _j (i ≠ j)}

Example 1
x∈ _N C _{N / 2} , Q = _N C _{N / 2−d / 2}
Since there are _{N / 2} C _{N / 2−d / 2} hamming distances at the point from x to Q, Q (x, _{N / 2} C _{N / 2−d / 2} ) is This is a distributed representation of x.
x = (2 / _{N / 2} C _{N / 2-d / 2} ) Σe _j , e _j ∈ _N C _{N / 2-d / 2}
For example, ₃₂ C ₁₆ vectors can be represented by a distributed representation of 120 ₃₂ C ₁₄ vectors.

Example 2
x∈N! ^{_{±, Q k = N C 1}} ±, N C 2 ±, ..., N C N-1 ±
From x, nearest points to _N C ₁ , _N C ₂ ,..., _N C _N−1 are obtained. In this way, a distributed expression with N-1 vectors is obtained.

[5.1.3] Pattern recognition method This section shows the basic method of pattern recognition using expressions as described in the previous section.

Since Q (x, p) is a subset of Q, it is an element of 冪 set 2 ^Q. That is, Q (x, p) can be expressed as an element of {0, 1} ^{| Q |} . When creating each of these from N _Q spaces Q _k , all the elements of these vectors are lined up to give a very high-dimensional binary vector:
b = (b _i ) ∈ {0, 1} ^{Σ | Qk |}
Can be made.

This is equivalent to mapping x to a very high dimensional space. Whatever the distribution of the original pattern, linear separation is always possible if it is mapped to a very high-dimensional space whose dimension is higher than the number of samples. Therefore, as shown in FIG. 14, a virtual single-layer discriminant function having Σ | Qk | input layers and N _C output layers can be constructed. Here, the category is Cj (j = 0,..., N _C −1).

The recognition of the unknown pattern x converts x to b,
score (x, C _j ) = Σb _i w _ij (5.2)
Calculate
k = argmax {score (x, C _j )}
The category Ck becomes the recognition result. score () corresponds to the similarity and will be referred to as a score here.

In this structure, a weighting factor w _ij that can completely identify the learning sample can be easily determined.

_Initially , all w _ij are set to 0. The learning sample x belonging to the category C _j is converted into b. When the element b _i of b is 1, w _{ij is set} to 1. This is performed for all learning samples. Since the score is always a perfect score for the learned pattern, it is always correct except when the scores of multiple categories are full and equal.

The dictionary only needs to be able to store information on i and j where w _ij = 1. Further, the calculation of the score only needs to be able to determine whether w _ij where b _i = 1 is 0 or 1. Now, assuming that the number of learning samples is _NL , there is an algorithm that creates a dictionary that satisfies these requirements, has a learning time of O (N _e × N _L ), and a recognition time of O (N _e ). To do. The dictionary size is less than O (N _e × N _L ). That is, the learning time is proportional to the number of learning samples, and the recognition time is a constant time without depending on the dictionary size.

[5.2] Recognition experiment by distributed coding and improvement of learning method [5.2.1] Improvement of weighting coefficient The structure of this method is a high-dimensional linear discriminant function as shown in equation (5.2). Therefore, it is conceivable to adjust the weighting coefficient w. In this section, the concept of simple ensemble learning is applied.

It is assumed that there are a large number of samples and these follow a true distribution. From this, N _L samples are randomly extracted to create a dictionary. A large number of dictionaries can be created by repeating the operation of taking out N _L samples many times independently. If recognition is performed in each dictionary and the sum of the obtained scores is used as a final recognition result, generally, the recognition rate is better than when recognition is performed with one dictionary.

In this case, the expected value of the score of each category is calculated. Now, when one pattern x belonging to category C is randomly extracted and a dictionary is created, the probability that w _ij = 1 is set as p _ij , and when x is converted to b = (b _i ),
p _ij = Pr (b _i = 1 and C = C _j )
It becomes.

N _L pieces of the probability of _{w ij} = 1 when you create a dictionary in the sample can _be written and use the _{p ij 1- (1-p ij} ) NL.

Therefore, the limit when averaging the recognition results from a large number of dictionaries is that the input pattern is x ^* → B ^* = (b _i ^* ).
E [score (x ^* , C _j )] = Σb _i ^* E [w _ij ] = Σb _i ^* (1- (1-p _ij ) ^NL )
It becomes.

Eventually, as shown in FIG. 15, one linear discriminant function in which the weight coefficient w _ij is 1- (1-p _ij ) ^NL can be obtained.

  By doing so, the storage area does not increase and the recognition speed can be equivalent to a simple algorithm.

In reality, the true appearance probability p _ij cannot be obtained, but since the approximate value p _ij ^ can be known from a large number of samples, this is used. In order to determine the optimum N _L , test data is prepared in addition to the learning sample data. Since there is a place where the maximum value of the recognition rate is obtained when N _L is changed, it is easy to search for the optimum value.

Note that when the number of samples is increased and the estimated value p _ij ^ approaches a true value, the optimal _NL decreases monotonically, and the sample of the saturation point of learning in the basic algorithm shown in section [5.1.3] Converge to a number. At this time, the recognition rate at the limit of the learning sample reaches a limit value that does not increase any more, and generally the best recognition rate cannot be reached. Nevertheless, a certain degree of effectiveness can be recognized in real applications. Such a structure in which the weight coefficient is adjusted by a function of the appearance frequency is called an improved algorithm.

[5.3] Summary A series of pattern recognition algorithms by distributed coding was presented. The algorithm properties are summarized below.

  -The dictionary has a single-layer identification structure, and recognition can be performed at high speed. Similarities are found for all categories. It can be applied to many categories of identification problems.

  -Basic algorithm: Learning can be performed by referring to all learning samples once. The dictionary has a single-layer identification structure, and weighting factors are 0 and 1. Saturation of learning may occur.

  -Improved algorithm: Learning is fast. The weight coefficient is a function of the appearance frequency of the element and takes a real value. The learning peak may occur.

  The recognition speed is not affected by the number of learning samples and is high speed. Therefore, by learning a large number of samples, a program with a high recognition rate and a high recognition speed can be realized.

[6] Difference from Kanelva's sparse distributed memory The difference between the distributed coding technique used in the embodiment of the present invention and Kanerva's sparse distributed memory will be supplemented. In the sparse distributed memory, a large number of random points are dispersed in a spherical space, and the written information is read and integrated for points within a distance r from x, thereby asymptotically determining the closest point of x. I will recall. Details of sparse distributed memory are described in P. Kanerva, "Sparse Distributed Memory", MIT Press, November, 1988.

Example of Canelva's sparse distributed storage Here, N, N ′, and X are symbols representing sets. Let x and y be points.
Let N = {0, 1} ¹⁰⁰⁰ . A set of points on which one million points are randomly selected on N is N ′. This is called a hard location. A set X of 10,000 N points is set as learning data.

[6.1] Writing of data The information of x is written to all N ′ points within the Hamming distance 451 from x where x∈X. When multiple X points write to the same hard location, the {0, 1} ¹⁰⁰⁰ points that are closest to the average of the points, more precisely the average of all points written, are written.

[6.2] Reading data Let y be an unknown point. Information on all points N ′ within a Hamming distance 451 from y is read out and averaged to obtain W ¹ (y). Do the same for W ¹ (y). This is defined as W ² (y). If this is repeated, W ^t (y) converges to a certain point. This is the closest point from y to X.

[6.3] Difference between Embodiment of the Present Invention and Sparsely Distributed Storage (1) In sparsely distributed storage, all points N ′ within a distance 451 to be written to or read from a certain point x are efficiently processed. There is no algorithm to find out. A normal computer cannot be processed efficiently, and a neurocomputer capable of parallel processing is required.

  (2) There are approximately 1000 N ′ points within a Hamming distance 451 from a certain point. This corresponds to an element expression that expresses a vector by N ′ 1000 neighboring points. However, the Hamming distance 451 corresponds to N ′ of 0.001. This is a very large number for a 1000-dimensional space. The angle formed with respect to the point of the Hamming distance 451 in 1000 dimensions corresponds to about 84.376 °. The mutual positional relationship between two points x and y whose angle formed from a point a is within 84.376 ° is such that the angle formed is 0 ° to 168.752 °. That is, very distant points share an element.

On the other hand, in the example of the ₃₂ C ₁₆ space of [2.2.1] in the embodiment of the present invention, since the number of elements is ₁₆ C ₁₄ out of the ₃₂ C ₁₄ space, 120/471435600 = 0.000000254 is small. Become a number. Such a small ratio has the effect of reducing the hit data, and the calculation time can be increased. Because the angle between the input data and the element is 28.955 °, the angle between the two points sharing the element is in the range of 0 ° to 57.91 °, and the element is shared only with a close point. It is.

  (3) When writing a plurality of data at the same address, the average value of all data is written in sparse distributed storage. On the other hand, in the present invention, a plurality of data are all stored in the link format. However, although it is called "link format", it does not necessarily take a link format in a narrow sense. For example, there is an open address method for the hash method. The meaning is exactly the same as the link format.

  The present invention has been described based on the embodiments. It is understood by those skilled in the art that these embodiments are exemplifications, and that various modifications can be made to combinations of the respective constituent elements and processing processes, and such modifications are also within the scope of the present invention. By the way.

  Such a modification will be described. In the embodiment, as the application field of distributed coding, the closest point search, the pattern recognition, and the closest point pair search are given, but the application field is not limited to this. For example, the present invention can be applied to an associative memory type data search method. In the associative memory type data search, the search target vector is X (t), and the initial state is X (0) = X. In the search, let X (t + 1) be the average vector of all found elements. If this is repeated, X (t) converges to a certain vector. This is the search result. In the associative memory type search, it is possible to search past case data for a newly generated case and determine an optimum action. At this time, it is possible to comprehensively judge from a plurality of candidates. In addition, the accuracy of determination can be changed according to processing time constraints. For example, even in an emergency, it is possible to make a robot that does not break down and performs adaptive behavior.

  In the embodiment, the input data is converted by a plurality of orthogonal matrices to generate a large number of distributed representations of the input data. However, the input data may be converted by a random matrix without using a strict orthogonal matrix. . Although the accuracy is reduced, it can be expected to be statistically stable by transforming with a large number of random matrices.

  The verification in the nearest point search and the nearest point pair search may or may not be necessary depending on the application and purpose. In the case of real number data, even if it reaches the first place in the score, it is not always the correct answer, and it is impossible to know if it is really correct or not. Therefore, in most cases, it is necessary to check, but depending on the purpose, it may not be necessary. For example, since an incomplete search may be performed, there is a case where it is desired to search for data close to the presented data. This is the case when an object such as associative memory or idea support is used, or when it is used in a processing system having real-time characteristics that must be determined dynamically within a limited time.

  In addition, if a search result such as 50 points for the first place, 1 point for the second place, 1 point for the third place and 0 points for the third place or less after 100 trials, there is no need to check and statistically Almost absolutely, the data with the highest score can be determined to be correct.

  In addition, the problem of handling the mutual distance between points is not always verified. In the point distribution problem, priority is given to finding a large number of pairs that are considered to be close to each other without being checked at first.

1 is a configuration diagram of a nearest point search device according to Embodiment 1. FIG. FIG. 3 is a configuration diagram of a pattern recognition apparatus according to a second embodiment. FIG. 10 is a configuration diagram of a nearest point pair search apparatus according to Embodiment 3. It is explanatory drawing of a hash table. It is a figure which shows the basic data structure of the dictionary for nearest point search which linked the list of the label of learning data to the element by using the element of learning data as a search key. It is a figure explaining the method of producing element data from learning data. It is a figure explaining the method of producing element data from learning data. It is a figure explaining the method of searching the learning data nearest to unknown data. It is a figure which shows the data structure of the nearest point search dictionary which linked the list | wrist of a data label to the element by using the element of learning data as a search key. It is a figure which shows the correspondence table of the data label and category of learning data. It is a figure which shows the data structure of the dictionary for pattern recognition which linked the list of the category label and the addition coefficient pair to the element by using the element of learning data as a search key. It is a figure explaining the dictionary produced | generated in the process of a nearest point pair search, and a nearest point pair candidate table. It is a figure explaining the dictionary produced | generated in the process of a nearest point pair search, and the nearest point pair candidate table which stored the inner product value. It is a figure explaining the high-dimensional single layer discriminant function model by distributed expression. It is a figure explaining the dictionary structure equivalent to many dictionaries.

Explanation of symbols

  DESCRIPTION OF SYMBOLS 10 Orthogonal transformation part, 20 Distributed expression production | generation part, 30 Dictionary production | generation part, 35 Addition coefficient determination part, 40 Search part, 50 Verification part, 60 Analysis part, 70 Database, 72 Dictionary storage part, 80 Search result storage part, 82 Analysis Result storage unit, 100 nearest point search device, 110 nearest point search dictionary, 130 nearest point candidate table, 200 pattern recognition device, 210 pattern recognition dictionary, 230 category candidate table, 300 nearest point pair search device, 330 nearest point pair Candidate table.

Claims (10)

A data conversion unit that converts learning data represented as points in a real space created by a real vector whose real values can be taken by each component by a random matrix;
Of the finite number of points arranged in the discrete space, by selecting at least one point closest to the converted learning data in order from the closest one , obtain at least one neighboring point of the converted learning data , A distributed representation generating unit that generates a distributed representation of the learning data representing learning data by the at least one neighboring point ;
A dictionary generation unit that generates a dictionary using each of the at least one neighboring points in the generated distributed representation as a search key;
The data conversion unit converts the learning data using a plurality of different random matrices and provides the distributed representation generation unit, and the distributed representation generation unit sequentially selects the points closest to the converted learning data in order from the closest one. by at least one selected by generating at least one obtains a point near, distributed representation of the training data representing the learning data the at least one near point learning data after conversion, the training data A database generating apparatus, wherein a plurality of distributed expressions are generated for each of the plurality of distributed expressions, and the dictionary is generated for each distributed expression. The database generation apparatus according to claim 1, wherein the dictionary generation unit generates a dictionary in which identification information of a category in which the learning data is to be classified is associated with the search key. A data conversion unit that converts learning data represented as points in a real space created by a real vector whose real values can be taken by each component by a random matrix;
Of the finite number of points arranged in the discrete space, by selecting at least one point closest to the converted learning data in order from the closest one , obtain at least one neighboring point of the converted learning data , A distributed representation generating unit that generates a distributed representation of the learning data representing learning data by the at least one neighboring point ;
A dictionary generation unit that generates a dictionary using each of the at least one neighboring point in the generated distributed representation as a search key, and associates the identification information of the learning data with the search key and registers the dictionary in the dictionary. See
The data conversion unit converts the learning data using a plurality of different random matrices and provides the distributed representation generation unit, and the distributed representation generation unit sequentially selects the points closest to the converted learning data in order from the closest one. The learning data is obtained by obtaining at least one neighboring point of the converted learning data by selecting at least one and generating a distributed representation of the learning data in which the learning data is represented by the at least one neighboring point. A database generating apparatus , wherein a plurality of distributed expressions are generated for each of the plurality of distributed expressions, and the dictionary is generated for each distributed expression . A data conversion unit that converts learning data represented by points in a real space created by a real vector whose values that each component can take are real numbers, using a random matrix;
Of the finite number of points arranged in the discrete space, by selecting at least one point closest to the converted learning data in order from the closest one , obtain at least one neighboring point of the converted learning data , A distributed representation generating unit for generating a distributed representation of the learning data representing learning data by the at least one neighboring point ;
A dictionary having each of the at least one neighboring points in the generated distributed representation as a search key is generated, and identification information of a category into which the learning data should be classified is associated with the search key and registered in the dictionary. A dictionary generator,
Based on the learning sample set of learning data whose classification category is known, the number of times P _{ij associated} with the i-th search key in the dictionary is tabulated, and P _ij Using the function f (P _ij ) that increases monotonically, the addition coefficient of the score at the time of classification is obtained, and this addition coefficient is associated with the i-th search key in the dictionary. And an addition coefficient determination unit that registers in association with the identification information of
The data conversion unit converts the learning data using a plurality of different random matrices and gives the distributed representation generation unit, and the distributed representation generation unit sequentially selects the points closest to the converted learning data in order from the closest one. The learning data is obtained by obtaining at least one neighboring point of the converted learning data by selecting at least one, and generating a distributed representation of the learning data in which the learning data is represented by the at least one neighboring point. A database generation apparatus , wherein a plurality of distributed expressions are generated for each of the expressions, and the dictionary is generated for each distributed expression . A data conversion unit that converts input data represented by points in a real space created by a real vector whose values that each component can take are real numbers, using a random matrix;
Of the finite number of points arranged in the discrete space, by selecting at least one point closest to the input data after conversion in order from the closest one , obtain at least one neighboring point of the input data after conversion , A distributed representation generation unit for generating a distributed representation of the input data representing the input data by the at least one neighboring point ;
A dictionary generating unit that generates a dictionary using each of the at least one neighboring point in the generated distributed representation as a search key, and associates the identification information of the input data with the search key and registers the dictionary in the dictionary;
When identification information of new input data is registered in the dictionary in association with a search key, an identification information pair is generated with the identification information of the input data already registered in the search key, and the identification look including an analysis unit to be stored in a table together with the number of occurrences of the pair information,
The data conversion unit converts the input data by a plurality of different random matrices and provides the distributed representation generation unit, and the distributed representation generation unit sequentially selects the points close to the converted input data in order from the closest one. By selecting at least one, at least one neighboring point of the input data after conversion is obtained, and by generating a distributed representation of the input data in which the input data is represented by the at least one neighboring point, the input data A data analysis apparatus characterized in that a plurality of types of distributed representations are generated for each and the dictionary is generated for each distributed representation . A dictionary generated by the database generation device according to claim 1 for each of a plurality of distributed representations for registered data represented as points in a real space created by a real vector whose values that each component can take are real numbers. A dictionary with each of the at least one neighboring points in each distributed representation of the registration data as a search key;
A data conversion unit that converts input data represented by points in a real space created by a real vector whose values that each component can take are real numbers, using a random matrix;
Of the finite number of points arranged in the discrete space, by selecting at least one point closest to the input data after conversion in order from the closest one , obtain at least one neighboring point of the input data after conversion , A distributed representation generation unit for generating a distributed representation of the input data representing the input data by the at least one neighboring point ;
A search unit that searches the dictionary using each of the at least one neighboring point in the generated distributed representation as a search key;
The data conversion unit converts the input data by a plurality of different random matrices and provides the distributed representation generation unit, and the distributed representation generation unit sequentially selects the points close to the converted input data in order from the closest one. By selecting at least one, at least one neighboring point of the input data after conversion is obtained, and by generating a distributed representation of the input data in which the input data is represented by the at least one neighboring point, the input data A database search device, wherein a plurality of distributed expressions are generated for each of the plurality of distributed expressions, and the dictionary is searched using each of the at least one neighboring points as a search key for each distributed expression. The dictionary is obtained by associating a list of identification information of categories to which the registration data is classified with the search key,
The search unit stores the identification information of the category in the list that has been hit by a search using each of the at least one neighboring points in each distributed representation of the input data as a search key together with a cumulative hit number in a table. The database search apparatus according to claim 6, wherein the database search apparatus is a database search apparatus. A dictionary generated by the database generation device according to claim 3 for each of a plurality of distributed representations for registered data represented as points in a real space created by a real vector whose values that each component can take are real numbers. A dictionary in which each of the at least one neighboring points in each distributed representation of registration data is used as a search key, and a list of identification information of the registration data is associated with the search key;
A data conversion unit that converts input data represented by points in a real space created by a real vector whose values that each component can take are real numbers, using a random matrix;
Of the finite number of points arranged in the discrete space, by selecting at least one point closest to the input data after conversion in order from the closest one , obtain at least one neighboring point of the input data after conversion , A distributed representation generation unit for generating a distributed representation of the input data representing the input data by the at least one neighboring point ;
A search unit that searches the dictionary using each of the at least one neighboring point in the generated distributed representation as a search key, and stores identification information of the registered data in the list that has been hit in a table ,
The data conversion unit converts the input data by a plurality of different random matrices and provides the distributed representation generation unit, and the distributed representation generation unit sequentially selects the points close to the converted input data in order from the closest one. By selecting at least one, at least one neighboring point of the input data after conversion is obtained, and by generating a distributed representation of the input data in which the input data is represented by the at least one neighboring point, the input data A database search device , wherein a plurality of distributed expressions are generated for each of the plurality of distributed expressions, and the dictionary is searched using each of the at least one neighboring points as a search key for each distributed expression .   It further includes a verification unit that obtains a value related to a distance between the registered data hit by the search by the search unit and the input data, and stores the value related to the distance in the table together with identification information of the registered data hit. The database search device according to claim 8. A dictionary generated by the database generation device according to claim 4 for each of a plurality of distributed representations for registered data represented as points in a real space created by a real vector whose values that each component can take are real numbers. Each of at least one neighboring point in each distributed representation of registration data is used as a search key, and the search key includes a pair of identification information of a category to which the registration data is classified and an addition coefficient of a score at the time of classification A dictionary associated with lists,
A data conversion unit that converts input data represented by points in a real space created by a real vector whose values that each component can take are real numbers, using a random matrix;
Of the finite number of points arranged in the discrete space, by selecting at least one point closest to the input data after conversion in order from the closest one , obtain at least one neighboring point of the input data after conversion , A distributed representation generation unit for generating a distributed representation of the input data representing the input data by the at least one neighboring point ;
The dictionary is searched using each of the at least one neighboring point in the generated distributed representation as a search key, and the identification information of the category in the list that has been hit is stored in a table together with the cumulative value of the addition coefficient And a search section to
The data conversion unit converts the input data by a plurality of different random matrices and provides the distributed representation generation unit, and the distributed representation generation unit sequentially selects the points close to the converted input data in order from the closest one. By selecting at least one, at least one neighboring point of the input data after conversion is obtained, and by generating a distributed representation of the input data in which the input data is represented by the at least one neighboring point, the input data A database search device , wherein a plurality of distributed expressions are generated for each of the plurality of distributed expressions, and the dictionary is searched using each of the at least one neighboring points as a search key for each distributed expression .

Images