11institutetext: Rzeszów University of Technology, Rzeszów, Poland
11email: {marekb<EMAIL_ADDRESS>22institutetext: 22email:
<EMAIL_ADDRESS>33institutetext: Systems Research Institute Polish Academy
of Sciences, Warsaw, Poland 33email: {maria.ganzha<EMAIL_ADDRESS>

# Application of genetic algorithm to load balancing in networks with a
homogeneous traffic flow

Marek Bolanowski 11 0000-0003-4645-967X Alicja Gerka 22 0000-0001-7406-8495
Andrzej Paszkiewicz 11 0000-0001-7573-3856 Maria Ganzha 33 0000-0001-7714-4844
Marcin Paprzycki 33 0000-0002-8069-2152

###### Abstract

The concept of extended cloud requires efficient network infrastructure to
support ecosystems reaching form the edge to the cloud(s). Standard approaches
to network load balancing deliver static solutions that are insufficient for
the extended clouds, where network loads change often. To address this issue,
a genetic algorithm based load optimizer is proposed and implemented. Next,
its performance is experimentally evaluated and it is shown that it
outperforms other existing solutions.

###### Keywords:

extended cloud computer network load balancing SDN routing IoT self-adapting
networks.

##  1 Introduction

Today, typical “data processing systems” consist of “distributed data sources”
and (a) “central cloud(s)”. However, the advent of Internet of Things forces
changes, since the “decision loop”, from the “sensor(s)” to the cloud and back
to the “actuator(s)”, may take too long for (near-)real time applications.
This problem is addressed by, so called, Extended Cloud (EC). Here, the whole
ecosystem becomes a logical/virtual cloud. Obviously, the EC encompasses
highly heterogeneous hardware (including networking devices). The typical
approach to functionalize this vision is by application of Software Defined
Networking (SDN). However, the question of SDN load balancing remains open as,
for networks with varying communication loads, dynamic load balancing is
needed.

Here, note that, in the classical approach, in both the L2 and L3 layer
protocols (of the ISO/OSI model; STP), in the case of multiple connection
paths, as a rule, only one is used, while the remaining paths become “backup
connections”. Obviously, multiple mechanisms to balance the load have been
proposed, e.g.: by modifying the STP root priority parameters for individual
VLANs; or by routing protocols attempting at balancing the load (OSPF equal-
cost multi-path, EIGRP unequal-cost multi-path) [31, 1, 16]. However, since
they redistribute the load “locally”, some links remain overloaded, while
others are not used.

In standard routing protocols, after a “warm-uptime”, the final routing table
is formed. For instance in the RiverBed Modeler [3], by default, the routing
stabilization occurs after 300 seconds. Attempts to dynamically modify routing
parameters are focused on modification of the routing algorithms, link
weights, etc. ([35, 32]). However, their implementation potential is low. For
example, continuous modification of link weights, or direct interference with
the routing protocol settings, during dynamic routing, may require reset of
the Open Shortest Path First (OSFP) process. This, is very time consuming, and
has negative impact on network reliability. Here, note that the keys to
effective management of network load balancing are: (I) global view of the
network, and (II) elimination of overloaded links through dynamic adaptation
of the routing policy. This requires an “arbitrator”, which will collect
information about communication requests and dynamically manage routing ([26,
7, 38]). At present, this vision is met by the SDN paradigm, which also
enables easy implementation of novel traffic control algorithms. This, in
turn, allows balancing loads in the aggregation layer, connecting EC elements
that, in addition to classic elements (servers, routers, etc.), may contain
“IoT elements”, e.g. sensors and actuators[34]. Here, note that such elements
are particularly sensitive to communication delays, e.g., in remote control of
industrial elements [33, 10, 30] (ECs realizing Industry 4.0 scenarios).

Separately, note that classic load balancing algorithms, when applied to the
SDN-based networks, are NP-hard [39]. Therefore, a genetic algorithm-based
approach (the SDNGALB algorithm), to SDN network load balancing, is being
proposed. The proposed solution delivers self-adaptive network that can evolve
over time, adapting to communication requests, e.g. within the EC running
network. The proposed approach has been implemented and tested in lab-based
network, showing its advantages.

In this context, Section 2 summarizes pertinent literature. Next, Section 3
contains problem formulation, and the proposed algorithm. In Section 4,
experimental results are presented and discussed. Section 5 summarizes main
contributions and suggests future work directions.

##  2 Related work

Effective optimization of use of network and system resources, in the Extended
Cloud, requires effective load balancing. Since the nature of the problem is
NP-hard, metaheuristic algorithms have been proposed. Therefore, in what
follows, only results related to application of metaheuristics-based
approaches to network load balancing will be discussed. Readers interested in
a comprehensive overview of other load balancing approaches may consult [8,
14, 28, 6, 24].

In [19], the authors compared the effectiveness of metaheuristics-based
approach to network resource and energy optimization. The performance of
Particle Swarm Optimization, Ant Colony Optimization, Artificial Bee Colony,
Genetic Algorithm (GA), and Bat scheduling algorithm, has been explored. These
algorithms can be also used for load balancing in actual networks, but the
cited work focuses only on virtualized distributed systems.

Work reported in [9] considers balancing the load of SDN controllers, using a
genetic algorithm, to improve the operating parameters of the network. The
authors have successfully used GA to pair elements of a cluster of controllers
and controlled switches. Similarly, in [23], research was focused on the
impact of sudden changes in network flows on the load distribution, between
SDN controllers. Such changes may impair processing of data flows by the most
loaded controllers and, simultaneously, limit use of lightly loaded ones.
Here, load balancing of other network elements, except for the SDN
controllers, was not considered.

In [25], a genetic algorithm-based strategy for load balancing in SDN optical
networks was proposed. This approach, however, focuses on optimal localization
of new (added) links, rather than on balancing load in existing connections.

A GA-based, strategy for balancing load of end devices, in wireless
metropolitan area networks, to optimize the performance of mobile
applications, was proposed in [21]. The solution deals with optimal
distribution of computing tasks across the network infrastructure. It was
found that while lowering the overall network response times, it does not
directly affect the load on individual links.

Work described in [20], is focused on SDN load balancing and uses genetic
algorithm to search for the best path for a given traffic, taking into account
the current load, bottlenecks and the shortest possible path. The proposed
solution has been tested for Fat-Tree topology only.

Optimization of weights, in MPLS and OSPF networks, is a separate research
area. However, it is directly related to the topic discussed here. The search
for a solution to the OSPF Weight Setting problem is very important in the
context of the load balancing. It is also NP-hard, and the authors of [12]
stated that even the search for an approximate solution should be treated as
an NP-hard task. In [18], the authors further confirm that solving the problem
of load balancing is NP-hard, while being very important from the point of
view of traffic engineering. Here, the authors take into account the matrix of
communication requests between the nodes, in order to define the traffic, but
the solution is dedicated to networks with a diameter of no more than 5.

Authors of [29], proposed a genetic algorithm to optimize the link weights
used in the OSFP protocol, to minimize the maximum load on the links,
perceived as the percentage saturation of the communication channel. This is a
continuation of the work presented in [13]. Here, the authors propose to use
GA to configure the OSPF weights for several popular network topologies, and
the optimization goal of such a distribution of traffic is to minimize the
total cost of the flow, which is defined as the quotient of link load and link
capacity. Finally, in [27], multi-objective particle swarm optimization
algorithm is used to efficiently solve the OSPFWS problem. Here, scalar cost
function, derived from optimization metrics such as maximum utilization,
number of congested links, and number of unused links, is used in the proposed
approach.

Overall, based on a comprehensive analysis of works related to use of
standard, and metaheuristics-based, approaches to network load balancing, the
following conclusions have been formulated:

  * •

Use of metaheuristics-based approaches, to solve the load balancing problem in
computer networks, remains an active (and promising) research area.

  * •

Solutions found in the literature are focused mainly on use of static values
of weights for communication links. This leads to creation of a temporarily
optimal, but static, connection structure, and leaves an open research gap.

  * •

In the conducted work, special attention should be paid to the possibility of
applying the developed solutions in the environment of real network devices.
Among other things, attention should be paid to reducing the time needed to
find solutions, which has a direct impact on the time needed to reconfigure
the network in response to changing operating conditions.

To address limitations of found approaches, and to deliver solution applicable
to ECs, a genetic algorithm, with high implementation potential, is proposed.
To describe it, let us start from a formal problem description.

##  3 Problem formulation and proposed solution

In what follows, computer network will be represented by a directed graph
$G(N,E)$, where $N$ is a set of nodes, representing network devices, and $E$
is a set of edges representing network links. Each edge ${{e}_{ij}}\in E$ is
assigned a weight ${{w}_{ij}}$, the modification of which will affect the
current shaping of the routing policy. Moreover, the following assumptions
have been made:

  * •

Communication channels, represented as ${{e}_{ij}}\in E$, have the same
bandwidth. Nevertheless, the application area of the algorithm includes:
distribution layer of networks, small and medium operator networks, MESH and
IoT networks.

  * •

$G\left(N,E\right)$ is a directed graph, which allows to take into account the
asymmetry of flows, typical for routing protocols operating in real networks.

  * •

Network switches, routers and intermediary nodes are treated as “identical
network devices” because, from the point of view of SDN network control, their
distinction is irrelevant [36].

The network topology is represented by a graph adjacency matrix $G(N,E)$,
denoted as $M$, with size $N\times N$. When there is a connection between two
nodes $i$ and $j$, the value ${{e}_{ij}}=1$ is assigned, while ${{e}_{ij}}=0$
otherwise. Note that $M$ is not a symmetric matrix.

In order to optimize the routing of flows, weights ${{w}_{ij}}$ are assigned
to individual transmission channels; while ${{w}_{ij}}$ are from the range of
natural numbers $(1,v)$ where $v$ can take any value. Weight matrices $W$ have
size of $N\times N$.

The weighted adjacency matrix ${M}_{W}$ is determined as the Hadamard product
[37] of $M$ and $W$ matrices:

${{M}_{W}}=M\bullet
W=\left(\begin{matrix}{{w}_{11}}\cdot{{e}_{11}}&\ldots&{{w}_{1N}}\cdot{{e}_{1N}}\\\
\vdots&\ddots&\vdots\\\
{{w}_{N1}}\cdot{{e}_{N1}}&\cdots&{{w}_{NN}}\cdot{{e}_{NN}}\\\
\end{matrix}\right)$ (1)

Figure 1 shows a sample graph representation of a network with $N=10$, and
$v=9$. For pairs of vertices $(s,d)$, where $s,d\in N$, homogeneous traffic
flow $f$ specifies requests to transmit information from the source node to
the destination node, represented by a flow matrix ${{F}_{sd}}$.

${F_{sd}}=\left({\begin{array}[]{*{20}{c}}{{p_{11}}}&\ldots&{{p_{1N}}}\\\
\vdots&\ddots&\vdots\\\ {{p_{N1}}}&\cdots&{{p_{NN}}}\end{array}}\right)$ (2)

where: $s=d\to{{p}_{sd}}=0$; ${{p}_{sd}}=m\cdot f$, $m\in\mathbb{N}$.
Homogeneous flow $f$ corresponds to the granularity of flows in the network,
as is the case with queues, e.g. in the Ethernet network ($f=64\text{kb}$).
Total flow ${{p}_{sd}}$, is therefore defined as a multiple of the base flow
$f$. When, a unit value $f$ is assumed, then ${{p}_{sd}}=m$. For example, for
channels 100 Mb/s and granulation $f=64\text{kb}$, for any edge $\max m=1563$.
In what follows, such network will be named a network with homogeneous flow
structure. The flow matrix can change over the life time of the network. The
values of the elements of this matrix can also be predicted in advance [15].

Figure 1: An example graph representation of a weighted, directed
interconnection network.

The matrix $L$ determines the current link load ${{e}_{ij}}$ of the network
topology. Here, it is assumed that it will be systematically modified, as a
result of the modification of weights in the matrix $W$ and the distribution
of flows defined in the matrix ${{F}_{sd}}$.

The path between the vertices $s,d$, for a given flow ${{p}_{sd}}$, will be
determined using the Dijkstra algorithm [11]. However, other algorithms can
also be used here. Thus, the value for ${{l}_{ij}}$ is determined as the sum
of flows ${{p}_{sd}}$ passing through the edge ${{e}_{ij}}$. Taking into
account the need of dynamic control of link weights (in the network), the
problem of load balancing can be defined, as seeking a set of link weights
$W$, for which the maximum number of flows passing through the “busiest edge”
in the network has been minimized. Therefore, the problem can be formulated
as:

$\min\left(\max\left({{l}_{ij}}\right)\right)$ (3)

Note that, in the algorithm, the load matrix $L$ is represented as a load
vector
$VL={{[{{l}_{11}},{{l}_{12}},...,{{l}_{1N}},...,{{l}_{N1}},{{l}_{N2}},...,{{l}_{NN}}]}^{T}}$

As mentioned before, the problem of balancing the load of links in the network
is NP-hard, i.e. the time to find the optimal solution grows exponentially
with the size of the problem. The overriding goal of this contribution is thus
to propose a solution characterized by low computational complexity, which
will allow actual implementation of the balancing algorithm, and its
deployment in a real production system. As a result, the SDN Genetic Algorithm
Load Balancer (SDNGALB) is proposed. Let us described it in more details.

###  3.1 Operation of the algorithm SDNGALB

In the first step, the values of the elements ${{w}_{ij}}$ are randomly
populated, with natural numbers from the range $(1,v)$. In what follows, $\max
v=9$ was assumed. However, for very large networks, with high connectivity, a
larger range of weights may be needed. However, this must be determined
experimentally, or based on the designers’ intuition [17].

The genetic algorithm, presented in Figure 2, uses standard genetic operators
(cross-over and mutation) to process the population of solutions originating
from the prior selection. The following decision have been made during the
design of SDNGALB (see, also, Figure 2 for the block diagram of the
algorithm).

  1. 1.

The chromosome is the weight list $VW$, of individual network links, created
on the basis of the matrix ${{M}_{W}}$, according to the rule: if for any
$x,y\in(1,N)$, ${{w}_{xy}}\cdot{{e}_{xy}}=0$ weight should be omitted; if
${{w}_{xy}}\cdot{{e}_{xy}}>0$ the weight should be added to the list (the
length of the chromosome is equal to the number of edges in the network
graph).

  2. 2.

The initial chromosomes are randomly generated, from range $(1,v)$. The size
of the population is selected experimentally, and is denoted as $n$.

  3. 3.

The fitness function (FF) is calculated using formula (3). The FF algorithm is
presented, in the form of a pseudocode, as Algorithm 1.

  4. 4.

Individuals are ranked on the basis of the value of their fitness function.

  5. 5.

Pairs of individuals, arranged according to the quality of adaptation, are
crossed with each other using the one-point method – the crossing point is
selected randomly, and the parts of the chromosome “after this point” are
exchanged, creating individuals of a new population.

  6. 6.

Mutation of individuals occurs with the probability determined by the
parameter $mp$, and consists in drawing a new value (from a specified range)
of any gene in the chromosome.

  7. 7.

The optimization process is performed until one of the following stop
condition is reached:

    1. (a)

Stagnation parameter ($sz$) is reached, i.e. number of solutions, during which
the obtained optimization result did not improve;

    2. (b)

The maximum number $gs$ of generations is reached.

Figure 2: Block diagram of the operation of the SDNGALB algorithm.

The Fitness Function algorithm requires a more detailed explanation. For each
of the defined flows ${{F}_{sd}}$, using the Dijkstra algorithm [11], the
shortest paths between the source node and the destination node are calculated
(taking into account matrices $M,W,{{M}_{W}}$). Optimization of load
distribution in the network is achieved by manipulating the link weights in
the matrix $W$, on the basis of which the matrix ${{M}_{W}}$ is built, in a
way to eliminate network bottlenecks, by reducing the load on the most
frequented edge in the network. For a set of weights $W$, of a given
chromosome $VW$, and a set flows ${{F}_{sd}}$, obtained using the Dijkstra
algorithm, the routing table $RT$ is determined. It contains a number of rows
equal to the number of non-zero matrix elements ${{F}_{sd}}$ and each row
contains a list of vertices to be traversed for a given flow ${{p}_{sd}}$,
marked as $P({{p}_{sd}})$. For example, a single row in the $RT$ routing
table, for a flow between $6$ and $0$ vertices $F_{6,0}$, might look like
$P\left({{F}_{6,0}}\right)\to e_{6,5},e_{5,3},e_{3,1},e_{1,0}$, where
$e_{u,d}$ denotes the edge connecting vertices $u$ and $d$. Then, on the basis
of $RT$, FF determines the value of the maximum link load in the network
$\max\left({{l}_{ij}}\right)$.

Below is the algorithm for evaluating the value $\max\left({{l}_{ij}}\right)$
used in the fit function. The source code of the algorithm is available at the
website [4]

Algorithm 1 Fit function (FF)
Data: $G\left(N,E\right),W,{{F}_{sd}},P\left({{F}_{sd}}\right)$
1: $L:=0,RT:=0$
2: for each ${{F}_{sd}}$
3: $P\left({{F}_{sd}}\right):=Dijkstra\left(G,W,{{F}_{sd}}\right)$
4: $RT=RT+P({{F}_{sd}})$
5: for each ${{e}_{sd}}\in P\left({{F}_{sd}}\right)$
6: if ${{l}_{sd}}={{e}_{sd}}$
7: then ${{l}_{sd}}={{l}_{sd}}+1$
8: end
9: end
10: return $max\left({{l}_{ij}}\right)$

The results of operation of SDNGALB is the optimal set of link weights $W$, in
the given network, on the basis of which a balanced routing table $RT$ is
built. This set of weights minimizes the maximum link load in the network.
Depending on the specifics of the network, the administrator can establish the
time step, at which the algorithm will be used to re-optimize the network. It
is also possible to use triggered reconfiguration, e.g. when any of the
communication channels reaches a specific throughput limit (e.g. 80%).

##  4 Experimental setup and results

The code of the algorithm was implemented in Python, during the
implementation, apart from the standard Python library modules, also numpy and
matplotlib libraries and the networkx package were used. All experiments were
carried in a simulation environment with the following parameters: Debian
GNU/Linux 10 4.19.0-8-amd64; 8 CPUs Intel® Xeon® CPU E5-2620 v3 @ 2.40GHz;
RAM: 39,3 GB. Research, carried in the computer networks laboratory of Rzeszów
University of Technology, included implementation of the SDN architecture in
the environment of real enterprise class network devices (Extreme and
OmniSwitch Alcatel-Lucent), “bare metal” switches (Edge Core), and
OpenvSwitches. During experiments, a special stand configured for research of
phenomena in the “Internet of Everything” was used [2]. The exact parameters
for each experiments will be provided as required.

The first set of tests was focused on the effectiveness of optimization. For
flows in the network represented by graph $G\left(N,E\right)$, where
$\left|N\right|=10$ and $\left|E\right|=39$, the values of the function (2)
were compared before and after using the SDNGALB algorithm. Table 1 shows the
mean value of $\max\left({{l}_{ij}}\right)$, before and after optimization,
calculated as the arithmetic mean of 10 executions of the SDNGALB algorithm
for the defined network, for $\left|{{F}_{sd}}\right|=20;30;40;50;100;200$.

Table 1: Comparison of the average effectiveness of optimization for a different number of flows in the network. Arithmetic mean | $\left|{{F}_{sd}}\right|$
---|---
of 10 executions | 20 | 30 | 40 | 50 | 100 | 200
$\overline{\max\left({{l}_{ij}}\right)}$ before optimisation | 5,6 | 8,6 | 8.8 | 11,6 | 21,8 | 41,6
$\overline{\max\left({{l}_{ij}}\right)}$ after optimisation | 2,8 | 4 | 4,8 | 5,8 | 11,6 | 22,4
Effectiveness of optimisation | 50% | 53% | 45% | 50% | 47% | 56%

As can be seen, application of the SDNGALB algorithm resulted in a noticeable
reduction in throughput on the most heavily loaded links in the tested
network. Simultaneously, the performance tests showed an increased load on
links that were previously not used and those that were only lightly loaded.

The next set of experiments was performed to compare the time of reaching
solution using the genetic algorithm and the exact algorithm searching the
entire solution space (i.e. the brute-force search; BF). Obviously, obtained
results should be seen only as base-line comparison with the worst case (time-
wise), but most efficient (finding best solution) approach. Here, 100
simulations were performed for both algorithms for a network with 4 nodes and
5 edges, and five defined flows. The same optimization result expressed by the
value of the function (3; the minimum value of the maximum link load in the
network) was obtained by both algorithms. For the genetic algorithm the mean
time was 0.0118065 seconds, while for the BF algorithm time was 4448.077889
seconds.

In the third set of experiments, the effectiveness of the proposed solution on
networks with different topologies was assessed. The speed of obtaining the
solution, and the quality of the obtained result, for
$\min\left(\max\left({{l}_{ij}}\right)\right)$ are reported. In the first
phase, 1000 simulations were performed, for six different network topologies,
in which the initial flows were randomly generated. The characteristics of the
networks $Net$, used in the study, is presented in Table 2, where the
connectivity parameter $Cn$ should be understood as the percentage ratio of
the number of edges in the tested network to the number of edges in the
network with all possible connections (represented as a complete graph).

Table 2: Parameters of networks used in the research. $Net$ | $n4e5$ | $n5e11$ | $n6e15$ | $n10e39$ | $n25e219$ | $n50e872$
---|---|---|---|---|---|---
$\left|N\right|$ | 4 | 5 | 6 | 10 | 25 | 50
$\left|E\right|$ | 5 | 11 | 15 | 39 | 219 | 872
$Cn$ | 31% | 44% | 42% | 39% | 35% | 35%
$v$ | 1-5 | 1-5 | 1-5 | 1-9 | 1-9 | 1-9
$\left|{{F}_{sd}}\right|$ | 5 | 10 | 15 | 20 | 45 | 100

Table 3 presents the average times $Ts$ (measured in seconds) of reaching the
solution; for 1000 simulations, performed for each of the networks listed in
Table 2. In this case, the flows were generated randomly for each individual
simulation. The algorithm parameters were set as follows: mutation
probability: $mp=10\%$; population size: $n=50$; generation size: $gs=500$;
stagnation: $sz=100$. Here, as the network size increases, i.e. from 4 nodes
and 5 connections to 50 nodes and 872 connections, the solution time remains
within an acceptable range. Therefore it can be stipulated that netwrk
optimization, based on the proposed SDNGALB algorithm, can find application in
real network systems.

Table 3: Average result of the load balancing time using the SDNGALB algorithm in seconds. $Net$ | $n4e5$ | $n5e11$ | $n6e15$ | $n10e39$ | $n25e219$ | $n50e872$
---|---|---|---|---|---|---
$Ts$ | 0.012 | 0.021 | 0.034 | 0.093 | 1.091 | 10.264

The proposed algorithm was implemented in the Mininet environment using
OpenvSwitches. Figure 3a shows an example of one the topologies $n10e39$ used
during tests. To control the flows, the scripts written in Python, were used.
During the simulation, additional host, named $h0$ to $h9$, was used as a
traffic generator. Application of the SDNGALB algorithm resulted in a
noticeable reduction (39%) in throughput on one of the most heavily loaded
links in the network $e_{3,1}$, as shown in Figure 3b. Simultaneously, the
performance tests showed an increased load on links that were not previously
loaded at all and on those that were loaded slightly - see the example load
change on link $e_{4,0}$, as shown in the Figure 3c.

Figure 3: a. The n10e39 network topology used in tests; throughput on links
$e_{3,1}$ (b.) and $e_{4,0}$ (c.) before and after running the SDNGALB

The final set of experiments compared the performance of the SDNGALB algorithm
with two alternative optimizers. The first one – Ant Colony Optimization Load
Balancer (ACOLAB [22]) uses ant colony optimization to determine optimal
routes between nodes. The second one – Dijkstra’s Shortest Path Algorithm
(DSPA, [5]) is based on the identification of the shortest paths between given
nodes, using Djkstra’s algorithm, under the assumption that link weights are
randomized (using values from a given range) and are not modified later. DSPA
did not optimize link weights and served only as a baseline in the context of
the execution time.

Experiments were performed on the n10e39 network (with 10 nodes, 39 edges)
with the assumption that $\left|{{F}_{sd}}\right|=20$. The performance of the
ACOLB algorithm was tested with different parameter values (number of ants: 1,
5, 10, 25, 50, 100, 500). For each combination of values for ACOLB algorithm,
100 simulations have been run, and the average results are reported. Moreover,
simulations were performed with the DSPA. Summary of the averaged results,
obtained for all three algorithms, is shown in Table 4.

Table 4: Summary of averaged results of all tested approaches | SDNGALB | ACOLB | DSPA
---|---|---|---
Execution time in second | 0.09263 | 0,02229 | 0,00546
$\overline{\max\left({{l}_{ij}}\right)}$ | 2,792 | 31,392 | 5,110

Based on Table 4, it can be concluded that the proposed solution to the
problem of optimization of link weights, in the network during routing, makes
it possible to achieve nearly twice the lower maximum link load in the
network, as compared to the performance of the DSPA algorithm. In contrast,
the ACOLB does not deliver satisfactory optimization vis-a-vis the proposed
solution.

##  5 Concluding remarks

In this work the need for efficient SDN network flow optimization has been
addressed by means of the dedicated genetic algorithm. The overarching goal
was to deliver efficient infrastructure for extended cloud infrastructures,
where resources, typically realized as services and microservices, can be
highly dispersed. The discussed approach is fast, which should allow to
quickly modify the routing table, in response to changing traffic patterns.
This is particularly important in EC ecosystems, which can be naturally
characterized by fast changing communication patterns. Results obtained during
tests, completed on actual networks (though in a laboratory) are very
encouraging, concerning both the speed and the quality of optimization.

As part of further work, (1) scalability of the proposed algorithm will be
tested for large, highly distributed, networks; (2) algorithm will be adapted
to modify the physical topology of MESH networks; and, (3) possibility of
automatic, adaptive tuning of optimizer parameters, using machine learning
techniques will be explored.

####  5.0.1 Acknowledgements

Work of Marek Bolanowski and Andrzej Paszkiewicz is financed by the Minister
of Education and Science of the Republic of Poland within the “Regional
Initiative of Excellence” program for years 2019–2023. Project number
027/RID/2018/19, amount granted 11 999 900 PLN. Work of Maria Ganzha and
Marcin Paprzycki was funded in part by the European Commission, under the
Horizon Europe project ASSIST-IoT, grant number 957258.

## References

  * [1] How Does Unequal Cost Path Load Balancing (Variance) Work in IGRP and EIGRP. https://www.cisco.com/c/en/us/support/docs/ip/enhanced-interior-gateway-routing-protocol-eigrp/13677-19.html, accessed: 2023-01-02
  * [2] Research stand IoE. https://zsz.prz.edu.pl/en/research-stand-ioe/about, accessed: 2023-01-02
  * [3] Riverbed Modeler. https://www.riverbed.com/pl/products/npm/riverbed-modeler.html , accessed: 2023-01-02
  * [4] SDNGALB source code. https://bolanowski.v.prz.edu.pl/download, accessed: 2023-01-02
  * [5] Babayigit, B., Ulu, B.: Load Balancing on Software Defined Networks. In: 2018 2nd International Symposium on Multidisciplinary Studies and Innovative Technologies (ISMSIT). pp. 1–4. IEEE, Ankara (Oct 2018). https://doi.org/10.1109/ISMSIT.2018.8567070, https://ieeexplore.ieee.org/document/8567070/
  * [6] Belgaum, M.R., Musa, S., Alam, M.M., Su’ud, M.M.: A Systematic Review of Load Balancing Techniques in Software-Defined Networking. IEEE Access 8, 98612–98636 (2020). https://doi.org/10.1109/ACCESS.2020.2995849, https://ieeexplore.ieee.org/document/9097181/
  * [7] Caria, M., Jukan, A., Hoffmann, M.: SDN Partitioning: A Centralized Control Plane for Distributed Routing Protocols. IEEE Transactions on Network and Service Management 13(3), 381–393 (Sep 2016). https://doi.org/10.1109/TNSM.2016.2585759, http://ieeexplore.ieee.org/document/7501614/
  * [8] Chaudhary, R., Kumar, N.: LOADS: Load Optimization and Anomaly Detection Scheme for Software-Defined Networks. IEEE Transactions on Vehicular Technology 68(12), 12329–12344 (Dec 2019). https://doi.org/10.1109/TVT.2019.2948222, https://ieeexplore.ieee.org/document/8876615/
  * [9] Chen, Y.T., Li, C.Y., Wang, K.: A Fast Converging Mechanism for Load Balancing among SDN Multiple Controllers. In: 2018 IEEE Symposium on Computers and Communications (ISCC). pp. 00682–00687. IEEE, Natal (Jun 2018). https://doi.org/10.1109/ISCC.2018.8538552, https://ieeexplore.ieee.org/document/8538552/
  * [10] Chien-Liang Lai, Pau-Lo Hsu: Design the Remote Control System With the Time-Delay Estimator and the Adaptive Smith Predictor. IEEE Transactions on Industrial Informatics 6(1), 73–80 (Feb 2010). https://doi.org/10.1109/TII.2009.2037917, http://ieeexplore.ieee.org/document/5356215/
  * [11] Dijkstra, E.W.: A note on two problems in connexion with graphs. Numerische Mathematik 1(1), 269–271 (Dec 1959). https://doi.org/10.1007/BF01386390, http://link.springer.com/10.1007/BF01386390
  * [12] Ericsson, M., Resende, M., Pardalos, P.: A Genetic Algorithm for the Weight Setting Problem in OSPF Routing. Journal of Combinatorial Optimization 6(3), 299–333 (2002). https://doi.org/10.1023/A:1014852026591, http://link.springer.com/10.1023/A:1014852026591
  * [13] Ericsson, M., Resende, M., Pardalos, P.: A Genetic Algorithm for the Weight Setting Problem in OSPF Routing. Journal of Combinatorial Optimization 6(3), 299–333 (2002). https://doi.org/10.1023/A:1014852026591, http://link.springer.com/10.1023/A:1014852026591
  * [14] Filali, A., Mlika, Z., Cherkaoui, S., Kobbane, A.: Preemptive SDN Load Balancing With Machine Learning for Delay Sensitive Applications. IEEE Transactions on Vehicular Technology 69(12), 15947–15963 (Dec 2020). https://doi.org/10.1109/TVT.2020.3038918, https://ieeexplore.ieee.org/document/9263348/
  * [15] Gao, K., Li, D., Chen, L., Geng, J., Gui, F., Cheng, Y., Gu, Y.: Predicting traffic demand matrix by considering inter-flow correlations. In: IEEE INFOCOM 2020 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS). pp. 165–170 (2020). https://doi.org/10.1109/INFOCOMWKSHPS50562.2020.9163001
  * [16] Grabowski, F., Bolanowski, M., Paszkiewicz, A.: Load balancing of communication channels with the use of routing protocols. Annales UMCS, Informatica 14(3) (Jan 2014). https://doi.org/10.2478/umcsinfo-2014-0024, https://journals.umcs.pl/ai/article/view/3408
  * [17] Hajder, M., Paszkiewicz, A., Bolanowski, M.: Intuicja projektanta jako nieokreśloność przy projektowaniu sieci komputerowych. In: XI International Science Conference on Computer Networks. pp. 259–268. WNT, Zakopane, Poland (2004)
  * [18] Jain, A., Chaudhari, N.S.: Genetic Algorithm for Optimizing Network Load Balance in MPLS Network. In: 2012 Fourth International Conference on Computational Intelligence and Communication Networks. pp. 122–126. IEEE, Mathura, Uttar Pradesh, India (Nov 2012). https://doi.org/10.1109/CICN.2012.119, http://ieeexplore.ieee.org/document/6375085/
  * [19] Jain, P., Sharma, S.K.: A systematic review of nature inspired load balancing algorithm in heterogeneous cloud computing environment. In: 2017 Conference on Information and Communication Technology (CICT). pp. 1–7. IEEE, Gwalior, India (Nov 2017). https://doi.org/10.1109/INFOCOMTECH.2017.8340645, http://ieeexplore.ieee.org/document/8340645/
  * [20] Jamali, S., Badirzadeh, A., Siapoush, M.S.: On the use of the genetic programming for balanced load distribution in software-defined networks. Digital Communications and Networks 5(4), 288–296 (Nov 2019). https://doi.org/10.1016/j.dcan.2019.10.002, https://linkinghub.elsevier.com/retrieve/pii/S235286481830261X
  * [21] Jia, M., Liang, W., Xu, Z., Huang, M., Ma, Y.: QoS-Aware Cloudlet Load Balancing in Wireless Metropolitan Area Networks. IEEE Transactions on Cloud Computing 8(2), 623–634 (Apr 2020). https://doi.org/10.1109/TCC.2017.2786738, https://ieeexplore.ieee.org/document/8244365/
  * [22] Keskinturk, T., Yildirim, M.B., Barut, M.: An ant colony optimization algorithm for load balancing in parallel machines with sequence-dependent setup times. Computers & Operations Research 39(6), 1225–1235 (Jun 2012). https://doi.org/10.1016/j.cor.2010.12.003, https://linkinghub.elsevier.com/retrieve/pii/S0305054810002935
  * [23] Li, G., Wang, X., Zhang, Z.: SDN-Based Load Balancing Scheme for Multi-Controller Deployment. IEEE Access 7, 39612–39622 (2019). https://doi.org/10.1109/ACCESS.2019.2906683, https://ieeexplore.ieee.org/document/8672555/
  * [24] Lin, Y.D., Wang, C.C., Lu, Y.J., Lai, Y.C., Yang, H.C.: Two-tier dynamic load balancing in SDN-enabled Wi-Fi networks. Wireless Networks 24(8), 2811–2823 (Nov 2018). https://doi.org/10.1007/s11276-017-1504-3, http://link.springer.com/10.1007/s11276-017-1504-3
  * [25] Mahlab, U., Omiyi, P.E., Hundert, H., Wolbrum, Y., Elimelech, O., Aharon, I., Erlich, K.S.Z., Zarakovsky, S.: Entropy-based load-balancing for software-defined elastic optical networks. In: 2017 19th International Conference on Transparent Optical Networks (ICTON). pp. 1–4. IEEE, Girona, Spain (Jul 2017). https://doi.org/10.1109/ICTON.2017.8024847, http://ieeexplore.ieee.org/document/8024847/
  * [26] Mazur, D., Paszkiewicz, A., Bolanowski, M., Budzik, G., Oleksy, M.: Analysis of possible SDN use in the rapid prototyping processas part of the Industry 4.0. Bulletin of the Polish Academy of Sciences: Technical Sciences 67(1), 21–30 (2019). https://doi.org/10.24425/BPAS.2019.127334, https://journals.pan.pl/dlibra/publication/127334/edition/111099/content, publisher: (:unav)
  * [27] Mohiuddin, M.A., Khan, S.A., Engelbrecht, A.P.: Fuzzy particle swarm optimization algorithms for the open shortest path first weight setting problem. Applied Intelligence 45(3), 598–621 (Oct 2016). https://doi.org/10.1007/s10489-016-0776-0, http://link.springer.com/10.1007/s10489-016-0776-0
  * [28] Montazerolghaem, A., Yaghmaee, M.H.: Load-Balanced and QoS-Aware Software-Defined Internet of Things. IEEE Internet of Things Journal 7(4), 3323–3337 (Apr 2020). https://doi.org/10.1109/JIOT.2020.2967081, https://ieeexplore.ieee.org/document/8962313/
  * [29] Mulyana, E., Killat, U.: An Alternative Genetic Algorithm to Optimize OSPF Weights. Internet Traffic Engineering and Traffic Management pp. 186–192 (Jul 2002)
  * [30] Nagy, J., Oláh, J., Erdei, E., Máté, D., Popp, J.: The Role and Impact of Industry 4.0 and the Internet of Things on the Business Strategy of the Value Chain—The Case of Hungary. Sustainability 10(10), 3491 (Sep 2018). https://doi.org/10.3390/su10103491, http://www.mdpi.com/2071-1050/10/10/3491
  * [31] Németh, K., Kőrösi, A., Rétvári, G.: Optimal OSPF traffic engineering using legacy Equal Cost Multipath load balancing. In: 2013 IFIP Networking Conference. pp. 1–9 (2013)
  * [32] O’Halloran, C.: Dynamic adaptation of OSPF interface metrics based on network load. In: 2015 26th Irish Signals and Systems Conference (ISSC). pp. 1–6. IEEE, Carlow, Ireland (Jun 2015). https://doi.org/10.1109/ISSC.2015.7163767, http://ieeexplore.ieee.org/document/7163767/
  * [33] Paszkiewicz, A., Bolanowski, M., Budzik, G., Przeszłowski, L., Oleksy, M.: Process of Creating an Integrated Design and Manufacturing Environment as Part of the Structure of Industry 4.0. Processes 8(9), 1019 (Aug 2020). https://doi.org/10.3390/pr8091019, https://www.mdpi.com/2227-9717/8/9/1019
  * [34] Prasad, V.K., Bhavsar, M.D., Tanwar, S.: Influence of Montoring: Fog and Edge Computing. Scalable Computing: Practice and Experience 20(2), 365–376 (May 2019). https://doi.org/10.12694/scpe.v20i2.1533, https://www.scpe.org/index.php/scpe/article/view/1533
  * [35] Rego, A., Sendra, S., Jimenez, J.M., Lloret, J.: Dynamic metric OSPF-based routing protocol for Software Defined Networks. Cluster Computing 22(3), 705–720 (Sep 2019). https://doi.org/10.1007/s10586-018-2875-7, http://link.springer.com/10.1007/s10586-018-2875-7
  * [36] Smiler. S, K.: OpenFlow cookbook. Quick answers to common problems, Packt Publishing, Birmingham Mumbai, 1. publ edn. (2015)
  * [37] Styan, G.P.: Hadamard products and multivariate statistical analysis. Linear Algebra and its Applications 6, 217–240 (1973). https://doi.org/10.1016/0024-3795(73)90023-2, https://linkinghub.elsevier.com/retrieve/pii/0024379573900232
  * [38] Tran, A.K., Piran, M.J., Pham, C.: SDN Controller Placement in IoT Networks: An Optimized Submodularity-Based Approach. Sensors 19(24), 5474 (Dec 2019). https://doi.org/10.3390/s19245474, https://www.mdpi.com/1424-8220/19/24/5474
  * [39] Wang, H., Xu, H., Huang, L., Wang, J., Yang, X.: Load-balancing routing in software defined networks with multiple controllers. Computer Networks 141, 82–91 (Aug 2018). https://doi.org/10.1016/j.comnet.2018.05.012, https://linkinghub.elsevier.com/retrieve/pii/S1389128618302238


# HSVA: Hierarchical Semantic-Visual Adaptation for Zero-Shot Learning

Shiming Chen1, Guo-Sen Xie3, Yang Liu2, Qinmu Peng1, Baigui Sun2,
Hao Li2, Xinge You1, Ling Shao3
1Huazhong University of Science and Technology (HUST), China
2Alibaba Group, Hangzhou, China
3Inception Institute of Artificial Intelligence (IIAI), UAE
<EMAIL_ADDRESS><EMAIL_ADDRESS>Corresponding author

###### Abstract

Zero-shot learning (ZSL) tackles the unseen class recognition problem,
transferring semantic knowledge from seen classes to unseen ones. Typically,
to guarantee desirable knowledge transfer, a common (latent) space is adopted
for associating the visual and semantic domains in ZSL. However, existing
common space learning methods align the semantic and visual domains by merely
mitigating distribution disagreement through one-step adaptation. This
strategy is usually ineffective due to the heterogeneous nature of the feature
representations in the two domains, which intrinsically contain both
distribution and structure variations. To address this and advance ZSL, we
propose a novel hierarchical semantic-visual adaptation (HSVA) framework.
Specifically, HSVA aligns the semantic and visual domains by adopting a
hierarchical two-step adaptation, i.e., structure adaptation and distribution
adaptation. In the structure adaptation step, we take two task-specific
encoders to encode the source data (visual domain) and the target data
(semantic domain) into a structure-aligned common space. To this end, a
supervised adversarial discrepancy (SAD) module is proposed to adversarially
minimize the discrepancy between the predictions of two task-specific
classifiers, thus making the visual and semantic feature manifolds more
closely aligned. In the distribution adaptation step, we directly minimize the
Wasserstein distance between the latent multivariate Gaussian distributions to
align the visual and semantic distributions using a common encoder. Finally,
the structure and distribution adaptation are derived in a unified framework
under two partially-aligned variational autoencoders. Extensive experiments on
four benchmark datasets demonstrate that HSVA achieves superior performance on
both conventional and generalized ZSL. The code is available at
https://github.com/shiming-chen/HSVA .

##  1 Introduction

Over the past decade, significant progress has been made in zero-shot learning
(ZSL), which aims to recognize new classes during learning by exploiting the
intrinsic semantic relatedness between seen and unseen categories
Lampert2009LearningTD ; Larochelle2008ZerodataLO ; Palatucci2009ZeroshotLW .
Inspired by the way humans learn unknown concepts, side-information (e.g.,
attributes Lampert2014AttributeBasedCF , word vectors Mikolov2013DistributedRO
, and sentences Reed2016LearningDR ) related to seen/unseen classes is
employed to guarantee knowledge transfer between the seen/unseen data. Common
space learning is one typical method for representing the relationship between
the visual and semantic domains for ZSL, which is key to dealing with the
knowledge transfer Wang2017ZeroShotVR . However, existing common space
learning methods align the distributions of the semantic and visual domains
with one-step adaptation Zhang2016ZeroShotLV ; Tsai2017LearningRV ;
Wang2017ZeroShotVR ; Liu2018GeneralizedZL ; Schnfeld2019GeneralizedZA , while
neglecting the fact that the heterogeneous feature representations of distinct
semantic and visual domains have both distribution and structure variations.
Thus, their performance is limited. In this work, we propose a novel common
space learning formulation that leverages a hierarchical semantic-visual
adaptation to learn an intrinsic common space for a better alignment of the
two heterogeneous representation domains.

(a) One-step adaptation (b) Hierarchical adaptation

(c) t-SNE visualization of features for CADA-VAE (d) t-SNE visualization of
features for HSVA

Figure 1: Illustration of HSVA. Common space learning methods learn domain-
aligned feature representations for semantic and visual domains in latent
embedding space with semantic-visual adaptation. However, the heterogeneous
feature representations of the semantic and visual domains vary in both
distribution and structure. (a) One-step adaptation focuses on distribution
alignment between visual and semantic domains, neglecting structure variation.
This causes the semantic and visual distributions to be located in different
manifolds, resulting in the misclassification of some samples. (b)
Hierarchical adaptation, in contrast, can learn an intrinsic and
discriminative common space for semantic and visual feature representations by
adopting sequential structure adaptation and distribution adaptation. We
provide t-SNE visualizations Maaten2008VisualizingDU  of features learned by
(c) CADA-VAE Schnfeld2019GeneralizedZA  and (d) our HSVA on 10 classes from
AWA2 (the "o" and "x" indicate visual and semantic features, respectively, and
different colors denote different classes). Best viewed in color.

The heterogeneous feature representations of the semantic and visual domains
are distinct Li2019HeterogeneousTL ; Luo2019TransferringKF . Although one-step
adaptation learns distribution-aligned feature representations for the
semantic and visual domains using two different mapping models (e.g.,
encoders) and distribution alignment constraints (e.g., maximum mean
discrepancy (MMD)), the two distributions are located in different manifolds
since the one-step adaptation does not consider the manifold structure
relationship between visual and semantic representations, as shown in Figure 1
(a) and (c). If we take the Euclidean distance or manifold distance
Fu2018ZeroShotLO ; Fu2015ZeroshotOR  to measure the relationship between
different classes, the classifier inevitably misclassifies some samples, thus
leading to inferior ZSL performance. As such, mapping the semantic and visual
domains into an intrinsic and desirable common space for conducting an
effective ZSL is highly necessary.

To learn structure- and distribution-aligned feature representations for
distinct visual and semantic domains, we propose a hierarchical semantic-
visual adaptation (HSVA) framework to learn an intrinsic common space that
contains the essential multi-modal information associated with unseen classes
(Figure 1 (b) and (d)). HSVA aligns the semantic and visual domains with
structure adaptation (SA) and distribution adaptation (DA) in a unified
framework, under two partially-aligned variational autoencoders. In the SA, we
use two task-specific encoders to encode source data (visual domain) and
target data (semantic domain), respectively, into a structure-aligned space,
which is learned through supervised adversarial discrepancy (SAD) learning to
minimize the discrepancy between the predictions of the two task-specific
classifiers. This encourages the visual and semantic feature manifolds to be
closer to each other, thus aligning the manifold structure variation. In the
DA, we map the structure-aligned features into a distribution-aligned common
space using a common encoder, which is optimized by minimizing the Wasserstein
distance between the latent multivariate Gaussian distributions of the visual
and semantic domains. The common encoder preserves the structure-aligned
representations in the DA. Thus, HSVA can learn a structure and distribution-
aligned common space for visual and semantic feature representations, which is
better than the distribution-aligned feature representations learned by
existing common space learning methods Zhang2016ZeroShotLV ;
Tsai2017LearningRV ; Wang2017ZeroShotVR ; Liu2018GeneralizedZL ;
Schnfeld2019GeneralizedZA ; Yu2019ZeroshotLV . To the best of our knowledge,
this is the first work that leverages hierarchical semantic-visual adaptation
to address heterogeneous feature alignment in ZSL. Following
Schnfeld2019GeneralizedZA , we conduct extensive experiments on four
challenging benchmark datasets, i.e., CUB, SUN, AWA1, and AWA2, under both
conventional and generalized ZSL settings. The proposed HSVA achieves
consistent improvement over the existing common space learning methods on all
datasets. We show qualitatively that the structural variation is important for
the interaction between visual and semantic domains. Moreover, we show
significantly better common space for visual and semantic feature
representations than the existing common space learning methods, e.g., CADA-
VAE Schnfeld2019GeneralizedZA .

##  2 Related Work

Zero-Shot Learning. In practice, the relationship between visual and semantic
domains is determined by learning an embedding space where semantic vectors
and visual features interact Akata2016LabelEmbeddingFI ; Felix2018MultimodalCG
; Vyas2020LeveragingSA ; Huynh2020CompositionalZL ; Xie2019AttentiveRE ;
Xu2020AttributePN ; Chou2021Adaptive ; Yu2019ZeroshotLV . There are three
mapping methods for learning such an embedding space, including direct
mapping, model parameter transfer, and common space learning
Wang2017ZeroShotVR . Direct mapping learns a mapping function from visual
features to semantic representations Lampert2014AttributeBasedCF ;
Akata2016LabelEmbeddingFI ; Akata2015EvaluationOO . However, its
generalization is limited by the high intra-class variability of the visual
domain. Meanwhile, the lower-dimensional semantic space shrinks the variance
of the projected data points, resulting in the hubness problem
Li2019RethinkingZL . Model parameter transfer, in contrast, takes place in the
visual space, where the model parameters for unseen classes are usually
obtained Gan2015ExploringSI ; Changpinyo2016SynthesizedCF . In essence,
generative ZSL follows this methodology, simultaneously learning
semantic$\rightarrow$visual mapping and data augmentation Vyas2020LeveragingSA
; Xian2019FVAEGAND2AF ; Yu2020EpisodeBasedPG ; Vyas2020LeveragingSA ;
Chen2021FREE . However, since the inter-class relationships among unseen
classes are not taken into account, model parameter transfer is often limited
Wang2017ZeroShotVR . Finally, common space learning learns a common
representation space into which both visual features and semantic
representations are projected for effective knowledge transfer
Frome2013DeViSEAD ; Tsai2017LearningRV ; Wang2017ZeroShotVR ;
Liu2018GeneralizedZL ; Schnfeld2019GeneralizedZA . By calibrating the common
space using bidirectionally aligned knowledge of the visual and semantic
representations, it can simultaneously avoid the issues of direct mapping and
model parameter transfer. As such, common space learning is a promising
methodology for ZSL. However, existing common space learning methods align the
semantic and visual distributions with one-step adaptation, which neglects the
distinct heterogeneous feature representations of the semantic and visual
domains that are characterized by structure and distribution variations. This
causes the distribution-aligned common space to be located in a different
manifold, and samples to thus inevitably misclassified. In contrast, we
propose an effective framework with both structure adaptation and distribution
adaptation to address these challenges.

Domain Adaptation. Domain adaptation aims to learn domain-invariant
representations by minimizing the discrepancy between the distributions of
source and target via distribution alignment, domain adversarial learning, or
task-specific methods. It can be divided into homogeneous and heterogeneous
domain adaptation according to the characteristics of the source and target
data. In the homogeneous domain adaptation setting, the feature spaces of the
source and target domains are identical, with the same dimensions. Thus, one-
step adaptation can be employed Long2018ConditionalAD ; Saito2018MaximumCD ;
Lee2019SlicedWD . In contrast, in the heterogeneous setting, the feature
spaces of the source and target domains are distant, and their dimensions also
typically differ. Since there is little overlap between the two domains, one-
step domain adaptation is not effective in the heterogeneous domain adaptation
Tan2015TransitiveTL ; Tan2017DistantDT . Thus, multi-step (or transitive)
domain adaptation methods are used for heterogeneous domain adaptation.
However, these methods cannot be directly used in ZSL. Since ZSL has four
domains (i.e., seen, unseen, semantic, and visual), knowledge cannot be
transferred between two domains only, i.e., the distributions of the source
and target domains cannot be aligned. We argue that the structure variation
should also be taken into account when aligning the visual and semantic
domains in ZSL.

Figure 2: The framework of the proposed hierarchical semantic-visual
adaptation (HSVA) framework. HSVA consists of two partially-aligned
variational autoencoders, which simultaneously perform structure adaptation
and distribution adaptation with various constraints. Our two-step adaptation
formulation helps HSVA learn structure and distribution-aligned feature
representations for visual and semantic in an unified framework, which avoids
the adverse effects of heterogeneous feature representations between distinct
visual and semantic domains.

##  3 Hierarchical Semantic-Visual Adaptation

The task of ZSL is formulated as follows. Let $S=\\{(x^{s},y^{s},a^{s})\mid
x^{s}\in X,y^{s}\in Y^{s},a^{s}\in\mathcal{A}\\}$ be a training set consisting
of image features $x$ extracted by a convolutional neural network (CNN)
Backbone (e.g., ResNet-101), where seen class embeddings $a^{s}$ are learned
by a language model and seen class labels $y^{s}$. In addition, an auxiliary
training set $U=\\{(y^{u},a^{u})\mid y^{u}\in Y^{u}\\}$ from unseen classes is
used, where $y^{u}$ denotes unseen classes from a set $Y^{u}$, which is
disjoint from $Y^{S}$. $x^{u}\in X$ are the unseen visual features in the test
set. Note that $x=x^{s}\cup x^{u}$ and $a=a^{s}\cup a^{u}$. The goal of
conventional ZSL (CZSL) is to learn a classifier for unseen visual features,
i.e., $f_{CZSL}:X\rightarrow Y^{U}$, while for generalized ZSL (GZSL) the goal
is to learn a classifier for seen and unseen visual features, i.e.,
$f_{GZSL}:X\rightarrow Y^{U}\cup Y^{S}$.

In the following, we introduce our HSVA, which learns an intrinsic common
space for semantic and visual feature representations to conduct ZSL. As shown
in Figure 2, our framework consists of two partially-aligned autoencoders,
which conduct structure adaptation (SA) and distribution adaptation (DA). In
the end of this section, we demonstrate how we perform zero-shot learning
using the feature representations extracted from the intrinsic common manifold
space.

###  3.1 Partially-Aligned Variational Autoencoders

Our HSVA model consists of two partially-aligned variational autoencoders. The
first includes two feature encoders (visual encoder $E^{x}$ and common encoder
$E^{z}$) and one decoder (visual decoder $D^{x}$). $E^{x}$ and $E^{z}$ are
used to learn structure and distribution-aligned visual embeddings,
respectively, which share two common spaces (i.e., structure and distribution-
aligned spaces) with the semantic embeddings. $D^{x}$ aims to decode the
distribution-aligned embeddings from the visual and semantic features to be
similar to the visual features. Analogously, the second variational
autoencoder has a similar structure to the first (i.e., it includes a semantic
encoder $E^{a}$, the $E^{z}$, and a semantic decoder $D^{a}$), but it is
employed to learn semantic embeddings. The partially-aligned variational
autoencoders are first optimized by two variational autoencoders (VAE) losses:

$\displaystyle\mathcal{L}_{VAE}^{x}(E^{x},E^{z})=\mathbb{E}[\log
D^{x}(z^{x^{s}})]-\gamma\mathrm{KL}(E^{z}(E^{x}(x^{s})))\|p(z^{x^{s}}|x^{s})),$
(1) $\displaystyle\mathcal{L}_{VAE}^{a}(E^{a},E^{z})=\mathbb{E}[\log
D^{a}(z^{a^{s}})]-\gamma\mathrm{KL}(E^{z}(E^{a}(a^{s})))\|p(z^{a^{s}}|a^{s})),$
(2)

