JP7054108B2 - Solution search system and method - Google Patents

Description

The present invention relates to a solution search system and a method suitable for searching a test object that is expected to output the best result among a plurality of test objects that output results based on a probability distribution.

In recent years, artificial intelligence (AI) -related technologies have been rapidly developing. In machine learning utilizing this artificial intelligence, reinforcement learning is important along with a technique called deep learning that demonstrates excellent abilities in image recognition and the like. Reinforcement learning is a method of learning through trial and error in an unknown environment. As one of the themes to which reinforcement learning can be applied, bandit is a typical example of the problem of searching for a solution that maximizes the expected value. There is a problem (see, for example, Non-Patent Document 1). This bandit problem aims to maximize the expected value of the total reward received, and the player repeats the action of selecting one option from n different action options. After each selection, the player is rewarded with the result selected from the probability distribution that depends on the selected action.

It is assumed that there are multiple slot machines, and coins (rewards) can be obtained under a certain probability distribution by pulling the lever of each slot machine. Consider the case where the probability distribution (winning probability) of coins is different for each slot machine, and the player does not know the winning probability. At this time, the most common way to know the winning probability of each slot machine is to play each slot machine in order many times, and the slot machine with the highest reward actually has the highest winning probability. to decide.

However, such a method requires playing the slot machine a considerable number of times in order to actually identify the slot machine having the highest winning probability, and as a result, a large investment is required. Also, the hitting platform of the slot machine may change from moment to moment. On the other hand, if you stop the trial shot of the slot machine early, you may miss the important point. In this way, the bandit problem has had a difficult dilemma in "search" and "decision". This problem is known as a multi-armed bandit problem, and various studies are expected because various applications such as frequency allocation in wireless communication, allocation of computational resources in data centers, robot control, and web advertising are expected. It is done.

S. -J. Kim, M. Aono, M. Hara, BioSystems 101,29-36 (2010)

However, in the past, no particular algorithm has been proposed for automatically searching for and finding a solution to a bandit problem. In these days when the amount of information is steadily increasing, it is thought that the social demand for finding the solution of the combined bandit problem from a large amount of information at high speed and efficiency will increase, but a special solution has been proposed for this. The current situation was that there was no such thing.

In particular, it is necessary to search for a hit table in order to solve this bandit problem, but in this search for a hit table, it is indispensable to randomly select a table. That is, in the early stage of the search for the hit table, the hit table is randomly selected, and in many cases, the hit table is selected based on the battle record so far with the passage of time.

Conventionally, when selecting a random hit table in the early stage, it is based on a pseudo-random number generated on a computer. However, since pseudo-random numbers are created based on an algorithm designed in advance on a computer, it is difficult to generate them at high speed, so that there is a problem that the bandit problem cannot be solved at high speed. Further, since this pseudo-random number has a limit in the qualitative aspect of the random number, there is also a problem that the solution search accuracy of the bandit problem cannot be improved.

Therefore, the present invention has been devised in view of the above-mentioned problems, and an object thereof is to realize a random selection of a hit table based on a particularly high-quality random number in solving a bandit problem. The purpose of the present invention is to provide a solution search system and a method capable of solving a bandit problem at high speed and with high accuracy.

The solution search system according to the first invention is an irregular solution search system that searches for a test object that is expected to output the best result among three or more test objects that output results based on a probability distribution. A signal transmitting means for transmitting an irregular signal whose signal strength changes, a signal detecting means for detecting the signal strength of the irregular signal transmitted from the signal transmitting means at each of two or more observation points, and the signal detecting means. A comparison means for comparing the signal strength detected at each observation time point with the threshold value set for each observation time point, a selection means for selecting the test object based on the comparison result by the comparison means, and the above selection. The output instruction means for instructing the output of the result to the subject selected by the means and the battle record so far based on the accumulation of the results output from the subject are obtained for each of the subject. The output indicating means is provided with a threshold adjusting means for adjusting each threshold set for each observation time based on the battle record of each subject to be inspected, and the output indicating means detects the signal strength by the signal detecting means and gives an output instruction. It is characterized in that a search solution based on the selection tendency of the test target by the selection means is output after repeating the instruction of the output of the result by the means.

In the first invention, the solution search system according to the second invention is the comparison means at the observation time point t _n (n is any natural number) for detecting the signal strength of the irregular signal transmitted from the signal transmitting means. The detected signal strength and the threshold value TH _n are compared, and if the signal strength is smaller than the threshold value TH _n , the signal strength detected at the observation time point t _{n + 1} and the threshold value TH _{n + 1} are compared, and the signal is described. When the intensity is equal to or higher than the threshold value TH _n , the signal intensity detected at the observation time point t _{n + 1} is compared with the threshold value TH _{n + 1} ′, and the selection means is the observation time point t _{n + 1} by the comparison means. Based on the comparison result in, the subject to be examined is selected with the threshold value TH _n and the threshold value TH _{n + 1} or the threshold value TH _{n + 1} ′ separated from each other.

