extfieldsofstudy:
Computer Science
Physics

text:
Efficiently estimating average fidelity of a quantum logic gate using few classical random bits

We give three new algorithms for efficient in-place estimation, without using ancilla qubits, of average fidelity of a quantum logic gate acting on a d-dimensional system using much fewer random bits than what was known so far. Previous approaches for efficient estimation of average gate fidelity replaced Haar random unitaries in the naive estimation algorithm by approximate unitary 2-designs, and sampled them uniformly and independently. In contrast, in our first algorithm we sample the unitaries of the approximate unitary 2-design uniformly using a limited independence pseudorandom generator, a powerful tool from derandomisation theory. This algorithm uses the same number of basic operations as previous efficient algorithms but much fewer number of random bits. Reducing the requirement of classical random bits increases the reliability of estimation as often, high quality random bits are an expensive computational resource. Our second efficient algorithm, based on a 4-quantum tensor product expander, works if the gate dimension d is large. It uses even lesser random bits than the first algorithm, and has the added advantage that it needs to implement only one unitary versus potentially all the unitaries of an approximate 2-design in the first algorithm. Our third efficient algorithm, based on an l-quantum tensor product expander for moderately large values of l, works for all values of the parameters. It uses slightly more random bits than the other algorithms but has the advantage that it needs to implement only a small number of unitaries versus potentially all the unitaries of an approximate 2-design in the first algorithm. This advantage is of great importance to experimental implementations in the near future.

I. INTRODUCTION
Unitary quantum logic gates serve as the basic building blocks of quantum circuits implementing quantum algorithms. They are nothing but unitary operators chosen from a predetermined set. Implementation of any quantum algorithm is achieved by application of an appropriate sequence of these gates. However, in practice there is always some error between the ideal gate output given a particular input state and the actual gate output because of noise. Thus if we want to apply a quantum gate, it is desirable that the noisy experimental version Λ be close to the ideal gate U with respect to some measure. Most works use the so-called fidelity as a measure of closeness. This leads to the notion of gate fidelity for a particular input state. Notice that this characterisation depends on the quantum state inputted to the gate. However when the gate is used as part of a quantum circuit, it may not be feasible to figure out the states that may possibly be inputted to the gate during the course of operation of the circuit. One would like to remove this state dependence in the definition of gate fidelity and instead come up with a quantity that serves as a general measure of the quality of the gate implementation. One way to do this is to consider the gate fidelity averaged over the Haar probability measure on all possible pure input states. This quantity is called the average gate fidelity [1].
Emerson et al. [1] gave an algorithm for estimating average fidelity of a unitary d-dimensional gate using several independent samples of d × d Haar random unitaries. While they did not explicitly bound the number of samples required in order to obtain an estimate of the average fidelity to within additive error ǫ, their method can be analysed to show that O(ǫ −2 ) independent Haar random samples of unitaries suffice. This is prohibitively expensive, both in terms of the computational cost required to implement the Haar random unitaries as well as in terms of the number of random bits required to do the sampling. Both these quantities are at least Ω(ǫ −2 d 2 log d log(1/ǫ)) [17,Corollary 4.2.13]. Later works [2,3] showed that the computational cost and the number of random bits can be drastically brought down by choosing independent uniform samples from a unitary 2-design. Again, these papers did not rigorously estimate the running time and the usage of random bits of their algorithm, but nevertheless those can be analysed to obtain a bound of O(ǫ −2 polylog(d/ǫ)) for both.
In this paper, we treat the usage of classical random bits as a resource and try to minimise it. One of the reasons behind this is that high quality random bits are an expensive computational resource. Thus, reducing them while preserving the efficiency of the algorithm and the estimation error would generally lead to more reliable estimation in practice. This is especially important because in the near future, we expect to have experimental realisations of quantum circuits on about ten to fifty qubits, and they have to be benchmarked accurately and reliably so as to further the goal for having a practical quantum computer one day. Another reason behind reducing the number of random bits is that it often gives us deep insights into the algorithms involved, leading to serendipitous additional optimisations that may have otherwise escaped our attention. In this paper, we shall actually see an example of such a serendipitous optimisation. Our second and third algorithms not only use far less random bits that what was known earlier; they also require the algorithms to implement a much smaller set of unitaries than potentially all unitaries of an approximate 2-design in earlier works [2,3]. This is very important for the near future because implementing a wide range of unitaries is technologically fraught with immense challenges. An excellent introduction to derandomisation goals and techniques in computer science can be found in the book [16].
We give three new algorithms for efficient in-place estimation, without using ancilla qubits, of the average fidelity of a quantum logic gate acting on a d dimensional system using much fewer random bits than what was known so far. We consider in-place algorithms only because good quality qubits are likely to remain a very expensive resource in near term experimental implementations, and so we want to avoid ancilla qubits as much as possible. In our first algorithm, in contrast to earlier works, we sample the unitaries of the approximate unitary 2-design uniformly using a limited independence pseudorandom generator [11,12], a powerful tool from derandomisation theory. This algorithm uses O(ǫ −2 (log δ −1 )(log d)(log ǫ −1 )) number of basic operations in order to estimate the average gate fidelity to within an additive error ǫ with confidence 1 − δ, which is the same as [2]. However, it only uses O((log δ −1 )((log d)(log ǫ −1 ) + log log δ −1 )) random bits, which is much lesser number than the Ω(ǫ −2 (log d)(log ǫ −1 )) random bits used in the previous works.
Our second efficient algorithm, based on a 4-quantum tensor product expander [15], works if the gate dimension d is large. It uses even lesser random bits than the first algorithm, and has the added advantage that it needs to implement only one unitary versus potentially all the unitaries of an approximate 2-design in the first algorithm. Our third efficient algorithm, based on an l-quantum tensor product expander [15] for moderately large values of l, works for all values of the parameters. It uses slightly more random bits than the other algorithms but has the advantage that it needs to implement only a small number of unitaries versus potentially all the unitaries of an approximate 2-design in the first algorithm.
The rest of the paper is organised as follows: • In Section II we build up some notations and preliminaries that will be used throughout the paper.
• Section III describes how to bound the tail of the gate fidelity distribution when the unitaries are chosen from an approximate l-quantum tensor product expander (qTPE).
• Section IV summarises the earlier work on estimating average gate fidelity adding a rigorous analysis of estimation and confidence errors missing in previous works.
• In Section V, we describe a randomness efficient algorithm for estimating average gate fidelity using approximate 2-designs combined with a limited independence pseudorandom generator.
• In Section VI, we describe a randomness efficient algorithm for estimating average gate fidelity using an approximate 4-qTPE, which works if the gate dimension is large and needs to implement only one unitary.
• In Section VII, we describe a randomness efficient algorithm for estimating average gate fidelity using approximate l-designs for moderate values of l ≥ 4, which has the advantage that the estimation procedure needs to potentially implement only a very small number of unitaries.
• We conclude in Section VIII with a discussion of what we have achieved, and directions for future work.