where $z^{x^{s}}$ and $z^{a^{s}}$ are the visual and semantic embeddings in
the distribution-aligned space, $\gamma$ is the weight of the KL-divergence,
and $p(z^{a^{s}}|a^{s})$ and $p(z^{x^{s}}|x^{s})$ are the prior distributions
assumed to be $\mathcal{N}(0,1)$. To make the visual and semantic embeddings
in the structure- and distribution-aligned spaces more consistent, we then use
a cross reconstruction loss to constrain the two partially-aligned variational
autoencoders:

$\displaystyle\mathcal{L}_{REC}(E^{x},E^{a},E^{z},D^{x},D^{a})=\mathcal{L}_{REC}^{x}(E^{x},E^{z},D^{x})+\mathcal{L}_{REC}^{a}(E^{a},E^{z},D^{a})$
(3)

where

$\displaystyle\mathcal{L}_{REC}^{x}(E^{x},E^{z},D^{x})=\left\|x^{s}-D^{x}(z^{a^{s}})\right\|_{1},$
(4)
$\displaystyle\mathcal{L}_{REC}^{a}(E^{a},E^{z},D^{a})=\left\|a^{s}-D^{a}(z^{x^{s}})\right\|_{1}.$
(5)

Finally, the two partially-aligned variational autoencoders conduct structure
and distribution adaptation for the visual and semantic features, which will
be introduced in the following.

