Hybrid RSO Algorithm with SFLA for Scientic Workow Scheduling in Cloud Using Clustering Techniques

An inevitable part of the cloud computing environment is virtualization, as it can multiplex or combine many virtual machines in a single physical machine, and simultaneously an isolated environment is provided to every virtual machine. An important issue in cloud computing is workow scheduling, which maps tasks of workow to VMs based on various functional and non-functional requisites. Workow scheduling is an NP-hard optimization problem and it is quite hard to achieve an optimal schedule. Metaheuristic algorithms helped in solving the problem of cloud task scheduling and this was compared to other heuristics. Reactive Search (RSO) and its structure will consist of a local heuristic based on a certain neighborhood complemented by making use of a memory-based mechanism. The Shued Frog Leaping Algorithm (SFLA) is based on swarm evolution that imitates information exchange divided into memeplexes when searching for food. This paper proposes a new set of optimization heuristics along with hybrid optimizations (RSO - SFLA) to solve problems in combinatorial optimization.

Introduction
The Internet has become the most sought-after technology which has become inevitable in day-to-day life. Many technologies that depend on the Internet such as cloud computing, World Wide Web (WWW), Internet Relay Chat (ITC) are in use for many years now. In today's computing world, cloud computing is being used commonly and can be termed as a new style of technology. This has become the technology present almost everywhere, and is a network on-demand and also user friendly (e.g, networks, servers, storage, applications, and services) that can be managed with minimal effort without much interaction with the service provider.
Cloud computing is one of the resources provided by the internet which is on an on-demand and rent basis, though the rent is quite minimal. This is one of the progressing technologies with computational and storage services as pay-as-you-go models. Generally speaking, the term internet or network is represented diagrammatically in the form of a cloud and so this technology gets its name as 'cloud computing and it is nothing but, using the internet in providing diverse computing resources to a different sector of the population with varying needs, living at different places. The main aim of cloud computing is the distribution of work to a varying group of individuals or interaction in a conductive manner with others while using resources of other organizations which perform large-scale computation. The various disciplines of cloud computing are Load Balancing, interoperability, Virtualization, Quality of Services, and so on [2].
The software that is used to isolate the physical machine from varied virtual machines is called Virtual Machine Monitor/hypervisor. The original de nition of Virtual Machine (VM) is that it is an e cient, isolated, duplicate of a real machine that allows multiplexing of the underlying physical machine.
Resources are allocated to virtual machines in a ne-grained manner through virtualization. The dynamic management of workload in servers is allowed by Virtual Machine Technology with increased elasticity. A separate machine is allocated to each user application and resources are provided based on the requirement of the application. Development platforms can be planned by the user based on the requirements of the application such as OS and other variables of the environment. Thus, multiple applications can be run in a single physical machine with different VMs Allocation of the necessary resources is done so that there is no violation of the Service Level Agreement, even in peak demand. Full control of resource allocation is provided through virtualization to the administrator that results in the use of resources optimally [15].
One of the main activities that are being executed in the cloud computing environment is scheduling. It is done to improve work pro ciency to attain the maximum bene t. The main objective of scheduling algorithms in the cloud environment is to utilize the resources properly while managing the load between resources so that the least execution time is taken.
The hybrid RSO-SFLA based method is proposed in this paper to improve work ow scheduling in the cloud [5]. The proposed method uses clustering techniques to enhance the scheduling. Related work available in the literature is presented in Section 2. The methods used were described in Section 3. The results were discussed in Section 4 and Section 5 concludes the paper.

Literature Review
Shirvani [12] had proposed another hybrid meta-heuristic algorithm that could solve the parallelizable and scienti c work ows on an elastic cloud platform. This was because applying one single approach will not be able to get an optimal solution to these complicated issues. Several scienti c work ows were modeled as a Directed Acyclic Graph (DAG) where the data dependency was in existence. For the marketplace of the cloud, every provider will deliver a set of Virtual Machine (VM) con gurations that are variable. Normally, such parallelizable task scheduling based on parallel computing machines for obtaining a minimum total execution time, or a makespan will be an NP-Hard problem. For dealing with such combinatorial issues, there was a Hybrid Discrete Particle Swarm Optimization (HDPSO) algorithm that was proposed with three phases. The rst phase had a random algorithm that was followed by some novel theorem applied for producing swarm members. This was an input proposed with a novel Discrete Particle Swarm Optimization (DPSO) algorithm for its second phase.
Shishido et al, [13] had examined the effects of the Particle Swarm Optimization (PSO) and the Geneticbased algorithms (GA) while attempting to optimize work ow scheduling. Another new security and costaware work ow algorithm were chosen for evaluating the metaheuristics and their performance. Three algorithms are evaluated in three different real-world work ows that have a constraint of risk rate ringing between 0 and 1 using a 0.1 step. The ndings had shown that the GA-based algorithms were able to outperform the PSO in terms of its response time and cost-effectiveness.
Singh et al, [14] had also proposed a new work ow scheduling algorithm that was inspired by the Hybrid Chemical Reaction Optimization (HCRO) algorithm. This scheme proved to be e cient in terms of energy and also proved to have a minimized makespan. This is referred to as an Energy E cient Work ow Scheduling (EEWS) algorithm. This EEWS was introduced in the form of a novel measure that determines the energy that has to be conserved by taking into consideration an environment that is DVS-enabled.
Employing certain simulations on various scienti c applications of work ow, it had been demonstrated that the scheme proposed was able to perform better compared to the HCRO and the Multiple Priority Queues Genetic Algorithm (MPQGA). This was observed, based on different metrics of performance that include the makespan and the energy conserved. The proposed algorithm and its signi cance were judged using an Analysis of Variance (ANOVA) test and an LSD analysis.
Wang et al, [16] had also proposed yet another multi-objective optimization work ow scheduling approach that was based on the dynamic game-theoretic model. It aimed at reducing the work ow make spans and their total cost thereby maximizing the system fairness which was identi ed in terms of its workload distribution which was among certain heterogeneous cloud-based Virtual Machines (VMs). Some extensive case studies were conducted on work ow templates along with real-world third-partybased commercial IaaS clouds. The results of the experiment suggested that the approach proposed was able to outperform all the traditional ones through achieving a lower makespan of work ow, lower cost, and a better level of system fairness.
On-demand provisioning along with the availability of resources in cloud computing have made it ideal to execute the applications of the scienti c work ow. The application begins execution with a minimum set of resources and some more were allocated when needed [5]. Work ow scheduling, however, was an NPhard problem thus making solutions based on metaheuristics explored widely. Kaur and Mehta [7] had proposed yet another augmented SFLA (ASFLA) method used for resource allocation along with work ow scheduling used in IaaS. Its performance was compared to other SFLA and PSO algorithms. The e cacy of the ASFLA was assessed with some work ows using a Java-based simulator. Simulations showed a signi cant reduction in the cost of execution.

Methodology
The section presents SFLA, RSO, and the proposed hybrid RSO-for scheduling in the cloud.

Reactive Search Optimization (RSO)
Reactive Search (RS] and its structure will consist of a local heuristic based on a certain neighborhood complemented by making use of a memory-based mechanism. This had been designed to avoid cycles.
There is an RSO framework that employs reinforcement learning based on history to implement knowledge acquisition by generalizing experiences before functioning. Some crucial parts are found in the RS algorithm which is: the objective function requiring optimization, the selected representation for which there are potential solutions needed. The algorithm has been designed to work for discrete problems in optimization [5].
The Shu ed Frog Leaping Algorithm (SFLA) is based on swarm evolution that imitates information exchange divided into memeplexes when searching for food. There is a need for a mixture of global search and local search in the memeplex to develop the algorithm to arrive at an optimal solution [17].
The NP-hard nature of the optimization problem in scheduling has made it very challenging to identify all the right solutions. This section can nd a way in which the hybrid Genetic Algorithm (GA), Arti cial Bee Colony (ABC), and the decoding heuristic can search for their ideal solutions. These decoding solutions can also generate certain feasible solutions based on tasks and their mapping to the VM [6].
There is yet another new set of optimization heuristics along with hybrid optimizations. These hybrid optimizations will assume that it has two or sometimes more than two algorithms for a similar optimization. This hybrid optimization tends to make use of a heuristic that chooses the best among such algorithms for being applied to a certain situation. For constructing this another hybrid allocator that can choose between two of the register allocation algorithms which are the linear scan and graph coloring [3] is employed. The primary goal here was the creation of another allocator to provide a proper balance between the two factors: attempting to identify a proper packing of these variables to the registers (thus achieving the good performance of running time) and reducing the allocator overheads. A hybrid optimization can bring down the effort of compilation making use of an e cient algorithm. This can be more effective but quite expensive as an optimization algorithm deems additional bene ts as well.
There was one more hybrid optimization approach to design the linkages method that is applied to a dimensional synthesis and also combines the advantages of stochastic, as well as deterministic optimization. The former is based on real-valued algorithms such as the EA and is used to extensively explore the design variable space while looking for a suitable linkage [11]. The latter, on the other hand, makes use of another technique of optimization for improving e ciency through reducing its high CPU time needed by the EA techniques for such applications. For this, the deterministic approach has to be implemented in two different stages. The rst one will be the evaluation of tness in which the deterministic approach is employed to obtain a new error estimator. In the next stage, this deterministic approach further re nes such solutions given by the algorithm and its evolutionary part. This new estimator ensures the evaluation of various individuals for each of these generations, thus avoiding all well-adapted linkages that cannot be detected by the other methods. This hybrid RSO-SFLA method was proposed for improving cloud work ow scheduling. The method makes use of clustering techniques for scheduling.