In the solution search system according to the third invention, in the second invention, the threshold value adjusting means is the threshold value TH _n used in the comparison by the comparison means in selecting one test target by the selection means. , The threshold value TH _{n + 1} or the threshold value TH _{n + 1} ′ is adjusted based on the battle record of the one subject to be inspected.

In any one of the first to third inventions, the solution search system according to the fourth invention has the threshold adjusting means relating the result output from the test subject to the battle record of each of the test subjects as a whole. It is characterized in that each threshold value set for each observation time point is adjusted based on the evaluation result.

In any one of the first to fourth inventions, the solution search system according to the fifth invention is the signal transmitting means, in which the light emitted from the semiconductor laser is returned to the inside of the laser cavity via the reflecting portion. It is characterized in that the expressed return semiconductor laser light is used as the irregular signal.

The solution search method according to the sixth invention is an irregular solution search method for searching for a test object that is expected to output the best result among three or more test objects that output results based on a probability distribution. In the signal transmission step of transmitting an irregular signal whose signal strength changes, the signal detection step of detecting the signal strength of the irregular signal transmitted in the signal transmission step at each of two or more observation points, and the signal detection step. A comparison step for comparing the signal strength detected at each observation time point with the threshold value set for each observation time point, a selection step for selecting the test target based on the comparison result in the comparison step, and the selection step. The output instruction step for instructing the output of the result to the subject selected in the above step and the battle record so far based on the accumulation of the result output from the subject to be examined are obtained for each of the above subjects, respectively. It has a threshold value adjustment step that adjusts each threshold value set for each observation time point based on the battle record of the test target, and in the output instruction step, the signal strength is detected in the signal detection step and the output instruction step is performed. It is characterized in that the search solution based on the selection tendency of the test target by the selection step is output after the instruction of the output of the result is repeated.

According to the present invention having the above-described configuration, the threshold value is adjusted so that the test target is easily selected or difficult to be selected based on the superiority or inferiority of the battle record output from the test target so far. conduct. Then, after repeating the output instruction by the test target, the test target to which the output instruction of the result is finally given can be specified as a solution to be searched. This makes it possible to automatically search for and find the solution of the combined bandit problem, and in these days when the amount of information is steadily increasing, it is possible to find the solution of the combined bandit problem from a large amount of information at high speed and efficiently. Is possible.

It is an overall block diagram of the solution search system to which this invention is applied. It is a block block diagram of the signal transmission part in the case of generating a return semiconductor laser light. It is a figure which shows the process of detecting the signal strength in a decision-making part. It is a figure which shows the example of the case of searching the test subject which is expected to output the best result from 8 test subjects. It is a figure for demonstrating the case where the process of detecting the signal strength in a decision-making part is defined by a general formula. It is a figure which shows the Example of the solution search system to which this invention is applied.

Hereinafter, the solution search system to which the present invention is applied will be described in detail with reference to the drawings.

FIG. 1 shows the overall configuration of the solution search system 1 to which the present invention is applied. This solution search system 1 is a system that searches for a test target 5 that is expected to output the best result among three or more test targets 5. The solution search system 1 includes a battle record superiority / inferiority comparison unit 2, an adjustment unit 3 connected to the battle record superiority / inferiority comparison unit 2, a decision-making unit 4 connected to the adjustment unit 3 and the test target 5, and a decision-making unit 4. It is provided with a signal transmitting unit 9 connected to the above. In the following example, the case where the test target 5 expected to output the best result is selected from the four test targets 5a to 5d will be described as an example, but the description is limited to this. Instead, a solution search may be performed on the test target 5 consisting of any number of 3 or more.

The test target 5 is a target that outputs a result based on each set probability distribution. For example, it may output a coin as a result based on a set probability distribution, such as a slot machine or a pachinko machine. Further, in wireless communication, the magnitude of the data transmission amount of each channel changes each time, and this can also be expressed by a probability distribution set at a certain point in time. When an arbitrary channel is selected in such wireless communication, the result of the actual "data transmission amount" is output. Further, the result is not limited to the "data transmission amount", but can also be set to "power consumption (small)", "communication delay (small)", and the like.

In this way, the test object 5 is a concept including all events, objects, systems, programs and algorithms that can convert the output result into a probability distribution. Incidentally, the probability distribution of the result output in the subject 5 may be not only a normal normal distribution and a Gaussian distribution but also a discrete distribution or a binomial distribution. Incidentally, the probability distribution of the test target 5 is unknown to the user of the solution search system 1. The user will use this solution search system 1 to search for a combination of test targets that are expected to output the best results among these test targets.

The test targets 5a to 5d output the result l based on the set probability distributions. At this time, the result output from the test target 5a is defined as the result l ₁ , the result output from the test target 5b is defined as the result l ₂ , and the result output from the test target 5c is defined as the result l ₃ . The result output from the target 5d is defined as the result _l4 . The output results l ₁ to l ₄ are transmitted to the battle record superiority / inferiority comparison unit 2.