###  3.2 Structure Adaptation

Structure adaptation (SA) is used to guide the encoder $E^{x}$ and $E^{a}$ to
learn a structure-aligned space for the visual and semantic features. Previous
methods Wang2017ZeroShotVR ; Schnfeld2019GeneralizedZA  directly align the
semantic and visual features with distribution distance constraints (e.g.,
MMD), which neglects the structure variation between the heterogeneous feature
representations of the two domains. Furthermore, these methods fail to learn
discriminative features as they do not take category relationships into
account, as shown in Figure 1 (a). Motivated by task-specific unsupervised
domain adaptation Saito2018MaximumCD ; Lee2019SlicedWD , we propose a
supervised adversarial discrepancy (SAD) module to minimize the discrepancy
between the outputs of two task-specific classifiers ($CLS^{1}$, $CLS^{2}$).
This enables us to learn a class decision boundary and embed semantic and
visual features into a structure-aligned common space for SA. Thus, SA can
learn discriminative structure-aligned representations for semantic and visual
features. Different from Saito2018MaximumCD ; Lee2019SlicedWD , which only
detect the target samples (e.g., semantic embeddings $E^{a}(a)$) to learn a
single encoder (generator), SAD simultaneously detects the source samples
(e.g., visual embeddings $E^{x}(x)$) and target samples (e.g., semantic
embeddings $E^{a}(a)$) to learn a good structure-aligned common space with two
task-specific encoders. Specifically, SAD includes three steps for
optimization: 1) semantic and visual embedding classification for $E^{x}$,
$E^{a}$, $CLS^{1}$ and $CLS^{2}$; 2) discrepancy maximization for $CLS^{1}$
and $CLS^{2}$; and 3) discrepancy minimization for $E^{x}$ and $E^{a}$.