Hybrid Optimization methods
The proposed Novel Fire y Algorithm (NFA) was quite different from the Standard Fire y Algorithms (SFAs) proposed originally to solve problems of continuous optimization to map real-encoded re ies to their solutions (task sequences). This employs a new mapping operator that is distance-based which considers the distance between the re y and the one that is the brightest and also considers the best solution [18]. These mapped solutions are evaluated using an e cient strategy of task assignment called the Fast Task Assignment (FTA). To ensure a good start to this, an effective composite heuristic was used to generate high-quality solutions. It also develops another movement scheme to maintain a better probability in the mapping operator for inheriting the ''good genes'' found in the current best solution.
In the case of the standard Particle Swarm Optimization (PSO) algorithm, all initial particles have been created randomly. This randomness can also reduce the chances of converging to its best solution. The Best-Fit (BF) algorithm was merged into the PSO to improve convergence. All the other steps used in a standard PSO algorithm were retained. At the same time, the TABU Search (TS) algorithm was used as a neighborhood search algorithm to employ an intelligent search along with exible techniques of memory.
This has been designed for guiding all other algorithms to nd a way to escape from the local optima [1]. Thus, this is applied for solving task scheduling problems. The TS has been thus merged to the PSO to avoid being trapped inside the local optima and accelerate the search.
The work further proposed a Multi-Objective Hybrid Arti cial Bee Colony (MOHABC) algorithm that was used for Service Composition and Optimal Selection (SCOS). This was used in cloud manufacturing, where both the consumption of energy and quality of service were viewed from the perspective of the environment and economy being the two pillars in sustainable manufacturing. MOHABC makes use of the concept known as Pareto dominance for directing the search of the bee swarm. It also maintains certain non-dominated solutions in external archives. For achieving an ideal distribution of various solutions in the Pareto front, the CS along with the Levy ight was introduced.
The Ant Colony Optimization (ACO) is viewed as another improved variant of the load adjusting system of the Ant Colony and Complex Network Theory (ACCNT) while working in an open and distributed computing alliance. These calculations can make use of the pheromone of the ants to gather and further update information regarding the cloud by selecting a certain hub using a particular node for assigning this task and also evenly distributing work. For the proposed calculation, the ants begin to form their Head Hub to navigate around the system to make forward or reverse development and also locate under stacked or over-burdened hubs [9].
Fire y Algorithm (FA) is yet another very popular algorithm based on the population that can perform a global search that is suitable as it tends to have a very high degree of convergence wherein every re y attempts to identify its best state individually. So, it can, therefore, avoid the local optimum and search for a global optimum. At the same time, Simulated Annealing (SA) algorithm tends to have a convenient process of local search. It is because of this reason that both algorithms have been combined to form an FA-SA algorithm to ideally bene t from the advantages of the algorithms and also to perform better in terms of task scheduling in the cloud. For the method proposed, the FA algorithm generally initiates rst to perform a global search within the search space. Once the FA algorithm completes this, the SA algorithm will be executed to be able to perform the local search to the earlier solution that was given by the FA algorithm. This means, the initial population that was employed in the SA algorithm is not randomly chosen but obtains the value that is provided to it by the FA algorithm. This is the actual optimum value that has been given by the FA algorithm [4].
Hybrid SFLA-Genetic Algorithm has an independent local search made in every memeplex with steps that have to shu e that is executed when the frog's interchange messages that can feature certain speedy searches similar to other algorithms. These can get trapped within the local optima and further help in preventing and identifying an ideal global optimal solution. To ensure these traps can be avoided, there has been a need to combine the GA which can be used in the form of a substitute to update the SFLA and GA equation that is optimally combined for preempting that is being trapped within the local optima. This is effectively done at the time the GA conducts its local search. For this algorithm, each memeplex independently evolves to make a local search in different regions of its solution space after which they may be shu ed and re-divided into newer ones. This is to make global searches by exchanging information with each other [6].
There are several code models to the GA chromosome and the SFLA frogs use the codes in a model known as the real-number mode. To conduct the allocation of resources using optimal algorithms, the code model for these optimal algorithms has been made. This has further modi ed the position of the solution and has represented this in the form of a binary string. The length of the string was equal to the number of resources. There was a bit value of 1 that was assigned to the chosen resource indicating there was a bit value of 0 for the non-selected resource. Identi ed was another modi cation of a solution (chromosomes and frogs) that were represented in the form of a binary string for ensuring the SFLA and GA were combined to the SFLA-GA. The expressions were interchanged during selection. While conducting the evolution of the memeplexes in the SFLA, frog features represent GA chromosomes and the GA was used to conduct a local search.

Proposed Reactive Search Optimization with Shu ed Frog Leaping Algorithm
In this section, the RSO, along with the SFLA are discussed. In a reactive search, search history had to be employed to obtain a new parameter that was based on the feedback. This can tune all the algorithms for maintenance of its internal exibility needed for covering various problems. This type of tuning was further automated and then implemented at the time the algorithm runs and monitors past behavior. Also, there was an automated balance that had to be made to diversi cation and intensi cation. This was for managing the dilemma known as "exploration versus exploitation" obtained by various feedback mechanisms that begin with intensi cation and progressively move to diversi cation.
The algorithms are merged to form a new hybrid SFLA-RSO algorithm. The steps involved in this are as shown below: Firstly, an initial population is created and each memeplex has a random position along with the cost (light intensity) is computed for the position.
The subsequent stage is the execution of the SFLA. Here, the cost, its basis, and magnitude (light intensity) for each memeplex for all preconditions of the other memeplex are not met and are used to update the algorithm.
Next, there may be the tendency to move towards the subsequent step that performs the RSO process. In this, the neighborhood is randomly chosen.
The reactive hints have been a ready response to the events during alternative solutions that were tested by using an internal online feedback loop used for self-tuning in the case of crucial parameters.
Yet another new memeplex was presented by the RSO and this was associated with the previous one. For the case of the cost, (light intensity) for a new memeplex, this was found as being better compared to the earlier one. For this, the global best was swapped to the new memeplex.
Lastly, for a condition where the termination criterion was met, the memeplex that was the best is considered to be the output. If it is not so, all subsequent iterations begin from its memeplex algorithm from its rst step.

Results And Discussion
The RSO without clustering, RSO with clustering, and SFLA-RSO Optimization methods are evaluated. Experiments are evaluated using 600 to 1000 tasks. The optimization ratio on makespan, resource utilization, and computational cost is represented in tables 5.1 to 5.4 and gures 5.2 to 5.5.

When The Number Of Tasks Is Increased
The RSO without clustering, RSO with clustering, and SFLA-RSO Optimization methods are evaluated. Experiments are evaluated using 5000 to 25000 tasks. The optimization ratio on makespan, resource utilization, and computational cost is represented in tables 5.5 to 5.8 and gures 5.6 to 5.9.

Conclusion
The Standard SFLA has a very good ability of exploration along with fast convergence speed and the traditional RSO, on the other hand, has an effective ability of exploration. At the time of applying this to solve the problems of work ow scheduling, the SFLA may be stuck to the local optima as it has a low e ciency of global exploration. The RSO had a slower speed of convergence in certain cases as there can be a lack of powerful local ability of exploitation. For overcoming these disadvantages of both algorithms, the work has proposed a new hybrid approach that was based on the RSO and the SFLA that is used for the scheduling of scienti c work ows that are found in the IaaS clouds. For this, the pay-peruse pricing model. There is a decoding heuristic that is integrated into a hybrid approach that generates a feasible solution. The proposed algorithm's performance was evaluated against all other algorithms that prove its effectiveness in solving the problems of work ow scheduling in the IaaS clouds. The results proved that the SFLA-RSO along with clustering had a higher Utilization ratio % that was by about 3.47% and 1.14% for the 600 number of tasks, by about 4.59% and 2.27% for the 700 number of tasks, 4.55% and 9.3% for the 800 number of tasks, 4.49% and 4.49% for the 900 number of tasks and 6.74% and 4.44% for the 1000 number of tasks on being compared to the RSO without clustering and the RSO with clustering.

Future Work
In the future, other metaheuristics may be chosen from the hybrid techniques for improvement in the currently existing results.
A security mechanism can be introduced to the proposed algorithm.

Declarations
Ethical approval This article does not contain any studies with human participants or animals performed by any of the authors.
Funding This study was not funded by any funding agency  Tables   Table 4 is not available with this version. Figure 1 The owchart for the hybrid SFLA-RSO algorithm Makespan for SFLA-RSO with Clustering


extfieldsofstudy:
Computer Science
Mathematics

text:
Preconditioned TBiCOR and TCORS Algorithms for Solving the Sylvester Tensor Equation

In this paper, the preconditioned TBiCOR and TCORS methods are presented for solving the Sylvester tensor equation. A tensor Lanczos $\mathcal{L}$-Biorthogonalization algorithm (TLB) is derived for solving the Sylvester tensor equation. Two improved TLB methods are presented. One is the biconjugate $\mathcal{L}$-orthogonal residual algorithm in tensor form (TBiCOR), which implements the $LU$ decomposition for the triangular coefficient matrix derived by the TLB method. The other is the conjugate $\mathcal{L}$-orthogonal residual squared algorithm in tensor form (TCORS), which introduces a square operator to the residual of the TBiCOR algorithm. A preconditioner based on the nearest Kronecker product is used to accelerate the TBiCOR and TCORS algorithms, and we obtain the preconditioned TBiCOR algorithm (PTBiCOR) and preconditioned TCORS algorithm (PTCORS). The proposed algorithms are proved to be convergent within finite steps of iteration without roundoff errors. Several examples illustrate that the preconditioned TBiCOR and TCORS algorithms present excellent convergence.