The battle record superiority / inferiority comparison unit 2 receives and stores the results l ₁ to l ₄ output from the test targets 5a to 5d. The battle record superiority / inferiority comparison unit 2 accumulates the results by sequentially storing the results l 1 to l 4 each time the results l ₁ to l ₄ are received from the test targets 5a to 5d. Then, the battle record superiority / inferiority comparison unit 2 obtains the battle record so far based on the accumulation of the output results for each of the test targets 5a to 5d. The battle record here indicates any data indicating whether the result output from the subject 5 is superior or inferior. If the test target 5 is a slot machine, it may indicate how many coins have been issued in a unit number of plays, or it is evaluated by two values, whether coins have been issued or not in a single play. It may be something to do. If the subject 5 to be inspected is a communication environment, it may be data indicating how quickly a connection has been made. Further, the battle record superiority / inferiority comparison unit 2 compares the superiority / inferiority of the battle record of each test target 5 in relation to the battle record of the entire test target 5. Here, the battle record index regarding the superiority or inferiority of the battle record for the subject 5a is q ₁ ^t , the battle record index regarding the superiority or inferiority of the battle record for the subject 5b is q ₂ ^t , and the battle record index regarding the superiority or inferiority of the battle record for the test target 5c. Let q ₃ ^t , and let q ₄ ^t be the battle record index relating to the superiority or inferiority of the battle record for the subject 5d. These battle record indexes q ₁ ^t to battle record index q ₄ ^t are sent to the coordinating unit 3, respectively.

In the adjustment unit 3, the battle record indexes q ₁ ^t to q ₄ ^t are input from the battle record superiority / inferiority comparison unit 2, respectively. The coordinating unit 3 makes various adjustments that affect various decisions in the decision-making unit 4 based on the superiority or inferiority of the input battle record.

The signal transmitting unit 9 transmits an irregular signal whose signal strength changes irregularly. The irregular signal transmitted from the signal transmitting unit 9 is supplied to the decision-making unit 4. The irregular signal transmitted by the signal transmitting unit 9 is not limited to the case where the signal strength simply changes randomly, and is not limited to the case where the signal strength changes chaotically. That is, this irregular signal may be composed of a signal having complete irregularity having no correlation with the signal strength at the signal transmission time immediately before the signal transmission time, or the signal transmission. It may be composed of a signal having a part of irregularity having a slight correlation with the signal strength at the time of signal transmission immediately before the time point.

It is not essential for the signal transmitting unit 9 to transmit an electrical or physical signal, and the data string of the irregular signal previously acquired may be supplied to the decision-making unit 4. For example, the irregular signal transmitted from the signal transmitting unit 9 is generated based on the return semiconductor laser light generated by returning the light emitted from the semiconductor laser into the laser cavity through the reflecting unit. It may be one.

FIG. 2 shows a block configuration of the signal transmitting unit 9 in the case of generating the return semiconductor laser light. The signal transmitting unit 9 includes a semiconductor laser 91, a coupler 92, an attenuator 93, a reflecting unit 94, an optical isolator 95, an attenuator 96, a light receiving unit 97, and an oscilloscope 98.

The semiconductor laser 91 oscillates a laser beam based on a supplied electric signal. The coupler 92 plays a role of branching the laser light from the semiconductor laser 91 and the return light from the attenuator 93 and the reflecting unit 94. The attenuator 93 attenuates the return light from the reflecting unit 94. The reflecting unit 94 is composed of a mirror or the like that reflects the laser beam from the semiconductor laser 91. The optical isolator 95 plays a role of transmitting only the component of light traveling in the forward direction and blocking the component of light in the opposite direction with respect to the laser light emitted from the coupler 92. The attenuator 96 attenuates the laser beam from the optical isolator 95. The light receiving unit 97 is composed of a photodiode or the like, and photoelectrically converts the laser light from the optical isolator 95 into an electric signal. The oscilloscope 98 uses the electrical signal photoelectrically converted in the light receiving unit 97 as a base on the time axis, and waveforms the signal intensity thereof.

According to the signal transmitting unit 9 having such a configuration, the laser light oscillated by the semiconductor laser 91 first reaches the reflecting unit 94 via the coupler 92 and the attenuator 93. This laser light is reflected by the reflecting unit 94, the amount of return light is adjusted by the attenuator 93, and then the laser light is returned to the semiconductor laser 91 as return light via the coupler 92 again. The return light returned to the resonator of the semiconductor laser 91 significantly increases the noise level of the light and destabilizes it, and as a result, the return semiconductor laser light is emitted again from there. This return semiconductor laser light has the above-mentioned irregular signal because the coherence has collapsed, so to speak, in a laser chaotic state. Such return semiconductor laser light is attenuated in the attenuator 96 via the coupler 92 and the optical isolator 95, photoelectrically converted in the light receiving unit 97, and further waveformized in the oscilloscope 98. The waveformized signal in this oscilloscope 98 is an irregular signal. The signal transmitting unit 9 supplies such an irregular signal to the decision-making unit 4.