Semantic and Visual Embedding Classification. We train $E^{x}$, $E^{a}$,
$CLS^{1}$ and $CLS^{2}$ by minimizing the softmax cross-entropy to collectly
classify the structure-aligned semantic and visual embeddings. This is crucial
for enabling classifiers and encoders ($E^{x}$, $E^{a}$) to obtain task-
specific discriminative features. The visual and semantic classification loss
is formulated as:

$\displaystyle\begin{aligned}
\mathcal{L}_{CLS}(E^{x},E^{a},CLS^{1},CLS^{2})&=\mathcal{L}_{CLS^{1}}(E^{x}(x^{s}),y^{s})+\mathcal{L}_{CLS^{2}}(E^{x}(x^{s}),y^{s})\\\
&+\mathcal{L}_{CLS^{1}}(E^{a}(a^{s}),y^{s})+\mathcal{L}_{CLS^{2}}(E^{a}(a^{s}),y^{s}),\end{aligned}$
(6)

where

$\displaystyle\mathcal{L}_{CLS^{1}}(\mathbf{x},\mathbf{y})=\mathcal{L}_{CLS^{2}}(\mathbf{x},\mathbf{y})=-\mathbb{E}\sum_{k=1}^{K}\mathbb{I}_{\left[k=\mathbf{y}\right]}\log
p\left(y\mid\mathbf{x}\right).$ (7)