II. NOTATION AND PRELIMINARIES
Throughout the paper, H denotes a complex Hilbert space of finite dimension d and H ⊗m denotes the m fold tensor product of H. We use 1 1 to denote the identity operator on H. M k,d denotes the vector space of k × d linear operators over complex field and M d = M d,d . Note that M d is itself a Hilbert dpace of dimension d 2 with Hilbert-Schmidt inner product, defined as: A, B T r(A † B). For p > 0, we let · p denote the Schatten p-norm of operators in M d , defined as: A p [Tr (A † A) p/2 ] 1/p . This is nothing but the ℓ p -norm of the vector of singular values of A. The case p = 1 is called the trace norm. The case p = 2 is the Frobenius norm or the Hilbert-Schmidt norm induced from the eponymous inner product. Letting p → ∞ gives us the Schatten ℓ ∞ -norm which is nothing but the largest singular value of A, aka operator norm or spectral norm of A. Often, we use ρ to denote a quantum state or a density matrix which is a Hermitian, positive semidefinite matrix with unit trace. We let D(d) denote the set of all d × d density matrices. A pure quantum quantum is a rank one density matrix. We denote by CP d−1 the set of pure quantum states in H. The notation |· denotes a vector of unit ℓ 2 -length. Thus if |ψ is a unit vector, |ψ ψ| is a pure quantum state. We will often abuse notation and use |ψ to denote a pure quantum state also.
We use Λ to denote the noisy experimental realisation of an ideal unitary quantum gate U. For a bipartite Hilbert space H 1 ⊗ H 2 , the partial trace Tr H2 denotes the operation of tracing out H 2 . We use X to denote a random variable andX to denote its expected value with respect to a probability measure µ, i.e., X X dµ. The notation Var(X) denotes the variance of random variable X, i.e. V ar(X) = (X −X) 2 . The symbol U(d) stands for the the unitary group on H i.e. the group of d × d complex unitary matrices. We tacitly assume that the ceiling is taken of any formula that provides dimension or value of t in unitary t-design. The symbol Haar is used to denote the unique unitarily invariant Haar probability measure on U(d), or CP d−1 as appropriate. Expectation with respect to a measure µ is denoted by E ν [·].
Fidelity between two quantum states ρ and σ is defined as: Fidelity is a measure of distinguishabilty of two states. It is easy to see that F (ρ, σ) = 1 implies ρ and σ are identical, and F (ρ, σ) = 0 implies that ρ and σ have orthogonal support and there exists a single measurement that distinguishes them perfectly. Fidelity is related to trace distance via the following inequality.
A linear mapping Λ : M m → M d is called a super operator, and a super operator which is completely positive and trace preserving is considered as a quantum operation. The vector space of superoperators is denoted by Then U is also a quantum operation defined as U(ρ) = U ρU † . Suppose Λ is a 'noisy' implementation of the unitary quantum operation U. Then Λ is a quantum operation from M d to M d , and so it can be represented using Kraus operators as Kraus operators of Λ, with the property that Σ k A † k A k = 1 1. It turns out that d 2 Kraus operators suffice to describe any quantum operation from M d to M d . We shall measure the distance between two superoperators via the so-called diamond norm [14]. The diamond norm of a superoperator Λ : M d → M d is defined as follows: where I m is the identity superoperator on M m . A quantum operation Λ always has Λ ♦ = 1.
Gate fidelity between Λ and U for an input state ρ is defined as: The average gate fidelityF Λ,U is now defined to be the expectation of the gate fidelity F Λ,U (|ψ ψ|) for pure input states |ψ ψ| chosen from the Haar probability measure on CP d−1 : In practice, when one wants to benchmark the quality of the experimental implementation of a unitary quantum logic gate U, one runs the implementation twice, first in the forward direction followed by the backward direction. If the implemenation were indeed perfect, this would just do the quantum operation U −1 U = 1 1. But because the implementation is noisy what we get is a quantum operation, which we will again denote by Λ, that is close to the identity quantum operation. Let |ψ be a unit length vector in H. Define Then the average gate fidelity of Λ is given bȳ The average gate fidelity defined above has a nice expression in terms of the Kraus operators of Λ [1]: The variance of the gate fidelity under the Haar measure on d × d unitaries V happens to satisfy the following inequality [8,Equation 18].
The gate fidelity is an example of a function from the unit ℓ 2 -norm sphere S 2d−1 in C d to R. More generally, consider a function f : The following fact was proved in [13, Lemma 2.7].
Consider the probability distribution on points (v 1 , . . . , v t ) ∈ (S 2d−1 ) ×t where the v i s are chosen independently from the Haar measure on S 2d−1 . Define Let δ > 0. Then, . Now let f be the following function Trivially, It is easy to see that which shows that the Lipschitz constant η ≤ 4t −1/2 . Let δ > 0. Consider the probability distribution on points (V 1 , . . . , V t ) ∈ U(d) ×t obtained by choosing each V i independently from the Haar measure. Define f (V 1 , . . . , V t ) in the natural fashion. By Fact 1, Now, we define an approximate unitary 2-design via the so-called twirling operation as in [2]. Let ν be a probability measure on U(d). Let Λ be a superoperator on M d . Define the ν-twirling operation E ν : L(M d ) → L(M d ) as follows: where Λ ∈ L(M d ) and X ∈ M d . When ν is the Haar probability measure on U(d), we shall write the above superoperator as E Haar (Λ).
We now recall the definition of a quantum tensor power expander [15].
Definition II.2. A quantum t-tensor product expander (t-qTPE) in H, |H| = d, of degree s can be defined as a quantum operation G : L(H ⊗t ) → L(H ⊗t ) that can be expressed as The qTPE is said to have second singular value λ if G − I ∞ ≤ λ, where I is the 'ideal' quantum operation defined by its action on a matrix M by We use the notation (d, s, λ, t)-qTPE to denote such a quantum tensor product expander.
From the above definition, it is easy to see that a (d, s, λ, t)-qTPE is also simultaneously a (d, s, λ, t ′ )-qTPE for any t ′ < t.
Let X 1 , X 2 , . . . , X n be a sequence of {0, 1}-valued random variables. Let 2 ≤ k ≤ n. Let S ⊆ {1, 2, . . . , n}, S = {s 1 , s 2 , . . . , s k }. Let X s1 X s2 · · · X s k denote the actual joint distribution of the corresponding random variables. Let 0 < p < 1. Let B(k, p) denote the Bernoulli distribution i.e. the distribution of k fully independent identical coin tosses with probability of a coin turning up HEAD equal to p. The sequence X 1 , X 2 , . . . , X n is said to be θ-approximate p-biased k-wise independent if for any subset S = {s 1 , . . . , s k }, i.e. the joint probability distribution of any subset of the random variables of size k is θ-close to the Bernoulli distribution in ℓ 1 -distance.
We first state a Chernoff bound for a fully independent (i.e. 0-approximate n-wise independent) sequence of random variables. This bound can be derived from [7, Corollary A.1.14]. .
We now state a Chernoff-like bound for θ-approximte k-wise independent random variables. This bound can be derived from [12,Theorem 5].
Fact 4. Let k, n be positive integers, θ > 0 and r k + 2 log log k + 2 log log n + 2 log θ −1 . Then there is a function f : {0, 1} r → {0, 1} n such that, if the uniform distribution on {0, 1} r is provided at the input, the resulting sequence X 1 , X 2 , . . . , X n at the output is a θ-approximate 1/2-biased k-wise independent sequence of random bits. Moreover there is a deterministic algorithm that, given an input string z ∈ {0, 1} r and a bit position i ∈ {1, 2, . . . , n}, computes the output bit f (z) i in time poly(r).
Facts 3 and 4 allow us to prove the following easily.
where the expectation is taken over the random variable Y uniformly distributed on Y. Let n be a positive integer, ǫ, θ > 0 and r 4ǫ 2 n log |Y|) + 2 log θ −1 . Then there is a function f : {0, 1} r → Y n such that, if the uniform distribution on {0, 1} r is provided at the input, the resulting sequence X 1 , X 2 , . . . , X n of random bits at the output, where X i = 1 with probability g(Y i ) and 0 otherwise, satisfies X being defined as n −1 n i=1 X i . Moreover there is a deterministic algorithm that, given an input string z ∈ {0, 1} r and a position i ∈ {1, 2, . . . , n}, computes the output element f (z) i ∈ Y in time poly(r) log |Y|.

III. BOUNDING THE TAIL OF THE GATE FIDELITY DISTRIBUTION
In this section, we show how to bound the tail of the gate fidelity distribution, both under the Haar measure as well as under the uniform measure on a qTPE. As a warmup, we first show that approximate unitary 2-designs and 2-qTPEs are related.
Above, we used the so-called swap trick Tr [M N ] = Tr [(M ⊗ N )S] in the second equality, ⊗ ′ , ⊗ ′′ in the fourth equality indicate that the splitting of the tensor multiplicands is different from the splitting in X ⊗ V , the fact that G(X) 1 ≤ |H| X 1 G ∞ for an operator X ∈ L(H) and superoperator G : L(H) → L(H) in the third inequality, and V 1 = d 2 in the fifth equality. Since This completes the proof.
We now prove four lemmas that will help us relate the tail of the distribution of gate fidelity calculated with respect to a unitary chosen from the Haar measure versus chosen from a t-qTPE.
Lemma III.1. Let {A k } k be Kraus operators of quantum operation Λ, i.e., Λ(ρ) = k A k ρA † k . We will use F (V ) as a shorthand for F Λ (V ). Let l be a positive integer. Let a ∈ C.
Proof. We have This proves the first equality. For the second equality, This completes the proof.
Lemma III.2. Under the notation of Lemma III.1, where the inequality is obtained by applying Cauchy-Schwarz to the Hilbert-Schmidt inner product. Then This completes the proof of the lemma.
Lemma III.3. Let d, l, s be positive integers and λ > 0. Let a ∈ C. The notation E V :qTPE [·] denotes the expectation with respect to a d × d unitary V chosen uniformly at random from a (d, s, λ, 2l)-qTPE. The notation E V :Haar [·] denotes the expectation with respect to a d × d unitary V chosen from the Haar measure. Then, Proof. Using Lemmas III.1 and III.2, we get This completes the proof of the lemma.
Lemma III.4. Let t be a positive integer. Let d, l, s be positive integers and λ > 0. Let 0 ≤ a ≤ 1.
The notation E V1,...,Vt:qTPE [·] denotes the expectation with respect to independently choosing d × d unitaries V 1 , . . . , V t uniformly at random from a (d, s, λ, 2l)-qTPE. The notation E V1,...,Vt:Haar [·] denotes the expectation with respect to independently choosing d × d unitaries V 1 , . . . , V t from the Haar measure. Define the function f : where in the fourth inequality we used the fact that if (i 1 , . . . , i p ) is a partition of l where each i m = 0, 1 ≤ m ≤ p, then for any x > 1, This completes the proof of the lemma.
We now prove the following important result giving a tail bound on the uniform average of t gate fidelity functions, when the t unitaries are chosen independently and uniformly from a qTPE.
Proposition III.5. Let t, d, s, l be positive integers and δ, λ > 0. Consider the probability distribution on points (V 1 , . . . , V t ) ∈ U(d) ×t obtained by choosing each V i independently and uniformly from a (d, s, λ, 4l)-qTPE. Define the function f : i.e., f is the average of t gate fidelities. Then, For the special case where l = 1, we get Proof For larger values of l, we employ the l-moment method of [4] as adapted into the quantum setting by Low [5], combined with the tail bound of Equation 3 for the Haar measure. We obtain

This gives us
Pr (V1,...,Vt):qTPE This completes the proof of the proposition.