The decision-making unit 4 detects the signal strength of the irregular signal transmitted from the signal transmission unit 9. FIG. 3 shows a process of detecting the signal strength in the decision-making unit 4. When the irregular signal is time on the horizontal axis and the signal strength is on the vertical axis, the decision-making unit 4 detects the signal intensity of the irregular signal at each of two or more observation time points. For example, when this observation time point is set to two time points, t ₁ and t ₂ , the signal strength P ₁ of the irregular signal at the observation time point t ₁ is detected, and the signal of the irregular signal at the observation time point t ₂ is detected. Detects intensity P ₂ .

Next, the decision-making unit 4 compares the signal strength detected at each observation time point with the threshold value set for each observation time point. Here, it is assumed that the threshold value TH ₁ is preset at the observation time point t ₁ , and the threshold values TH 2, ₀ and TH 2, ₁ are preset at the observation time point t ₂ . First, the signal strength P ₁ of the irregular signal at the observation time t ₁ and the threshold value TH ₁ are compared. As a result, when the signal strength P ₁ is smaller than the threshold value TH ₁ , the process proceeds in the arrow direction of the threshold value TH 2, ₀ , and when the signal strength P ₁ is equal to or higher than the threshold value TH ₁ , the arrow direction of the threshold value TH ₂ , 1. Proceed to. When the threshold TH _2,0 is advanced in the direction of the arrow, the signal strength P ₂ of the irregular signal at the observation time t ₂ is compared with the threshold TH _2,0 , and the signal strength P ₂ and the threshold TH _2,0 are compared. The test target 5 is selected according to the magnitude relationship of. Similarly, when the threshold value TH ₂ , 1 is advanced in the direction of the arrow, the signal strength P 2 of the irregular signal at the observation time point t ₂ is compared with the threshold value TH ₂ , ₁ , and the signal strength P ₂ and the threshold value TH ₂ are compared. Select the test target 5 according to the magnitude relationship of _{1, 1} .

Here, the test objects 5a to 5d described above are assigned in advance with threshold values TH ₁ , TH 2, ₀ , and TH ₂ , 1, respectively. For example, the subject 5a to be tested is assigned below the threshold TH _2,0 , the subject 5b to be tested is assigned above the threshold TH _2,0 , and the subject 5c to be tested is assigned below the threshold TH _2,1 . It is assumed that the inspection target 5d is assigned at the threshold value TH _2.0 or higher. As a result of comparison between the signal strength P ₂ of the irregular signal and the threshold value, the test target 5 to be selected corresponds to the test target 5 assigned in advance across each threshold value.

In the case of the above-mentioned example, when the signal strength P ₂ is smaller than the threshold value TH 2, ₀ , the test target 5a is selected. When the signal strength P ₂ is equal to or higher than the threshold value TH 2, ₀ , the test target 5b is selected. When the signal strength P ₂ is smaller than the threshold value TH 2, ₁ , the test target 5c is selected. When the signal strength P ₂ is equal to or higher than the threshold value TH 2, ₁ , the test target 5d is selected.

That is, the case where the test target 5a is selected is the case where the signal strength P ₁ is less than the threshold value TH ₁ and the signal strength P ₂ is less than the threshold value TH _2.0 . The case where the test target 5b is selected is a case where the signal strength P ₁ is less than the threshold value TH ₁ and the signal strength P ₂ is equal to or higher than the threshold value TH _2.0 . The case where the test target 5c is selected is a case where the signal strength P ₁ is equal to or higher than the threshold value TH ₁ and the signal strength P ₂ is lower than the threshold value TH _{2 1} . The case where the test target 5d is selected is a case where the signal intensity P ₁ is the threshold value TH ₁ or more and the signal intensity P ₂ is the threshold value TH 2, ₁ or more. When the test targets 5a and 5b are actually selected, the threshold values TH ₁ and the threshold values TH 2, ₀ are used, and the threshold values TH 2, ₁ are not particularly used. Similarly, when the test targets 5a and 5b are selected, the threshold values TH ₁ and the threshold values TH 2, ₁ are used, and the threshold values TH 2, ₀ are not particularly used.

By the way, when the numerical values 0 to 3 in decimal are assigned to the subjects 5a to 5b, respectively, and the numerical values 0 to 3 are converted into binary numbers, the subject 5a is (00) and the subject 5b is (01). , The test target 5c is (10), and the test target 5d is (11).

When the digits in this binary number are defined as the first digit and the second digit from the upper order, when the first digit is 0, the threshold value TH _2,0 is advanced, and when the first digit is 1, the digit is advanced to the threshold value TH 2,0. This is the case of advancing to the threshold value TH _2,1 . That is, _{k at the threshold values TH 2 and k} corresponds to the numerical value of the first digit. The numerical values in the second digit are the test target 5a (00) or the test target 5b (01) separated by the threshold values TH _2,0 and TH _2,1 and the test target 5c (10) or the test target. It corresponds to 5d (11).