Here K is the number of seen classes, $\mathbb{I}_{\left[k=\mathbf{y}\right]}$
is an indicator function (i.e., it is one when $k=\mathbf{y}$, otherwise
zero), and $p\left(y|\mathbf{x}\right)$ is the prediction of $\mathbf{x}$. We
use two classifiers to simultaneously classify the visual and semantic
embeddings to initialize the classifiers, which are used for discrepancy
learning later.

Discrepancy Maximization for Classifiers. In this step, we freeze the
parameters of the encoders ($E^{x}$, $E^{a}$) and update the classifiers
($CLS^{1}$, $CLS^{2}$) to maximize the discrepancy between the outputs of the
two classifiers on the visual and semantic embeddings. Thus, the source and
target samples outside the support of task-specific decisions are identified,
providing the positive signals to separate the class decision boundaries.
Since sliced Wasserstein discrepancy (SWD) Lee2019SlicedWD  provides
geometrically meaningful guidance for capturing the natural notion of
dissimilarity, we use it to measure the discrepancy between two classifier
predictions for visual embeddings ($p_{1}(y^{s}|E^{x}(x^{s}))$,
$p_{2}(y^{s}|E^{x}(x^{s}))$) and semantic embeddings
($p_{1}(y^{s}|E^{a}(a^{s}))$, $p_{2}(y^{s}|E^{a}(a^{s}))$):