Introduction
This paper is concerned of the computation of the Sylvester tensor equation of the form where matrices A n ∈ R In×In (n = 1, 2, ..., N ) and the tensor D ∈ R I1×I2×...×IN are given, and the tensor X ∈ R I1×I2×...×IN is unknown. The Sylvester tensor equation (1.1) plays vital roles in many fields such as image processing [8], blind source separation [22] and the situation when we describes a chain of spin particles [2]. If N = 2, then (1.1) can be reduced to the Sylvester matrix equation which has many applications in system and control theory [12][13][14]. When N = 3, (1.1) becomes which often arises from the finite element [20], finite difference [3] and spectral methods [21]. Many approaches are constructed to solve the Sylvester tensor equation (1.1) in recent years. Chen and Lu [9] proposed the GMRES method based on a tensor format for solving (1.1) and presented the gradient based iterative algorithms [10] for solving (1.3). Beik et al. [24] also presented some global iterative schemes based on Hessenberg process to solve the Sylvester tensor equation (1.3). Beik et al. [5] solved the Sylvester tensor equation (1.1) with severely ill-conditioned coefficient matrices and considered its application in color image restoration. Heyouni et al. [15] proposed a general framework by using tensor Krylov projection techniques to solve high order the Sylvester tensor equation (1.1). Beik et al. [1] proposed the Arnoldi process and full orthogonalization method in tensor form, and the conjugate gradient and nested conjugate gradient algorithms in tensor form to solve the Sylvester tensor equation (1.1). When D in (1.1) is a tensor with low rank, Bentbib et al. [6] proposed Arnoldi-based block and global methods. Kressner and Tobler [19] developed Krylov subspace methods based on extended Arnoldi process for solving the system of equation (1.1). The perturbation bounds and backward error are presented in [27] for solving (1.1). For more methods on other linear systems in tensor form we refer to [4,16,18,23]. Using the nearest Kronecker product (NKP) in [28], Chen and Lu [9] presented an efficient preconditioner for solving Eq.(1.1) based on GMRES in tensor form. Very recently Zhang and Wang in [30] gave a preconditioned BiCG (PBiCG) and a preconditioned BiCR (PBiCR) based on the nearest Kronecker product (NKP) in [28].
Inspired by the Lanczos biorthogonalization (LB) algorithm in [26], BICOR and CORS methods in [11] for non-symmetric linear equation, in this paper, we present two improved Lanczos L-orthogonal algorithms in tensor form for solving the Sylvester tensor equation (1.1). We further present preconditioned TBiCOR (PTLB) and preconditioned TCORS (TCORS) algorithms by using the NKP preconditioner in [9] for solving Eq (1.1). The preconditioned LB in tensor form (PTLB) is also considered.
The rest of this paper is organized as follows. Section 2 reviews some related symbols, concepts and lemmas that will be used in the contexture. Section 3 presents a tensor Lanczos L-biorthogonalization algorithm (TLB) and two improved TLB methods are shown in section 4. The tensor biconjugate L-orthogonal residual(TBiCOR) and tensor conjugate L-orthogonal residual squared(TCORS) algorithms for solving the tensor equation (1.1) are presented in subsections 4.1 and 4.2, respectively. The convergence of the TBiCOR and TCORS methods are proved. Section 5 presents the preconditioned TLB, TBi-COR and TCORS algorithms and the convergence of the preconditioned TBi-COR and TCORS algorithms. Section 6 presents several examples and some conclusions are drawn in section 7.

Preliminaries
The notations and definitions as follows are needed. For a positive integer N , an N -way or N th-order tensor X = (x i1 ... iN ) is a multidimensional array with I 1 I 2 ...I N entries, where 1 ≤ i j ≤ I j , j = 1, ..., N . R I1×...×IN denotes the set of the N th-order I 1 × ... × I N dimension tensors over the real field R, while C I1×...×IN defines the set of the N th-order I 1 × ... × I N dimension tensors over the complex field C.
Let X × n A define the n-mode (matrix) product of a tensor X ∈ R I1×I2×...×IN with a matrix A ∈ R J×In , i.e., The n-mode (vector) product of a tensor X ∈ R I1×I2×...×IN and a vector v ∈ R In is denoted by X × n v, i.e., The inner product of X , Y ∈ R I1×I2×...×IN is defined by x i1i2...iN y i1i2...iN , and the norm of X is denoted by Furthermore, it derives from [9] that We refer more notions and definitions in [17].
The following results from [1] will be used later.
Lemma 1. Suppose A ∈ R Jn×In , y ∈ R Jn and X ∈ R I1×I2×...×IN , we have X × n A× n e = X × n (A T y).
where e j is the j-th column of the I N -order identity matrix E IN , and X j denotes the j-th frontal slice of X .
and (2.4) can be represented as We also need the following results. (2.8)

A Tensor Lanczos L-Biorthogonalization Algorithm
Define the linear operator of the form Let L T define the dual linear operator of L, i.e., then it holds that L(X ), Y = X , L T (Y) for any X , Y ∈ R I1×I2×...×IN . Define the Krylov subspaces in tensor form as follows: Algorithm 1 lists the Lanczos L-Biorthogonalization procedure in tensor form that will be used to produce two series of biorthogonalization tensors.
Algorithm 1 A Lanczos L-biorthogonalization procedure in tensor form.
We have the following results for Algorithm 1. The proofs of these results are similar to the proof of Proposition 1 in [11] by using the definitions of the inner product (2.4), (2.5) and linear operator L in (3.1) and are omitted. Proposition 1. If Alogrithm 1 stops at the m-th step, then the tensors V j and W i (i, j = 1, 2, ..., m) produced Algorithm 1 are L-biorthogonal, i.e., Proposition 2. Suppose that V m is the (N + 1)-order tensor with columns V 1 , V 2 , ..., V m , and W m is the (N +1)-order tensor with the columns W 1 , W 2 , ..., W m , H m and G m are the (N + 1)-order tensors with the columns H j := L(V j ) and G j := L T (W j ) (j = 1, 2, ..., m), respectively. Then we have and being a triangular matrix with its elements generated by Algorithm 1. Moreover, it holds that and where E m denotes the identity matrix with m order.
We remark that (3.8) and (3.9) can be represented as and

1). For any initial tensor
It is easy to verify that a series of tensors {V 1 , V 2 , ..., V m } produced via Algorithm 1 form a basis of K m (L, V 1 ). Thus we have where y m ∈ R m . By Eq (3.17) and (3.18), we have A further computation results in Through a simple inner product operation and according to Eq.(2.6) and Lemma Submitting Eq.(3.13) into Eq.(3.21) results in the tridiagonal system on y m : Once we compute y m by (3.22), we get the solution X m of (1.1) by (3.18). We summarize this method in Algorithm 2, which is called Tensor Lanczos L-Biorthogonalization algorithm (TLB).
We remark Algorithm 2 have to compute the inverse of T m . When T m is of large size, it needs much computation. We present two improved algorithms for Algorithm 2 in the next section.

The TBiCOR Algorithm
In this subsection, we develop an improved algorithm by introducing the LU decomposition to T m in Algorithm 2.
Let the LU decomposition of T m be  .22), the solution of the dual system L T (X * ) = D * can be represented as .
Proposition 4. Let P i and P * i (i = 1, ..., k) are the i-th column tensor of P k and P * k , respectively. It holds that Proof. According to Lemma 4 and (3.13), we have which implies that (4.8) holds.
For a given initial guess X 0 , let R 0 = D − L(X 0 ) and P 0 = R 0 . Set Similarly, for the dual linear system L T (X * ) = D * , we set Now we determine α j and β j in (4.11)-(4.14). According to (4.11) we have that then by Propositions 3, 4 and (4.11)-(4.14) it holds that . (4.16) Similarly according to we have Algorithm 3 summarizes the biconjugate L-orthogonal residual algorithm in Tensor form for solving (1.1), which is abbreviated as TBiCOR.
We have the following convergence properties on Algorithm 3.

Algorithm 3
TBiCOR: A tensor biconjugate L-orthogonal residual algorithm for solving (1.1) According to Proposition 3, we have

The TCORS Algorithm
This subsection presents an improved method on Algorithm 3 by introducing a squared operator of the residual of X n produced by Algorithm 3. The proposed method is called the conjugate L-orthogonal residual squared algorithm in tensor form, which is abbreviated as TCORS.
Algorithm 4 TCORS: A tensor conjugate L-orthogonal residual squared algorithm for solving (1.1) The residual tensor of X n produced by Algorithm 3 can be represented as R n = a 0 R 0 + a 1 L(R 0 ) + a 2 L 2 (R 0 ) + ... + a n L n (R 0 ) = (a 0 L 0 + a 1 L + a 2 L 2 + ... + a n L n )R 0 , where a i is determined by Algorithm 3. Denote ϕ n (L) = a 0 L 0 + a 1 L + a 2 L 2 + ... + a n L n , then (4.19) can be represented as Similarly, we have where φ n (L) = b 0 L 0 +b 1 L+b 2 L 2 +...+b n L n , and b i can be derived by Algorithm 3. For the directions R * n and P * n in Algorithm (3), replacing L in (4.20) and (4.21) with L T results in Thus α n in (4.16) and β n in (4.18) can be represented as According to (4.11)-(4.12), ϕ j and φ j can be expressed as respectively. Squaring on both sides of (4.24) and (4.25) results in Furthermore, we have Taking (4.28) into (4.26) results in then (4.34)-(4.36) can be represented as  Proof. The proof of Theorem 2 is similar to that of Theorem 1 by replacing R k with U k , thus is omitted.

Preconditioned BiCOR and TCORSs Algorithms
This section presents two preconditioned methods based on Algorithms 3-4 for solving Eq.(5.1).
Using the definition of the Kronecker product in [4], one can transform Eq.(1.1) to its equivalent linear system . We refer to [17] for more details.
Algorithm 5 PTBiCOR: A preconditioned tensor biconjugateL-orthogonal residual algorithm for solving (1.1)  [28], Chen and Lu [9] presented an efficient preconditioner for solving Eq.(5.1) based on GMRES in tensor form, which is abbre-viated as preconditioned GMRES (PGMRES) later. Zhang and Wang in [30] gave a preconditioned BiCG (PBiCG) and a preconditioned BiCR (PBiCR) based on NKP in [28]. The preconditioner based on NKP approximates where the optimal parameters a ij in (5.3) can be computed by using the nonlinear optimization software, such as fminsearch in MATLAB.
Proof. The proof is very similar to those of Propositions (3) and (4) with the operator L being replaced byL in Algorithm 5, and is omitted. Proof. The proof is similar to that of Theorem 1 by replacing L withL and is omitted.
We can also obtain a preconditioned TLB (PTLB) by introducing the NKP preconditioner in [9] to Algorithm 2, which is listed in Algorithm 7.