IV. EARLIER WORK ON ESTIMATING AVERAGE GATE FIDELITY
We first recall the naive algorithm [1] for estimating average gate fidelity using Haar random unitaries for reference and comparison. The basic procedure is the following. It is easy to see that the probability of success in one iteration of the basic procedure is, by taking |ψ U |0 , The basic procedure of the naive algorithm is prohibitively expensive, both in terms of the computational cost required to implement the Haar random unitaries as well as in terms of the number of random bits required to do the sampling. Uniformly sampling a d × d Haar random unitary to within ℓ 2 -distance ǫ requires at least Ω(d 2 log(1/ǫ)) random bits and circuit size at least Ω( d 2 log d log(1/ǫ)) [17, Lemma 3.5]. Thus the overall number of random bits used by the basic procedure becomes Ω(d 2 log(1/ǫ)), and the overall circuit size of the basic procedure Ω( d 2 log d log(1/ǫ)). Since twirling with a Haar random unitary is the same as twirling with a uniformly random unitary chosen from an exact unitary 2-design, we can replace the Haar random unitary in the basic procedure by a uniformly random unitary chosen from an exact 2-design without changing the probability of success at all [2]. The advantage of doing so is that there exist 2-designs each of whose unitaries can be implemented by a circuit of size O((log d) 2 ), whereas a Haar random unitary almost always requires circuits of size at least Ω(d 2 log(1/ǫ)) to implement within precision ǫ.
One iteration of the basic procedure succeeds with probabilityF Λ . A single outcome, success or failure, gives us no clue about the value ofF Λ . So in order to actually estimateF Λ to within an additive error ǫ, with confidence 1 − δ, we have to repeat the basic procedure several times. Neither [1] nor [2] do this rigorously. We now address this important shortcoming. Let us repeat the basic procedure independently Θ(ǫ −2 log(1/δ)) times and take the empirical average of successes. By Fact 2, an estimate ofF to within an additive error of ǫ with probability at least 1 − δ. The running time of this algorithm turns out to be O(ǫ −2 log δ −1 (log d) 2 ), and the number of random bits consumed turns out to be O(ǫ −2 log δ −1 log ǫ −1 (log d) 8 ) [9]. We note that there are constructions of exact unitary 2-designs [10] using Clifford gate circuits of size O((log d)(log log d) 2 (log log log d)), but they use at least Ω(log d) ancilla qubits. Since qubits are likely to be a very expensive resource in foreseeable implementations of quantum gates, we prefer that all our algorithms be in-place without using ancilla qubits.
Dankert et al. [2] showed how to improve the running time and the number of random bits in the basic procedure by replacing the use of an exact 2-design by a θ-approximate 2-design. Due to the replacement, the probability of success in the basic procedure becomes where we used the fact that Λ ♦ = 1 as Λ is a quantum operation. We can now take θ = ǫ/2 and repeat the basic procedure Θ(ǫ −2 log(1/δ)) times and take the empirical average of successes, in order to get an estimate ofF Λ to within an additive error of ǫ with confidence 1 − δ. The running time and usage of random bits of this algorithm turn out to be O(ǫ −2 log δ −1 (log d) log ǫ −1 ). [2]. We note that Dankert et al. [2,Theorem 3] incorrectly repeat the basic procedure O(log δ −1 ) times to get confidence 1 − δ, ignoring the issue of additive error ǫ completely.
By Fact 6, replacing the Haar random unitary U in the basic procedure by a (d, s, ǫ 2d 4 , 2)-qTPE G also leads to an efficient algorithm for estimating average gate fidelity. In fact, a direct analysis shows that a (d, s, ǫ 2d , 2)-qTPE suffices too. Such 2-qTPEs can be obtained via the so-called zigzag product [6]. The unitaries of the qTPE can be implemented by circuits of size O((log d) 2 (log d/ǫ). The number of random bits required is only O(log(d/ǫ)). The running time of this algorithm turns out to be O(ǫ −2 log δ −1 (log d) 2 (log d/ǫ)), and the number of random bits consumed turns out to be O(ǫ −2 log δ −1 log(d/ǫ)). The circuit size is slightly inferior to Dankert et al. [2] but the number of random bits used is less.

V. RANDOMNESS EFFICIENT ALGORITHM USING APPROXIMATE UNITARY 2-DESIGNS
Instead of repeating Algorithm 1 with independently chosen unitaries per iteration, we pick the sequence of unitaries of the approximate 2-design from an approximate k-wise independent distribution for a suitable value of k. For clarity, we give the full algorithm below. Algorithm 3 consists of a classical preprocessing step where the sequence Y 1 , Y 2 , . . . , Y n is computed. This takes classical deterministic time O(ǫ −2 poly(r)). After the preprocessing step, Algorithm 3 runs in quantum time O(ǫ −2 log δ −1 (log d) 2 (log(d/ǫ))). The number of random bits used is r = O(log δ −1 (log(d/ǫ) + log log δ −1 )). By Fact 5, Algorithm 3 gives an estimate b ofF Λ such that Pr[|b −F Λ | > ǫ] ≤ δ. Comparing with the zigzag product based algorithm in Section IV, we get the same quantum circuit size but much lesser usage of random bits.
Instead of the zigzag product, we can take the ǫ/2-approximate unitary 2-design of Dankert et al. [2]. An advantage of doing this is that we use only Clifford gates in the approximate unitary 2-design which may be technologically easier to implement. That would give us classical preprocessing time of O(ǫ −2 poly(r)), quantum time of O(ǫ −2 log δ −1 (log d)(log ǫ −1 )) and number of random bits r = O(log δ −1 ((log d)(log ǫ −1 ) + log log δ −1 )). Comparing with the corresponding algorithm in Section IV, we get the same quantum circuit size but much lesser usage of random bits. Thus this algorithm is a good candidate for actual experimental implementations in the near future.
unitary Y will give an estimate b of F Λ (Y ) such that where the probability arises because of inherent quantum uncertainty of measurement outcomes. Overall we get, Pr[|b −F Λ | > ǫ] ≤ δ. Algorithm 4 takes quantum running time O(ǫ −2 log δ −1 (log d) 3 ) which is the same as the zigzag product based approximate 2-design Algorithm 3 of Section V. However it consumes only O(log d) random bits, where the constant hiding in the O(·) is independent of ǫ and δ, which is less than what Algorithm 3 consumes. The drawback of Algorithm 4 is that it requires that 108 ǫ 2 d < δ 2 , whereas Algorithm 3 has no such assumption. In practice, this means that Algorithm 4 can only be used if the dimension d is large and the estimation error ǫ and confidence error δ are not too small.

VII. RANDOMNESS EFFICIENT ALGORITHM USING APPROXIMATE 4l-QTPE
We now address the main drawback of Algorithm 4 i.e. what if the dimension d is not large enough? This is a pertinent question because in the near future we hope to experimentally implement and benchmark quantum circuits acting on ten to fifty qubits. For ten to twenty qubits, the dimension d may not be large enough to satisfy the assumption 108 ǫ 2 d < δ 2 for reasonably small values of ǫ and δ. It would be nice to have an efficient algorithm using a few random bits for arbitrary values of d, ǫ and δ. Algorithm 3 is one such algorithm, but it requires us to be able to implement the entire plethora of 2 Ω(log(d/ǫ)) unitaries in an approximate 2-design. In some technological scenarios, it may be better to spend a few more random bits but reduce the number of unitaries that may need to be implemented by the algorithm. Algorithm 4 is indeed a step in this direction but it suffers from the drawback mentioned above.
To achieve this goal, we develop Algorithm 5 by combining ideas from Algorithms 3 and 4. Algorithm 5 is a two-phase algorithm using an l-qTPE for l ≥ 4, but still small enough to be efficiently implementable.
Choose: independently and uniformly at random unitaries V 1 , . . . , V t from Y. Call this set of unitaries as Y.
Construct: a sequence Y 1 , Y 2 , . . . , Y n of unitaries from Y as the output of f : {0, 1} r → Y n guaranteed by Fact 5, when a uniformly random input z ∈ {0, 1} r is fed to f , where r ǫ 2 n log t + 2 log θ −1 .
In Phase 1, we take a (d, s, λ, 4l)-qTPE V and sample from it independently and uniformly at random a small number of unitaries V 1 , . . . , V t . For l = log(16/δ), t = 2 11 l ǫ 2 d = 2 11 log(16/δ) . λ ( ǫ 2 2 5 d 2 ) l = ( ǫ 2 2 5 d 2 ) log 16/δ , Proposition III.5 will ensure that the gate fidelity averaged over this small set of unitaries is ǫ/2-close to the actual average gate fidelityF Λ with confidence at least 1 − δ 2 . The number of random bits required to independently sample t times uniformly from V is Each unitary in V can be implemented in quantum time O((log d) 2 (log δ −1 ) 3 (log log δ −1 ) log(d/ǫ)). The constants hiding in both the O(·) notations above are independent of d, ǫ, δ. These facts follow from the so-called zigzag product [6]. Morally speaking, this preprocessing step achieves the goal of the first phase of Algorithm 4. In Phase 2 of our algorithm, we sample only from the set Y {V 1 , . . . , V t } in an approximate limited independence fashion as in Fact 5, and run Algorithm 2 on those samples in so as to empiricially estimate the gate fidelity averaged over the set Y. We apply Fact 5 with n 2 4 log(4/δ) 2 4 log(4/δ) ) log(4/δ) , r ǫ 2 n log t + 2 log θ −1 = 16 log δ −1 (log log δ −1 + 2 log ǫ −1 − log d + O(1)) + 2 log(4/δ) Morally speaking, this achieves the goal of the second phase of Algorithm 3.
We now analyse the running time and number of random bits used by Algorithm 5. The total confidence of Phases 1 and 2 is at least 1 − δ. Suppose 2 11 log(16/δ) Then, we set t = 1 and so Phase 2 does not use any more random bits. The total number of random bits used in Phases 1 and 2 now becomes O(log δ −1 log(d/ǫ)), where the constant hiding in the O(·) notation does not depend on ǫ, δ, d. This is comparable to the total number of random bits used by Algorithm 3. However, Algorithm 5 requires us to implement only one unitary as opposed to implementing potentially all the unitaries in an approximate 2-design in Algorithm 3. Also the constraint on the dimension d is less stringent than the constraint required by Algorithm 4. Suppose 2 11 log(16/δ) The total number of random bits used in Phases 1 and 2 becomes where the constant hiding in the O(·) notation does not depend on ǫ, δ, d. Now the number of random bits used is greater than that of Algorithm 3. However, Algorithm 5 requires us to implement only log(16/δ) ǫ 2 d unitaries as opposed to implementing potentially 2 Ω(log(d/ǫ)) unitaries in Algorithm 3. This is a big saving on the number of unitaries an algorithm has to potentially implement. In both cases, the total running time of Algorithm 5 is O(ǫ −2 (log δ −1 ) 4 (log d) 2 (log log δ −1 ) log(d/ǫ)), which is slightly worse than that of Algorithm 3. The worse running time is due to the fact that Algorithm 5 needs a O(log δ −1 )-qTPE whereas Algorithm 3 only needs a 2-qTPE. Any future improvement in construction of t-qTPEs for large t will improve the running time of Algorithm 5.