$\displaystyle\mathcal{L}_{DIS^{1}}(CLS^{1},CLS^{2})=-\mathcal{L}_{SWD}(E^{x}(x^{s}))-\mathcal{L}_{SWD}(E^{a}(a^{s})),$
(8)
$\displaystyle\mathcal{L}_{SWD}\left(\mathbf{x}\right)=\sum_{m}\left(\mathcal{R}_{\theta_{m}}p_{1}(y|\mathbf{x}),\mathcal{R}_{\theta_{m}}p_{2}(y|\mathbf{x})\right),$
(9)

where $\mathcal{R}_{\theta_{m}}$ is the $m$th one-dimensional linear
projection operation, and $\theta$ is a uniform measure on the unit sphere
$S^{(d-1)}$ in $\mathbb{R}^{d}$. The larger the $\mathcal{L}_{DIS}$, the
larger the discrepancy.

Discrepancy Minimization for Encoders. To encourage the visual embedding
($E^{x}(x^{s})$) and semantic embedding ($E^{a}(a^{s})$) to be aligned well in
the structure-aligned space, we freeze the parameters of the two classifiers
and update the two encoders ($E^{x}$, $E^{a}$) to minimize the discrepancy
between the outputs of the two classifiers on $E^{x}(x^{s})$ and
$E^{a}(a^{s})$:

$\displaystyle\mathcal{L}_{DIS^{2}}(E^{x},E^{a})=\mathcal{L}_{SWD}(E^{x}(x^{s}))+\mathcal{L}_{SWD}(E^{a}(a^{s})).$
(10)

This encourages the visual and semantic feature manifolds to be closer to each
other, and thus the manifold structure variation is circumvented.

###  3.3 Distribution Adaptation

After structure adaptation, HSVA can learn a structure-aligned common space to
avoid manifold structure difference between visual and semantic embeddings.
However, the structure-aligned common space is still limited by distribution
variation. To further learn a distribution-aligned common space for visual and
semantic feature representations, we propose distribution adaptation. Existing
common space learning methods Zhang2016ZeroShotLV ; Tsai2017LearningRV ;
Wang2017ZeroShotVR ; Liu2018GeneralizedZL ; Schnfeld2019GeneralizedZA  employ
two different mapping functions (encoders) to align the visual and semantic
distributions to learn distribution-aligned embedding. In contrast, our main
idea is to protect the structure-aligned visual and semantic embeddings in a
distribution-aligned space using a common encoder $E^{z}$, which preserves the
structure-aligned representations in the DA. Our DA is first optimized by
minimizing the Wasserstein distance between the latent multivariate Gaussian
distributions, formulated as follows:

$\displaystyle\mathcal{L}_{DA}(E^{x},E^{a},E^{z})=\left(\left\|\mu^{x^{s}}-\mu^{a^{s}}\right\|_{2}^{2}+\left\|(\delta^{x^{s}})^{\frac{1}{2}}-(\delta^{a^{s}})^{\frac{1}{2}}\right\|_{\text{F}}^{2}\right)^{\frac{1}{2}},$
(11)

where $\|\cdot\|_{F}^{2}$ denotes the squared matrix Frobenius norm.

In essence, our HSVA is also a generative model, which is different to the
GAN/VAE based methods Narayan2020LatentEF ; Xian2019FVAEGAND2AF ; Chen2021FREE
(i.e., learning mechanism and optimization). Due to the bias problem that
arises when using generative models for ZSL, the synthesized unseen samples
($E^{z}(E^{a}(a^{u}))$) in the distribution-aligned common space might be
unexpectedly close to the seen ones. We propose to explicitly tackle this
seen-unseen bias problem by preventing the encoded unseen samples
($E^{z}(E^{a}(a^{u}))$) from colliding with the encoded seen ones
($E^{z}(E^{x}(x^{s}))$)111Since $E^{z}(E^{x}(x^{s}))$ and
$E^{z}(E^{a}(a^{u}))$ are used to train a ZSL classifier later, we take the
visual features of seen classes and semantic features of unseen classes into
account.. Since correlation alignment (CORAL) Sun2016ReturnOF  has been shown
effective for asymmetric transformations in domain adaptation, we take the
CORAL-based metric to measure the discrepancy between seen and unseen class
samples. Different from Sun2016ReturnOF , which takes CORAL to decrease the
discrepancy between two domains, we aim to increase the discrepancy. Hence, we
employ the inverse CORAL (iCORAL), defined upon the numerical negation of
CORAL:

$\displaystyle\mathcal{L}_{iCORAL}(E^{x},E^{a},E^{z})=-CORAL(E^{z}(E^{x}(x^{s})),E^{z}(E^{a}(a^{u}))).$
(12)

###  3.4 Optimization

Our full model optimizes the partially-aligned variational autoencoders, DA
and SA, simultaneously with the following objective function:

$\displaystyle\begin{aligned}
\mathcal{L}_{HSVA}(E^{x},E^{a},CLS^{1},CLS^{2},E^{z},D^{x},D^{a})&=\mathcal{L}_{VAE}^{x}+\mathcal{L}_{VAE}^{a}+\lambda_{1}\mathcal{L}_{REC}+\mathcal{L}_{CLS}\\\
&+\lambda_{2}(\mathcal{L}_{DIS^{1}}+\mathcal{L}_{DIS^{2}})+\lambda_{3}(\mathcal{L}_{iCORAL}+\mathcal{L}_{DA}),\end{aligned}$
(13)

where $\lambda_{1}$, $\lambda_{2}$, $\lambda_{3}$ are the weights that control
the importance of the related loss terms. Similar to the alternative updating
policy for generative adversarial networks (GANs), we alternately train
$E^{x}$, $E^{a}$, $CLS^{1}$, $CLS^{2}$ when optimizing SA. Although, HSVA has
three components in total, the whole training process are simultaneous and
loss weights of all terms in Eq. 13 are the same for all datasets. The
consistently significant results on all datasets show that our model is robust
and easy to train.

###  3.5 Classification

Once our HSVA model is learned, the visual and semantic features are encoded
as new feature representations in a distribution-aligned common space, where
structure variation is aslo considered for classification. Using the
reparametrization trick Kingma2014AutoEncodingVB , we take $E^{x}$ and $E^{z}$
to encode the visual features of seen classes ($x^{s}$) and unseen classes
($x^{u}$) into structure- and distribution-aligned feature representations,
i.e., $z^{x^{s}}=E^{z}(E^{x}(x^{s}))$ and $z^{x^{u}}=E^{z}(E^{x}(x^{u}))$.
Analogously, we take $E^{a}$ and $E^{z}$ to encode the semantic embeddings $a$
as $z^{a}=E^{z}(E^{a}(a))$, where $z^{a}=z^{a^{s}}\cup z^{a^{u}}$. We employ
$z^{x^{s}}$ ($x^{s}$ from the training set) and $z^{a^{u}}$ to train a
supervised classifier (e.g., softmax). Once the classifier is trained, we use
$z^{x^{s}}$ ($x^{s}$ from the test set) and $z^{x^{u}}$ to test the model.
Note that our HSVA is an inductive method as we do not use the visual features
of unseen classes for training.

##  4 Experiments

Datasets. We conduct extensive experiments on four well-known ZSL benchmark
datasets, including fine-grained datasets (e.g., CUB Welinder2010CaltechUCSDB2
and SUN Patterson2012SUNAD ) and coarse-grained datasets (e.g., AWA1
Lampert2014AttributeBasedCF  and AWA2 Xian2017ZeroShotLC ). CUB includes
11,788 images of 200 bird classes (seen/unseen classes = 150/50) with 312
attributes. SUN contains 14,340 images from 717 scene classes (seen/unseen
classes = 645/72) with 102 attributes. AWA1 and AWA2 contain 30,475 and 37,322
images from 50 animal classes (seen/unseen classes = 40/10) with 85
attributes.

Implementation Details. We use the training splits proposed in
Xian2018FeatureGN . Meanwhile, the visual features are extracted from the
2048-dimensional top-layer pooling units of a CNN backbone (i.e., ResNet-101)
pre-trained on ImageNet. The encoders and decoders are multilayer perceptrons
(MLPs). We employ the Adam optimizer Kingma2015AdamAM  with $\beta_{1}$ = 0.5
and $\beta_{2}$ = 0.999. We use an annealing scheme Bowman2016GeneratingSF  to
increase the weights $\gamma$, $\lambda_{1}$, $\lambda_{2}$, $\lambda_{3}$
with same setting for all datasets. Specifically, $\gamma$ is increased by a
rate of 0.0026 per epoch until epoch 90, $\lambda_{1}$ is increased from epoch
21 to 75 by 0.044 per epoch, and $\lambda_{2}$, $\lambda_{3}$ are increased
from epoch 0 to epoch 22 by a rate of 0.54 per epoch. In the CZSL setting, we
synthesize 800, 400 and 200 features per unseen class to train the classifier
for AWA1, CUB and SUN datasets, respectively. In the GZSL setting, we take 400
synthesized features per unseen class and 200 synthesized features per seen
class to train the classifier for all datasets. The dimensions of the
structure-aligned and distribution-aligned spaces are set to 2048 and 64 for
three datasets (i.e., CUB, AWA1, AWA2), respectively, and 2048 and 128 for SUN
benchmark.

Evaluation Protocols. During testing, we follow the unified evaluation
protocols proposed in Xian2017ZeroShotLC . Specifically, we measure the top-1
accuracy of unseen class (Acc) for the CZSL setting. In the GZSL setting, we
take the top-1 accuracy on seen classes (S) and unseen classes (U), as well as
their harmonic mean (defined as $H=(2\times S\times U)/(S+U)$).

Method | AWA1 | CUB | SUN
---|---|---|---
Acc | Acc | Acc
DeViSE(NeurIPS’13) Frome2013DeViSEAD  | 54.2 | 52.0 | 56.5
DCN(NeurIPS’18) Liu2018GeneralizedZL  | 65.3 | 56.2 | 61.8
CADA-VAE(CVPR’19) Schnfeld2019GeneralizedZA  | 63.0 | 59.8 | 61.7
Our HSVA | 70.6 | 62.8 | 63.8

Table 1: Results of common space learning methods under the CZSL setting on
three datasets.

###  4.1 Experimental Results

Results of Conventional Zero-Shot Learning. Table 1 presents the results of
CZSL on various datasets. Our HSVA, with a softmax classifier, significantly
outperforms other common space learning methods Frome2013DeViSEAD ;
Liu2018GeneralizedZL ; Schnfeld2019GeneralizedZA  by at least 5.3%, 3.0% and
2.0% on AWA1, CUB and SUN, respectively. Our significant performance
improvements demonstrate that hierarchical semantic-visual adaptation can
effectively learn an intrinsic common space to represent visual and semantic
features. This space is structure- and distribution-aligned and alleviates the
gap between heterogeneous feature representations.