In this way, the test objects 5a to 5d selected by the decision-making unit 4 output the result l based on the probability distributions set respectively.

Next, the operation of the solution search system 1 to which the present invention is applied will be described.

First, the irregular signal transmitted from the signal transmitting unit 9 is supplied to the decision-making unit 4. As a result of comparing the signal strength P ₁ of the irregular signal at the observation time point t ₁ with the threshold value TH ₁ for this irregular signal, the decision-making unit 4 first finds that the signal strength P ₁ is smaller than the threshold value TH ₁ . It proceeds in the direction of the arrow of the threshold value TH 2, ₀ , and when the signal intensity P ₁ is equal to or higher than the threshold value TH ₁ , it proceeds in the direction of the arrow of the threshold value TH ₂ , 1. When the threshold TH _2,0 is advanced in the direction of the arrow, the signal strength P ₂ of the irregular signal at the observation time t ₂ is compared with the threshold TH _2,0 , and the signal strength P ₂ and the threshold TH _2,0 are compared. One of the test targets 5a and 5b is selected according to the magnitude relationship of. Similarly, when the threshold value TH ₂ , 1 is advanced in the direction of the arrow, the signal strength P 2 of the irregular signal at the observation time point t ₂ is compared with the threshold value TH ₂ , ₁ , and the signal strength P ₂ and the threshold value TH ₂ are compared. Either the test target 5a or the test target 5b is selected according to the magnitude relationship of _{1 and 1} . As a result, any one of the test targets 5a to 5d is selected in the decision-making unit 4.

Next, the result is output for any one of the selected subjects 5a to 5d. The results l output from the test targets 5a to 5d are sent to the battle record superiority / inferiority comparison unit 2, respectively. The battle record superiority / inferiority comparison unit 2 specifically performs the following processing operations based on the sent result l.

The battle record superiority / inferiority comparison unit 2 manages the battle ^records of the subjects 5a to 5d to be inspected via the battle record index _qit . The value increases when the test target 5 outputs a better result and when the test target 5 other than the test target 5 for which the q _i ^t is obtained outputs a worse result. Is supposed to do. If the test target 5 is a slot machine, if one test target 5a is elected, the battle record index q ₁ ^t of the test target 5a is increased, the test target 5a is defeated, and the other test target 5a is defeated. When the test target 5 is elected, the battle record index q ₁ ^t of the test target 5a is not changed or is lowered.

Such a battle record index q ₁ ^t is managed for each test target 5a to 5d, and the battle record index q ₁ ^t increases as the battle record becomes better, and the battle record index increases as the battle record becomes inferior. q ₁ ^t is lowered.

Which of the results l output from each test target 5 is superior and which result l is inferior may be determined under any criteria. The above-mentioned example of the slot machine is not limited to the case where the superiority or inferiority is determined by whether or not coins are issued, and the superiority or inferiority may be determined according to the number and types of coins. Further, the superiority or inferiority is not limited to the case where the superiority or inferiority is set in two stages of superiority or inferiority, and the superiority or inferiority may be evaluated in three or more stages. By the way, even when the superiority or inferiority is ranked in three or more stages, the higher the rank of one test target 5, the higher the q _i ^t , and the lower the rank of the other test target 5, the q _i . Make adjustments to lower ^t . The battle record q _i ^t of each test target 5 may be adjusted in relation to the battle record of the entire test target 5.

The battle record indexes q ₁ ^t to q ₄ ^t obtained for each of the test targets 5a to 5d in this way are sent to the adjusting unit 3. In the adjusting unit 3, the battle record indexes q ₁ ^t to q ₄ ^t are input respectively. The adjusting unit 3 adjusts each threshold value TH set for each observation time point in the decision-making unit 4 based on the input battle record indexes q ₁ ^t to q ₄ ^t .

Each of the test objects 5a to _5d is assigned in advance with thresholds TH ₁ , TH 2, ₀ , and TH 2, 1, respectively. When adjusting the threshold value for any one of the test objects 5, only the threshold value TH used for comparison in the decision-making unit 4 shall be performed. For example, the test target 5a is assigned at a threshold value of less than _TH1 and _a threshold value of less than 2.0. Therefore, when adjusting the threshold value based on the battle record index q ₁ ^t of the test target 5a, the threshold value TH ₁ and the threshold value TH 2, ₀ used in the comparison are adjusted.

The adjusting unit 3 adjusts the threshold value so that the ^better the battle record index _qit of the subject 5 is, the easier it is to select the subject 5. Further, the adjusting unit 3 adjusts the threshold value so that the ^inferior the battle record index _qit of the test target 5 is, the more difficult it is to select the test target 5. For example, in the case of adjusting the threshold value for the subject 5b to be inspected, the better the battle record index q ₂ ^t , the higher the threshold value TH ₁ and the lower the threshold value TH ₂ , 1 will be. There is a high possibility that the test target 5b will be selected. On the other hand, the inferior the battle record index q ₂ ^t , the lower the threshold TH ₁ and the higher the threshold TH ₂ , 1, and the less likely it is that the test target 5c will be selected from the next time onward. .. Similarly, when adjusting the threshold value for the subject 5c to be inspected, the better the battle record index q ₃ ^t , the more the threshold value TH ₁ is reduced and the threshold value TH ₂ , 1 is further increased. There is a high possibility that the test target 5c will be selected. On the other hand, the inferior the battle record index q ₃ ^t , the lower the possibility that the test target 5c will be selected from the next time onward by further increasing the threshold value TH ₁ and further decreasing the threshold value TH ₂ , 1. ..