VIII. CONCLUSION
We have described three new algorithms for efficient in-place estimation, without using ancilla qubits, of average fidelity of a quantum logic gate using much fewer random bits than what was known so far. We considered only in-place algorithms in this work because qubits are likely to remain an expensive resource in experimental implementations in the near future, and so we would like to avoid ancilla qubits as far as possible. We achieve the reductions in the number of random bits by appealing to two powerful tools. The first tool, a limited independence pseudorandom generator, comes from classical derandomisation theory in computer science. It is used in the first and the third estimation algorithms. The second tool, an approximate l-quantum tensor product expander (l-qTPE) for moderate values of l, is a recent quantum computational object defined as an analogue of an approximate l-wise independent pseudorandom generator well known from classical derandomisation theory. In fact, to obtain our parameters we actually have to appeal to the state of the art in quantum tensor product expanders, which in turn were obtained by 'quantising' another famous result from classical derandomisation theory viz. the zigzag product of graphs. The second tool is used in our second, and more strongly, in our third estimation algorithm.
Each of our algorithms have unique features that, depending upon the experimental limitations and desired parameters, sometimes make one of them the most suitable, sometimes another. If one wants an efficient algorithm that works for all values of the gate dimension d, estimation error ǫ and confidence error δ, and uses the least number of random bits, then the first algorithm is the way to go. Reducing the number of random bits will increase the reliability of the estimation in practice as explained earlier. Moreover, this algorithm can be chosen to be implemented using only Clifford gates which may be an advantage for some technologies.
If the gate dimension is large, then the second algorithm is the best one. It uses the least number of random bits and needs to implement only one unitary from an approximate 4-qTPE. If the aim is to use an algorithm that works for all parameter values but needs to implement as few unitaries as possible, then the third algorithm is the right one. Though it uses more random bits than the first algorithm, it needs to implement much fewer unitaries than the first. This feature can be the most crucial for certain technologies.
Moving on from estimating average gate fidelity, it will be interesting to find other applications of both classical derandomisation as well as quantum derandomisation tools in quantum computation, both theoretical and experimental. The experimental implementations of quantum computers of the near future, of the order of tens of qubits, will be very noisy. Reliable and efficient test suites optimised for every bit of precision and performance are the need of the hour to measure progress in the exciting times to come.


extfieldsofstudy:
Computer Science
Medicine
Mathematics

text:
Learning Where to See: A Novel Attention Model for Automated Immunohistochemical Scoring

Estimating over-amplification of human epidermal growth factor receptor 2 (HER2) on invasive breast cancer (BC) is regarded as a significant predictive and prognostic marker. We propose a novel deep reinforcement learning (DRL) based model that treats immunohistochemical (IHC) scoring of HER2 as a sequential learning task. For a given image tile sampled from multi-resolution giga-pixel whole slide image (WSI), the model learns to sequentially identify some of the diagnostically relevant regions of interest (ROIs) by following a parameterized policy. The selected ROIs are processed by recurrent and residual convolution networks to learn the discriminative features for different HER2 scores and predict the next location, without requiring to process all the sub-image patches of a given tile for predicting the HER2 score, mimicking the histopathologist who would not usually analyze every part of the slide at the highest magnification. The proposed model incorporates a task-specific regularization term and inhibition of return mechanism to prevent the model from revisiting the previously attended locations. We evaluated our model on two IHC datasets: a publicly available dataset from the HER2 scoring challenge contest and another dataset consisting of WSIs of gastroenteropancreatic neuroendocrine tumor sections stained with Glo1 marker. We demonstrate that the proposed model outperforms other methods based on state-of-the-art deep convolutional networks. To the best of our knowledge, this is the first study using DRL for IHC scoring and could potentially lead to wider use of DRL in the domain of computational pathology reducing the computational burden of the analysis of large multigigapixel histology images.

I. INTRODUCTION
uman epidermal growth factor receptor 2 (HER2) is a protein that influences the growth of malignant epithelial cells. The over-amplification of HER2 gene is observed in breast cancer (BC) cases having invasive tumor regions. Cancer cells in HER2+ (positive) cases of BC encounter neoplastic transformations which lead to an uncontrolled growth of tumor cells as compared to HER2 (negative) cases. Approximately all the invasive breast carcinomas cases are recommended for HER2 testing [1] and nearly 20-30% of cases have overexpression of HER2 protein [2] which is associated with poor prognosis, lower survival, and high recurrence [3]. Recent studies have reported the HER2 status as a predictive factor for anti-HER2 and hormonal therapies and also a prognostic factor to associate invasive tumors with mortality and duration of recurrence free survival [4]. Therefore, precise quantification of HER2 overexpression is crucial for ensuring that HER2+ patients receive appropriate anti-HER2 treatment.
The most common method for assessment of HER2 biomarker expression is immunohistochemical (IHC) staining. In routine clinical practice, an expert pathologist visually examines IHC stained BC histology slides under the microscope to quantify the expression of HER2 and reports a score between 0 and 3+. Example regions of interest (ROIs) from slides with different HER2 scores (0 to 3+) are shown in Fig. 1. Samples scoring 0 or 1+ contain no or weak membrane staining in less than 10% of the tumor cells and are regarded as HER2. A score of 3+ is assigned to cases where strong membrane staining is observed in more than 10% of the tumor cells and regarded as HER2+. Borderline cases, in which a non-uniform staining is observed, are classified as equivocal with a 2+ score. Such cases are recommended for fluorescence in-situ hybridization (FISH) test to measure the status of HER2/neu gene amplification. A limitation of the current practice for HER2 scoring is that the visual examination of glass slides is a time consuming and laborious task, as well as subjective by nature and more likely to be affected by interand intra-observer variability. It has also been reported that up to 20% of the HER2 results may contain inaccuracies [5].
Recently, there has been an upward trend in the adoption of digital pathology and consequently a surge of research on algorithms for analysis of pathology images. Despite the recent progress that highlights the significance of image analysis in computational pathology [6] [7], there are several challenges that hinder the adoption of algorithms in routine clinical practice. Computational pathology algorithms usually require detailed annotated datasets to predict the slide label. For the task at hand, the ground-truth (GT) label for IHC score (HER2 score in our case) is generally provided at the whole slide image (WSI) level and there are no detailed annotations provided about which ROIs from the tissue slides are consulted for the final HER2 score. Amongst existing automated approaches, the simplest approach is to manually or randomly extract patches from desired ROIs of a WSI and train a supervised model to predict the required HER2 score. H Such approaches offer an inevitable bias to the model predictions and disjoint selection of small patches may also suffer from loss of visual context. Another potential shortcoming is computational inefficiency, as these models need to process all the regions of a given image, where some of the tissue regions may not be diagnostically relevant for the prediction of the correct HER2 score. With regards to the aforementioned challenges, we ask the question: can we train a model that ignores the irrelevant information and learn where to see? To answer this question, we propose a novel deep learning approach for automated scoring of IHC stained HER2 slides of invasive breast carcinoma, based on the concept of policy gradients. Given a large tile from a WSI, the proposed model identifies some of the diagnostically relevant locations from a low resolution (2.5 ×) coarse representation of a given image by learning a parameterized policy over the interaction sequences of ROIs locations. The model sequentially samples the multi-resolution ROIs 40 × and 20 ×, from the relevant locations to learn the discriminative features for different HER2 scores (0 to 3+). The core components of the proposed model are a residual convolutional neural network (ResNet) and a recurrent neural network (RNN). The role of ResNet in this model is to learn discriminative features whereas the RNN sequentially analyzes the provided features to predict the outcome and the next location. Since the GT information was only provided for WSI level with no prior knowledge of ROI locations, we train the model with policy gradients. Our model is designed to explore spatially distinct locations and learn features from visually discriminative regions. In cognitive psychology, this phenomenon is known as inhibition of return (IoR) [8] that prevents the previously attended regions to be attended again. Our model incorporates the concept of IoR in order to encourage the model to attend non-overlapping diagnostically relevant regions. Another important issue is that an erroneous scoring of 3+ as 0/1+ or vice versa may have far-reaching effects for a patient. In order to avoid such large errors, we propose a task-specific regularization term that penalizes such predictions. This study was conducted on a publicly available dataset from the HER2 scoring contest [9] containing 172 WSIs from 86 cases. Extensive experiments on the contest dataset show the efficacy of our proposed model, for guiding deep learning models to ignore irrelevant regions and scaling up to large images. The proposed method outperforms all the 18 algorithms that participated in the HER2 contest, most methods using state-of-the-art CNNs.

II. RELATED WORK
Automated IHC scoring has been approached with a variety of handcrafted features and deep learning based methods. The most common approach for automated IHC scoring involves a pre-processing step to identify the potential tissue regions for training the underlying model. Then, a handful of small patches are sampled from selected tissue regions, either randomly or by using sliding window approach. The identification of potential tissue regions is generally accomplished by manual selection [10] [11], semi-automated [12] or thresholding based automated methods [13]. The preprocessing step is generally followed by training a patch-based supervised model, to learn the discriminative features and predict the outcome of each input patch. A range of handcrafted [13] [14], approaches have been proposed to improve the IHC scoring of hormone receptors in breast cancer. For HER2 scoring, Rodner et al. [15] recently proposed an algorithm that computes a set of bilinear filters using convolutional layers. For classification of HER2 scores on patch level, they use bilinear features to train a multi-class logistic regression model. A deep neural network has been presented by Saha et al. [16] for HER2 quantification by segmenting nuclei and cell membranes. Mukundan et al. [17] introduced a set of characteristic curves by varying the intensity of saturation channel with a handpicked threshold for classification of HER2 score. The final step of HER2 scoring in general involves aggregation of patch level scores to the WSI level score which is typically done by finding the most dominant class within a WSI or by training a shallow classifier on features selected from the output probability map of a WSI. Supervised patch-based approaches have established well for problems where tissue level GT is readily available. However, in IHC scoring where tissue level GT is generally not available, it is imperative to explore how deep learning models can be trained to ignore unnecessary information from the given image and focus only on regions that eventually helps in predicting the correct outcome.
Recent studies have shown that deep reinforcement learning (DRL) has been employed in widespread applications. For object detection, Caicedo et al. [18] proposed a deep Q-Network (DQN) for multi-class object localization. The model localizes target objects by following a search strategy, which starts with analyzing the input image and then agent guides the model to narrow down the field of view for precise object localization. The reward function was calculated by computing the intersection-over-union between the GT and the predicted bounding box for the object. This work was further extended for medical images including automated anatomical landmark [19] and breast lesion detection [20] for DCE-MRI images, whereby an agent localizes the potential ROI containing the lesion by iteratively adjusting the bounding box. The reward function was computed by using the Dice coefficient between the GT and the predicted box. There also exist some works that incorporate DRL for genomics data to enhance the annotation of biological sequences in genome sequencing [21] and construction of protein interaction network for prostate cancer [22]. Another interesting extension is the incorporation of attention models with policy gradients that enable the underline model to learn a parametrized policy based on spatial dependencies. This combination has been explored for a number of applications including object detection [23], action recognition [24] and image captioning [25]. However, having precisely annotated GT for computing the reward function limits the use of deep Q-learning for IHC scoring.
In this work, we treat IHC scoring as a sequential learning task to learn discriminative features and select informative regions within a large image tile of a WSI. To the best of our knowledge, this is the first study that uses DRL for IHC scoring of histology WSIs. In terms of policy learning methodology, our work has some similarities to the methods proposed by Mnih et al. [26] and Ranzato et al. [27]. Our proposed model contains a context module that incorporates the coarse representation of input image, before predicting attentive locations. The end-to-end inhibition of return (IoR) mechanism encourages the model to explore spatially distinct attentive locations. Moreover, the scope of existing attention methods is limited to relatively small natural images whereas tumors in IHC stained WSIs are heterogeneous in terms of their morphological appearance, color variability, shape, and temporal locations.