Numerical Experiments
In this section, we show several numerical examples to illustrate Algorithms 2-7 and compare them with CGLS in [16], MCG in [23], preconditioned GMRES (PGMRES) in [9], preconditioned BiCG (PBiCG) and preconditioned BiCR (PBiCR) in [30]. All experiments are implemented on a computer with macOS Big Sur 11.1 and 8G memory. The MATLAB R2018a (9.4.0) is used to run all examples. All algorithms are stopped when the relative error r k = X k − X * / X * < 10 −10 , where X * is assumed to be an exact solution of (1.1). Example 6.1. In this example, we consider the Poisson equation in d-dimensional space [4] −△u = f, in Ω = (0, 1) d , u = 0, on ∂Ω.
A finite difference discretization leads to the Sylvester tensor equation (1.1), with the mesh-width h = 1 11 . We set d = 3 and let the initial tensor X 0 = O. The right-hand side D of (1.1) is constructed by (1.1) with the exact solution X * of (1.3) derived by the MATLAB command tenones(10, 10, 10) in [7]. Algorithms 2-6 are used to solve (1.1) with the matrices A i in (6.1). These methods are compared with CGLS in [16] and MCG in [23], respectively. Figure 1 shows the convergence of the relative error r k versus the number of iterations for all methods. From Figure 1, we can see that our preconditioned Algorithms 5-7 present better convergence than Algorithms 2-4 without preconditioning, PGMRES in [9], PBiCG and PBiCR in [30]. While Algorithms 2-4 can compare with PGMRES, PBiCG and PBiCR, and are better than CGLS [16] and MCG [23]. Algorithm 6 converges fastest among all algorithms. Algorithm 5 converges the second fastest among all algorithms.
A standard finite difference discretization on equidistant nodes combined with the second order convergent scheme [18,20] for the convection term leads to the linear system (1.1) with 2) where n = 1, 2, ..., N and the mesh-size h = 1 p+1 . We consider the case when N = 3 and p = 10. The right-hand side D is constructed by (1.1) with the exact solution X * of (1.3) produced by the MATLAB commend tenones(10, 10, 10) in [7]. Let the initial solution X 0 be a tensor with each element being zero. Algorithms 2-7 are used to solve (1.1) with A i given in (6.2). These methods are compared with CGLS [16], MCG [23], PGMRES in [9], PBiCG and PBiCR in [30]. Table 1 displays the running time, total iteration number (TIN) and relative error of different method with different parameters v = 1, 0.1, 0.001 and c i . Figure 2 shows the convergence of the relative error r k for each method with the parameters v = 0.01, c 1 = 1, c 2 = 2 and c 3 = 3. Table 1 shows that, when the stop criterion is satisfied, preconditioned Algorithms 5-6 require less CPU time and iterations than Algorithms 2-4, PGMRES, PBiCG and PBiCR. In most cases Algorithms 2-4 requires much less CPU time but more iterations than PGMRES, PBiCG and PBiCR, and are better than CGLS [16] and MCG [23] both in CPU time and the number of iterations. Algorithm 6 requires the minimal CPU time and iterations among all methods. Figure 2 shows similar results to that in Figure 1. on the unit square [0, 1]× [0, 1] with homogeneous Dirichlet boundary conditions. We use the MATLAB command fdm 2d matrix in the Lyapack package [25] to generate matrices A i : A i = f dm 2d matrix(I i , e xy , sin(xy), y 2 − x 2 ), ,
The initial solution X 0 is selected as zero tensor. Algorithms 2-6 are used to solve (1.1) with A i given in (6.4). These methods are compared with CGLS [16], MCG [23], PGMRES in [9], PBiCG and PBiCR in [30]. Figure 3 shows that Algorithm 6 converges fastest among all methods and Algorithm 6 converges the second fastest among all methods, which are very similar to those in Figures 1 and 2.

Conclusion
This paper first presents a tensor Lanczos L-Biorthogonalization (TLB) algorithm for solving the Sylvester tensor equation (1.1) based on the Lanczos L-Biorthogonalization procedure. Then two improved methods based on the TLB algorithm are developed. The one is the biconjugate L-orthogonal residual algorithm in tensor form (TBiCOR). The other is the conjugate L-orthogonal residual squared algorithm in tensor form (TCORS). The preconditioner based on the nearest Kronecker product (NKP) are used to accelerate the TBiCOR and TCORS algorithms, thus we present preconditioned a preconditioned TBi-COR method and a preconditioned TCORS method. The convergence of these proposed algorithms are proved. Numerical examples show the advantage of the preconditioned TBiCOR and TCORS methods. 8 Acknowledgments


s2fieldsofstudy:
Computer Science
Psychology

text:
CARE: Commonsense-Aware Emotional Response Generation with Latent Concepts

Rationality and emotion are two fundamental elements of humans. Endowing agents with rationality and emotion has been one of the major milestones in AI. However, in the field of conversational AI, most existing models only specialize in one aspect and neglect the other, which often leads to dull or unrelated responses. In this paper, we hypothesize that combining rationality and emotion into conversational agents can improve response quality. To test the hypothesis, we focus on one fundamental aspect of rationality, i.e., commonsense, and propose CARE, a novel model for commonsense-aware emotional response generation. Specifically, we first propose a framework to learn and construct commonsense-aware emotional latent concepts of the response given an input message and a desired emotion. We then propose three methods to collaboratively incorporate the latent concepts into response generation. Experimental results on two large-scale datasets support our hypothesis and show that our model can produce more accurate and commonsense-aware emotional responses and achieve better human ratings than state-of-the-art models that only specialize in one aspect.

Introduction
Rationality and emotion are two fundamental elements of humans and indispensable to our social interactions (Keltner and Haidt 1999;Colman 2003). Endowing agents with rationality and emotion has been one of the major milestones in AI. In recent studies of conversational AI, there is an emerging research trend in endowing conversational models with rationality (Zhou et al. 2018b;Zhang et al. 2020) or emotion (Zhou et al. 2018a;Song et al. 2019). Rational conversational models can leverage commonsense knowledge to reason and have been shown to produce more appropriate and informative responses (Zhou et al. 2018b). Emotional conversational models can generate appropriate emotional responses, leading to improved user satisfaction (Prendinger and Ishizuka 2005;Zhou et al. 2018a) and long-term relationships with users (Zhou et al. 2018c).
Rationality and emotion are not independent for humans (De Sousa 1990). In fact, emotions are often rational in social interactions (Pham 2007). However, most existing  (Song et al. 2019) and our model. EmoDS generates generic or unrelated emotional responses. Our model extracts the message concept "starbucks", and generates more commonsense-aware emotional responses by referring to our constructed relational (in bold) and emotional (in italic) latent concepts, e.g., company, coffee and bitter.
conversational models only specialize in one aspect and neglect the other 1 , which often leads to dull or unrelated responses. For example, as shown in Table 1, the stateof-the-art emotional conversational model (EmoDS) (Song et al. 2019) produces generic or unrelated emotional responses due to the lack of specific modelling of rationality. In addition, existing rational conversational models, e.g., the commonsense-aware conversational model (CCM) (Zhou et al. 2018b), are not able to generate emotional responses, rendering them difficult to build long-term relationships with users (Zhou et al. 2018c).
A recent work (Roller et al. 2020) proposed to blend several human skills such as knowledge, personality, and empathy into a conversational agent and obtained the stateof-the-art performance in human evaluations. Their experimental analysis suggests that blending these skills is critical for achieving good human ratings. Motivated by the facts that 1) rationality and emotion are two fundamental qualities of humans and that 2) empirical performance improvement has been achieved via combining several human qualities (Roller et al. 2020), we hypothesize that combining rationality and emotion into conversational agents can improve response quality and their human ratings.
In this paper, we narrow the scope of rationality and emotion to specific settings for easier implementation and evaluation. Specifically, we focus on one fundamental aspect of rationality, i.e., commonsense, and the discrete representation of emotion. Commonsense is an important foundation of rationality and the basis of rational human conversations (Ross 1978). The discrete representation of emotion categorizes emotions into discrete basic emotions, e.g., joy, anger, etc., and is a well-established emotion theory in Psychology (Ekman 1992). To test our hypothesis, we propose a novel model for Commonsense-Aware Response generation with specified Emotions (CARE) and assess its empirical performance. Two major challenges to this task are 1) the lack of relevant datasets or resources that can provide such supervision and 2) how to generate appropriate commonsenseaware emotional words. We tackle the first challenge by building an emotion-aware commonsense knowledge graph (EA-CKG) to integrate commonsense and emotion knowledge. We tackle the second challenge by incorporating both relational and emotional latent concepts constructed from EA-CKG into response generation. Specifically, we build EA-CKG by augmenting an external CKG with emotional triplets extracted from emotional conversations. We then construct latent concepts using learned EA-CKG embeddings, endowing the response with commonsense and emotion by reasoning over the EA-CKG. Finally, we propose three methods to sequentially and collaboratively incorporate the latent concepts during attention, optimization, and sampling. CARE is illustrated in Figure 1.
In summary, our contributions are as follows: • We identify the problem of lacking either rationality or emotion in existing conversational models, which often leads to dull or unrelated responses. We hypothesize that combining rationality and emotion into conversational agents can improve response quality.
• We focus on one fundamental aspect of rationality, i.e., commonsense, and propose CARE, the first commonsense-aware emotional response generation model, to address the aforementioned problem.
• We conduct extensive automatic and human evaluations and show that CARE can produce better commonsenseaware emotional responses than state-of-the-art models that only specialize in one aspect. The experimental results support our hypothesis.

Related Work
Rational Response Generation: Existing rational response generation models usually rely on knowledge bases, such as open-domain response generation (Han et al. 2015;Young et al. 2018;Ghazvininejad et al. 2018;Liu et al. 2018;Tuan, Chen, and Lee 2019;Moon et al. 2019), task-oriented response generation (Madotto, Wu, and Fung 2018;Wu, Socher, and Xiong 2019) and question answering Banerjee et al. 2019). Zhou et al. (2018b) proposed CCM to incorporate commonsense knowledge by applying attention mechanisms on 1-hop knowledge triplets for  Figure 1: Illustration of CARE. Given the message "Do you wanna have beer tonight?" (beer is a message concept) and the learned EA-CKG embeddings, CARE first constructs latent concepts depending on the specified emotions of the response. For example, tasty is constructed for "joy" and soda is constructed for "sadness", because tasty is linked to beer via the "joy" relation, and soda is linked to beer via a composite of "sadness" and "IsA" relations. Then CARE leverages the proposed three methods to incorporate the latent concepts, e.g., tasty, into response generation.
open-domain response generation. Zhang et al. (2020) (Ghosh et al. 2017) and Seq2Seq models Xu et al. 2019). Keskar et al. (2019) trained a Transformer-based conditional language model on a large collection of corpora with control codes that govern style, content, and task-specific behavior. Li and Sun (2018) and Peng et al. (2019) proposed topic-aware emotional response generation models. In contrast, we focus on commonsense, i.e., the semantic network of words, instead of topics, i.e., word clusters.

Our CARE Model
In this section, we introduce the task definition and our CARE model, which includes a framework for constructing latent concepts and three methods to incorporate the latent concepts.

Task Definition
We denote {X i , Y i , e i }, i = 1, ..., N , as a collection of {message, response, emotion} tuples, where e i is chosen from a predefined set of emotions and denotes the emotion category of Y i , and N denotes the number of conversations in the training dataset. Our task can be formulated as follows: given a new message X new and an emotion category e, generate a natural and commonsense-aware response Y new that has emotion e.

