Chapter 2: What is the Cost Function?

Section 2: How to create a cost function

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.

[Rationale for formulation]

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.

Review of $\Sigma$

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.

$$ \tag*{Equation (1)} - \sum_{i \in V}y_i s_i $$

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$).

$$ \sum y_i s_i $$

means the result by adding every $ys$ ($y \times s$) from the first to the last.

$$ \sum_{i \in V}y_i s_i $$

$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).

How to create a cost function continued

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.

$$ \tag*{Equation(2)} - \sum_{(ij) \in E}s_i s_i $$

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.

$$ \tag*{Equation(1)+(2)} - \sum_{(ij) \in E}s_i s_i - \eta \sum_{i \in V}y_i s_i $$

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 be removed.
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 preferance 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.

After creating the cost function

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.