III. LEARNING WHERE TO SEE
Given an image , the task is to predict the HER2 score ranging from 0 to 3+ by selecting a set of diagnostically relevant regions as well as learning discriminative features from those regions. The schematic diagram of the proposed model is shown in Fig. 2. At each time step , the model receives two ROIs = ( , ), where ,  are regions of width 128 and height 128 sampled at the region center at different magnification levels 40 × and 20 ×, respectively. The convolutional network with learnable parameters analyzes and transforms it into a fixed length feature vector ∈ ℜ . The recurrent model with learnable parameters sequentially processes the aggregated ROI features to update its internal state. Besides, the context model processes the down-sampled version ↓ (down-sampled by a factor of 16 in both directions) of the input image and perform the IoR operation, as described in Section III.D. The next location is predicted by analyzing the hidden state ( ( )) from the RNN that reflects where we currently are, and the output ↓ of CNN , with learnable parameters , that represents the context. The whole process is repeated for iterations and at the end of the sequence ( , , … . , ), the model predicts the final output score . This iterative process wrapped around an RNN model forms a classical environment-agent interface that can be formalized by the partially observable Markov decision process (POMDP). In the current setup, the RNN and CNNs collectively act as a decision maker, which is formally known as an agent in the reinforcement learning (RL) literature. The agent sequentially interacts with the environment, which in our case is the image . For each time step , the agent receives a state from the environment. It then processes the given state and responds with appropriate actions, which in our cases is ), directing the model where to see and eventually deciding on the HER2 score. Overall this process of predicting the next location is partly stochastic and nondifferentiable, requiring the use of policy gradients. The ultimate task for an agent is to map the given states into actions by learning a parametrized policy ( ) through trial and error. At the end of this sequential process, the agent receives a scalar reward based on its actions, which in our case is linked to correct prediction of the HER2 score as described in Section III.C.
At a high level, our model mimics the histopathologist practice treating a given image as an environment and the histopathologist as an agent who acts as a decision maker. Given the environment, the agent glances through different tissue components at a high level (low magnification) and then selects certain visual fields (ROIs) at low level (high magnification) to observe and store the relevant morphological features into the memory. The agent repeats this process for a certain number of iterations on different states to build an internal representation of the overall environment before coming up with the final decision, i.e. assigning the final score. For the sake of simplicity, in the remainder of this paper, we refer to the combination of RNN and CNNs as an agent and the selected ROIs as the state.

A. Sequential Modelling
The recurrent component (RNN) acts as the backbone of the proposed model. At each time step , the recurrent model updates the parameters of hidden states and predicts the HER2 score for a CNN based feature representation of = ( , ). The input to the RNN is , the CNN based feature vector for multi-resolution ROIs centered at location . The RNN model also updates internal states (memory) that capture information from previous time steps. The output ( ) of the RNN model is defined as below, We choose long short-term memory (LSTM) [28] as a preferred choice for RNN to learn spatial dependencies between the ROIs. LSTM has proven to be more robust and less likely to suffer from the problem of vanishing gradients. An important task of the model is to predict the next location by using ↓ provided by CNN and hidden representation ( ) of ROI images processed by CNN and LSTM. We computed the Hadamard product of ( ) and ↓ to obtain a combined feature vector. Finally, the location module ( ), linearly transforms the combined representation to predict the normalized coordinates of the next location ( , ). During the training process, the model eventually learns to encode the information from the past sequences and decide where to see.

B. Residual Convolutional Network
In the proposed model, the convolutional network serves as a non-linear function that maps a given RGB image into a fixed length vector representation. More specifically, we are using a variant of residual CNN [29] that contain residual connections to reroute the input information into deeper convolutional layers. Residual blocks ensure the end-to-end training of deep models by preventing the gradient to vanish within lower layers of a CNN. It also enables the underlying model to reuse the low level features along with deeper convolutional (high level) features. For a given input , the residual block function is defined as below where ( , ) is representing a sequence of convolutional operations, denote the trainable weights (biases are omitted), represents the residual block of the CNN, is the output of residual block and ( ) = is an identity function. The function (. ) denotes a non-linear activation function, which in our case is a ReLU. The ( , ) + operation is representing element-wise addition of two activation maps. A schematic illustration of the residual CNN is shown in Fig. 3.
We use two residual CNNs, and where learns discriminative features by producing a fixed length non-linear vector representation for further processing by the recurrent network and incorporates the context information. The input to ( ) is the corresponding ROIs (at 40 × and 20 ×) sampled at ( , ) from the input image . The network separately processes the selected ROIs and concatenates the feature representative of , . The concatenation operation is previously used in [30] for a hierarchical CNN to combine the feature representation of corresponding up/down convolution layers. The CNN features of extracted ROIs mainly assist our model to learn the discriminative patterns of different HER2 scores. The task for ( ) is to embed the contextual awareness within the proposed model.

C. Model Training
The proposed model (Fig. 2) is trained end-to-end by maximizing the performance over the parameters = ( , , ) of the residual CNNs, recurrent network and the location module. By interacting with the environment, the model forms a special case of the POMDP framework with an episodic sequence of states, actions, and rewards. The task for the model is to learn a parameterized DRL policy ( ) that maps a given state into action(s) by maximizing the sum of expected reward while following the parameterized policy . The parameterized policy for calculating the probability of a certain action from the action space at iteration for a given state with parameters can be defined as follows, where denotes the set of possible states at time t. Similarly, for the problem at hand, the model needs to learn a parameterized policy (( , ) | ( , ↓ ); ) to predict the HER2 score ( ) and coordinates of the next location ( , ), given the selected ROIs ( ) from ( , ) and down-sampled input image ↓ . The model receives a scalar reward after interacting with each selected ROIs ( , ,.. ) of the given image, ' 1 argmax 0 otherwise as provided in (5), where denotes the GT score, represents the output of the softmax layer and s denotes the output label. The total sum of reward is computed after analyzing all the selected ROIs, as defined below, where is the weight factor for reward at time t. For a finite horizon problem such as classification, we set = 1.
Here the learning task is to optimize the parameters that maximize the overall performance ( ), associated with reward . A straightforward approach for handling this maximization task is by using the gradient ascent. The update rule follows the standard backpropagation and is defined as, where is the iteration index and is the learning rate. In order to maximize ( ), we employ the REINFORCE rule [31] from the class of policy gradients to adjust the model parameters. In this episodic scenario, on average, the model computes the gradients for actions that lead to higher rewards and consequently, the log probability of actions with low rewards will be decreased. The policy gradient, as described above, can be mathematically expressed as follows, One limitation of the above formulation is that the model convergence can be challenging if intra-class variance in the training dataset is relatively high. To generalize the policy gradient algorithm, we include a baseline function = [ ] for comparing the action values to the cumulative reward [32], 16

D. Inhibition of Return
An important factor in adequate selection of diagnostically relevant regions is to inhibit the model from visiting the previously attended regions. We observe that for some of the selected locations during the sequential process, the sampled ROIs are not spatially distinct.  (2 nd row). A straightforward strategy to address this issue would be to suppress the texture information [8] of previously attended locations that would encourage the model to rapidly explore spatially distinct locations. This simple Inhibition of return (IoR) strategy leads to the model giving higher priority to regions that it has not previously considered for learning the discriminative features. The IoR strategy is computationally efficient, widely studied in cognitive psychology [33] and in sequential learning [8] [18].
Further, we introduced an additional constraint in the loss function. At the end of the iteration sequence = (1, … , ), computes the overlap between the coordinates of selected ROIs, penalizing selection of image patches relatively close to each other. The scope of IoR penalization vanishes (its value becomes 0) if selected locations are spatially distinct from each other. The term is defined as below, where [ ] and [ ] represent rectangular coordinates sampled from the input image and is the number of combinations of different ROIs, in turn helping in limiting the intersection values between 0 and 1. The above loss function updates the policy parameters to correctly predict the HER2 score by penalizing the model for locating spatially overlapping regions.

E. Task-Specific Regularization
The clinical impact of large erroneous predictions of HER2 score is highly significant and should be avoided as much as possible. Inaccurate prediction for patients of score 0/1+ as 3+ will lead to giving treatment with toxic anti-HER2 drugs to patients who do not need it, while predicting cases with score 3+ as 0/1+ will lead to the patient not given the appropriate treatment needed. To avoid such scenarios, we added a taskspecific regularization term.
The final loss function combines the parameterized loss with task-specific regularization and IoR as given in (13), where  controls the sensitivity (scope of penalty) for both and .