Latent Concepts Construction Framework
In this framework, we first build an emotion-aware commonsense knowledge graph (EA-CKG) and then construct latent concepts from EA-CKG.
EA-CKG We extract emotional triplets from emotional conversations and augment them into an external CKG to obtain EA-CKG. We use ConceptNet (Speer, Chin, and Havasi 2017) as our CKG 2 . Each triplet in ConceptNet follows the {head, relation, tail} format, e.g., {beer, AtLocation, bar}. Note that we use n-gram matching with Concept-Net to extract concepts from utterances, and ignore stopwords and n-grams that are formed entirely by stopwords.
We define an emotional triplet as in the {msg concept, emotion, res concept} format, representing an emotional link from a message concept to a response concept. For example, given a message "I heard there is a bar nearby with nice beer." and its response "I love tasty beer." with joy emotion, the triplet {beer, joy, tasty} is a valid emotional triplet because there is a commonly expressed emotional link, i.e., joy, from beer in the message to tasty in the response. We propose a two-step approach based on the pointwise mutual information (PMI) (Church and Hanks 1990) to extract such emotional triplets from emotional conversations. PMI can measure the association between two words in a corpus. We extend the smoothed positive PMI, i.e., PPMI α (Levy, Goldberg, and Dagan 2015), as follows: where (w 1 , w 2 ) denotes the word pair, P α (w) = count(w) α x count(x) α denotes the smoothed probability of w, and α denotes a smoothing factor set to 0.75 (Levy, Goldberg, and Dagan 2015) to alleviate the bias towards rare words.
In our two-step approach, we first construct a PPMI matrix between concepts in messages and in the corresponding responses to extract strongly associated concept pairs in conversations 3 , denoted as conversational concept pairs 2 We remove non-English and rare concepts. 3 We consider concept pairs whose frequency ≥ 5 and PPMI ≥ 1 as strongly associated pairs (CCP).  (CCP). Note that in this case, w 1 refers to a message concept and w 2 refers to a response concept in Equation 1. We then construct a second PPMI matrix between CCP and their expressed emotions and extract CCP that statistically express certain emotions more often than other emotions 4 . Note that in this case, w 1 refers to a CCP and w 2 refers to its expressed emotion in Equation 1. We do not smooth P (w 2 ). By using this two-step approach, we can effectively extract conversational triplets that are commonly expressed with certain emotions. The statistics of EA-CKG are presented in Table 2. Our approach shares similarities with commonsense knowledge base completion methods (Li et al. 2016c;Saito et al. 2018;Bosselut et al. 2019); however, they cannot be trivially adapted to extract emotional CCP.

Latent Concepts Construction
During training and inference, given a message X i and a desired emotion e i , we construct the latent concepts of the response based on EA-CKG embeddings. Specifically, we first train a well-established knowledge embedding model, i.e., TransE (Bordes et al. 2013) 5 , on the entire EA-CKG to learn global concept and relation embeddings. The embeddings in TransE are learned such that the score -||h + r − t|| 2 for a correct triplet (h, r, t) is much higher than a corrupted one, where h, r, t denote the TransE embeddings of h, r, t, respectively, and ||h|| 2 = 1 and ||t|| 2 = 1 (Bordes et al. 2013). Hence, given a message concept h, a relation r and a response concept t, we can estimate the relatedness between h and t via r as follows: We then obtain the top m related latent concepts of the response from EA-CKG, i.e., {t} m 1 , as follows: where h ∈ C Xi , r ∈ R ∪ {e i }, C Xi denotes all concepts in X i , R denotes all 36 relations in ConceptNet, and t is searched over the concept vocabulary of EA-CKG. For messages without any concepts 6 , we use a null message concept whose embedding is the average of all concept embeddings.
Framework Analysis Our framework constructs plausible relational (r ∈ R) and emotional (r = e i ) concepts for the response. By leveraging the EA-CKG embeddings, our framework inherits the ideas from knowledge base completion and has two major advantages over the graph search methods used in existing models (Zhou et al. 2018b;Zhang et al. 2020) to find related concepts: 1) our framework can find concepts that are both commonsense-aware and emotional due to the incorporation of emotional triplets in EA-CKG, e.g., tasty is found given beer and joy whereas bland is found given beer and sadness; and 2) our framework can not only traverse through the EA-CKG to find related concepts in a multi-hop neighborhood but also discover an arbitrary number of novel related concepts using Equation 3, without being limited by the CKG coverage (see Result Analysis).

Incorporating Latent Concepts
After obtaining the latent concepts, we propose three methods to collaboratively incorporate them into our Transformer-based conversational model (Vaswani et al. 2017), as illustrated in Figure 2. Note that similar to the idea of persona embedding (Li et al. 2016b), we additionally employ an emotion embedding layer in our decoder.
Emotion-Aware Graph Attention We incorporate latent concepts into the decoder using an emotion-aware graph attention (EAGA) prior to the cross-attention layer, inspired by (Zhong, Wang, and Miao 2019b). We assume that important latent concepts are those related to the message concepts and have strong emotional intensity. The relatedness between concepts is obtained from Equation 2. The emotional intensity of a concept is computed based on an emotion lexicon NRC VAD (Mohammad 2018) and an emotional intensity computation method (Zhong, Wang, and Miao 2019b). We expand the size of NRC VAD from 20K to 34K using synonym expansion for better coverage 7 . Formally, let {t 1 , t 2 , ..., t m } be the latent concepts of response Y i obtained from Equation 3, {s 1 , s 2 , ..., s m } be their relatedness scores obtained from Equation 2, and {q 1 , q 2 , ..., q m } be their emotion intensities based on NRC VAD, we compute the latent concept embedding of Y i , i.e., C Yi , as follows: where t i denotes the word embedding of t i and β i is computed as follows: where λ i denotes the trade-off coefficient between relatedness and emotional intensity, and δ 1i , δ 2i denote softmax temperatures. Note that λ i , δ 1i and δ 2i are concept-specific and can be fixed a prior or learned during training. The obtained latent concept embedding C Yi is then averaged with the response representation prior to being fed to the crossattention layer. Compared with the graph attention in CCM (Zhou et al. 2018b), EAGA measures concept relatedness using translation-based distance in TransE instead of MLP and additionally considers the emotion property of concepts.

Dynamic Label Smoothing
Label smoothing is conventionally adopted in the Transformer (Vaswani et al. 2017) to improve translation quality. We propose a simple but effective dynamic label smoothing (DLS) method to explicitly enforce the supervision of latent concepts in producing concept-related responses, as well as to stabilize the learning process. Specifically, starting from the conventional label smoothing, we linearly increase the smoothing values for latent concepts with the training step and decrease the smoothing values for other words in the vocabulary. Note that the smoothing value of the target word remains unchanged. The maximum of the total smoothing value for latent concepts is a hyper-parameter to be tuned in experiments. We optimize model parameters to minimize the Kullback-Leibler (KL) loss (Kullback and Leibler 1951).
Concept-Aware Top-K Decoding During inference, we propose a concept-aware top-K decoding (CATD) method to encourage the generation of words that are more related to the associated latent concepts. Formally, given the conventional top-K unnormalized token probabilities P (w 1 ), ..., P (w k ), our concept-aware token probability P for w i , i = 1, ..., k, is computed as follows: where γ denotes a trade-off hyper-parameter between fluency and relatedness, and P c (w i ) is computed as follows: where C Y denotes the latent concept embedding obtained from Equation 4 during inference. One merit of CATD is that it only reorders top-K tokens by additionally considering their relatedness to latent concepts and thus does not introduce unlikely tokens into the sampling process.

Experimental Settings
In this section, we present the datasets, evaluation metrics, baselines, and model settings.

Datasets
We conduct experiments on two large-scale datasets, namely Reddit and Twitter. The Reddit dataset is obtained from comments on the CasualConversation subreddit 8 discussing a variety of casual topics 9 . The Twitter dataset is obtained from chats on twitter.com 10 . We truncate each sentence to a maximum of 30 tokens and use the most frequent 30K tokens as the vocabulary for each dataset.
To obtain the ground-truth emotion label for each response, similar to (Zhou et al. 2018a;Song et al. 2019), we train an emotion classifier on emotional conversations. Specifically, we use the emotional tweets (Mohammad 2012;Mohammad et al. 2018) to train the classifier. We consider neutral and Ekman's six basic emotions (Ekman 1992): joy, sadness, surprise, fear, and anger, but exclude disgust due to its small amount of training samples in the emotional tweets. We propose an emotion classifier based on DeepMoji embeddings (Felbo et al. 2017) followed by a linear layer and a softmax layer. Our classifier achieves an accuracy of 0.562 on a balanced test dataset, outperforming several competitive baselines such as BiLSTM (0.446), CNN (0.547), BERT (Devlin et al. 2019) (0.530) and XLNet (Yang et al. 2019) (0.522). We then use the trained emotion classifier to annotate the responses in the datasets. The statistics of the annotated datasets are presented in Table 3.

Evaluation Metrics
We conduct both automatic and human evaluations. Automatic evaluation metrics include 1) Fluency: perplexity (PPL), which measures the confidence of the generated responses; 2) Diversity: distinct-1 (dist-1) and distinct-2 (dist-2) (Li et al. 2016a), which measure the percentage of unique unigrams and bigrams in the generated responses, respectively; 3) Emotion Accuracy (EA): the emotion accuracy of the generated responses measured by our trained emotion classifier; and 4) Commonsense Awareness (CA): the average number of commonsense triplets in one pair of message and generated response, measured by ConceptNet.
Following (Zhou et al. 2018a), we conduct human evaluations to measure both content quality (rating scale in {0, 1, 2}) and emotion quality (rating scale in {0, 1}) of the generated responses. Content quality measures whether the response is natural and related to the message, as well as how commonsense-aware the response is. Emotion quality measures whether the response expresses the desired emotion appropriately and accurately. We randomly sample 200 test messages and emotions to generate 200 responses for each model. Each response is evaluated by three annotators.