The threshold value may be adjusted by the adjusting unit 3 every time for all the test targets 5a to 5d, or may be performed only for one test target 5a to 5d selected by the decision-making unit 4. good. In the latter case, when the threshold value is adjusted only for one selected subject 5a to 5d, the number of times the threshold value is adjusted increases as the number of times of selection is larger. In addition, it is judged that the probability of winning is higher as the test target 5 is selected more frequently. Therefore, it can be determined that the test target 5, which is frequently selected by the decision-making unit 4, is close to the search solution in the solution search system 1.

In this way, the test target 5 is easily or selected by the decision-making unit 4 based on the battle record index _qit ^based on the superiority or inferiority of the battle results so far output from the test target 5. Adjust the threshold so that it becomes difficult. Then, after repeating the output instruction by the test target 5, the test target 5 for which the output instruction of the result is finally given can be specified as a solution to be searched. This makes it possible to automatically search for and find the solution of the combined bandit problem, and in these days when the amount of information is steadily increasing, it is possible to find the solution of the combined bandit problem from a large amount of information at high speed and efficiently. Is possible.

In the above-described embodiment, the case of searching for a test target expected to output the best result from the four test targets 5a to 5d has been described as an example. Not limited to. FIG. 4 below shows an example of searching for a test target that is expected to output the best results from the eight test targets 5a to 5h.

In this example, when the observation time points are set to three time points of t ₁ , t ₂ , and t ₃ , the signal strength P ₁ of the irregular signal at the observation time point t 1 is detected, and the signal strength P ₁ at the observation time point t ₂ is detected. The signal strength P ₂ of the ordered signal is detected, and the signal strength P ₃ of the irregular signal at the observation time point t ₃ is further detected.

The decision-making unit 4 compares the signal strength detected at each observation time point with the threshold value set for each observation time point. The comparison of the threshold values for the signal strengths P ₁ and P ₂ is the same as described above. The signal strength P ₃ of the irregular signal detected at the observation time point t ₃ is compared with the threshold values TH _3,0,0 , TH _3,0,1 , TH _3,2,0 , and TH _3,2,1 , respectively. The eight test subjects 5a to 5h are assigned by being separated by these threshold values TH _3,0,0 , TH _3,0,1 , TH _3,2,0 , and TH _3,2,1 . For example, the test target 5a is assigned below the threshold TH _3,0,0 , and the test target 5b is assigned at the threshold TH _3,0,0 or more. The test target 5c is assigned below the threshold TH _3,0,1 and the test target 5d is assigned at the threshold TH _3,0,1 or more. The test target 5e is assigned below the threshold TH _3,2,0 , and the test target 5f is assigned at the threshold TH _3,2,0 or more. The test target 5g is assigned below the threshold TH _3,2,1 and the test target 5h is assigned at the threshold TH _3,2,1 or more. As a result of comparison between the signal strength P ₃ of the irregular signal and the threshold value, the test target 5 to be selected corresponds to the test target 5 assigned in advance across each threshold value.

In the case of the above-mentioned example, when the signal strength P ₃ is smaller than the threshold value TH _3,0,0 , the test target 5a is selected. When the signal strength P ₃ is the threshold value TH _3,2,1 or more, the test target 5f is selected.

The test target 5 selected by the decision-making unit 4 in this way outputs the result and is similarly reflected in the battle record index q _i ^t . The battle record index q _i ^t is managed for each test target 5a to 5f, and the battle record index q _i t is increased as the battle record becomes better, and the battle record index q _i ^t increases as the battle record becomes inferior. ^{Lowering t} is the same as described above. Then, based on the battle record index q _i ^t , the threshold values at the observation points t ₁ , t ₂ , and t ₃ are adjusted so that the test target 5 is easily or difficult to be selected in the decision-making unit 4. What to do is the same as above.

In addition, when searching for a test target that is expected to output the best results from the 16 test targets 5, another observation point t is added in the same manner, and a new threshold value is added. By allocating the test target 5 so as to separate the threshold values, the same search operation can be performed. The same applies when searching from 32 or more test targets 5, by adding the observation time point t according to the number of test targets 5 and allocating the test targets 5 so as to separate the threshold values corresponding to the observation time point t. realizable.