A. The Dataset
This study is conducted on a publicly available dataset from the HER2 scoring contest [9]. The contest dataset consists of WSIs from 172 histology slides of 86 invasive breast carcinomas cases scanned using Hamamatsu NanoZoomer C9600 at the highest resolution (40 ×), two slides per case (one IHC stained with HER2 and another with the standard H&E). On average, each scanned WSI contains more than 10 pixels. The GT for the contest was marked by a minimum of two expert histopathologists. For each case in the training dataset, the GT consists of a HER2 score and a percentage of complete membrane staining (PCMS), both at the WSI level. The training dataset is made of 52 cases, 13 cases from each HER2 score (0-3+) and the test set consists of 28 cases. The remaining 6 cases were not included in the test/training dataset and only reserved for the on-site part of the competition, see [12] for more details.

B. Experimental Setup
The ROIs were cropped at 40 × and 20 × resolutions, each ROI of size 128 × 128 × 3 pixels. The size of the input image was 2048 × 2048 × 3 (471.1 × 471.1 ) sampled at 40 ×. In total, we extracted 58,500 tiles (with 50% overlap) from the 52 training WSIs after tissue segmentation and a simple DAB intensity based thresholding. The number of neurons in hidden layers of RNN was set to 256 and 128, respectively. The CNN transforms the given image into the feature representation of size 1 × 128. ReLU activation function was used after each residual block. To overcome the overfitting problem, we performed data augmentation by random rotations (0°, 90°, 180°, 270°), horizontal and vertical flipping, and the transpose of all the images in the training dataset. The regularization parameter  controls the sensitivity of the task-specific regularization and IoR penalization, as in (13). Through empirical observations, we found that the best performance was achieved with a value of 0.04 for  , which we used for all the experiments. The initial learning rate was set to 0.001 with exponential reduction of 0.97 and the momentum was adjusted at 0.9. The batch size was selected as 10. The location of the first ROI was randomly selected. The number of ROIs per image was selected as 6, more details on this in Section IV.C.2. The learning parameters were initialized as Gaussian random numbers with 0 mean and 10 standard deviation and biases were set to 0.

C. Comparative Analysis
In this section, we discuss a variety of experiments to demonstrate the efficacy and evaluate the performance of the proposed method. For the following experiments, we performed 4-fold cross validation across 52 cases. We split the 52 cases into 4 subsets, with nearly equal representation of all four HER2 scores, and used 3 subsets for training and the remaining one subset for validation. The GT for the test dataset is not publicly available and, in this section, we have reported the performance of different variants of the proposed model on the validation dataset. We report the results for the test dataset in Section IV.D. Generally, a large part of WSI contains background (glass) regions with no tissue components. For tissue segmentation, we perform local entropy filtering on a lower resolution (2.5 ×) version of the WSI.

1) Comparative Results:
In this experiment, we evaluate the significance of different sub-components of the proposed model, including , , and . Another important aspect is to evaluate the significance of the parameterized policy for selecting relevant ROIs and how it affects the performance if we select ROIs randomly instead of following a certain policy. For random selection of ROIs, we perform two main experiments: a) select ROIs randomly from the entire and b) select ROIs randomly from only DAB regions of . In the first approach of random selection, we predict the HER2 score of given ROIs ( ) and select the next location randomly without consulting the context and current state of the model. Fig. S-1 in Supplementary Material-I shows the qualitative results for randomly selected regions and locations selected by the parameterized policy. Random selection correctly predicts HER2 score for images where most of the area is covered by discriminative tissue regions. However, it is susceptible to selecting regions that contain mostly background and sparse DAB regions. For the second approach, we perform stain deconvolution [34] on by estimating the stain matrix using [35]. DAB regions contain low luminance and therefore for binarizing the DAB channel using ( ), we empirically chose a relatively high threshold value of 0.8. The ( ) is then followed by morphological operations to exclude the noisy (small) components of the DAB channel. Table I shows the results for both experiments. Evidently, the second method is a relatively direct way of selecting and therefore yields higher performance as compared to the first approach for random selection. However, it offers some limitations as compared to the proposed model: the first major limitation is the absence of , that enables the model to explore spatially distinct locations. The restrains the proposed model from overemphasizing on particular locations by penalizing the learnable parameters and encourages the model to learn discriminative features from different tissue regions. One way of handling the absence of is to introduce a set of hardconstraints for selecting spatially distinct ( , ). However, defining a set of generalized hard-constrained is a non-trivial task and it may influence the model performance on images where we have sparse DAB representation (3 rd row of Fig. 5). Secondly, it has no longer access to the overall ↓ and the context module. Consequently, this variant of our proposed model could be considered a departure from the routine clinical practice, where a pathologist glances through a coarse representation of input image at a higher level and then selects ROIs at lower levels before concluding the outcome. Therefore, it is imperative to follow a parameterized policy that incorporates the context and offers a temporal connection (via LSTM) between the selected locations.
Further, we investigate the implications of the context module, task-specific regularization ( ) and IoR ( ). The context module allows the model to analyze a coarse representation of the overall environment and use that to predict ( , ). Existing attention based models [23][36] including RMVA (recurrent model for visual attention) have no mechanism to prevent models from revisiting the previously attended regions. Besides, RMVA also incorporates a strong location prior to the model, which is irrelevant in histology image analysis mainly due to the random orientation and morphological appearance of underlying tissue. Table I  ). Fig. 5 shows a sample of representative patches with selected ROIs. The most challenging images were from HER2 class 1+ and 2+, where resemblance in morphological appearance was present due to tumor heterogeneity, as shown in 2 nd and 3 rd rows of Fig. 5. In Fig. 5, the image patch for score 2+ contains relatively smaller extent of DAB expression and most of the tissue region belongs to 0/1+. In that case, the model starts with a relatively less informative region and sequentially learn to focus on the informative regions of the image to predict the correct outcome.
2) Number of ROIs: The aim of this experiment is to investigate the effect of number of ROIs for a given image . We evaluate the performance of the proposed model by using 4, 5, 6 and 8 number of ROIs. For this contest dataset, we observed the best performance with 6 ROIs, as shown in Fig.  6. One of the main reasons for relatively low performance with 8 ROIs is the images containing tissue boundary regions, where most of the image region is covered by background glass. Therefore, in those cases, selecting more locations may confound the model in predicting the correct outcome. Another interesting aspect is the reduction of inference time and gain in the overall performance (as discussed in Section IV.D), in a conventional patch-based setting, for a given image of size 2048 × 2048 × 3 at 40 ×. The model needs to process all 64 ROIs (each of size 256 × 256 × 3). In contrast, the proposed model can predict the HER2 score after consulting a handful of ROI patches accompanied with downsampled version of . However, although computing time may not be the most decisive aspect in clinical practice, it may be an important factor in high-volume diagnostic settings and for high-throughput IHC screening.

3) Selection of multiple resolution regions:
This experiment compares the performance of the proposed model for selecting a suitable combination of magnification levels. We perform this experiment with three sets of magnification levels including 40 ×, 20 ×, and 10 ×. We observed that for IHC HER2 scoring, ROIs selected from 40 × and 20 × yield the best performance. The results for mean scoring accuracy for all 4 classes are shown in Table II. ROIs selected at higher resolutions offer more detailed information regarding HER2 expression at cell levels. On the other hand, ROIs selected at 10 × or lower magnification offer more context information, but they are also more likely to contain background or irrelevant tissue regions, including non-invasive hematoxylin stained regions.  Acccomb denotes combined accuracy and CM (in 3 rd row) denotes the context module. In DAB ROIs, the locations were randomly selected from the diaminobenzidine (DAB) regions.

4) Size of ROI:
The main objective of this experiment was to evaluate the performance of the proposed model on different sizes of ROIs. After selecting the location ( , ), it is worthwhile to quantify the extent of context required for predicting the correct outcome. Recent studies in computational pathology have also emphasized the significance of visual context [37]. We perform this experiment on three different patch sizes, including 48 × 48, 64 × 64, and 128 × 128, with results in Fig. 7. We noticed the best performance with ROIs of size 128 × 128. As expected, the performance of the proposed model increases with increase in the context. However, in HER2 scoring, it is important to limit the ROI size to prevent the inclusion of irrelevant tissue regions.

D. Contest Leaderboards:
This subsection covers the description for scaling the patch level results to WSIs and performance of the proposed algorithm on the contest tasks.