Baselines
We compare CARE with the following baselines: Vanilla Models: Seq2Seq (Vinyals and Le 2015) and Transformer (Vaswani et al. 2017). Commonsense-Aware Models: CCM (Zhou et al. 2018b) and ConceptFlow (Zhang et al. 2020). ConceptFlow leverages multi-hop knowledge triplets and is a state-of-the-art model for commonsense-aware response generation. Emotional Models: ECM (Zhou et al. 2018a) and EmoDS (Song et al. 2019). EmoDS is a state-of-the-art model for emotional response generation. Pre-trained Model: CTRL (Keskar et al. 2019). CTRL is a large pre-trained conditional language model with 1.6 billion parameters trained on 140GB of text. We fine-tune CTRL on our training conversations such that it is able to produce emotional responses. CTRL has also been shown to contain commonsense knowledge (Petroni et al. 2019;Bosselut et al. 2019).

Model Settings
We use the same hyper-parameters for both datasets. Our TransE embeddings have a dimension of 100 and achieve an accuracy of 0.89 for triplet classification on EA-CKG. Our Transformer model has 1 layer and 4 attention heads. We initialize the word embedding layer with pre-trained GloVe embeddings (Pennington, Socher, and Manning 2014) of size 300. The emotion embedding and feedforward layers have sizes of 50 and 512, respectively. We train our model using Adam (Kingma and Ba 2014) with learning rate of 1, batch size of 64, and dropout of 0.1 for 80K steps, including 6K steps for warmup. We empirically construct 30 relational latent concepts and 10 emotional latent concepts for each response using Equation 3. We use label smoothing of 0.1, total smoothing value of 0.08 for latent concepts in DLS, and top-10 decoding with γ = 1 in CATD.

Result Analysis
In this section, we discuss our evaluation results, model analysis, case study, error analysis and limitation.

Comparison with Baselines
We present the results of automatic evaluations in Table 4. Seq2Seq achieves the lowest perplexity while Transformer achieves slightly better diversity than Seq2Seq. Commonsense-aware models, i.e., CCM and ConceptFlow, obtain slightly better diversity and CA; however, they are    (Fleiss and Cohen 1973), are 0.441 and 0.626 for content and emotion on Reddit, respectively, and 0.479 and 0.673 for content and emotion on Twitter, respectively. Both datasets obtain "moderate agreement" and "substantial agreement" for content and emotion, respectively.
unable to generate responses with specified emotions. Emotional models, i.e., ECM and EmoDS, achieve the highest EA among all baselines but the worst in perplexity and CA, suggesting that they only specialize in emotion and neglect commonsense. CTRL achieves the highest diversity among all models, partially due to its large vocabulary size of 250K. However, it obtains an inferior EA. Our model achieves better EA and CA than all baselines, including CTRL, which is also capable of producing commonsense-aware emotional responses.
We present the results of human evaluations in Table  5. The responses of non-emotional models are generated via top-10 decoding six times. ConceptFlow obtains similar emotion quality but noticeably better content quality than Seq2Seq due to its incorporation of multi-hop triplets. EmoDS achieves comparable content quality but much better emotion quality than Seq2Seq. CTRL obtains the best content quality among all models but only mediocre emotion quality, especially on Reddit. Our model performs best in emotion quality (t-test, p < 0.01). In addition, our model achieves significantly better content quality than EmoDS (ttest, p < 0.01), showing that our model can produce better commonsense-aware emotional responses than EmoDS. Finally, our model outperforms ConceptFlow, a competitive commonsense-aware model, in content quality, possibly because the graph search method in ConceptFlow heavily relies on the coverage of ConceptNet to extract knowledge triplets, but ConceptNet only has an average coverage of 27% on Reddit and Twitter. In contrast, our model has less such restriction and can construct an arbitrary number of latent concepts given any input message.
We report model complexity in the rightmost columns of Table 4. Our model has comparable space and time complexity with vanilla baselines. In contrast, CTRL is around 80x larger and 1,000x slower than our model, rendering it intractable for real-time applications.

Model Analysis
We conduct ablation study, as shown in Table 6. Removing any component except EAGA from our model leads to much worse performance in both EA and CA. In particular, we   observe that 1) our approach of constructing latent concepts performs better than alternatives (-ET+EL and -TransE); and 2) the removal of EAGA leads to significantly higher perplexity, diversity, and CA. The higher perplexity may be attributed to the additional supervisions of DLS on latent concepts, which are not explicitly incorporated into the model due to the lack of EAGA. The higher diversity and CA may be attributed to the untrained λ, δ 1 , and δ 2 (see Equation 5), which sometimes leads to ungrammatical but diverse latent concepts during decoding. Our observation validates the importance of EAGA in attending more related latent concepts. We analyze the impact of model hyper-parameters on EA and CA, as shown in Figure 3. Using m = 40 latent concepts achieves the sweet spot for model complexity. Regarding DLS, increasing the total smoothing values for latent concepts in the [0, 0.08] range improves model performance. However, we do observe degraded fluency when using larger smoothing values, which is expected because the true learning signal is weakened. Increasing γ in CATD consistently improves EA and CA for our model. However, models with larger γ, e.g., 1.5, sometimes produce unfluent long responses due to its overemphasizes on latent concepts.

Case Study and Error Analysis
We present two sample cases in Table 7. Given a message and desired emotions, our model produces commonsenseaware responses with the desired emotions, guided by both relational and emotional latent concepts. For example, given "starbucks" and anger, the relational latent concept "coffee" and emotional latent concept "gross" are constructed and incorporated into response generation. However, we do ob-serve bad cases where the latent concepts overemphasize on emotional intensity, and the response becomes unnatural.

Limitation
One major limitation of our work is the mediocre accuracy of our trained emotion classifier, which can be attributed to the unavailability of large-scale datasets for emotional conversations and sentences. Nevertheless, our proposed lightweight classifier obtains better performance than the best models reported in (Zhou et al. 2018a;Song et al. 2019) and BERT. A potential solution to this limitation is to leverage few-shot learning on BERT-like models.

Conclusion
We propose CARE as the first attempt to test the hypothesis that combing rationality (commonsense) and emotion into conversational agents can improve response quality and human ratings. Specifically, we build an EA-CKG and leverage its TransE embeddings to allow CARE to reason over the EA-CKG and construct both relational and emotional latent concepts. We further propose three methods to collaboratively incorporate the latent concepts into response generation. Extensive ablation studies show that our methods of constructing and incorporating latent concepts outperform alternative methods. In addition, both automatic and human evaluations show that CARE can produce more accurate and commonsense-aware emotional responses than state-of-theart commonsense-aware models and emotional models. Finally, our work provides empirical evidence for our hypothesis. In the future, we plan to extend our work to other aspects of rationality, e.g., logical reasoning.


extfieldsofstudy:
Computer Science
Physics

text:
Design and Integrate Real Time Clock and Temperature Digital Signal Processing with ARM System

The integrated circuit had been developed rapidly from microprocessor to microcontroller and System-on-Chip (SoC) just happen within a few decade. The development is continuing as the demand for the functionality increase. The Real Time Clock (RTC) is one of the peripherals most widely used inside the microcontroller. Besides, when Moore’s law is still applied, the number of transistor will increase, so does the temperature. Thus, the temperature digital signal processing (TDSP) unit had become an important peripheral to monitor the system-on-chip temperature. In this paper, these two Intellectual Property which are RTC and TDSP are designed and integrated into ARM system. The system architecture and implementation strategies are discussed. The results were run and simulated in the Synopsys software.

Introduction
The embedded system had evolve since it had been created. Since then, more and more transistor and function had been integrated together to accomplish the task. The system had already become the System-on-Chip (SoC), which all the peripherals are integrated into a single chip. The advantages of SoC are the overall performance and time to market compare to traditional Application Specific Integrated Circuits (ASIC) [1][2][3].
The most common component for a SoC is the Real Time Clock (RTC). It is widely used in many microcontroller or embedded system. For example, some of the devices need to record the real time when collecting the data [4]. The real time can provide the analyzer how the period of a particular data formed. The other common component that is widely used is the Temperature Digital Signal Processing (TDSP). It is needed when number of the transistors are increasing, and the temperature can be a disaster to the board [5]. The TDSP can prevent the processor and the peripheral overheat and cut off the power supply if necessary.
In this paper, two IP which are RTC and TDSP will be integrated into the ARM system. The ARM system include the Cortex-M0 core processor, the AMBA bus [6][7][8] and other ARM peripherals. The ARM system is readily to be use in order to reduce the time to market. The ARM system allow designer to modify, to suit the need. Some of the passed research also been review and compare in the following section. Design strategies are discuss in the methodology section. Result and discussion show the successful integration and verification using hardware software co-verification.

Literature Review
In paper [9], a landmine system on chip detector was designed and implement on FPGA. The design was using AMBA bus architecture as the on chip bus to achieve a high speed processing. The system architecture made up of processor, concurrent processor, and some port as shown in Figure 1. The input data will be transfer from Digital Analogue Converter (DAC) in the processor. Then, the concurrent processor will process the signal. The result will be shown at the output port. This process will be repeated for the detection. A comparator inside the concurrent processor will compare the pre-stored value inside the memory. Figure 1. The block diagram of landmines architecture [9]. In paper [10], the author proposed a changeable processor platform in order to reduced time to market. The design include modules which are the building blocks for most of the embedded application such as timer, GPIO as shown in Figure 2. The design processor used in the design are ARM9 based processor and the PalmBus as the bus architecture. The CPU interface controller handle the signal between the processor and the PalmBus. The controller can decode up to 64MB address. The PalmBus will be receive either read or write request from the processor. The design was run on the Spartan3 and run with 33.3MHz. The design claim that only 19% FPGA slices is used and is suitable for more module using this platform. Figure 2. : The changeable processor architecture [10]. In paper [11], a power efficient x86 processor and an AMBA bus architecture system on chip was proposed. The PKUnity86 and an AMD Geode GX2 processor is design to support massive PC software resources such as Microsoft Window. The design was implement on Virtex-4 LX200 FPGA. The designer need to take care of address space, memory, I/O ad interrupt allocation, external float point unit exception, cache coherence that are huge difference between AMBA and the Windows system. The function of XAB component is to translate the transaction GeodeLink to AHB. The design was download into FPGA and run with Window XP BIOS.  [11]. In paper [12], a AHB-DMA controller has been reviewed and shown in Figure 4. The Direct Memory Access (DMA) is the memory that is able to transfer the data from the bus and the IP directly for a given programmed count. Initially, the processor will start to program the operational registers of the AHB-DMA. The DMA will start to transfer data after receive the control word register and will generate interrupt after the process. The DMA enable to the processor away from transfer a long data.  [12]. In paper [13], an APB controller and the peripheral devices had been integrated. The design architecture is based on the standard AMBA protocol. The design only focus on APB side and integrated with IP modules such as keypad decoder, timer, seven segment decoder, UART as shown in Figure 5. The AHB to APB Bridge is the master for the APB and the APB controller will control the flow of data and control signals. The design was implemented on the SPARTAN 3 board with 50MHz.  Figure 5. The APB controller on APB side [13].
In conclusion, several system architecture had been reviewed. Each of the design has its advantages, and challenges. Some the design had shown how to design and the way to implement on hardware which are useful for this paper.