FIG. 5 shows a case where this is defined by a general formula. The signal strength P _n detected at the observation time point t _n (n is any natural number) for detecting the signal strength of the irregular signal transmitted from the signal transmitting unit 9 is compared with the threshold value TH _n , and the signal strength P _n is calculated. When it is smaller than the threshold value TH _n , the signal intensity P _{n + 1} detected at the observation time t _{n + 1} is compared with the threshold value TH _{n + 1} , and when the signal intensity P _n is equal to or more than the threshold value TH _n , it is observed. The signal strength P _{n + 1} detected at the time point t _{n + 1} is compared with the threshold value TH _{n + 1} ′. Then, based on the comparison result at the observation time point t _{n + 1} , the threshold value TH _n and the test target 5 assigned to the threshold value TH _{n + 1} or the threshold value TH _{n + 1} ′ are selected.

At this time, the threshold value TH _n used in the comparison in selecting one test target 5 and either the threshold value TH _{n + 1} or the threshold value TH _{n + 1} ′ are set to the one test target 5 Adjust based on the battle record of. If the threshold value TH _n and the threshold value TH _{n + 1} are used for comparison with the signal strength P, the threshold value TH _n and the threshold value TH _{n + 1} are adjusted. Similarly, when the threshold value TH _n and the threshold value TH _{n + 1} ′ are used for comparison with the signal strength P, the threshold value TH _n and the threshold value TH _{n + 1} ′ are adjusted.

In the example of FIG. 5 described above, it is assumed that the number of test objects 5 to be searched is 2 ⁿ and n is a natural number, but if the number of test objects 5 deviates from 2 ⁿ . Can be considered in the same way. If the number of test targets 5 deviates from 2 ⁿ , the threshold value leading to the unused test target 5 may be canceled. For example, in the example of FIG. 4, in the case of being composed of seven objects 5a to 5g, the search in the decision-making unit 4 is executed in the same manner as described above, and TH to which the object 5h to be examined should be originally assigned. If _3,2,1 or more are selected, the selection may be canceled.

Further, according to the present invention, the above-mentioned threshold values may be adjusted based on both the result output from the test target 5 and the variable Ω indicating the battle record of the entire test target.

If there are two subjects 5a and 5b, the winning percentage of the subject 5a is 90%, and the winning percentage of the subject 5b is 70%, the winning percentage of the entire subject 5 is Since (0.9 + 0.7) / (1 + 1) = 0.8, it is 80%. On the other hand, the defeat rate of all the test subjects 5 is 1-0.8 = 0.2. Ω as a ratio of this winning rate to the losing rate is 0.8 / 0.2 = 4. This Ω indicates the battle record of the entire subject to be inspected.

That is, when the ratio Ω of the winning rate to the losing rate is high, the rate of losing in the entire test target 5 is low, so that the output result of the test target 5 selected by the decision-making unit 4 is lost. If so, it means that the fact must be emphasized. In other words, with the current threshold setting, there remains a risk of selecting the subject to be elected and removing it as a matter of course. In such a case, it is shown that there is a high need to change the threshold value. At this time, if the threshold value is equal to or higher than the median of the intensity of the irregular signal, the shift is made to be lower, or if the threshold value is lower than the median of the intensity of the irregular signal, the threshold value is made higher. Perform processing such as shifting to.

On the other hand, when the winning percentage of the subject 5a is 30% and the winning percentage of the subject 5b is 10%, the winning percentage of the entire subject 5 is (0.3 + 0.1) / (1 + 1). Since it is 0.2, it is 20%. On the other hand, the defeat rate of all the test subjects 5 is 1-0.2 = 0.8. Ω as a ratio of this winning rate to the losing rate is 0.2 / 0.8 = 0.25. That is, when the ratio of this win rate to the defeat rate is low, the rate of losing in the entire test target 5 is high, so that the output result of the test target 5 selected by the decision-making unit 4 is lost. Even in this case, it means that it is not necessary to take the fact as a big picture without giving special importance to it. In other words, it means that there is no particular problem even if the current threshold value is set. In such a case, it is shown that the necessity of changing the threshold value is low.

In this way, the Ω as the battle record of the entire test target 5 expressed by the ratio of the win rate to the defeat rate is examined, and the result output from the test target 5 is referred to as the battle record Ω of the entire test target 5. Evaluate in relations. Then, the threshold value is adjusted based on this evaluation result.

This Ω can be defined by the following equation (1).
Ω = (A ₀ + A ₁ ) / {2- (A ₀ + A ₁ )} ... (1)

Here, A ₀ is the winning percentage of one subject 5 and A ₁ is the winning percentage of another subject. Actually, even when there are 4 or more non-samples, the result output from the test target 5 is evaluated in relation to the battle record Ω of the entire test target 5, and the threshold value is adjusted based on the evaluation result. do.

Hereinafter, the results of experiments and calculation simulations performed to confirm the effects of the present invention will be described. In this experiment and simulation, the search accuracy of the answer to the irregularity of the irregular signal transmitted from the signal transmitting unit 9 is verified.

As the prepared irregular signals, three types of return semiconductor laser light actually using the semiconductor laser 91, a quasi-periodic signal (sampling interval: 10 ps), and color noise (negative autocorrelation) were prepared. The relationship between the signal strength and the time of these signals is shown in FIG. 6 (a).