1) Contest Tasks:
The performance of the proposed algorithm on the WSI level is evaluated by using 3 different criteria, as suggested in the contest guidelines: a) agreement points, b) weighted confidence and c) combined points. In agreement points, a penalty method was introduced that assigned points between 0 and 15 to each case based on the clinical significance of the difference in predicted and actual scores. To resolve tie situation in the first criterion, bonus points were also awarded based on a correct prediction of PCMS. A weighted confidence was devised to estimate the credibility of WSI results predicted by the algorithm. This measure may also help in stratifying cases that need further input from pathologists. And finally, for each case, a combined point was calculated by taking the product of the other two assessment criteria. Further details regarding the evaluation criteria is explained in [9]. ; represent the number of image tiles predicted as 0, 1+, 2+, 3 +, respectively. The PCMS for invasive breast cases was estimated by the WSI output maps. For each score map, we simply compute the ratio between the area covered by each predicted score over the total area of tissue region within the WSI.
3) Combined Leaderboards: One of the most challenging aspects in analyzing histology images is to limit the automated analysis to diagnostically relevant tissue parts. A fully supervised method processes the given image regardless of noisy or irrelevant contents. In contrast, recurrent models can appropriately tackle such scenarios by only processing the relevant ROIs.  Table III reports the WSI level performance of the proposed method on all 3 evaluation criteria. It also contains the results of top-10 performing algorithms in the contest. The proposed method ranked as 1 st amongst all 18 submissions in the contest, including the combined points criterion and point based scoring. The contesting algorithms were based on a wide range of the state-of-the-art deep convolutional networks including GoogleNet [38], AlexNet [39] and LeNet [40]. On 28 WSIs from the test dataset, the proposed algorithm correctly classified 26 WSIs. The most difficult cases were from borderline class 2+ and 3+. Both the false predictions belonged to those classes. It is worth noting that the scores of 2+ and 3+ are the most difficult to call for expert histopathologists as well. On the other hand, the proposed model correctly predicted the scores of 12 out of 14 WSIs with scores 2+ or 3+.
E. Glyoxalase-1 protein (Glo1) Scoring: In this experiment, we evaluate the performance of the proposed method on IHC stained gastroenteropancreatic neuroendocrine tumors (GEPs). The over-amplification in glyoxalase-1 protein (Glo1) is associated with resistance in  multidrug tumor chemotherapy [41]. In routine practice, an expert pathologist visually examines IHC stained GEP slides and reports a score between 1+ and 3+, which represents weak, moderate and intense Glo1 immunostaining, respectively. This experiment is conducted on 82 WSIs from 39 patients with 25 midguts and 14 pancreatic cases, with a total number of 22, 33 and 27 WSIs scored by an expert pathologist as 1+, 2+ and 3+ respectively. Further details regarding the dataset and GEP tumors can be found in [42].
The main objective of this experiment is to test the efficacy of the proposed IHC scoring method on another IHC stain by quantifying the concordance between the pathologist GT score and Glo1 score predicted by the proposed method. We first split the dataset into two folds and perform cross-validation by selecting half of the dataset for training and the remaining half for testing. We then repeat the experiment by swapping the training and test datasets. For each fold, the training dataset was further spilt into training and validation subsets by selecting 35 WSIs for training and remaining 6 (≈15% of the training data) for validation. Tissue regions from WSIs were segmented by performing local entropy filtering on a lower resolution (2.5×) version of the WSI. To avoid the class imbalance problem, we extracted all the image tiles (containing tissue) from 1+ WSIs and randomly sampled equal number of image tiles from classes 2+ and 3+. In total, we extracted 86,700 tiles each of size 2048 × 2048 × 3 at 40 ×. We then retrained the proposed model by retaining the same data augmentation methods and hyperparameters (including learning rate, lambda, number of ROIs, etc.,) as explained in Section IV.B. Optimal weights were selected based on the validation set. The final Glo1 score on the WSI level was estimated by aggregating the scores of image tiles, as explained in Section IV.D.2. Fig. 8 shows two confusion matrices (CF) containing WSI results of Glo1 scoring. The CF in Fig. 8(b) shows the results for the proposed method and the results for automated hormone receptors scoring (HRS) method [14], which was initially used in [42], are shown in Fig. 8(c). The overall agreement between the GT and the proposed method is 81.7% (Glo1 scores for 67 WSIs were correctly predicted), whereas the agreement is 60.9% in case of HRS. For IHC scoring, HRS relies heavily on pixel intensities for quantifying the chromatin and protein content. Therefore, heterogeneous morphological characteristics of neuroendocrine cells within tumor regions pose the risk of confusing the algorithm in extracting the desired features for IHC scoring. Fig. 9 shows some of the qualitative results on image tiles with different Glo1 scores. Overall, it is encouraging that the proposed method outperforms the HRS with a noticeable margin. It is worth mentioning that the performance of the proposed method may improve by appropriately tuning the hyperparameters. Our intention here is to demonstrate to some extent the generalizability of the hyperparameters selected from HER2 scoring. The IHC scoring of HER2 and Glo1 cases have some fundamental similarities: a) in both cases the GT was provided on the WSI level and therefore, it is imperative that the underlying model learns a stochastic policy and identifies some of the diagnostically relevant regions in predicting the final outcome, and b) similar to HER2 scoring, an erroneous scoring of 1+ as 3+ or vice versa may have far reaching effects for a patient. It is somewhat necessary to have a mechanism that penalizes the learnable parameters for overcalling those classes. We also observed that in some tissue regions, cells are densely packed and pose difficulties for the model in selecting ROIs from the invasive tumor regions.

V. DISCUSSION
With the adoption of digital slide scanners in routine pathology labs, large-scale WSIs or virtual slides (10 pixels) have emerged as a reliable alternative to conventional glass slides [43]. Typically, for effective training of deep learning models, it is incumbent to train computational models with large-scale precisely annotated regions. The ineludible fact is that sourcing precise high-resolution annotations of scanned slides is a laborious task and not considered as a part of the routine clinical practice. Hence, attaining tissue-level annotations for a significantly large dataset is one of the factors that may delay the acceptability of automated methods in clinical practice [44].
This study proposes a novel recurrent model for IHC scoring of HER2 slides of breast cancer. In some respects, the model mimics the pathological behavior by learning a parameterized policy to select diagnostically relevant regions. Experimental results conducted on a challenging contest dataset demonstrate the efficacy of the proposed model by outperforming the state-of-the-art methods, as shown in Table  III. It is worth noting that the proposed model only identifies a small number of regions required for predicting the correct outcome. Depending on the requirements, the model can be extended to assign different scalar rewards to each selected ROI. Different rewards may also be interpreted as the significance of each selected ROIs. Nevertheless, a challenge remains in that some times the model selects regions that may not appear to be diagnostically relevant (e.g., non-invasive tumor regions) due to tumor heterogeneity. An example is shown in Fig. 5, the last location of score 1+.
In computational pathology, diagnostic efficiency may be based on two main factors: 1) selecting potential ROIs from a given WSI, and 2) extracting discriminative features from within the selected ROIs. Some studies on eye movement have shown that with the passage of time trainee pathologists eventually gain experience in the selection of diagnostically relevant ROIs and learn discriminative features. Another recent study [45] shows that the overlap ratio between ROIs selected by different pathologists is associated with higher diagnostic accuracy. An interesting extension of our work would be to find correlation between the diagnostically relevant ROIs selected by machines and experts. This may help in evaluating the diagnostic reliability of computerassisted diagnostic systems. The proposed model also offers several advantages over the conventional fully supervised approaches. First, the model is capable of handling unwanted background regions that are often quite common in histology images due to several non-standardization factors in slide preparation. Second, the proposed model is capable of scaling up to WSIs or significantly large tiles of a WSI as the number of trainable parameters are directly linked with the size of ROIs instead of image tiles. However, in order to perform end-to-end training of the proposed model, we need the uncompressed representation of all required tiles of a WSI to be hosted into the memory and it is worth mentioning that on average, a 24-bit representation of an uncompressed WSI at 40 × requires approximately 56 GB [46] of memory, making it intractable to load an entire WSI into the GPU memory. Another extension of our work to achieve end-to-end learning would be to devise a multi-stage (or scale) attention mechanism. In the first stage, model analyzes the given WSI at a lower magnification (1.25 × or lower) to identify the potential ROIs and in the second stage the attention model analyzes selected ROIs at higher resolution (40×, 20 ×) to learn the discriminative features. However, such a model would require a prudent selection of reward function(s) and tuning of hyper-parameters to ensure the inclusion of diagnostically relevant regions in the first stage. In addition, the model would require a large number of WSIs to effectively optimize the weights for the first stage of the attention model.
The scope of the proposed model is not only limited to HER2 antibody quantification. The scoring of other prognostic and predictive markers like estrogen receptor (ER), progesterone receptor (PR), and proliferation of Ki-67 on the WSI level may also be possible with a similar approach. In the United States alone this year (2018), it is expected that there will be 266,120 new invasive BCa cases 1 . Whereas visual examination of histological specimens is generally influenced by subjectivity measures for learning discriminative features. the proposed model may assist experts in reducing subjectivity and serve as a semi-automated tool to find diagnostically relevant regions that may require the pathologist attention.

VI. CONCLUSIONS
In this study, we presented a deep reinforcement learning approach for automated scoring of IHC stained HER2 slides of breast cancer. Unlike fully supervised models that process all the regions of a given input image, the proposed model treats IHC scoring as a sequential selection task and effectively localizes diagnostically relevant regions by deciding where to see. The proposed model carries the potential to solve other histology image analysis problems where it is difficult to get precise pixel-level annotations. A similar approach may also eventually assist the pathologist in automated localization and classification of potential ROIs in both H&E and IHC stained histology images. The evaluation was conducted on a publicly available HER2 scoring contest dataset. Detailed comparative evaluation is in the favor of the proposed model. This study could potentially commence more interpretable incorporation of sequential learning and policy gradients in the domain of computational pathology.

SUPPLEMENTARY MATERIAL -II
Fig. S-2: Examples of four images with selected regions-of-interest (ROIs) predicted by the algorithm. Correctly predicted HER2 scores are 1+, 3+, 2+, and 2+. The first column shows input images and colored circles shows the predicted locations. The first location is shown with blue bounding boxes and similarly the last location is shown with red bounding boxes.


Explore Semantic Pixel Sets Based Local Pattern with Entropy Information for Face Recognition and Application in Back Propagation

In this paper, a combination of the Local Binary Pattern method with a semantic pixel set of entropy information is used on back propagation networks for face recognition. This method divides the sample data into NxM zones and calculates the feature value of each zone. In this paper the sample data is divided into 6x9 zones, ie 54 zones with the size of each zone is 10x10 pixels. The LBP method is a uniform pattern of each zone and makes comparisons to zones that have the most number of active pixels. Then from the LBP method the semantic method is used to extract the entropy information from each image. From the feature extraction, there are 107 feature values, 54 of LBP and 53 methods of semantic method. The value of the feature is used as input for classification using back propagation networks. 100 sample data were used for training and 60 different sample data were used for recognition level test. From the test conducted got the recognition rate using a combination of two methods of this extraction feature is 98%.