Methodology
In this paper, the design start by using the ready to use ARM Cortex-M system design kit as the base system. The system include several peripheral such as AHB bus components, UART, GPIO. The design of two reusable IP are integrate into the system and create a multipurpose microcontroller. The design of RTC is include function controller, counter binary frequency divider and also an AMBA interface as shown in Figure 6 based on [14]. The RTC is consider the leap year feature, which the date will increase one day in every four years. Besides, alarm function also included in this IP. The counter resolution for this IP will up to plus minus 1 millisecond per counter. This will increase the accuracy of the clock. Figure 6. The design block diagram of RTC. Next, Temperature Digital Signal Processing (TDSP) is design to monitor the temperature of the chip especially the part that has highly usage. The architecture in block diagram of TDSP is shown in Figure  7 based on [15]. The design also include AMBA bus protocol signal for reuse purposes. An interface register, function controller, programmable watchdog, and interrupt generator are the main components for this TDSP. The TDSP is able to give interrupt to the processor when the surrounding is overheat and prevent hard fault on the chip. The conception of the TDSP is the processor will set a threshold value for the TDSP to compare the signal receive from Analogue Digital Converter (ADC). An interrupt will send out to the processor when the ADC value is higher than the threshold value. Figure 7. The block diagram for TDSP. The overall system architecture is shown in Figure 8. All the IP are then integrated into the system with the memory map which is designed as shown in Table 1.  Subsequently, an application for the processor is added. The program is generated using Keil software. The application use C language to test the design by input the time and date. The program let the RTC to run for a few cycle before other input. The alarm included by set a certain time to trigger the interrupt. Next, the TDSP is provided with the threshold value, and a model input from ADC was created in the testbench.

Result and Discussion
The Figure 9 show that the simulation waveform run in Synopsys. The important signal for the RTC was highlighted which are seconds, minutes, hours, date, months and years. The data 0x5096_9670 is transfer using write data bus which is known as PWDATA. The time shown is 08:18:52am and 21st June 2017. The design for date, month and years shown are not exactly the value as the time. This is because the design of RTC is initiate the value to zero and the software can adjust the value by plus one. The Figure 10 show the value input to TDSP. The TDSP show the interrupt when the value of ADC show high which the value from temperature sensor (INPUTADC) is 2'b11 and the interrupt is occurred in PRDATA which is 2'b10. The system and the support documents was obtained from ARM official website [14][15] through ARM University Program.

Conclusion
This paper has presented the design of a system on chip microcontroller system. The primary goal of this effort is to design the reusable IP and integrate into the AMBA platform. The most widely used IP such as RTC and TDSP are chosen as the IP to integrate. The result was run on Synopsys tool and the simulation result showed was same as intended. In future study, more and more IP can be design and integrate into this microcontroller so that the microcontroller is multi-function.


Instance-weighted Central Similarity for Multi-label Image Retrieval

Deep hashing has been widely applied to large-scale image retrieval by encoding high-dimensional data points into binary codes for efficient retrieval. Compared with pairwise/triplet similarity based hash learning, central similarity based hashing can more efficiently capture the global data distribution. For multi-label image retrieval, however, previous methods only use multiple hash centers with equal weights to generate one centroid as the learning target, which ignores the relationship between the weights of hash centers and the proportion of instance regions in the image. To address the above issue, we propose a two-step alternative optimization approach, Instance-weighted Central Similarity (ICS), to automatically learn the center weight corresponding to a hash code. Firstly, we apply the maximum entropy regularizer to prevent one hash center from dominating the loss function, and compute the center weights via projection gradient descent. Secondly, we update neural network parameters by standard back-propagation with fixed center weights. More importantly, the learned center weights can well reflect the proportion of foreground instances in the image. Our method achieves the state-of-the-art performance on the image retrieval benchmarks, and especially improves the mAP by 1.6%-6.4% on the MS COCO dataset.

Introduction
Representing images efficiently is an important task for large-scale multimedia retrieval. Hashing has attracted extensive attention due to its computational and storage efficiency. It aims to encode high-dimensional data points into compact binary codes, hence the original feature space can be efficiently approximated via low-dimension Hamming space [26,20]. Recently, deep learning to hash methods can perform simultaneous feature learning and hash code learning in an end-to-end way, which has shown state-of-the-art performance on many benchmarks [30,12,33   Use multiple hash centers with the equal weights to generate a centroid as the learning target, which does not consider the relationship between the center weights and the proportion of foreground instances in the image. (c) We propose instance-aware weighting approach to automatically learn the hash center weights by an alternative optimization. As illustrated in sub-figure (c), the center weights corresponding to the three foreground instances (shape, dog and chair) are 0.70, 0.18, and 0.12 respectively, which well reflect their proportion in the image.
The existing data-dependent hashing methods mostly generate similar binary codes for similar data points by utilizing pairwise or triplet data similarity [14,28,2]. Yuan et al. [31] analyzed the limitations of the pairwise/triplet based hashing methods, and proposed the Central Similarity Quantization (CSQ) for image retrieval that not only captures the data similarity globally but also improves the learning efficiency. The existing central similarity methods utilize the row vectors or column vectors of Hadamard matrix to generate hash centers [17,3,15,31]. As shown in Figure 1 (a), a single center is used as the target to learn the hash function for single-label image retrieval. For multilabel image retrieval illustrated in 1 (b), however, Yuan et al. [31] only uses multiple hash centers with equal importance to generate one centroid as the learning target. The central similarity based methods neglect the relationship between the importance of the hash centers and the proportion of foreground objects in the image. In addition, the above methods only consider the semantic similarities at image level, which may be suboptimal for multi-label image retrieval.
The existing multi-label image retrieval methods can be divided into two main categories: one is to use the region proposal module to extract foreground objects and generate multiple hash codes for a multi-lable image [13,8,22]. The other is to consider the number of common labels of multi-label image as the metric of similarity [32,21]. The former methods achieve instance-aware retrie, but their limitation is that the generation of hash codes is dependent on the quality of region proposal module. Therefore, how to make the model automatically learn the multi-scale semantic information contained in the image without using region proposal module?
In this paper, we propose an nstance-weighted Central Similarity (ICS) to learn the relative importance of each hash center corresponding to a hash code as shown in 1 (c). Our method use multiple hash centers to guide the model to focus only on the foreground objects and ignore the background. ICS is a two-step alternative optimization approach. In the first step, we apply the maximum entropy regularizer to prevent one hash center from dominating the loss function, and compute the center weights via projection gradient descent. In the second step, the neural network parameters are updated by standard back-propagation. In addition, the center weights learned by ICS can reflect the proportion of foreground objects in the image, instead of leveraging the region proposal generation model to produce hash codes for foreground objects. The performance of proposed ICS for multi-label image retrieval is evaluated on NUS-WIDE [4] and MS COCO [18] datasets. Our contributions are summarized as follows.
• We first consider the relationship between the importance of hash centers and the proportion of foreground instance regions in the image, and propose the ICS to automatically learn the hash center weights by an alternative optimization.
• The maximum entropy regularizer in ICS leads the distribution of center weights to be more reasonable and the learning process of center weights can converge within few iterations via project gradient descent.
• The proposed ICS is also a instance-aware method that the center weight value can well reflect the proportion of foreground objects in the image. Our visualization results can support this point well.
• Our experimental results demonstrate that the ICS can improve the performance on the three data sets NUS-WIDE, MS COCO and FLICKR25K by 0.4%-1.1%, 1.6%-6.4% and 6.0%-7.6% in mAP, respectively.

Related Work
In this section, we briefly review the related works in terms of deep learning to hash methods, and divide them into two categories according to whether the multi-label information in the image is considered.
The first category is represented by HashNet [2] and CSQ [31]. 1) HashNet [2] considered the imbalanced similarity relationships between positive and negative pairwise samples, and used weighted maximum likelihood objective function to learn hash codes. DCH [1] used Cauchy distribution to improve search performance from a Bayesian perspective. However, the above pairwise/triplet based methods ignore the global structure of samples and suffer from low retrieval efficiency. 2) Recent deep hashing methods [17,16,3,31] based on Hadamard matrix show promising results due to its orthogonal and balanced structure. CSQ [31] leveraged Hadamard matrix to generate hash centers for learning central similarities between samples. HCDH [3] used label information to guide the learning of hash centers. For multi-label images, however, the previous methods ignore the relative importance of each hash center and consider each lable equally in a image. In this paper, we consider the proportion of each foreground object should be different and propose to learn the center weights automatically.
The second category is represented by IAH [13] and RCDH [21]. DSRH [32] and IAH [13] used the region proposal module to generate multiple hash codes for a multilable image. The limitation is that the generation of hash codes is dependent on the quality of region proposal module. RCDH [21] considers the number of common labels of multi-label image as the metric of similarity.

The Proposed Method
In this section, we first introduce how to generate hash centers via Hadamard matrix. Afterwards, maximum entropy regularizer is applied to learn the relative importance of each hash center. Finally, we propose the two-step based optimization approach to update the hash center weights and neural network parameters alternatively.

Problem Definition
Let X be a set of training data, i.e.
where D is the dimension of input, M denotes the number of labels, and y i stands for the label corresponding to the i-th sample. Our goal is to learn a nonlinear hash function f θ : K that encodes each data point x into compact Kbit hash code, where θ denotes the model parameters. At the same time, similarities in the original space are preserved in the Hamming space. Given a set of hash centers and their corresponding weights , where c i represents the number of labels of x i . We aim to automatically learn the hash center weights w. In addition, we hope that the value of w can reflect the proportion of the corresponding foreground objects in the image.