| Method | AWA1 | AWA2 | CUB | SUN
---|---|---|---|---|---
| ${U}$ | ${S}$ | ${H}$ | ${U}$ | ${S}$ | ${H}$ | ${U}$ | ${S}$ | ${H}$ | ${U}$ | ${S}$ | ${H}$
Non-common space | CRnet(ICML’19) Zhang2019CoRepresentationNF  | 58.1 | 74.7 | 65.4 | - | - | - | 45.5 | 56.8 | 50.5 | 34.1 | 36.5 | 35.3
PQZSL(CVPR’19) Li2019CompressingUI  | - | - | - | 31.7 | 70.9 | 43.8 | 43.2 | 51.4 | 46.9 | 35.1 | 35.3 | 35.2
TCN(ICCV’19) Jiang2019TransferableCN  | 49.4 | 76.5 | 60.0 | 61.2 | 65.8 | 63.4 | 52.6 | 52.0 | 52.3 | 31.2 | 37.3 | 34.0
SGMA(NeurIPS’19) Zhu2019SemanticGuidedML  | 37.6 | 87.1 | 52.5 | - | - | - | 36.7 | 71.3 | 48.5 | - | - | -
DVBE(CVPR’20) Min2020DomainAwareVB  | - | - | - | 63.6 | 70.8 | 67.0 | 53.2 | 60.2 | 56.5 | 45.0 | 37.2 | 40.7
DAZLE(CVPR’20) Huynh2020FineGrainedGZ  | - | - | - | 60.3 | 75.7 | 67.1 | 59.6 | 56.7 | 58.1 | 52.3 | 24.3 | 33.2
RGEN(ECCV’20) Xie2020RegionGE  | - | - | - | 67.1 | 76.5 | 71.5 | 60.0 | 73.5 | 66.1 | 44.0 | 31.7 | 36.8
Composer(NeurIPS’20) Huynh2020CompositionalZL  | - | - | - | 62.1 | 77.3 | 68.8 | 63.8 | 56.4 | 59.9 | 55.1 | 22.0 | 31.4
APN(NeurIPS’20) Xu2020AttributePN  | - | - | - | 56.5 | 78.0 | 65.5 | 65.3 | 69.3 | 67.2 | 41.9 | 34.0 | 37.6
f-CLSWGAN(CVPR’18) Xian2018FeatureGN  | 57.9 | 61.4 | 59.6 | - | - | - | 43.7 | 57.7 | 49.7 | 42.6 | 36.6 | 39.4
f-VAEGAN(CVPR’19) Xian2019FVAEGAND2AF  | - | - | - | 57.6 | 70.6 | 63.5 | 48.4 | 60.1 | 53.6 | 45.1 | 38.0 | 41.3
LisGAN(CVPR’19) Li2019LeveragingTI  | 52.6 | 76.3 | 62.3 | - | - | - | 46.5 | 57.9 | 51.6 | 42.9 | 37.8 | 40.2
LsrGAN(ECCV’20) Vyas2020LeveragingSA  | 54.6 | 74.6 | 63.0 | - | - | - | 48.1 | 59.1 | 53.0 | 44.8 | 37.7 | 40.9
AGZSL(ICLR’21) Chou2021Adaptive  | - | - | - | 65.1 | 78.9 | 71.3 | 41.4 | 49.7 | 45.2 | 29.9 | 40.2 | 34.3
Common space | DeViSE(NeurIPS’13) Frome2013DeViSEAD  | 13.4 | 68.7 | 22.4 | 17.1 | 74.7 | 27.8 | 23.8 | 53.0 | 32.8 | 16.9 | 27.4 | 20.9
ReViSE(ICCV’17) Tsai2017LearningRV  | 46.1 | 37.1 | 41.1 | 46.4 | 39.7 | 42.8 | 37.6 | 28.3 | 32.3 | 24.3 | 20.1 | 22.0
DCN(NeurIPS’18) Liu2018GeneralizedZL  | 25.5 | 84.2 | 39.1 | - | - | - | 28.4 | 60.7 | 38.7 | 25.5 | 37.0 | 30.2
CADA-VAE(CVPR’19) Schnfeld2019GeneralizedZA  | 57.3 | 72.8 | 64.1 | 55.8 | 75.0 | 63.9 | 51.6 | 53.5 | 52.4 | 47.2 | 35.7 | 40.6
SGAL(NeurIPS’19) Yu2019ZeroshotLV  | 52.7 | 74.0 | 61.5 | 52.5 | 86.3 | 65.3 | 40.9 | 55.3 | 47.0 | 35.5 | 34.4 | 34.9
Our HSVA | 59.3 | 76.6 | 66.8 | 56.7 | 79.8 | 66.3 | 52.7 | 58.3 | 55.3 | 48.6 | 39.0 | 43.3

Table 2: State-of-the-art comparison under the GZSL setting on four datasets.
The best and second-best results are marked in red and blue, respectively. The
"Common space" and "Non-common space" denote common space learning and non-
common space learning methods, respectively. Meanwhile, the non-common space
learning methods include the non-generative methods and generative methods.

Method | AWA1 | AWA2 | CUB | SUN
---|---|---|---|---
${U}$ | ${S}$ | ${H}$ | ${U}$ | ${S}$ | ${H}$ | ${U}$ | ${S}$ | ${H}$ | ${U}$ | ${S}$ | ${H}$
HSVA w/o $\mathcal{L}_{SA}$ | 55.2 | 71.5 | 62.3 | 53.9 | 77.2 | 63.5 | 49.3 | 57.9 | 53.2 | 49.7 | 37.2 | 42.6
HSVA w/o $\mathcal{L}_{DA}$ and $\mathcal{L}_{iCORAL}$ | 31.3 | 70.6 | 43.4 | 26.3 | 78.4 | 39.3 | 41.9 | 56.1 | 47.9 | 42.2 | 35.5 | 38.6
HSVA w/o $\mathcal{L}_{iCORAL}$ | 54.3 | 73.5 | 62.4 | 51.3 | 82.6 | 63.3 | 51.1 | 57.0 | 53.9 | 45.1 | 38.9 | 41.8
HSVA (full) | 59.3 | 76.6 | 66.8 | 56.7 | 79.8 | 66.3 | 52.7 | 58.3 | 55.3 | 48.6 | 39.0 | 43.3

Table 3: Ablation study of HSVA under the GZSL setting on four datasets. "HSVA
w/o $\mathcal{L}_{SA}$" denotes HSVA without the constraints in SA, "HSVA w/o
$\mathcal{L}_{DA}$ and $\mathcal{L}_{iCORAL}$" denotes HSVA without the
constraints in DA, "HSVA w/o $\mathcal{L}_{iCORAL}$" denotes HSVA without
$\mathcal{L}_{iCORAL}$, and "HSVA (full)" denotes our full model HSVA.

(a) CUB

(b) AWA1

Figure 3: t-SNE visualization Maaten2008VisualizingDU  of visual/semantic
features learned by our HSVA and CADA-VAE Schnfeld2019GeneralizedZA  for the
same seen and unseen classes. Different colors denote different classes. The
"o" and "x" indicate visual and semantic features, respectively. We conduct
experiments on 10 classes of (a) CUB and (b) AWA1. CADA-VAE clearly maps the
visual and semantic features into various manifolds focusing on distribution
alignment, while HSVA learns an intrinsic common space for discriminative
feature representations by adopting sequential structure and distribution
adaptation.

Results of Generalized Zero-Shot Learning. Table 2 shows the GZSL performances
of various methods, including non-generative methods (direct mapping and model
parameter transfer), generative methods, and common space learning methods.
Compared to other common space learning models Frome2013DeViSEAD ;
Tsai2017LearningRV ; Liu2018GeneralizedZL ; Schnfeld2019GeneralizedZA ;
Yu2019ZeroshotLV , our HSVA achieves significant improvements of at least
2.7%, 1.0%, 2.9% and 2.7% in harmonic mean on AWA1, AWA2, CUB and SUN,
respectively. Especially, our HSVA outperforms the latest common space
learning method (i.e., SGAL Yu2019ZeroshotLV ) by a large margin, resulting in
harmonic mean improvements of 5.3%, 1.0%, 8.3% and 8.4% on AWA1, AWA2, CUB and
SUN, respectively. Since our method can also act as a generative method, we
compare it with other state-of-the-art generative methods. The results show
that our method performs significantly better on AWA1, CUB and SUN datasets.
Our model also achieves competitive results compared to non-generative
methods. For example, HSVA performs best results (e.g., the harmonic mean of
43.3) on SUN that is the most challenging benchmark in ZSL. These results
consistently demonstrate the superiority and great potential of hierarchical
semantic-visual adaptation.

Ablation Study. We conduct ablation studies to evaluate the effectiveness of
our HSVA in terms of the structure adaptation constraints (denoted as
$\mathcal{L}_{SA}$), distribution adaptation constraints (i.e.,
$\mathcal{L}_{DA}+\mathcal{L}_{iCORAL}$), and only inverse CORAL
$\mathcal{L}_{iCORAL}$. Our results are shown in Table 3. HSVA performs poorer
than its full model when no constraints are used during structure adaptation,
i.e., the harmonic mean drops by 4.5% on AWA1 and 2.1% on CUB. If constraints
are not used during distribution adaptation, HSVA achieves very poor results
compared to its full model, i.e., the harmonic mean drops by more than 23.4%
on coarse-grained datasets and 4.7% on fine-grained datasets. These results
show that distribution alignment is essential for common space learning, while
structure adaptation is necessary for semantic-visual adaptation. This is
typically neglected by distribution alignment methods with one-step adaptation
Zhang2016ZeroShotLV ; Tsai2017LearningRV ; Wang2017ZeroShotVR ;
Liu2018GeneralizedZL ; Schnfeld2019GeneralizedZA ; Yu2019ZeroshotLV .
Moreover, $\mathcal{L}_{iCORAL}$ pushes unseen classes away from seen classes,
which explicitly tackles the seen-unseen bias problem. HSVA cooperates with
iCORAL to improve the accuracy of classification using softmax, achieving
harmonic mean improvement of 4.4%, 3.0%, 1.4%, and 1.5% on AWA1, AWA2, CUB,
and SUN, respectively.

Qualitative Results. We first qualitatively investigate the difference between
our HSVA and one-step adaptation methods (e.g., CADA-VAE
Schnfeld2019GeneralizedZA ) for common space learning. We conduct t-SNE
visualization Maaten2008VisualizingDU  of visual/semantic features mapped by
our HSVA and CADA-VAE on 10 classes from (a) CUB and (b) AWA1. As shown in
Figure 3, CADA-VAE maps semantic and visual features into different manifolds,
which confuses the visual and semantic features of various categories,
resulting in misclassification for some samples. This intuitively shows that
the existing common space learning methods neglect the different structures of
the heterogeneous feature representations in the visual and semantic domains.
In contrast, HSVA learns an intrinsic common space that better bridges the gap
between the heterogeneous feature representations for effective knowledge
transfer, using structure and distribution adaptation. Thus, hierarchical
semantic-visual adaptation is an effective solution for common space learning
in ZSL.

In addition, unlike other methods Zhang2016ZeroShotLV ; Tsai2017LearningRV ;
Wang2017ZeroShotVR ; Liu2018GeneralizedZL ; Schnfeld2019GeneralizedZA  that
can only align visual and semantic distributions, our HSVA can take class
relationships into account to learn discriminatively aligned feature
representations. As shown in Figure 3, CADA-VAE maps visual and semantic
features into compact manifolds, resulting in confused class relationships. In
contrast, HSVA learns discriminative structure- and distribution-aligned
features for the visual and semantic feature representations, which enables
HSVA to achieve better ZSL classification.

##  5 Conclusion