A sample of such an irregular signal was supplied to the decision-making unit 4 in the solution search system 1 to which the present invention was applied. FIG. 6 (b) shows the ratio of correct decisions to the cycle. In this example, the number of the test objects 5 is set to 2, and the test target outputs two values of hit and miss as a result. The probability of winning in each test target 5 is known, and the result searched by this solution search system 1 when the correct answer of the test target 5, which is expected to output the best result, is also known. And, the correct answer rate is calculated from the consistency with the correct answer. The vertical axis of FIG. 6B shows the correct answer rate.

As a result of this simulation, the one with the highest correct answer rate was the return semiconductor laser light (sampling interval: 50 ps). In addition, the correct answer rate was higher than that of semi-periodic signals and color noise. Therefore, it is shown that the higher the irregularity of the supplied irregular signal, in other words, the closer to the chaotic state, the higher the correct answer rate.

1 Solution search system 2 Battle record superiority / inferiority comparison unit 3 Coordination unit 4 Decision-making unit 5 Test target 9 Signal transmitter 91 Semiconductor laser 92 Coupler 93, 96 Attenuator 94 Reflector 95 Optical isolator 97 Light receiving unit 98 Oscilloscope

Claims (6)

In a solution search system that searches for a test target that is expected to output the best result among three or more test subjects that output results based on a probability distribution.
A signal transmission means that transmits an irregular signal whose signal strength changes irregularly,
A signal detecting means for detecting the signal strength of an irregular signal transmitted from the above signal transmitting means at each of two or more observation points, and a signal detecting means.
A comparison means for comparing the signal strength detected at each observation time point by the signal detection means with the threshold value set for each observation time point.
The selection means for selecting the test target based on the comparison result by the comparison means, and the selection means.
An output instruction means for instructing the output of the result to the subject to be inspected selected by the selection means, and an output instruction means.
The battle record up to now based on the accumulation of the results output from the test target is obtained for each test target, and each threshold value set for each observation time is adjusted based on the battle record of each test target. Equipped with threshold adjustment means to
The output instruction means outputs a search solution based on the selection tendency of the subject to be inspected by the selection means after repeating the instruction of the output of the result by the output instruction means from the detection of the signal strength by the signal detection means. A solution search system characterized by doing. The comparison means compares the signal strength detected at the observation time point t _n (n is any natural number) for detecting the signal strength of the irregular signal transmitted from the signal transmission means with the threshold value TH _n , and compares the signal strength with the threshold value TH n. When the intensity is smaller than the threshold value TH _n , the signal intensity detected at the observation point t _{n + 1} is compared with the threshold value TH _{n + 1} , and when the signal intensity is equal to or higher than the threshold value TH _n , the signal intensity is t _n at the observation time point. Compare the signal strength detected at ₊₁ with the threshold TH _{n + 1} ´.
The selection means is a subject to be examined, which is assigned with the threshold value TH _{n + 1} or the threshold value TH _{n + 1} ′ separated from the threshold value TH _n based on the comparison result at the observation time point t _{n + 1} by the comparison means. The solution search system according to claim 1, wherein the method is selected. The threshold value adjusting means sets the threshold value TH _n used in the comparison by the comparison means and the threshold value TH _{n + 1} or the threshold value TH _{n + 1} ′ in selecting one test target by the selection means. , The solution search system according to claim 2, wherein the adjustment is made based on the battle record of the one subject to be inspected. The threshold value adjusting means evaluates the result output from the subject to be inspected in relation to the battle record of each of the subjects to be inspected, and adjusts each threshold value set for each observation time point based on the evaluation result. The solution search system according to any one of claims 1 to 3, wherein the solution search system is characterized in that. The signal transmitting means is characterized in that the return semiconductor laser light expressed by returning the light emitted from the semiconductor laser to the inside of the laser resonator via the reflecting portion is used as the irregular signal. The solution search system according to any one of Items 1 to 4. In a solution search method for searching for a test target that is expected to output the best result among three or more test targets that output results based on a probability distribution.
A signal transmission step that transmits an irregular signal whose signal strength changes irregularly,
A signal detection step that detects the signal strength of the irregular signal transmitted in the above signal transmission step at each of two or more observation points, and a signal detection step.
A comparison step for comparing the signal strength detected at each observation time point in the signal detection step with the threshold value set for each observation time point.
The selection step of selecting the test target based on the comparison result in the comparison step, and the selection step.
An output instruction step for instructing the output of the result to the subject to be inspected selected in the selection step, and an output instruction step.
The battle record up to now based on the accumulation of the results output from the test target is obtained for each test target, and each threshold value set for each observation time is adjusted based on the battle record of each test target. Has a threshold adjustment step and
In the output instruction step, the signal strength is detected in the signal detection step, the output instruction of the result is repeated by the output instruction step, and then the search solution based on the selection tendency of the test target by the selection step is output. A solution search method characterized by doing.

Images