Generation of Hash Centers
Following [31], we define the row vectors in Hadamard matrix as hash centers. Hadamard matrix satisfies the independence and balance principles that its row vectors and column vectors are pair-wise orthogonal, and half of bits are 1 or -1. The generation of 2 k -order Hadamard matrix H is rather simple using the Sylvester's algorithm [25]: where ⊗ represents the Kronecker product. The generation of hash centers is related to the number hash bits K and the number of class labels M , which includes three strategies: 1) When M ≤ K, the row vectors are randomly sampled from H as hash center. 2) is utilized to sample hash centers. 3) When 2K ≥ M and K is not the power of 2, each bit in a hash center v is sampled from a Bernoulli distribution Bern(0.5), which means that random half of bits are 1 or -1.

Instance-weighted Central Similarity
In order to measure the similarity of hash code and its corresponding hash centers {v ij } ci j=1 , Binary Cross Entropy (BCE) is used to measure the Hamming distance d i between the hash code b i and its hash centers v i . The distance function d i = Ω(b i , v i ) can be written as: As illustrated in Figure 1, the proportion of foreground instances in the image is different. Therefore, for the hash centers {v ij } ci j=1 representing different labels, hash code b i should be given different weights according to the distance.
We think the Hamming distance between each hash code b i and its corresponding hash centers {v ij } ci j=1 should be weighted non-uniformly. We introduce weights {w ij } ci j=1 to reflect the weights of hash centers and assume that it is learnable rather than with the same importance. Therefore, we design a weighted central similarity loss: where j = 1, 2, ..., c i represents the number of hash centers corresponding to a hash code. In addition, we regard the probabilities of assigning each hash code to the hash centers as a classification problem. We convert the distance Ω(b i , v i ) based on the adaptive Sigmoid function as follows: where β is a smooth parameter to control its bandwidth. Inspired from HashNet [2], the Sigmoid function with larger β will have larger saturation zone where its gradient is zero. To perform more effective back-propagation, we usually require β ≤ 1 in our experiments. It is easy to see that the smaller Ω(b i , v i ) is, the larger p(Ω(b i , v i )) will be. Therefore, maximizing the likelihood of p(Ω(b i , v i )) will make the Hamming distance between hash centers and hash codes small, which means that the foreground instances with larger proportion in an image, the higher classification probability of the corresponding hash centers.
We define the following likelihood function to learn center weight w: By taking log of p(Ω(b i , v i )), it can be derived as: We redefine the loss function as: We can expand this formula as: However, the direct minimization of above equation with respect to w ij may produce unreasonable hash center weights. This is obvious from the following Lemma 1.
We can obtain a unique minimum solution for Eq. 8 with the weights w ij = 1 if j = argmin 1≤j≤ci d ij and 0 elsewhere. However, the weighted distance function for a multilabel image only minimizes Hamming distance between a hash code and its corresponding one hash center, which obviously makes no sense for multi-label image retrieval. To prevent one hash center from dominating the loss function, we apply the maximum entropy principle to learn the hash center weights.
We can reformulate the loss function as : The above equation has a new parameter λ that is used to control the degree of maximum cross entropy regularization. If λ approaches zeros from positive and w ij approaches 1 ci , then the minimization of above loss function tends to give equal weight to each hash center. If λ approaches a positive infinity, then w ij will approach w ij = 1 if j = argmin 1≤j≤ci d ij and 0 elsewhere. Obviously, such a result is not suitable for multi-label image retrieval. The detailed analysis of how to choose a proper λ will be further demonstrated in section 4.
We also use the quantization loss J q to make the hash codes converge to hash centers [9].

Algorithm 1 Instance-weighted Central Similarity
Input: where γ is fixed and set to 0.05.

Alternative Optimization
In order to automatically solve center weight w and perform model training, we propose a two-step alternative optimization approach. In the first step, parameters of model f θ are frozen and we compute the hash codes {v i } N i=1 via f θ and Hamming distance {d i } N i=1 , we then utilize project gradient descent [27] to optimize {w i } N i=1 . In the second step, update f θ by backpropagation with fixed w. We briefly summarize the major workflow of our proposed ICS method in Algorithm 1. The solving process of w is as follows.
The gradient vector of the objective function J with respect to w i can be derived as: where w t ij denotes the value of parameter w ij at iteration t. Hence, we can find the optimum value of w ij by gradient descent: where η denotes the learning rate. In all experiments, η is set to 0.1. After obtaining solution w t i , in order to compute the Euclidean projection of w t i onto the probability simplex, Algorithm 2 Euclidean projection of w t i onto the probability simplex Input: w t i ∈ R ci Output: w t i s.t.w t ij = max w t ij + ξ, 0 , j = 1, 2, ..., c i 1: Sort w t i into q : the optimization problem is defined as follows: The solution [27] of Eq. 15 is presented in Algorithm 2.

Experiments
We first perform extensive experiments to evaluate our ICS against several state-of-the-art hashing methods on three multi-label datasets, NUS-WIDE [4] and MS COCO [18]. Afterwards, we visualize the convergence behavior of solving the optimization via project gradient descent. Finally, we conduct ablation studies to analyze the effectiveness of the learned hash center weights.

Datasets
The following three benchmark datasets are used in our experiments and their statistics are summarized in Table 1.
NUS-WIDE contains about 0.27M images in 81 categories [4]. Each image belongs to more than one label. We follow similar experimental protocols as CSQ [31], we randomly sample 10,000 images as training set, 5,000 images as queries, the remaining images are used as database.
MS COCO is an image recognition, segmentation, and captioning dataset, which contains 80 common object categories with 82,783 training images and 40,504 validation images [18]. We randomly sample 5,000 images as queries, with the rest images are used as the database; furthermore, we randomly sample 10,000 images from the database as training set.

Implementation Details
We implement the ICS method on the Pytorch framework [23], and adopt AlexNet [10] and ResNet-50 [7] pretrained on ImageNet as backbone architectures to evaluate the performance of our proposed method. We use the standard data argumentation strategies such as random horizontal flip and random crop. Each image is resized to 256×256 and then is cropped to 224×224. We apply Adam optimizer with β 1 = 0.9 and β 2 = 0.99 to optimize model parameters, and set weight decay to 0.9 and batch size to 64. The neural network is trained for 90 epochs where the learning rate starts from 0.0001 and is divided by 10 every 30 epoch.

Experimental Results
As illustrated in Table 2, our method using AlexNet backbone increases the performance by 1.1%, 0.4%, 0.5% for 16 bits, 32 bits and 64 bits on the NUS-WIDE, and yields an improvement of 6.4%, 2.8%, 1.6% for 16 bits, 32 bits, and 64 bits on the MS COCO. The results in Table 3 achieve absolute improvements of 2% and 6.6% for 16 bits on the two datasets, respectively. The above impressive results clearly demonstrate that our method achieves state-of-the-art performance by considering the relationship between the hash center weights and the proportion of foreground instances in the image.
Convergence of Project Gradient Descent We would like to study the convergence behaviour of the adopted projected gradient descent for automatically learning the  Figure 2 shows that the loss converges within 10 iterations or even fewer, which demonstrates that PGD can solve the optimization problem efficiently. The extra computational cost of PGD is relatively small, the time consuming is about 8 ms.

Ablation Study
We analyse the effectiveness of our proposed ICS in the following three aspects.

Equal Center Weights
We compare our proposed ICS with its variant, Equal Weighted Central Similarity (E-WCS). Different from CSQ [31] using single centroid as learning target, E-WCS uses multiple hash centers as learning target and fixes their weights with equal values, 1 ci . As illutrated in Table 4, the average performance of E-WCS is inferior to CSQ, and ICS achieves higher mAP than E-WCS and CSQ for different bits on NUS-WIDE and MS COCO datasets. In addition, The results demonstrate the necessity of automatically learning the hash center weights, rather than fixing them with equal values or learning with single centroid.

Parameter Analysis
We firstly tune the parameter β with fixed λ = 1, and then choose the optimal parameter β for different bits to adjust λ. We construct experiments on the analysis of hyperparameters using AlexNet backbone on Ms COCO dataset, and the chosen hyper-parameters are directly applied to all the other datasets. Parameter β. The β is a smooth parameter on the Sigmoid function Eq. 4 to control its bandwidth. As shown   Figure 5, When β is 0.001, 0.01, 0.1, the model achieves the best performance on 16, 32, and 64 bits respectively. We can conclude that smaller bits achieve the best results with smaller β, For image retrieval in 64 bits, the distance between each hash code and its corresponding hash centers is larger than lower bits. Therefore, larger β makes the curve of Sigmoid function more smoother to prevent the gradient from disappearing, which is consistent with the result of HashNet [2].
Parameter λ. The λ is used to control the maximum entropy regularization. We choose the value of λ from {10, 1, 0.1, 0.01, 0.001, 0.0001} and compare their performance on MS COCO dataset in 16, 32 and 64 bits. As discussed in Lemma 1 and illutrated in Figure 6, larger λ makes one hash center dominate the loss resulting in poor retrieval performance. The results also demonstrate that the     proposed maximum entropy regularization is not very sensitive to the value of λ when λ ≤ 1.

Visualization of Center Weights
We evaluate the model on the MS COCO dataset for visualizing the values of weights. Figure 4.4 shows the weight value of hash center corresponding to each foreground instance belonging to different categories. For example, in the last images in the lower right corner, the center weights of "person", "toothbrush" and "bench" are 0.50, 0.25 and 0.25, respectively. The visualization results illustrate that the weight values learned by ICS can well reflect the proportion of each foreground instance in the image. Moreover, although the "toothbrush" occupy a smaller region than "bench" in the image, they have same values of center weights, which demonstrate that our proposed ICS can guides the model focusing on more semantic and salient regions to improve the retrieval performance.
In addition, we also visualize the distribution of center weights. As shown in Figure 4, our method achieves the best performance 0.764 where the variance of weights is smaller. Compared with CSQ [31] in which all the weight values are equal to 1, our results demonstrate that the more uniform distribution of center weights is conducive to model learning for multi-label image retrieval.

Conclusion
In this paper, we propose to automatically learn the hash center weights by an alternative optimization approach for multi-label image retrieval. The maximum entropy regularizer prevents one hash center from dominating the loss function, and guides the model to identify the relative importance of hash centers. Our method is also an instanceaware method that the learned hash center weights can well reflect the proportion of foreground objects in the image. Experiments on two datasets validate the effectiveness of our proposed method. Beyond the multi-label image retrieval task, our method has great potential on other tasks, which needs to be further explored.