INTRODUCTION
Current digital image processing is not only limited to digital image processing, but also includes character recognition techniques such as alphanumeric characters, handwriting, etc. (Emanuel and Hartono, 2008). In addition to writing recognition, facial recognition is also one of the interesting topics to be used as an area of research in the field of image processing and pattern recognition in recent years. Face recognition is a popular biometric technique. Because it can be applied in several applications, for example: application access control, video, and human interaction with computers (Jain and Li, 2005).
The initial stage for facial recognition is image processing and feature extraction. The selection of a good feature extraction method is one of the important factors to achieve a high level of recognition (Jain and Taxt, 1996). Feature extraction is an important factor in the face recognition process but to get strong features to describe facial images is still a problem (Zhao et al, 2003). Local descriptors that are known at this time, such as the Gabor wavelet method are one of the best performances, but the method still requires too much processing time in the extraction feature. (Serrano et al, 2010) while Local Binary Pattern (LBP) is more popular, very simple, and very fast to calculate (Pietikäinen et al 2011).
Vol.6; Issue: 6; June 2019 Most methods used such as LTP, TP-LBP, and Multi-scale LBP, where to represent faces have not got maximum results due to variations in expression. Semantic pixel method set Local Binary Pattern (sps-LBP) is an approach to solve image block problems involving variations in expression, sps-LBP is the development of modified LBP. Sps-LBP is one approach that is intended to solve the problem of dividing blocks using the simple clustering method to divide pixels into an area by assuming the value of intensity. In sps-LBP the face image is divided into a number of square regions of origin and then the pixels in each area of origin are again grouped in a semantic manner. The workings of the semantic pixel set method based on LBP is to divide the pixels in an area of origin of images into sets (sets) so as to make it better to use spatial information when building histograms (Chai et al, 2012). In this study for each sample data that has gone through the image processing process, feature extraction will be carried out. First, the Local Binary Pattern (LBP) operator is used for image texture classification and then applied for facial recognition, the semantic pixel method is a method for grouping pixels into sizes selected based on the image used LBP method, after that the image is extracted using probability density function (PDF) to calculate entropy information. The ability of the semantic value by taking a description of the image from entropy information using the PDF function was tested to recognize image images with the next step using backpropagation artificial neural networks. It is expected that with these two feature extractions it can increase the level of recognition in terms of facial recognition.

LITERATURE REVIEW Image
Image (image) is an image in a twodimensional field. Viewed from a mathematical point of view, the image is a continuous function of the light intensity in the two-dimensional field (Munir, 2004). The light source illuminates the object, the object returns to reflect part of the beam of light. This reflection of light is captured by optical devices, such as the eyes in humans, cameras, scanners (scanners) and so on, so that the image of an object called the image is recorded. Digital imagery is a visual representation of an object after experiencing various transformations of data from various forms of numerical circuits. Digital images can be classified into several types: 1. Binary imagery Binary imagery (binary image) is an image that only has two gray values: black and white. The object pixels are 1 and the background pixels are 0. When displaying images, 0 is white and 1 is black. To change the grayscale image to a binary image, the process carried out is to change the quantization of images by means of globalimage thresholding. Each pixel in the image is mapped into two values, 1 or 0. With the floating function: 2) with I (x, y) is the gray level of a coordinate obtained by setting the color R (red), G (green), B (blue) indicated by the parameter values α, β and γ. In general the values of α, β and γ are 0.33. Other values can also be given for the three parameters provided that the total is 1 (Putra, 2009 Image processing Image processing is processing or an attempt to transform an image / image into another image using certain techniques.

Feature Extraction
Feature extraction is the process of measuring data that has been normalized to form a feature value. Feature values are used by classifiers to recognize input units with target output units and facilitate classification because these values are easy to distinguish (Pradeep et. Al, 2011). Another definition of feature extraction is one of the most important steps in the face recognition process, but to get discriminatory and strong features to describe facial images is still a problem for now. Broadly speaking, features are all measurement results that can be obtained. The feature can also describe the characteristics of the object being monitored (Putra, 2009). An example of a low level feature is signal intensity. Features can be either symbol, numeric or both. An example of a symbol feature is color. An example of a numerical feature is weight. Features can be obtained by applying the feature search algorithm to the input data. Features can be expressed with continuous, discrete or discrete-binary variables. Binary features can be used to indicate the presence or absence of a particular feature.

Artificial Neural Network Artificial
Neural Networks are computational networks that simulate nerve cell networks (neurons) from the central nervous system of living things (humans or animals) (Graupe, 2007). Artificial neural networks were first designed by Warren Mc-Culloh and Walter Pitts in 1943. Mc Culking-Pitts found that combining many simple neurons so that they become a nervous system is an increase in computational energy. Artificial neural networks are arranged with the same assumptions as biological neural networks (Puspitaningrum, 2006): Information processing occurs in processing elements (neurons). The signal between two neurons is transmitted through connection links. Each connection link has associated weights. Each neuron applies an activation function to the network input (number of weighted input signals). The aim is to determine the output signal.

Reverse Propagation Algorithm
The first Back Propagation algorithm was developed in 1986 by Rumelhart, Hinton and Williams to determine weights and is used for multi-layer perceptron training (Graupe, 2007). The back propagation method is a very good method of dealing with the problem of complicated complex patterns. . This method is a popular neural network method. Some examples of applications that involve this method are compressing data, detecting computer viruses, identifying objects, synthesizing sounds from text, and others (Puspitaningrum, 2006). The term "back propagation" is taken from the workings of this network, namely that the gradient error of hidden units is derived from re-broadcasting the errors associated with the output units. This is because the target values for hidden units are not given (Puspitaningrum, 2006). Back propagation is a supervised learning method. This method requires a predetermined value to get the desired output in the learning process. from the semantic pixel set based method. 5. Analysis using the back propagation algorithm for training images and test images so that they get the right recognition process.

Designing
The semantic pixel set-based local patterns formula takes the entropy value from the divided image in square form, the value taken is the trained image that will be forwarded to the back propagation neural network algorithm, from the back propagation it will be concluded how accurate both algorithms it goes on.

RESULTS AND DISCUSSION Implementation
Analysis and facial recognition models must be implemented into the program code to be able to find out the ability of the combination of semantic pixel methods and their entropy information.
Encoding is divided into five main modules, namely: 1. Image processing module Is a module to carry out all image processing processes and carry out feature extraction processes.

Network training module
Is a module to carry out the back propagation network training process.

Network testing module
Is a module to carry out the back propagation network testing process that has been trained. In this study, coding was done using the Python 2.7 programming language, because the Pyhon language does not have a module to do image processing so that additional complete modules are needed, check at https://www.python.org/download/releases/ 2.7/

Testing
After the implementation phase is carried out testing the ability of the combination of zoning methods and diagonal based feature extraction on the back propagation network for the introduction of handwritten numbers. To find out the addition of the level of recognition obtained by using a combination of methods, two other networks were built with the same architecture and parameters but each one uses only an extraction method, namely zoning or diagonal based feature extraction. The network that uses a combination of zoning and diagonal based feature extraction methods uses 123 feature values, a network that uses the zoning method uses 54 feature and network values using the diagonal based feature extraction method using 69 feature values as input.

Network Preparation
The three networks have the same hidden layer and output layer, 96 hidden layer neurons and 10 output layer neurons. The input layer is built according to the extraction method used, namely Semantic pixel information entropy (54 input neurons), Semantic Pixel Rate Information Entropy (69 input neurons) and its combination (107 input neurons) to be included in backpropagation. The architecture of the three networks can be seen in table 1.
Vol.6; Issue: 6; June 2019 So, according to the table for networks I and II, I will explain for the input layer stage, the value is clearly 54 and both networks are given blanks for hidden layers and output layers because it is not needed, which is only needed for network III because it is needed for training tests and tests test, then for backpropagation input a combined layer from networks I and II, for hidden layers we need 96 layers and the output layer (output layer) we only need 3 input layers. Before being tested, the three networks were trained to use training data with training parameters, namely the learning rate of 0.1, momentum 0.5 and the limit of error 0.01. The three networks are trained until the error value (MSE) achieved is smaller than 0.01. Unlike the iteration of 5000 accuracy of fixed objects and the error error is getting better with an accuracy of 0.010903. Then the results achieved for 5000 iterations are better with the least MSE, so we use 5000 iterations.

Figure 1 Accuracy of Iteration Values
In figure 1 above, it shows from the visualization of the data performed for several iterations. For example, the iteration at 3000 shows an error error value above 0.04, iterating when 4000 error errors are generated 0.02. it is better than the previous one and in the end the last iteration of 5000 produces an error of 0.01. Then it can be concluded that the larger the iteration should produce a smaller error error than the smaller iterations.

Test Result
After the three networks were trained, testing the level of recognition of the three networks was conducted. The level of introduction is tested using tested using test data, i.e. new data that is not used at the training stage. The results of the introduction of test data from the three networks tested can be seen in Figure 2. The test results from the program can be seen in table 3 below. Then we see from the table above with the image ujimark5.jpeg with the target mark, because it is known from the picture above that is Mark's image so that the target is marked as Mark, the accuracy closest to the output is Mark with an accuracy of 0.99487, then the image is tested again with a fixed target the mark with wozniak output is close to the second but the accuracy is too far and not even close to 50% at 0.00401, so the output for Chelsea island and Iqbal, with 0.00025 and 0.00001 the difference is too striking.

Figure 3 Steven Wozniak as Test Image
Source:https://www.n-tv.de/technik/Apple-1mit-allen- Komponenten-und-Originalverpackung-unterm-Hammer-article11549561.html The test results from the program can be seen in table 4.5 below. Then we see from the table above with the test image wozniak.jpeg with the wozniak target, it is known that the target image is wozniak so the target tested is wozniak, the accuracy closest to the output is wozniak with an accuracy of 0.97583, then the image is retested but the mark output close to the second but the accuracy is too far and not even close to 50%, so with the output for Chelsea island and Iqbal, the difference is too striking.

Figure 4 Chelsea Islan as a test image
Source:https://hello-pet.com/foto-chelsea-islandi-instagram-ini-bikin-hati-tenang-1823549 The test results from the program can be seen in table 5 below. Then we see from the table above with the image ujichelsea3.jpeg with the Chelsea target, it is known that the target of the image is Chelsea so that the target tested is Chelsea, the accuracy closest to the output is Chelsea with an accuracy of 0.96891, the mark output approaches the second but the accuracy is too far not even close to 50%, so with the output for Wozniak and Iqbal, the difference is too striking.