Let me explain how to formulate the equation using the case of the "Image Noise Reduction" demo application on this site. In this problem, we use an annealing machine to solve the problem of removing noise (incorrect dots in the image data) from an image. The closer the result is to the original image, the more correct it is, so in this case, this is a demo application to check how the annealing machine works, assuming that the correct answer is known before solving the problem. The attempt to formulate an equation to solve with an annealing machine is based on the following rationale.
Creating an equation by taking into account the situations described as (a) and (b), we obtain the correct answer, that is, the state in which noise is removed afterwards.
Now, for those of you who have no recollection of what the $\Sigma$ symbol is, let me explain. (If you don't need to know that, skip ahead to "How to Create a Cost Function Continued.") The cost function is represented by the addition of several terms. However, you can imagine it would be tough to write the entire addition equation of all states of a huge number of black-and-white points. Therefore, we express additions in terms of $\Sigma$ instead of writing down additions of every member.
Check the noise reduction demo application. Look at equation (1) in the Noise Reduction tutorial. The equation is an expression of the rationale (a) mentioned above.
where $y_i$ is the value of the $i$th point in the input image (the noisy image before the optimization process) ($+1$ or $-1$) and $s_i$ is the $i$-th value of the output image (denoised image) ($+1$ or $-1$).
means the result by adding every $ys$ ($y \times s$) from the first to the last.
$i \in V$ is the range over which this calculation is performed. It means that $i$ is contained in the set of $V$. Of course, the dots exist only in the range of the image, so $y_1s_1+y_2s_2+y_3s_3+......$ does not have to be calculated infinitely, meaning that the formula defines that it is within the range of $V$ (the image range).
Let us now return to the tutorial. It is written as follows
In other words, since the majority of pixels, except for the black points of noise, are the same (black or white) before input and after output, multiplying before and after input should result in $(+1)\times(+1)$ or $(-1)\times(-1)$, which is a uniformly positive value. This time we are making the equation based on the assumption that the optimal solution will be given by minimizing the energy. Therefore, we put a minus sign in front of $\Sigma$, which is the sum of all the positive values added together, so that the overall value is the smallest.
Next, let us look at equation (2), which expresses rationale (b).
Equation (2), which represents the rationale (b), shows that "neighboring pixels are often the same.
The contents of $\Sigma$ are $s_is_j$, and under $\Sigma$ is accompanied by $(i,j)\in E$, which is explained as "the set of adjacent pixel pairs. This means that in a correct image, adjacent points are often the same color.
Finally, (1) and (2) added together to form the following equation, which completes the cost function. Actually, one more twist has been made.
You have not only added (1) and (2) together, but also the letter $\eta$ has appeared. This is explained as follows.
In other words, if only equation (1) is used, the image will be black or white and will not work.
Also, if only equation
(2) is used, the image before and after the input is exactly the same, so the noise will not disappear
at all, and this
will also not work well. To get the best result, multiply (2) by 2 or 3 before (2), and the noise will
Thus, to get the formula into the annealing machine, it is important to make adjustments such as setting $\eta$ to 2 or 3 depending on the user's preference to lean on the facts.
What do you think? We hope you can somewhat understand how to apply the problem of removing noise from that black-and-white image to the problem of energy minimization.
What to do next is to put the equation using $\Sigma$ into an annealing machine with a programming language such as Python. Then the annealing machine will fit the cost function to the Ising model and derive the combination of the lowest energy case found for the equation.
Combinatorial optimization will be explained by using two easy-to-understand examples of familiar combinatorial optimization problems. The importance of finding and using fast solution methods for combinatorial optimization processes in an IoT society will also be discussed.
In the wake of the COVID-19 epidemic, we present a use case in which an annealing machine is used to create shifts for researchers under constraints that take into account the risk of infection.
This article presents a use case in which an annealing machine is used to formulate a reinsurance portfolio that leverages the vast amount of data held by an insurance company to address natural catastrophe risks.
For beginners, this article explains the procedures and key points of the process of solving optimization problems with an annealing machine. The process involves dividing the problem into four stages: "organizing problem and defining problem," "formulation," "input data preparation," and "executing CMOS annealing machine".