In this work, we develop a zero-shot learning framework, i.e. hierarchical
semantic-visual adaptation (HSVA), to learn an intrinsic common space for
visual and semantic feature representations. By conducting structure and
distribution adaptation using two partially-aligned variational autoencoders,
our model effectively tackles the problem of heterogeneous feature
representations and bridges the gap between the visual and semantic domains.
We demonstrate that HSVA achieves consistent improvement over the current
state-of-the-art methods on four ZSL benchmarks. We qualitatively verify that
our hierarchical semantic-visual adaptation framework can align the visual and
semantic domains in terms of both structure and distribution, while other
common space learning methods only take distribution alignment into account.
This intuitively shows that the learned feature representations of HSVA are
more discriminative and accurate than other methods. To the best of our
knowledge, we are the first to investigate the different structural
characteristics of the visual and semantic domains in ZSL. We believe that our
work will facilitate the development of stronger visual-and-language learning
systems, including zero-shot learning, visual question answering
Antol2015VQAVQ , image captioning Herdade2019ImageCT , natural language for
visual reasoning Li2020OscarOA , heterogeneous domain adaptation
Li2020SimultaneousSA .

## References

  * (1) C. H. Lampert, H. Nickisch, and S. Harmeling, “Learning to detect unseen object classes by between-class attribute transfer,” in _CVPR_ , 2009, pp. 951–958.
  * (2) H. Larochelle, D. Erhan, and Y. Bengio, “Zero-data learning of new tasks,” in _AAAI_ , 2008, pp. 646–651.
  * (3) M. Palatucci, D. Pomerleau, G. E. Hinton, and T. M. Mitchell, “Zero-shot learning with semantic output codes,” in _NeurIPS_ , 2009, pp. 1410–1418.
  * (4) C. H. Lampert, H. Nickisch, and S. Harmeling, “Attribute-based classification for zero-shot visual object categorization,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 36, pp. 453–465, 2014.
  * (5) T. Mikolov, I. Sutskever, K. Chen, G. S. Corrado, and J. Dean, “Distributed representations of words and phrases and their compositionality,” in _NeurIPS_ , 2013, pp. 3111–3119.
  * (6) S. Reed, Z. Akata, H. Lee, and B. Schiele, “Learning deep representations of fine-grained visual descriptions,” in _CVPR_ , 2016, pp. 49–58.
  * (7) Q. Wang and K. Chen, “Zero-shot visual recognition via bidirectional latent embedding,” _International Journal of Computer Vision_ , vol. 124, pp. 356–383, 2017.
  * (8) Z. Zhang and V. Saligrama, “Zero-shot learning via joint latent similarity embedding,” in _CVPR_ , 2016, pp. 6034–6042.
  * (9) Y.-H. H. Tsai, L.-K. Huang, and R. Salakhutdinov, “Learning robust visual-semantic embeddings,” in _ICCV_ , 2017, pp. 3591–3600.
  * (10) S. Liu, M. Long, J. Wang, and M. I. Jordan, “Generalized zero-shot learning with deep calibration network,” in _NeurIPS_ , 2018.
  * (11) E. Schönfeld, S. Ebrahimi, S. Sinha, T. Darrell, and Z. Akata, “Generalized zero- and few-shot learning via aligned variational autoencoders,” in _CVPR_ , 2019, pp. 8239–8247.
  * (12) L. V. D. Maaten and G. E. Hinton, “Visualizing data using t-sne,” _Journal of Machine Learning Research_ , vol. 9, pp. 2579–2605, 2008.
  * (13) H. Li, S. J. Pan, R. Wan, and A. Kot, “Heterogeneous transfer learning via deep matrix completion with adversarial kernel embedding,” in _AAAI_ , 2019\.
  * (14) Y. Luo, Y. Wen, T. Liu, and D. Tao, “Transferring knowledge fragments for learning distance metric from a heterogeneous domain,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 41, pp. 1013–1026, 2019.
  * (15) Z. Fu, T. Xiang, E. Kodirov, and S. Gong, “Zero-shot learning on semantic class prototype graph,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 40, pp. 2009–2022, 2018.
  * (16) Z. Fu, E. Kodirov, T. Xiang, and S. Gong, “Zero-shot object recognition by semantic manifold distance,” in _CVPR_ , 2015, pp. 2635–2644.
  * (17) H. Yu and B. Lee, “Zero-shot learning via simultaneous generating and learning,” in _NeurIPS_ , 2019.
  * (18) Z. Akata, F. Perronnin, Z. Harchaoui, and C. Schmid, “Label-embedding for image classification,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 38, pp. 1425–1438, 2016.
  * (19) R. Felix, B. V. Kumar, I. Reid, and G. Carneiro, “Multi-modal cycle-consistent generalized zero-shot learning,” in _ECCV_ , 2018.
  * (20) M. R. Vyas, H. Venkateswara, and S. Panchanathan, “Leveraging seen and unseen semantic relationships for generative zero-shot learning,” in _ECCV_ , 2020\.
  * (21) D. T. Huynh and E. Elhamifar, “Compositional zero-shot learning via fine-grained dense feature composition,” in _NeurIPS_ , 2020.
  * (22) G.-S. Xie, L. Liu, X. Jin, F. Zhu, Z. Zhang, J. Qin, Y. Yao, and L. Shao, “Attentive region embedding network for zero-shot learning,” in _CVPR_ , 2019, pp. 9376–9385.
  * (23) W. Xu, Y. Xian, J. Wang, B. Schiele, and Z. Akata, “Attribute prototype network for zero-shot learning,” in _NeurIPS_ , 2020.
  * (24) T.-L. L. Yu-Ying Chou, Hsuan-Tien Lin, “Adaptive and generative zero-shot learning,” in _ICLR_ , 2021.
  * (25) Z. Akata, S. Reed, D. Walter, H. Lee, and B. Schiele, “Evaluation of output embeddings for fine-grained image classification,” in _CVPR_ , 2015, pp. 2927–2936.
  * (26) K. Li, M. R. Min, and Y. Fu, “Rethinking zero-shot learning: A conditional visual classification perspective,” in _ICCV_ , 2019, pp. 3582–3591.
  * (27) C. Gan, M. Lin, Y. Yang, Y. Zhuang, and A. Hauptmann, “Exploring semantic inter-class relationships (sir) for zero-shot action recognition,” in _AAAI_ , 2015.
  * (28) S. Changpinyo, W.-L. Chao, B. Gong, and F. Sha, “Synthesized classifiers for zero-shot learning,” in _CVPR_ , 2016, pp. 5327–5336.
  * (29) Y. Xian, S. Sharma, B. Schiele, and Z. Akata, “F-vaegan-d2: A feature generating framework for any-shot learning,” in _CVPR_ , 2019, pp. 10 267–10 276.
  * (30) Y. Yu, Z. Ji, J. Han, and Z. Zhang, “Episode-based prototype generating network for zero-shot learning,” in _CVPR_ , 2020, pp. 14 032–14 041.
  * (31) S. Chen, W. Wang, B. Xia, Q. Peng, X. You, F. Zheng, and L. Shao, “Free: Feature refinement for generalized zero-shot learning,” in _ICCV_ , 2021\.
  * (32) A. Frome, G. S. Corrado, J. Shlens, S. Bengio, J. Dean, M. Ranzato, and T. Mikolov, “Devise: A deep visual-semantic embedding model,” in _NeurIPS_ , 2013.
  * (33) M. Long, Z. Cao, J. Wang, and M. I. Jordan, “Conditional adversarial domain adaptation,” in _NeurIPS_ , 2018.
  * (34) K. Saito, K. Watanabe, Y. Ushiku, and T. Harada, “Maximum classifier discrepancy for unsupervised domain adaptation,” in _CVPR_ , 2018, pp. 3723–3732.
  * (35) C.-Y. Lee, T. Batra, M. H. Baig, and D. Ulbricht, “Sliced wasserstein discrepancy for unsupervised domain adaptation,” in _CVPR_ , 2019, pp. 10 277–10 287.
  * (36) B. Tan, Y. Song, E. Zhong, and Q. Yang, “Transitive transfer learning,” in _KDD_ , 2015.
  * (37) B. Tan, Y. Zhang, S. J. Pan, and Q. Yang, “Distant domain transfer learning,” in _AAAI_ , 2017.
  * (38) S. Narayan, A. Gupta, F. Khan, C. G. M. Snoek, and L. Shao, “Latent embedding feedback and discriminative features for zero-shot classification,” in _ECCV_ , 2020.
  * (39) B. Sun, J. Feng, and K. Saenko, “Return of frustratingly easy domain adaptation,” in _AAAI_ , 2016.
  * (40) D. P. Kingma and M. Welling, “Auto-encoding variational bayes,” in _ICLR_ , 2014.
  * (41) P. Welinder, S. Branson, T. Mita, C. Wah, F. Schroff, S. J. Belongie, and P. Perona, “Caltech-ucsd birds 200,” _Technical Report CNS-TR-2010-001, Caltech,_ , 2010.
  * (42) G. Patterson and J. Hays, “Sun attribute database: Discovering, annotating, and recognizing scene attributes,” in _CVPR_ , 2012, pp. 2751–2758.
  * (43) Y. Xian, B. Schiele, and Z. Akata, “Zero-shot learning — the good, the bad and the ugly,” _Proc. CVPR_ , pp. 3077–3086, 2017.
  * (44) Y. Xian, T. Lorenz, B. Schiele, and Z. Akata, “Feature generating networks for zero-shot learning,” in _CVPR_ , 2018, pp. 5542–5551.
  * (45) D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” in _ICLR_ , 2015.
  * (46) S. R. Bowman, L. Vilnis, O. Vinyals, A. M. Dai, R. Józefowicz, and S. Bengio, “Generating sentences from a continuous space,” in _CoNLL_ , 2016\.
  * (47) F. Zhang and G. Shi, “Co-representation network for generalized zero-shot learning,” in _ICML_ , 2019.
  * (48) J. Li, X. Lan, Y. Liu, L. Wang, and N. Zheng, “Compressing unknown images with product quantizer for efficient zero-shot classification,” in _CVPR_ , 2019, pp. 5458–5467.
  * (49) H. Jiang, R. Wang, S. Shan, and X. Chen, “Transferable contrastive network for generalized zero-shot learning,” in _ICCV_ , 2019, pp. 9764–9773.
  * (50) Y. Zhu, J. Xie, Z. Tang, X. Peng, and A. Elgammal, “Semantic-guided multi-attention localization for zero-shot learning,” in _NeurIPS_ , 2019\.
  * (51) S. Min, H. Yao, H. Xie, C. Wang, Z. Zha, and Y. Zhang, “Domain-aware visual bias eliminating for generalized zero-shot learning,” in _CVPR_ , 2020, pp. 12 661–12 670.
  * (52) D. Huynh and E. Elhamifar, “Fine-grained generalized zero-shot learning via dense attribute-based attention,” in _CVPR_ , 2020, pp. 4482–4492.
  * (53) G.-S. Xie, L. Liu, X. Jin, F. Zhu, Z. Zhang, Y. Yao, J. Qin, and L. Shao, “Region graph embedding network for zero-shot learning,” in _ECCV_ , 2020\.
  * (54) J. Li, M. Jing, K. Lu, Z. Ding, L. Zhu, and Z. Huang, “Leveraging the invariant side of generative zero-shot learning,” in _CVPR_ , 2019, pp. 7394–7403.
  * (55) S. Antol, A. Agrawal, J. Lu, M. Mitchell, D. Batra, C. L. Zitnick, and D. Parikh, “Vqa: Visual question answering,” in _ICCV_ , 2015.
  * (56) S. Herdade, A. Kappeler, K. Boakye, and J. Soares, “Image captioning: Transforming objects into words,” in _NeurIPS_ , 2019.
  * (57) X. Li, X. Yin, C. Li, X. Hu, P. Zhang, L. Zhang, L. Wang, H. Hu, L. Dong, F. Wei, Y. Choi, and J. Gao, “Oscar: Object-semantics aligned pre-training for vision-language tasks,” in _ECCV_ , 2020.
  * (58) S. Li, B. Xie, J. Wu, Y. Zhao, C. Liu, and Z. Ding, “Simultaneous semantic alignment network for heterogeneous domain adaptation,” in _ACM MM_ , 2020\.