Ziyi Liu

Le Wang

Nanning Zheng

Content-Aware Attention Network for Action Recognition

Keywords: Action Recognition, Attention Mechanism, Content-Aware Score Fusion softmax softmax Adaptive Attention Weighting Block Content-Aware Weighting Block Base Model for Feature Embedding Content-Aware Attention Weighting Module Fixed-Length Representation Classification Clean and Jerk Adaptive Attention Weighting Block Content-Aware Weighting Block Input Frames and Optical Flow Fields

This paper presents a content-aware attention network (Cat-Net) for action recognition task, which can leverage attention mechanism to aggregate frame-level features into a compact video-level representation. Unlike most previous methods that consider every video frame equally, our CatNet contains an attention module which can adaptively emphasize the representative frames, and thus can benefit the action recognition task. Moreover, the CatNet can take an action video with arbitrary length yet produce a compact video representation with fixed length. The attention module consists of two cascaded blocks, an adaptive attention weighting block and a content-aware weighting block. The experiments are carried on two challenging video action datasets, i.e., the UCF-101 dataset and HMDB-51 dataset. Our method achieves significantly improvements on both datasets compared with existing methods. The results show that our proposed CatNet is able to focus on the representative frames corresponding to a specific action category, and meanwhile significantly improve the recognition performance.

Introduction

Recognizing human actions in various videos is a challenging task, and has received significant attention in the computer vision community [START_REF] Poppe | A survey on vision-based human action recognition[END_REF][START_REF] Cheng | Advances in human action recognition: A survey[END_REF][START_REF] Herath | Going deeper into action recognition[END_REF][START_REF] Wang | Action recognition with improved trajectories[END_REF][START_REF] Lan | Beyond gaussian pyramid: Multi-skip feature stacking for action recognition[END_REF][START_REF] Simonyan | Two-stream convolutional networks for action recognition in videos[END_REF][START_REF] Ng | Beyond short snippets: Deep networks for video classification[END_REF][START_REF] Tran | Learning spatiotemporal features with 3d convolutional networks[END_REF][START_REF] Wang | Temporal segment networks: Towards good practices for deep action recognition[END_REF][START_REF] Girdhar | ActionVLAD: Learning spatio-temporal aggregation for action classification[END_REF][START_REF] Carreira | Quo vadis, action recognition? a new model and the kinetics dataset[END_REF][START_REF] Huang | Video-based sign language recognition without temporal segmentation[END_REF]. From hand-crafted features based methods [START_REF] Wang | Action recognition with improved trajectories[END_REF][START_REF] Lan | Beyond gaussian pyramid: Multi-skip feature stacking for action recognition[END_REF], to deep learning based methods [START_REF] Simonyan | Two-stream convolutional networks for action recognition in videos[END_REF][START_REF] Ng | Beyond short snippets: Deep networks for video classification[END_REF][START_REF] Tran | Learning spatiotemporal features with 3d convolutional networks[END_REF][START_REF] Wang | Temporal segment networks: Towards good practices for deep action recognition[END_REF][START_REF] Girdhar | ActionVLAD: Learning spatio-temporal aggregation for action classification[END_REF][START_REF] Carreira | Quo vadis, action recognition? a new model and the kinetics dataset[END_REF][START_REF] Huang | Video-based sign language recognition without temporal segmentation[END_REF], impressive progresses have been achieved in recent years. Similar with other computer vision tasks, the performance of action recognition has been significantly improved due to the emerging deep learning, especially the convolutional neural networks (CNN), based methods.

However, compared with the successes achieved by CNN in still image classification field [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF][START_REF] He | Deep residual learning for image recognition[END_REF][START_REF] Ran | A hyperspectral image classification framework with spatial pixel pair features[END_REF][START_REF] Ran | Convolutional neural network-based robot navigation using uncalibrated spherical images[END_REF], the action recognition task has not been fully explored yet. There still remains many challenges need to be further addressed. In order to better recognize the action categories inside a variety of videos, the action/video representation should be discriminative and, more importantly, compact. Thus, one of the key issues is how to construct a discriminative and compact video-level representation. Hand-crafted feature based methods usually employ encoding Fig. 1. Some example frames alone with their action category labels that are not suited for the action recognition task. In these cases, it is very difficult to predict the video category by a single frame. The first row consists of frames with semantic ambiguity, which can be easily mistaken for PlayingDaf, BrushingTeeth, CleanAndJerk, ApplyLipstick and Skiing from left to right. The second row consists of frames in poor condition, such as motion blur and poor illumination.

methods, such as Fisher Vectors [START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF], to aggregate local hand-crafted descriptors into a global video representation [START_REF] Wang | Action recognition with improved trajectories[END_REF]. With the benefit from the deep CNN, early CNN based methods propose to use a single frame to represent the whole video [START_REF] Simonyan | Two-stream convolutional networks for action recognition in videos[END_REF], or feed multiple frames into CNN and aggregate them with average or max pooling strategy [START_REF] Karpathy | Largescale video classification with convolutional neural networks[END_REF][START_REF] Wang | Temporal segment networks: Towards good practices for deep action recognition[END_REF]. In addition, [START_REF] Donahue | Long-term recurrent convolutional networks for visual recognition and description[END_REF] proposed to employ a long shortterm memory (LSTM) network upon the CNN, which can model the temporal correlations among frames into a fixed-length representation. To further explore both the spatial and temporal correlations among video frames simultaneously, [START_REF] Ji | 3d convolutional neural networks for human action recognition[END_REF] first proposed the 3D convolution pipeline to handle related tasks in videos.

We argue that to effectively aggregate frame-level descriptors and construct a compact video-level representation, an adaptive content-aware aggregation method is vital. The motivation behind this idea is quite intuitive, i.e., there should exist a subset of the video frames, which are more tightly related to the action category. Thus, we should emphasize these representative frames when aggregating the frame-level descriptors, in order to make the aggregated videolevel representation discriminative. Fig. 1 gives some example frames alone with their action category labels that are not suitable for the recognition task, due to semantic ambiguity or motion blur. These "bad" samples will introduce noisy information into the inference stage of the neural network [START_REF] Lan | Deep local video feature for action recognition[END_REF]. These ambiguities should be suppressed during the inference process. Therefore, it is a natural sense to utilize the attention mechanism for action recognition, which can enable the whole network to focus on the representative frames and suppress the noises.

We propose a content-aware attention network (CatNet) embedding an effective attention module to identify the representative frames from the noisy ones. The framework of the CatNet is illustrated in Fig. 2. The attention module consists of two cascaded blocks, i.e., an adaptive attention weighting block which can adaptively weight all frames fed into the CatNet based on their extracted features, and a content-aware weighting block which is added to constrain the aggregation weights to be more consistent with the video content. To capture both the appearance and motion information, a standard two-stream structure is adopted, where each stream can be trained in an end-to-end manner.

The main contributions of this paper are:

-We propose a novel structure, namely CatNet, for action recognition, which achieves state-of-the-art performance. -We introduce the attention mechanism to action recognition and validate it is beneficial for the action recognition task.

The rest of the paper is organized as follows. Section 2 reviews previous work related to action recognition. Section 3 presents the content-aware attention network for action recognition. Section 4 introduces the experiments and discussions. Section 5 presents the conclusion and future work.

Related Work

In this section, we review the related work in action recognition, mainly including hand-crafted feature based methods, and deep learning based methods.

Hand-Crafted Feature Based Methods

Before the prevalent of deep learning, hand-crafted feature based methods have dominated the action recognition filed [START_REF] Laptev | On space-time interest points[END_REF][START_REF] Dollár | Behavior recognition via sparse spatio-temporal features[END_REF][START_REF] Sadanand | Action bank: A high-level representation of activity in video[END_REF][START_REF] Wang | Action recognition with improved trajectories[END_REF]. Plenty of image local descriptors have been extended to the video domain, such as 3D-sift [START_REF] Scovanner | A 3-dimensional sift descriptor and its application to action recognition[END_REF], HOG3D [START_REF] Klaser | A spatio-temporal descriptor based on 3d-gradients[END_REF], and motion boundary histograms (MBH) [START_REF] Dalal | Human detection using oriented histograms of flow and appearance[END_REF]. The improved Dense Trajectory (iDT) [START_REF] Wang | Action recognition with improved trajectories[END_REF] achieves state-of-the-art performance among these hand-crafted feature based methods. The iDT consists of multiple local descriptors extracted along with the dense trajectories where camera motion is compensated. To perform action recognition, the descriptors are then aggregated into a video-level representation by using encoding methods, such as Fisher vector [START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF].

Deep Learning Based Methods

Aggregating frame-level features. Recently, the CNN based image descriptors have emerged as the state-of-the-art generic descriptors for visual recognition. To obtain a discriminative frame-level representation, the recent work on action recognition almost always extract the CNN feature as the frame-level descriptor, and then aggregate them into a global video-level representation. The aggregation methods can be roughly divided into two categories. The first one is to employ recurrent neural network (RNN) upon a frame-level feature extractor, such as LSTM [START_REF] Donahue | Long-term recurrent convolutional networks for visual recognition and description[END_REF]. By plugging RNN on top of CNN, temporal correlations within the action video can be easily captured, and a compact fixed-length video representation is then obtained. The other one aims to aggregate the frame-level features via different pooling methods, such as the average or max pooling over time [START_REF] Wang | Temporal segment networks: Towards good practices for deep action recognition[END_REF], the vector of locally aggregated descriptors (VLAD) [START_REF] Arandjelovic | Netvlad: Cnn architecture for weakly supervised place recognition[END_REF][START_REF] Girdhar | ActionVLAD: Learning spatio-temporal aggregation for action classification[END_REF], and the temporal pyramid pooling (TPP) [START_REF] Wang | Temporal pyramid pooling-based convolutional neural network for action recognition[END_REF]. All these methods treat the frame-level features equally during aggregation, which may inevitably over-weight the noisy frames. To eliminate the negative influence from noisy frames, we propose to embed an attention module into action recognition, which can adaptively emphasize the representative frames while suppressing the influence from noisy frames.

Spatio-temporal CNN. The spatio-temporal CNN was first proposed in [START_REF] Ji | 3d convolutional neural networks for human action recognition[END_REF] and named 3D CNN, and later a number of its variants were proposed [START_REF] Tran | Learning spatiotemporal features with 3d convolutional networks[END_REF][START_REF] Sun | Human action recognition using factorized spatio-temporal convolutional networks[END_REF][START_REF] Varol | Long-term temporal convolutions for action recognition[END_REF][START_REF] Carreira | Quo vadis, action recognition? a new model and the kinetics dataset[END_REF]. The 3D CNN based action recognition methods take the video clip as input, and aim to model both the spatial and temporal correlations among the video content. Considering the 3D convolution brings extra kernel parameters, to fully train 3D CNN model usually requires massive video data and is time consuming, and thus 3D CNN is unsuitable to handle small dataset [START_REF] Karpathy | Largescale video classification with convolutional neural networks[END_REF][START_REF] Carreira | Quo vadis, action recognition? a new model and the kinetics dataset[END_REF].

Content-Aware Attention Network

This section details the proposed content-aware attention network (CatNet). As shown in Fig. 2, our proposed CatNet takes a video with arbitrary length as input, and outputs a fixed-length video representation for subsequent action recognition task. The frame-level feature embedding is based on the CNN model, which is followed by an adaptive attention weighting block and a content-aware weighting block. These two blocks enable the CatNet to adaptively emphasize the representative frames and meanwhile suppress the noisy ones.

Frame-Level Feature Embedding

The frame-level features are extracted using the deep CNN, which embeds each frame of an action video to a fixed-length vector. Here, we adopt the Inception with Batch Normalization [START_REF] Ioffe | Batch normalization: Accelerating deep network training by reducing internal covariate shift[END_REF] as the feature extractor (base model). Note that our proposed attention module is not limited to a specific CNN model, other CNN models can also be used. The extracted d-dimension CNN features are first normalized by L2 norm and then fed into the attention module. Formally, given a video V = {f t } T t=1 with T frames, where f t denotes the tth frame, the feature embedding can be formulated as

x t = F(f t ; W), (1) xt
= x t ||x t || , (2)
where F denotes the base model and W denotes the parameters of F. x t ∈ R d represents the extracted d-dimensional feature of f t . xt is a normalized feature.

Adaptive Attention Weighting Block

As obtained the feature x t of each frame f t by feature embedding, our goal is to obtain a fixed-length video representation for video V by aggregating its frame-level descriptors X = {x t } T t=1 . Our adaptive attention weighting block first computes a corresponding weight w t for each frame f t , and then aggregates the frame-level descriptors into a fix-length video-level representation by

v = T t=1 w t xt . (3)
Here, the key is how to compute an appropriate weight w t for x t according to its importance. If w t = 1 T , then this block will degrade to average pooling. There are two issues need to be considered when building the adaptive attention weighting block . First, the block should be able to handle videos with arbitrary lengths. Second, the block should be differentiable, i.e., can be easily plugged into the current networks to perform an end-to-end training. Our proposed solution is to introduce a learnable kernel k with the same dimension as x. Then, w t can be calculated by

w t = k T xt . (4)
Here, k actually serves as a scoring function. It is expected that if x t is discriminative, w t will be larger, and vice versa. In this way, the video representation v calculated by Eq. (3) will adaptively emphasize the representative frames and suppress the noisy frames during aggregation.

Content-Aware Weighting Block

To leverage context information, which is popular in image segmentation field [START_REF] Wang | Automatic salient object extraction with contextual cue[END_REF][START_REF] Wang | Video object discovery and co-segmentation with extremely weak supervision[END_REF], a content-aware weighting block is introduced to let the attention module select the discriminative features by considering the content throughout the video instead of single frames. Inspired by [START_REF] Dauphin | Language modeling with gated convolutional networks[END_REF] for language modeling, we borrow the ideas from [START_REF] Dauphin | Language modeling with gated convolutional networks[END_REF][START_REF] Miech | Learnable pooling with context gating for video classification[END_REF] and adjust it to the action recognition task. The content-aware weighting block can be formulated as

k c = C(v; (W c , b)) = σ(W c v + b), (5)
w c t = k T c x t , (6)
v c = T t=1 w c t x t , (7)
where σ denotes the sigmoid function and k c serves as a new weighting kernel which is content-aware. W c ∈ R d×d and b ∈ R d are trainable parameters of this block. v c is the final fixed-length representation of the input video.

Two-Stream Structure

It is critical to capture temporal information for action recognition. A common way to capture temporal information is adopting the two-stream structure [START_REF] Simonyan | Two-stream convolutional networks for action recognition in videos[END_REF][START_REF] Feichtenhofer | Convolutional two-stream network fusion for video action recognition[END_REF]. We also employ this validated effective structure to combine the spatial and temporal features. Each of the two streams is constructed as described above, and can be trained in an end-to-end way. To fuse the scores from these two streams, the simplest weighted average fusion strategy is utilized.

Experiments and Discussions

We evaluate the performance of the proposed CatNet on two challenging action datasets, including UCF-101 dataset [START_REF] Soomro | UCF101: A dataset of 101 human actions classes from videos in the wild[END_REF] and HMDB-51 dataset [START_REF] Kuehne | Hmdb: a large video database for human motion recognition[END_REF]. The UCF-101 dataset contains 13320 action videos in 101 action categories. Our evaluation on UCF-101 dataset follows the scheme of the THUMOS-13 challenge [START_REF] Jiang | THUMOS challenge: Action recognition with a large number of classes[END_REF]. We use all the three training/testing splits, and report the average accuracy on them.

The HMDB-51 dataset contains 6766 videos in 51 action categories. We follow the standard evaluation scheme with three training/testing splits, and report the average accuracy on them. We proceed to introduce the implementation details of our method, and then explore the efficacy of our attention module and compare with baseline method. Finally, our CatNet is compared with the state-of-the-art methods.

Implementation Details

We use the stochastic gradient descent optimizer to train the network, by setting momentum to be 0.9 and batch size to be 32. We implement a two-stream CNN framework with the spatial stream for RGB image inputs and temporal stream for optical flow inputs, as multi-modality inputs offer more information [START_REF] Wang | Temporal segment networks: Towards good practices for deep action recognition[END_REF][START_REF] Zhang | Multi-view visual recognition of imperfect testing data[END_REF][START_REF] Zhang | Auxiliary training information assisted visual recognition[END_REF][START_REF] Zhang | Can visual recognition benefit from auxiliary information in training?[END_REF]. We choose the Inception with Batch Normalization (BN-Inception) [START_REF] Ioffe | Batch normalization: Accelerating deep network training by reducing internal covariate shift[END_REF] as the building block for both spatial and temporal stream, because of its good balance between accuracy and efficiency. We adopt the partial BN with extra dropout layer proposed in [START_REF] Wang | Temporal segment networks: Towards good practices for deep action recognition[END_REF] to avoid over-fitting. For the spatial stream, the weights are initialized by pre-trained models from ImageNet [START_REF] Deng | Imagenet: A large-scale hierarchical image database[END_REF]. While for the temporal stream, we use the cross modality pre-training proposed in [START_REF] Wang | Temporal segment networks: Towards good practices for deep action recognition[END_REF]. As to data augmentation, we employ the scale jittering technique [START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF] and random horizontal flipping. For the computation of optical flow, we use the TVL1 optical flow algorithm [START_REF] Zach | A duality based approach for realtime tv-l 1 optical flow[END_REF], which is implemented in OpenCV with CUDA. When fusing the scores from the two streams, we average the final prediction score of each stream with a weight 1 for spatial stream and a weight 1.5 for temporal stream.

Evaluation of the Proposed Attention Module

To validate the efficacy of the proposed attention module, we compared it with a baseline aggregation strategy, i.e. average pooling. The average accuracies for action recognition of them are summarized in Table 1. They showed that our aggregation strategy outperforms the average pooling on both of the UCF-101 dataset [START_REF] Soomro | UCF101: A dataset of 101 human actions classes from videos in the wild[END_REF] and HMDB-51 dataset [START_REF] Kuehne | Hmdb: a large video database for human motion recognition[END_REF]. This clearly manifests that the proposed attention module can improve the action recognition performance. It can be also seen that the performance improvement on HMDB-51 is larger than that on UCF-101. This is mainly because the videos in HMDB-51 contain more noisy frames that should be suppressed. Note that the improvement on temporal stream is less than that on spacial stream. This is because the optical flow fields contain less noise and are more discriminative than RGB images, especially for the action recognition task.

Table 1. The average accuracies by using average pooling and our aggregation strategy on the UCF-101 dataset [START_REF] Soomro | UCF101: A dataset of 101 human actions classes from videos in the wild[END_REF] and HMDB-51 dataset [START_REF] Kuehne | Hmdb: a large video database for human motion recognition[END_REF]. Besides, to further verify the efficacy of the proposed attention module, we visualize what has been learnt by the attention module. Fig. 3 presents some example frames sorted by their attention weights. They showed that the proposed attention module can automatically pay more attention to the representative frames while suppressing the frames in poor condition, without providing any extra supervision during training. For example, in video "Hug", it is difficult to judge it is either hugging or hand shaking by the frames with low attention. However, the frames with higher attention can clearly reveal the hugging action. Similar examples can be found in other videos shown in Fig. 3.

Stream

Moreover, it is interesting to observe that our attention module assigns high attention to frames containing action "Stand" in the video labelled as "Stand", while it assigns low attention to frames containing similar action in other videos (as shown in "Sit" and "Stand" videos in Fig. 3). This validates that our attention module is content-aware.

Table 2. The average accuracies of our CatNet and other state-of-the-art methods on the UCF-101 dataset [START_REF] Soomro | UCF101: A dataset of 101 human actions classes from videos in the wild[END_REF] and HMDB-51 dataset [START_REF] Kuehne | Hmdb: a large video database for human motion recognition[END_REF].

Method UCF101 HMDB51

iDT+FV [START_REF] Wang | Action recognition with improved trajectories[END_REF] 85.9 57.2 Spatio-Temporal ConvNet [START_REF] Karpathy | Largescale video classification with convolutional neural networks[END_REF] 65.4 -LRCN [START_REF] Donahue | Long-term recurrent convolutional networks for visual recognition and description[END_REF] 82.9 -C3D [START_REF] Tran | Learning spatiotemporal features with 3d convolutional networks[END_REF] 85.2 -Factorized ConvNet [START_REF] Sun | Human action recognition using factorized spatio-temporal convolutional networks[END_REF] 88.

Evaluation of the Proposed CatNet for Action Recognition

After comparing with baseline methods to validate the efficacy of our proposed attention module, it is also very important to compare our CatNet with other state-of-the-art methods for action recognition. We present the average accuracies of CatNet and a variety of recently proposed action recognition methods on both UCF-101 dataset [START_REF] Soomro | UCF101: A dataset of 101 human actions classes from videos in the wild[END_REF] and HMDB-51 dataset [START_REF] Kuehne | Hmdb: a large video database for human motion recognition[END_REF] in Table 2.

The results showed that, the two-stream version of CatNet significantly outperforms other state-of-the-art methods, although we adopt the simplest weighted average fusion strategy. Moreover, both the single stream versions of our method can achieve competitive performances, when comparing with the handcrafted based methods (e.g., [START_REF] Wang | Action recognition with improved trajectories[END_REF]), LSTM based methods (e.g., [START_REF] Donahue | Long-term recurrent convolutional networks for visual recognition and description[END_REF]), and 3D CNN based methods (e.g., [START_REF] Tran | Learning spatiotemporal features with 3d convolutional networks[END_REF]).

Conclusion and future work

This paper proposed a content-aware attention network for action recognition, which leverages an attention module to aggregate the frame-level features into a compact video-level representation. Experimental results on the UCF-101 dataset and HMDB-51 dataset validated the efficacy of the proposed attention module and also the whole action recognition method, and demonstrated that the attention module can lead the content-aware attention network to adaptively emphasize the representative frames while suppressing the noisy frames.

For future work, we aim to extend our content-aware attention network to handle untrimmed action videos, where we argue that the attention module can play a more significant role. We will conduct extensive experiments on untrimmed videos to fully explore the efficacy of the attention module. Moreover, we only validate that the attention module can help improving the action recognition performance in this paper. In future work, we will extend the attention module to action localization or action segmentation task.

Fig. 2 .

 2 Fig. 2. Content-aware attention network. The inputs are video frames and optical flows. First, they are embedded by a CNN (base model). Then, the extracted features are aggregated by the proposed content-aware attention weighting module, and a fixedlength representation can be obtained. Finally, we use this representation to classify the input video, and adopt score fusion to obtain the prediction of the video.

Fig. 3 .

 3 Fig.3. Some example frames sorted by their attention weights from high (left) to low (right) along with their action category labels. The frames of the left part are from the UCF-101 dataset, and the frame of the right part are from the HMDB-51 dataset. We can see that the representative frames are assigned with higher attention weights compared with frames in poor conditions, such as motion blur (e.g., Biking and Knitting), shot changing (e.g., Smile), irrelevant clips (e.g., Shoot Gun and Run), partial observation (e.g., Brushing Teeth and Haircut), and semantic ambiguity (e.g., Tennis Swing and Hug).

Acknowledgments. This work was supported partly by NSFC Grants 61629301, 61773312, 91748208, and 61503296, China Postdoctoral Science Foundation Grant 2017T100752, and key project of Shaanxi province S2018-YF-ZDLGY-0031.


Kai Yi

Shitao Chen
email: chenshitao@stu.xjtu.edu.cn

Yu Chen

Chao Xia

Nanning Zheng
email: nnzheng@mail.xjtu.edu.cn

Cognition-based Deep Learning: Progresses and Perspectives

Keywords: Cognitive mechanisms, Deep learning, Attention, Memory, Knowledge, Decision-making

d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

In recent years, deep learning, characterized by learning large neural-networkstyle models with multiple layers of representations, has received lots of attention. Those models based on deep learning have achieved remarkable gains in many domains, including image classification [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF], [START_REF] He | Deep residual learning for image recognition[END_REF], [START_REF] Szegedy | Going deeper with convolutions[END_REF], control and decisionmaking [START_REF] Mnih | Playing atari with deep reinforcement learning[END_REF], [START_REF] Mnih | Human-level control through deep reinforcement learning[END_REF]. [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] trained a deep convolutional neural network that nearly halved the error rate of the previous state-of-the-art methods on the typical image classification dataset. In recent years, [START_REF] He | Deep residual learning for image recognition[END_REF] even surpass the human-level performance on several challenging classification datasets. In the field of decision-making, deep learning in combination with reinforcement learning, have been widely used to play games. [START_REF] Mnih | Human-level control through deep reinforcement learning[END_REF] achieved several human even superhuman level performance on several games, illustrating that computer can master go learning from scratch by trial-and-error strategies. These accomplishments have helped Deep Neural Networks (DNNs), the core of deep learning, to regain their status as a leading paradigm in machine learning.

Nowadays, deep learning has shown more and more interests on how our brain works and how an artificial intelligence system can be inspired by cognitive science. The human brain doesn't learn through a unified undifferentiated neural network. It is composed of multiple modular subsystems, with a unique way interacting among. These subsystems have their own unique characteristics, and interact to support cognitive functions, such as memory, attention, language and cognitive control. What's more, the brain can combine knowledge (including internal knowledge from self experience, environment knowledge by interacting with objects around, global knowledge extracted from the universe), with different cognitive functions to conduct complicated tasks with a few data.

In this article, we review the latest progresses and future perspectives of deep learning systems based on the cognitive core elements, especially memory, attention and knowledge. In section two, we will review the fundamental concepts of deep learning, cognitive mechanism, and what deep neural networks can benefit from cognitive science. In section three to section five, we review and summarize the latest progresses of deep learning methods based on memory, attention and knowledge respectively. In section six, we propose a general framework of cognition-based deep learning and make assumptions of the essential future directions towards this field. In the last section, we'll make conclusions about all above-mentioned issues concerning cognition-based deep learning.

Fundamental Concepts

In this section, we will review the basic concepts of deep learning, cognitive mechanism, as well as the reason and the way that the former two are combined. We first introduce the core concepts of deep learning and it's foundations (i.e., two kind of neural works). Then, the major mechanisms of cognitive science, especially those that have been applied to more powerful deep learning systems will be presented. Further, we give some directions on how to build deep learning systems inspired or based on important elements of cognitive science.

Deep Learning

Deep learning is a kind of computational methods. It is composed of multiple processing layers which learn and represent the feature and the distribution of input data with multiple levels of abstraction, (i.e., different depth of feature map). Nowadays, the success of deep learning can own to two branches of welldesigned neural networks: Convolutional Neural Networks (CNNs or ConvNets) and Recurrent Neural Networks (RNNs).

ConvNets are feature extractor indeed. They are very excellent at dealing with structured 2D arrays in areas like image processing. ConvNets achieved a state-of-the-art performance on image classification [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF], [START_REF] He | Deep residual learning for image recognition[END_REF], [START_REF] Szegedy | Going deeper with convolutions[END_REF], image segmentation [START_REF] Long | Fully convolutional networks for semantic segmentation[END_REF], and object detection [START_REF] Shaoqing Ren | Faster r-cnn: Towards real-time object detection with region proposal networks[END_REF], [START_REF] Liu | Ssd: Single shot multibox detector[END_REF]. RNNs are excellent at dealing with sequence inputs, such as speech and language [START_REF] Graves | Speech recognition with deep recurrent neural networks[END_REF], [START_REF] Yin | Comparative study of cnn and rnn for natural language processing[END_REF]. RNNs process an input sequence one element at a time, maintaining in their hidden units a "state vector" that implicitly contains information about the history of all the past elements of the sequence. For more detailed explanations, please refer to [START_REF] Lecun | Deep learning[END_REF].

Cognitive Mechanisms

Cognitive science is a discipline and a recognition of a fundamental set of common concerns shared by psychology and artificial intelligence [START_REF] Herbert | Cognitive science: The newest science of the artificial[END_REF]. The key point of cognitive science is the way we reflect to our environment and the effect of our brain activities. Our brain is composed of several subsystems, which interact with each other in a very complicated way. And they communicate to support cognitive functions, including attention, memory, language and cognitive control. The combination of the above-mentioned functions with knowledge extracted from self experience, environments, intuitive psychology and physical worlds are among the key characteristics of human.

Combination

The most important elements of cognitive science are attention, memory and knowledge. The last one can be classified to internal knowledge, environment knowledge and global knowledge. Deep learning system can benefit from every element separately or together by increasing dynamics and target-oriented accuracy with fewer training data. Further, the cognitive science mechanisms are derived from human brains. Deep learning, which is regarded as the "black box", can be interpreted at the aspect of cognitive science, such as the view of decision tree [START_REF] Wu | Beyond sparsity: Tree regularization of deep models for interpretability[END_REF] and the view of shape bias [START_REF] Ritter | Cognitive psychology for deep neural networks: A shape bias case study[END_REF].

Deep Learning Inspired by Memory Mechanism

From the perspective of cognitive science and our intuitions, humans can learn in a continuous spatial sequence and memorize the pattern and characteristics. Therefore applying this mechanism to deep learning systems is of vital importance. How to guide those systems to memorize sequences of input and how to memorize according to the relative importance are two topics that will be reviewed next.

RNNs-based Memory Model

RNNs is a type of artificial neural network where connections between units form a directed cycle. This creates an internal state of the network which allows it to exhibit dynamic behavior. Unlike feed forward neural networks, RNNs can use their internal memory to process and work on arbitrary sequences of inputs. This makes deep neural networks applicable to handle the data with rich structures, especially the sequences. It has been widely used in speech recognition [START_REF] Sak | Long short-term memory recurrent neural network architectures for large scale acoustic modeling[END_REF], [START_REF] Miao | Simplifying long short-term memory acoustic models for fast training and decoding[END_REF], natural language processing [START_REF] Yin | Comparative study of cnn and rnn for natural language processing[END_REF], [START_REF] Prakash M Nadkarni | Natural language processing: an introduction[END_REF] and object detection [START_REF] Liang | Recurrent convolutional neural network for object recognition[END_REF], [START_REF] Tripathi | Context matters: Refining object detection in video with recurrent neural networks[END_REF].

Traditional RNNs structures have been used to deal with sequences of input mentioned above, but [START_REF] Bengio | Learning long-term dependencies with gradient descent is difficult[END_REF] found it is difficult to train RNNs to capture longterm dependencies because the gradient tends to either vanish or explode, which can cause severe effects. Long Short-Term Memory (LSTM) [START_REF] Hochreiter | Long short-term memory[END_REF] and Gated Recurrent Units (GRU) [START_REF] Cho | Learning phrase representations using rnn encoder-decoder for statistical machine translation[END_REF] are two of the well-designed recurrent neural networks which can elevate this problem. The idea of those two RNNs is to design a more sophisticated activation function than an usual one, consisting of affine transformation followed by a simple element-wise nonlinearly part by using gating units.

Memory Model with Importance

In the process of human learning, the old information we stored will be overwritten by new incoming information [START_REF] Jonides | The mind and brain of short-term memory[END_REF]. However, what we memorized are rarely with equal importance: frequently used and important knowledge is often prevented from being erased. Inspired by the memory mechanism, we think evaluating what is important and what is not behind the structure of a deep neural network is really meaningful. Elastic Weight Consolidation [START_REF] Kirkpatrick | Overcoming catastrophic forgetting in neural networks[END_REF] used an approximation of the diagonal term of the Fisher information matrix to identify the important parameters for the task. While training a new task, a regularizer is used to prevent those important weights from being overwritten by the new task. The Fisher information matrix needs to be computed in a separate phase after each task and also needs to be stored for each task for later use when learning a new task. Thus, this model stores a large number of parameters that grows with the number of executed tasks. To avoid this, Improved multi-task learning through synaptic intelligence [START_REF] Zenke | Improved multitask learning through synaptic intelligence[END_REF] adopts an online way of computing the importance of the network parameters. [START_REF] Aljundi | Memory aware synapses: Learning what (not) to forget[END_REF] formulates the importance of memorized information as the absolute gradient of the parameters in deep neural network based on the sensitivity of the predicted output to a change in this parameter. When learning a new task, changes to important parameters are penalized. The memory-based deep learning method shows the ability to adapt the importance of the parameters towards what the network needs (not) to forget.

Attention Mechanism Applied to Deep Learning

Human attention is a built-in mechanism for deciding how to apply their brainpower from moment to moment, (e.g., decide where to see in saliency visual object detection [START_REF] Liu | Learning to detect a salient object[END_REF]). Attention mechanism is a reasonably well studied subject within the field of cognitive psychology and is known to be a key feature of human artificial intelligence [START_REF] Pll | General attention mechanism for artificial intelligence systems[END_REF]. Nowadays, attention-based deep learning methods are active especially in dealing problems concerning sequence prediction or control, including object detection, natural language processing, and deep reinforcement learning.

Natural Language Processing

The seminal work of natural language processing with attention was proposed by [START_REF] Bahdanau | Neural machine translation by jointly learning to align and translate[END_REF] for English-to-French translation. They used a novel neural machine translation model that implements an attention mechanism in the decoder, which achieved much better performance than traditional phrase-based models. In order to allow parallelisation, [START_REF] Gehring | Convolutional sequence to sequence learning[END_REF] proposed a highly parallelisable multi-hop attention module with convolutional neural network, which takes multiple glimpses at the sentence to determine what will be translated next, and a separate attention module in each decoder layer. Moreover, the attention mechanisms have been widely used in other language processing fields, like text classification [START_REF] Yang | Hierarchical attention networks for document classification[END_REF], [START_REF] Singh Chaplot | Gated-attention architectures for task-oriented language grounding[END_REF] and text understanding [START_REF] Dhingra | Gated-attention readers for text comprehension[END_REF].

Object Detection

Attention mechanism in object detection decides which object or which field we need to see. Recurrent attention models are widely used to deal with the problem. [START_REF] Mnih | Recurrent models of visual attention[END_REF] represented how an attention mechanism can be applied to ignore irrelevant objects in a scene and how an object can be "seen" by the system with the help of the attention mechanism. [START_REF] Ba | Multiple object recognition with visual attention[END_REF] proposed a deep recurrent neural network trained with reinforcement learning to detect multiple objects automatically. [START_REF] Xu | Show, attend and tell: Neural image caption generation with visual attention[END_REF] found the attention models with deep neural networks are the insights gained by approximately visualizing where and what the attention focused on (i.e., what the model "sees") after feeding a sequence of data. Besides, attention models with deep learning are hot methods in several topics related to object detection, including saliency detection [START_REF] Kuen | Recurrent attentional networks for saliency detection[END_REF], [START_REF] Li | Visual saliency based on multiscale deep features[END_REF] (detecting the most salient object and segmenting the accurate region of that object), eye fixation [START_REF] Liu | Predicting eye fixations using convolutional neural networks[END_REF], [START_REF] Srinivas | Deepfix: A fully convolutional neural network for predicting human eye fixations[END_REF], [START_REF] Cornia | Predicting human eye fixations via an lstm-based saliency attentive model[END_REF] (maintaining the visual gaze on a single location).

Deep Reinforcement Learning

Deep reinforcement learning is widely used in decision-making and control. Deep Q-Network (DQN) proposed by [START_REF] Mnih | Playing atari with deep reinforcement learning[END_REF] showed a single algorithm that can outperform human or even superhuman performance on Atari 2600 games. By combining the attention mechanisms into DQN, [START_REF] Sorokin | Deep attention recurrent q-network[END_REF] proposed the Deep Attention Recurrent Q-Network (DARQN). By combining what they called "soft" and "hard" attention mechanisms, the model greatly outperformed the traditional DQN. The attention network takes the current game state as input and generates a context vector based on the features observed. Then an typical LSTM network takes the context vector with a previous hidden state and the memory state to evaluate the action that an agent can take. Further, [START_REF] Choi | Multi-focus attention network for efficient deep reinforcement learning[END_REF] improved on DARQN by implementing a multi-focus attention network where the agent has the ability to attend to multiple important elements. They proposed a novel model by using multiple parallel attention to attend to entities concerning the problem instead of just one attention layer in DARQN.

Deep Neural Networks with Knowledge

Humans can combine different kinds of knowledge in a complicated manner to solve very difficult problems without being trained with plenty of data. On the one hand, our brains use knowledge accompanied with other elements (e.g. attention, reasoning) to realize associative memory and build high-level concepts. On the other hand, the logical and physical constraints derived from our knowledge can be used to build a more robust model, especially towards solving natural problems as it can be influenced by too many factors. Beriefly speaking, our knowledge originated from three different parts: self experience (i.e., internal knowledge), surrounding objects (i.e., environment knowledge) and universe (i.e., global knowledge). Human brains process and summarize that knowledge into three categories: intuitive originates psychology knowledge, intuitive derives from physical knowledge and domain specific knowledge.

Intuitive Psychology

Humans gain plenty of psychology knowledge by interacting with the environment. Infants can understand mental states of other people like beliefs and goals, and this understanding strongly guides and constraints decisions that they make [START_REF] Brenden | Building machines that learn and think like people[END_REF]. Besides, humans tend to assign the same name to similarly shaped items rather than to items with similar color, texture, or size by psychological experiments [START_REF] Landau | The importance of shape in early lexical learning[END_REF]. Those psychology intuitions can help create more interpretable neural networks and create a new area of one-shot learning. [START_REF] Ritter | Cognitive psychology for deep neural networks: A shape bias case study[END_REF] found that several well-performed one-shot learning models trained on ImageNet exhibit a similar bias to that observed in humans: they prefer to categorize objects according to shape rather than color. Inspired by cognitive psychology, [START_REF] Vinyals | Matching networks for one shot learning[END_REF] proposed shape Matching Network (MN) with inception network, which has the state-of-the-art one-shot learning performance on ImageNet.

Intuitive Physics

Deep learning can learn features and patterns not only from plenty of labeled data, but also from physical laws. The limitation and constraints can help neural networks learn from fewer labeled data, even without any labeled data (i.e., unsupervised learning). Further, deep learning methods with physical constraints can help build high-level structural models and solve complicated scientific problems. In many fields, labeled data and long-time training is scarce and obtaining more labels is expensive. Constraint learning with physical knowledge is another active field of machine learning, which is aimed at uncover the hidden structure of models. By using physical knowledge, [START_REF] Stewart | Label-free supervision of neural networks with physics and domain knowledge[END_REF] trained a convolutional neural network to detect and track objects without any labeled examples.

Domain Knowledge

Regulating deep neural networks (DNNs) with human structured domain knowledge has been confirmed to be of great benefit for improved accuracy and in-terpretability with fewer training data. Recently, [START_REF] Hu | Harnessing deep neural networks with logic rules[END_REF] proposed a general distillation framework that transfers knowledge into neural networks by combining first-order logic (FOL), where FOL constraints are integrated via posterior regularization [START_REF] Ganchev | Posterior regularization for structured latent variable models[END_REF]. Further, [START_REF] Hu | Deep neural networks with massive learned knowledge[END_REF] used a generalized framework that makes it possible to learn procedure for knowledge representations and adapt their weights jointly with the help of the regulated DNN models. [START_REF] Hu | Deep neural networks with massive learned knowledge[END_REF] proposed to transfer logical knowledge information into neural networks with diverse architectures such as recurrent networks and convolutional networks.

Perspectives

Cognition-based deep learning has become one hot research topic, and some of the most important functions of our human brains like memory and attention associated with knowledge extracted from experience and the universe, have been widely used in the design of a more human-like deep learning system. Meanwhile, the brain does not learn through a unified undifferentiated neural network. The brain is composed of multiple modular subsystems, with an unique and complicated way interacting among. Although deep neural network can process structural data well, it can't deal with dynamic clouds of data. What's more, data is really scarce in some fields. Deep learning systems can get a lot of inspirations from cognitive science, to alleviate and even eliminate those problems.

In this section, we will discuss the essential trend to apply more elements of cognitive science to build more dynamic, robust and intelligent deep learning systems. We are going to give a general framework of cognition-based learning firstly. Then we will discuss the key problems of fusing deep neural network with cognitive mechanisms and essential solutions.

General Framework of Cognition-based Deep Learning

We suggest the general framework of designing cognition-based deep learning systems. This framework use cognitive mechanisms in a particular way. It can help build more dynamic, robust and intelligent systems. More accurately speaking, it can process unstructured data as constructed one with the help of our memory with concepts, especially associative memory. Also the system based on the proposed framework can reasoning and infer based on the knowledge by gaining structural feature map with hierarchical knowledge sets in the top-down manner. Every layer in hierarchical knowledge sets is corresponding to each layer in the structural feature maps. As feedback is also very essential in our human brains, we can monitor this mechanism by designing two feedback loops. One is knowledge feedback loop, to update our knowledge based on attention select network, which is aimed at deciding what we need to see. Another is memory feedback loop, to update our memory (especially the experience), and gains highlevel concepts after measuring actions/decisions the system make. The general framework is shown in Fig 1 . The model based on this framework can be suitable for plenty domains such as image processing and nature language processing.

Key Problems and Potential Solutions

This part will discuss the future directions of cognition-based deep learning. It is organized by current problems and essential solutions.

Associative Memory

Human brains can associate patterns similar to the input patterns when being stimulated. Associative memory model was once prevailing in 1980s and 1990s, accompanied with the popularity of Hopfield Neural Network [START_REF] John | Neural networks and physical systems with emergent collective computational abilities[END_REF], a typical network that can store patterns and realize associative memory. Due to the potential chaos state of network evolution, HNNs alone is difficult to handle natural realworld problems well. However, it has the potential as it is an important kind of brain-like neural network. Besides, synesthesia is a typical perceptual phenomenon in cognitive science. That is, a person can activate a sensory when stimulated by another sensory (e.g., grapheme-color synesthesia means a person can directly associate a colorful image when listening to music). The proposition of an effective associative memory model by combining human-like neural network and synesthesia with deep learning is a promising direction. A recent successful attempt was Dense Associative Memory [START_REF] Krotov | Dense associative memory for pattern recognition[END_REF], which combined associative memory with deep learning and achieved a good result on MNIST dataset.

Interpretable Network with Cognitive Mechanisms

For we human, it's difficult to understand how deep neural networks work and how they react towards a task. However, interpretable systems in many applications are of vital importance. For example, suppose that there is a person who may be in the early stage of cancer, the system based on deep neural networks needs to infer whether he is suffering from cancer. We can gather all features of the person as the input of DNNs, such as age, history of disease. The question is why we can trust the output of this system as we can not check the correctness. What if the process of inference can be understood or monitored (e.g., the decision tree) by an expert? Interpretability is important in these fields.

[13] proposed a tree regularization to interpret the neural network in the perspective of decision tree. This method can not train towards the typical backpropagation learning rule as the tree is undifferentiated. They suggested replacing trees with multi-layer perceptrons in the training phase, but this solution is not very elegent and does not create a really interpretable network indeed. According to psychological experiments [START_REF] Landau | The importance of shape in early lexical learning[END_REF], humans tend to assign the same name to similarly shaped items instead of items with similar color, texture or size. [START_REF] Vinyals | Matching networks for one shot learning[END_REF] proposed shape MN with inception network, which achieved better performance than several state-of-the-art methods in the field of one-shot learning on ImageNet. And [START_REF] Ritter | Cognitive psychology for deep neural networks: A shape bias case study[END_REF] found that this kind of networks that exhibits a similar shape bias to that observed in humans. Cognitive mechanisms like shape bias, decision and inference can help design more interpretable neural networks.

Cognition-based Deep Reinforcement Learning

Deep reinforcement learning has raised a lot of interests nowadays. However, due to the uncertainty of the state space and the complexity of the reward function, it is difficult for the traditional trial-and-error strategies to associate continuous actions with reward. Imagination is utilized to make use of the knowledge embedded in the model. However, deep reinforcement learning is still in its early stage.

As decision making and feedback mechanism are very similar to that of humans, there is a trend to apply cognitive mechanisms to reinforcement learning. As for attention mechanism, [START_REF] Sorokin | Deep attention recurrent q-network[END_REF] proposed the Deep Attention Recurrent Q-Network (DARQN), which greatly outperformed the traditional Deep Q-Network (DQN) on Atari 2600 games by combining what they called "soft" and "hard" attention mechanisms. Besides, [START_REF] Choi | Multi-focus attention network for efficient deep reinforcement learning[END_REF] used a multi-focus attention network where the agent can give attention to multiple important elements. This model achieved better performance than the traditional DARQN. Further, [START_REF] Oh | Control of memory, active perception, and action in minecraft[END_REF] extended the typical LSTM-based memory network to choose more sophisticated addressing schemes over the past k frames by using memory mechanism. [START_REF] Parisotto | Neural map: Structured memory for deep reinforcement learning[END_REF] proposed a spatially structured 2D memory image that is capable of learning to store arbitrary information about the environment over long time lags. As for our human knowledge mechanism, in which field we call usually transfer learning. What's more, a novel policy distillation (i.e., knowledge-based reinforcement learning policy) architecture was proposed by [START_REF] Yin | Knowledge transfer for deep reinforcement learning with hierarchical experience replay[END_REF] for deep reinforcement learning. This architecture was well organized by implementing task-specific high-level convolutional features as the inputs to the multi-task policy network. However, how to hierarchically reconstruct the knowledge and uncover the hidden characteristics, how to abstract our knowledge and experience for the feasibility to deal with unstructured data by fusion, how to design a generalized attention selection network, may remain issues that lead the future research direction in this field.

Conclusion

Cognition-based deep learning has gained widely interests recent years. Several core functions of cognitive science (i.e. attention, memory) and knowledge, are used to design more dynamic and robust systems based on deep neural network. We reviewed the recent progress related to this field. Meanwhile, deep neural networks are not interpretable to our human brains. We can design a more interpretable neural network in the perspective of cognitive science. Finally, we proposed a general framework of cognition-based deep learning and made assumptions of the essential future directions towards this field.

Fig. 1 :

 1 Fig. 1: General framework of cognition-based deep learning

Acknowledgment

This research was partially supported by the Programme of Introducing Talents of Discipline to University (No. B13043), the National Natural Science Foundation of China (No. 61773312, 61790563).


Akemi Gálvez

Andrés Iglesias
email: iglesias@unican.es

Improved Cuckoo Search with Luus-Jakoola Heuristics for the IFS Inverse Problem of Binary Self-Similar Fractal Images

Keywords: swarm intelligence, hybrid methods, improved cuckoo search algorithm, Luus-Jakoola heuristics, iterated function systems, self-similar fractal images

This paper addresses the following problem: how to reconstruct a given binary self-similar fractal image through iterated functions systems. This means to obtain an iterated function system (IFS) whose attractor is a good approximation of the input image. This problem is known to be a very difficult multivariate nonlinear continuous optimization problem. To tackle this issue, this paper introduces a new hybrid method comprised of a modification of the original cuckoo search method for global optimization called improved cuckoo search (ICS) along with the Luus-Jakoola heuristics for local search. This hybrid methodology is applied to three fractal examples with 3, 4, and 26 contractive functions. Our experimental results show that the method performs very well and provides visually satisfactory solutions for the instances in our benchmark. The numerical values of the similarity index used in this work also show that the results are not optimal yet, suggesting that the method might arguably be further improved.

Introduction

Fractals are one of the most challenging and intriguing mathematical shapes ever defined. Basically, they are geometric figures created by repeating a simple process over and over so that it yields a self-similar pattern across different scales. Interestingly, in the case of fractals, the scale factor of this replicating pattern is not an integer number, but a real one. Such a number is called the fractal dimension and it is usually larger than the topological dimension of the fractal [START_REF] Falconer | Fractal Geometry: Mathematical Foundations and Applications[END_REF][START_REF] Gutiérrez | A Mathematica package for the analysis and control of chaos in nonlinear systems[END_REF]. Fractals have become ubiquitous objects in popular culture, particularly since the 80s of last century, owing to the technological advances in hardware and software and the widespread availability of personal computers. They are also very popular in science due to their ability to describe many growing patterns and natural structures commonly found in real-life objects: branches of trees, river networks, coastlines, mountain ranges, and so on. Furthermore, fractals have found remarkable applications in computer graphics, scientific visualization, image processing, dynamical systems, telecommunications, medicine, biology, arts, and many other fields [START_REF] Barnsley | Fractals Everywhere[END_REF][START_REF] Falconer | Fractal Geometry: Mathematical Foundations and Applications[END_REF][START_REF] Gutiérrez | A Mathematica package for the analysis and control of chaos in nonlinear systems[END_REF][START_REF] Gutiérrez | Analyzing the multifractal structure of DNA nucleotide sequences[END_REF][START_REF] Gutiérrez | Generating and rendering fractal images[END_REF].

There are several methods described in the literature to obtain fractal images. They include the Brownian motion, escape-time fractals, finite subdivision rules, L-systems, strange attractors of dynamical systems, and many others [START_REF] Barnsley | Fractals Everywhere[END_REF][START_REF] Falconer | Fractal Geometry: Mathematical Foundations and Applications[END_REF]. One of the most popular methods is the Iterated Function Systems (IFS), originally conceived by J.E. Hutchinson [START_REF] Hutchinson | Fractals and self similarity[END_REF] and popularized by M. Barnsley in [START_REF] Barnsley | Fractals Everywhere[END_REF]. Roughly, an IFS consists of a finite system of contractive maps on a complete metric space. It can be proved that the Hutchinson operator over the set of all compact subsets of this space has a unique non-empty compact fixed set for the induced Hausdorff metric, called the attractor of the IFS. The graphical representation of this attractor is (at least approximately) a self-similar fractal image. Conversely, each self-similar fractal image can be represented by an IFS. Obtaining the parameters of such IFS is called the IFS inverse problem. Basically, it consists of solving an image reconstruction problem: given a fractal image, compute the IFS whose attractor approximates the input image accurately.

This IFS inverse problem has shown to be extremely difficult. In fact, the general case is still unsolved and only partial solutions have been reached so far. In this paper we propose a new approach to address this problem for the case of binary fractal images. Our methodology consists of the hybridization of a bio-inspired metaheuristics based on the cuckoo search algorithm for global optimization and a local search procedure. In particular, we consider a modification of the original cuckoo search method called the improved cuckoo search (ICS), which is based on the idea of allowing the method parameters to change over the generations [START_REF] Valian | Improved cuckoo search for reliability optimization problems[END_REF]. This method is hybridized with the Luus-Jakoola (LJ) heuristics, a search method aimed at improving the local search step to refine the quality of the solution.

The structure of this paper is as follows: Section 2 introduces the basic concepts and definitions about the iterated function systems and the IFS inverse problem. Then, Section 3 describes the original and the improved cuckoo search algorithms. Our proposed method is described in detail in Section 4, while the experimental results are briefly discussed in Section 5. The paper closes with the main conclusions and some ideas about future work in the field.

Basic Concepts and Definitions

Iterated Function Systems

An Iterated Function System (IFS) is a finite set Øφ i Ù i 1,...,η of contractive maps φ i : Ω Ω defined on a complete metric space M ÔΩ, ΨÕ, where Ω R n and Ψ is a distance on Ω. We refer to the IFS as W ØΩ; φ i , . . . , φ η Ù. For visualization purposes, in this paper we consider that the metric space ÔΩ, ΨÕ is R 2 along with the Euclidean distance d 2 , which is a complete metric space. Note, however, that our method can be applied to any other complete metric space of any dimension without further modifications. In this two-dimensional case, the affine transformations φ κ are of the form:

ξ ¦ 1 ξ ¦ 2 φ κ ξ 1 ξ 2 θ κ 11 θ κ 12 θ κ 21 θ κ 11 . ξ 1 ξ 2 σ κ 1 σ κ 2 (1)
or equivalently: Φ κ ÔΞÕ Θ κ .Ξ Σ κ where Σ κ is a translation vector and Θ κ is a 2 ¢ 2 matrix with eigenvalues λ κ 1 , λ κ 2 such that λ κ j 1. In fact, µ κ detÔΘ κ Õ 1 meaning that φ κ shrinks distances between points. Let us now define a transformation called the Hutchinson operator, Υ , on the compact subsets of Ω, HÔΩÕ, by:

Υ ÔBÕ η κ 1 φ κ ÔBÕ (2)
with B È HÔΩÕ. If all the φ κ are contractions, Υ is also a contraction in HÔΩÕ with the induced Hausdorff metric [START_REF] Barnsley | Fractals Everywhere[END_REF][START_REF] Hutchinson | Fractals and self similarity[END_REF]. Then, according to the fixed point theorem, Υ has a unique fixed point, Υ ÔAÕ A, called the attractor of the IFS.

Consider a set of probabilities P Øω 1 , . . . , ω η Ù, with η κ 1 ω κ 1. There exists an efficient method, known as probabilistic algorithm, for the generation of the attractor of an IFS. It follows from the result ØΞ j Ù j A provided that Ξ 0 È Ω, where: Ξ j φ κ ÔΞ j¡1 Õ with probability ω κ 0, see [START_REF] Elton | An Ergodic Theorem for Iterated Maps[END_REF]. Picking an initial point Ξ 0 , one of the mappings in the set Øφ i , . . . , φ η Ù is chosen at random using the weights Øω 1 , . . . , ω η Ù. The selected map is then applied to generate a new point, and the same process is repeated again with the new point and so on. As a result of this stochastic iterative process, we obtain a sequence of points that converges to the fractal as the number of points increases [START_REF] Barnsley | Fractals Everywhere[END_REF][START_REF] Gutiérrez | A multifractal analysis of IFSP invariant measures with application to fractal image generation[END_REF].

The Collage Theorem

The Collage Theorem basically says that any digital image I can be approximated through an IFS [START_REF] Barnsley | Fractals Everywhere[END_REF][START_REF] Gutiérrez | A multifractal analysis of IFSP invariant measures with application to fractal image generation[END_REF]. In particular, it states that given a non-empty compact subset I È HÔΩÕ, the Hausdorff metric HÔ., .Õ, a non-negative real threshold value ǫ 0, and an IFS W ØΩ; φ i , . . . , φ η Ù on Ω with contractivity factor 0 s 1 (the maximum of the contractivity factors

s κ of maps φ κ ), if H ÔI, Υ ÔIÕÕ H ¢ I, η ä κ 1 φ κ ÔIÕ ª ǫ then H ÔI, AÕ ǫ 1 ¡ s , where A is the attractor of the IFS. That is: H ÔI, AÕ 1 1 ¡ s H £ I, η κ 1 φ κ ÔIÕ « .

The IFS Inverse Problem

Suppose that we are given an initial fractal image F . The Collage Theorem says that it is possible to obtain an IFS W whose attractor has a graphical representation F that approximates F accurately according to a similarity function S, which measures the graphical distance between F and F [START_REF] Barnsley | Fractals Everywhere[END_REF]. Note that once W is computed, F Υ ÔI Õ for any (not necessarily fractal) initial image I . Mathematically, this means that we have to solve the optimization problem: minimize

ØΘκ,Σκ,ωκÙκ 1,...,η S F , Υ ÔI Õ ¨(3)
The problem ( 3) is a continuous constrained optimization problem, because all free variables in ØΘ κ , Σ κ , ω κ Ù i are real-valued and must satisfy the condition that the corresponding functions φ κ have to be contractive. It is also a multimodal problem, since there can be several global or local minima of the similarity function. The problem is so difficult that only partial solutions have been reported so far, but the general problem still remains unsolved to a large extent. In this paper we address this problem by using a hybrid approach based on the cuckoo search algorithm described in next paragraphs.

3 The Cuckoo Search Algorithms

Original Cuckoo Search (CS)

The Cuckoo search (CS) is a powerful metaheuristic algorithm originally proposed by Yang and Deb in 2009 [START_REF] Yang | Cuckoo search via Lévy flights[END_REF]. Since then, it has been successfully applied to difficult optimization problems [START_REF] Gálvez | Cuckoo search with Lévy flights for weighted Bayesian energy functional optimization in global-support curve data fitting[END_REF][START_REF] Iglesias | Cuckoo search with Lévy flights for reconstruction of outline curves of computer fonts with rational Bézier curves[END_REF][START_REF] Yang | Nature-Inspired Metaheuristic Algorithms[END_REF][START_REF] Yang | Engineering optimization by cuckoo search[END_REF]. The algorithm is inspired by the obligate interspecific brood-parasitism of some cuckoo species that lay their eggs in the nests of host birds of other species to escape from the parental investment in raising their offspring and minimize the risk of egg loss to other species, as the cuckoos can distributed their eggs amongst a number of different nests. This interesting and surprising breeding behavioral pattern is the metaphor of the cuckoo search metaheuristic approach for solving optimization problems. In the cuckoo search algorithm, the eggs in the nest are interpreted as a pool of candidate solutions of an optimization problem while the cuckoo egg represents a new coming solution. The ultimate goal of the method is to use these new (and potentially better) solutions associated with the parasitic cuckoo eggs to replace the current solution associated with the eggs in the nest. This replacement, carried out iteratively, will eventually lead to a very good solution of the problem.

In addition to this representation scheme, the CS algorithm is also based on three idealized rules [START_REF] Yang | Cuckoo search via Lévy flights[END_REF][START_REF] Yang | Engineering optimization by cuckoo search[END_REF]:

1. Each cuckoo lays one egg at a time, and dumps it in a randomly chosen nest; 2. The best nests with high quality of eggs (solutions) will be carried over to the next generations; 3. The number of available host nests is fixed, and a host can discover an alien egg with a probability p a È Ö0, 1×. In this case, the host bird can either throw the egg away or abandon the nest so as to build a completely new nest in a new location. For simplicity, this assumption can be approximated by a fraction p a of the n nests being replaced by new nests (with new random solutions at new locations). The basic steps of the CS algorithm are summarized in the pseudocode shown in Table 1. Basically, the CS algorithm starts with an initial population of n host nests and it is performed iteratively. The initial values of the jth component of the ith nest are determined by the expression x j i Ô0Õ rand.Ôup j i ¡low j i Õ low j i , where up j i and low j i represent the upper and lower bounds of that jth component, respectively, and rand represents a standard uniform random number on the interval Ô0, 1Õ. With this choice, the initial values are within the search space domain. These boundary conditions are also controlled in each iteration step.

For each iteration t, a cuckoo egg i is selected randomly and new solutions x t 1 i are generated by using the Lévy flight. According to the original creators of the method, the strategy of using Lévy flights is preferred over other simple random walks because it leads to better overall performance of the CS. The general equation for the Lévy flight is given by:

x t 1 i x t i α levyÔλÕ (4)
where t indicates the number of the current generation, and α 0 indicates the step size, which should be related to the scale of the particular problem under study. The symbol is used in Eq. ( 4) to indicate the entry-wise multiplication. Note that Eq. ( 4) is essentially a Markov chain, since next location at generation t 1 only depends on the current location at generation t and a transition probability, given by the first and second terms of Eq. ( 4), respectively. This transition probability is modulated by the Lévy distribution as:

levyÔλÕ t ¡λ , Ô1 λ 3Õ (5)
which has an infinite variance with an infinite mean. From the computational standpoint, the generation of random numbers with Lévy flights is comprised of two steps: firstly, a random direction according to a uniform distribution is chosen; then, the generation of steps following the chosen Lévy distribution is carried out. The authors suggested to use the Mantegna's algorithm for symmetric distributions (see [START_REF] Yang | Engineering optimization by cuckoo search[END_REF] for details), which computes the factor:

φ ¤ ¥ Γ Ô1 βÕ.sin ¡ π. β 2 © Γ ¡¡ 1 β 2 © . β.2 β¡1 2 © ¬ 1 β (6)
where Γ denotes the Gamma function and β 3 2 in the original implementation by Yang and Deb [START_REF] Yang | Engineering optimization by cuckoo search[END_REF]. This factor is used in Mantegna's algorithm to compute the step length ς as:

ς u v 1 β
, where u and v follow the normal distribution of zero mean and deviation σ 2 u and σ 2 v , respectively, where σ u obeys the Lévy distribution given by Eq. ( 6) and σ v 1. Then, the stepsize ζ is computed as ζ 0.01 ς Ôx ¡ x best Õ. Finally, x is modified as: x x ζ.∆ where ∆ is a random vector of the dimension of the solution x and that follows the normal distribution N Ô0, 1Õ. The CS method then evaluates the fitness of the new solution and compares it with the current one. In case the new solution brings better fitness, it replaces the current one. On the other hand, a fraction of the worse nests (according to the fitness) are abandoned and replaced by new solutions so as to increase the exploration of the search space looking for more promising solutions. The rate of replacement is given by the probability p a , a parameter of the model that has to be tuned for better performance. Moreover, for each iteration step, all current solutions are ranked according to their fitness and the best solution reached so far is stored as the vector x best .

Improved Cuckoo Search (ICS)

The improved cuckoo search (ICS) method was proposed in [START_REF] Valian | Improved cuckoo search for reliability optimization problems[END_REF] to enhance the performance of the original CS. It is based on the idea of allowing its parameters p a and α to change over the generations, as opposed to their fixed values in the original CS. In ICS the parameter p a is modified as:

p t a p aM ¡ p aM ¡ p am Λ t (7)
where the subscripts M and m are used to indicate the maximum and minimum values of the parameter respectively, and Λ indicates the total number of iterations. According to Eq. ( 7), the parameter p a is now decreased linearly with the number of iterations from a maximum value p aM until a minimum one, p am . At early iterations, its value is high to enforce the diversity of solutions in the algorithm. This diversity is decreasing over the time so as to intensify the search using the best candidates of the population in final iterations for a better finetuning of the solutions. The parameter α, also assumed constant in the CS, is primarily used to promote exploration of the search space. Therefore, it makes sense to modify it dynamically starting from a high value, α M , to perform a extensive exploration and gradually reducing it until a low value, α m , to promote exploitation and eventually homing into the optimum, in a rather similar way to the inertia weight in PSO. Consequently, it is modified as:

α t α M Exp ¤ ¦ ¦ ¥ Ln ¢ α m α M ª Λ t ¬ AE AE (8)
4 Proposed Approach

Hybrid ICS with Luus-Jakoola Heuristics

To address the IFS inverse problem described in Section 2.2, we propose a new hybrid scheme for proper balance between exploration and exploitation. Firstly, we consider the improved cuckoo search method for global optimization described in Section 3.2. This modified scheme is improved by its hybridization with a local search procedure. In particular, we apply the Luus-Jaakola (LJ) method, a gradient-free heuristics firstly proposed in [START_REF] Luus | Optimization by direct search and systematic reduction of the size of search region[END_REF] to solve nonlinear programming problems. LJ starts with an initialization step, where random uniform values are chosen within the search space by computing the upper and lower bounds for each dimension. Then, a random uniform value in-between is sampled for each component. This value is added to the current position of the potential solution to generate a new candidate solution, which replaces the current one only when the fitness improves; otherwise, the sampling space is multiplicatively decreased by a factor (usually of value 95%, but other values can also be used). In practice, we found that it is better to consider a self-adaptive size for this factor, with the effect of speeding up the convergence to the steady state. This process is repeated iteratively. With each iteration, the neighborhood of the point decreases, so the procedure eventually collapses to a point.

Application to the IFS inverse problem

Given a 2D self-similar binary fractal image I comprised of η functions φ κ , we apply our hybrid method to solve the IFS inverse problem. We consider an initial population of χ individuals ØC i Ù i 1,...,χ , where each individual

C i ØC κ i Ù κ
is a collection of η real-valued vectors C i κ of the free variables of Eq. ( 1), as: These individuals are initialized with uniform random values in Ö¡1, 1× for the variables in Θ κ and Σ κ , and in Ö0, 1× for the ω i κ , such that η κ 1 ω i κ 1. After this initialization step, we compute the contractive factors µ κ and reinitialize all functions φ κ with µ κ 1 to ensure that only contractive functions are included in the initial population. Before applying our method, we also need to define a suitable fitness function. In this paper we use the Hamming distance: the fractal images are stored as bitmap images of 0s and 1s for a given resolution defined by a mesh size parameter, m s . Then, we divide the number of different values between the original and the reconstructed matrices by the total number of boxes in the image. This yields the normalized similarity error rate index between both images, denoted by S , the fitness function used in this work.

C κ i Ôθ κ,i 1,1 , θ κ,i 1,2 , θ κ,i 2,1 , θ κ,i 2,2 σ κ,i 1 , σ κ,i 2 ω i κ Õ (9)

Parameter Tuning

It is well-known that the parameter tuning of metaheuristic methods is troublesome and problem-dependent. The cuckoo search is specially advantageous in this regard, as it depends on only two parameters: the population size, χ, set to χ 100, and the probability p a , calculated taking: p aM 0.5 and p am 0.005 in Eq. [START_REF] Gálvez | KETpic Matlab binding for efficient handling of fractal images[END_REF]. Moreover, the method is executed for Λ iterations. In our simulations, we found that Λ 1500 is enough to reach convergence in all cases. Our hybrid method also requires to define suitable values for α M and α m in Eq. ( 8). Similar to [START_REF] Valian | Improved cuckoo search for reliability optimization problems[END_REF], in this work they are set to 0.5 and 0.01, respectively. Finally, our method requires to define the mesh size, ν, set to ν 80 in this work.

Experimental Results

Our method has been applied to several examples of fractals. Only three of them are included here because of limitations of space: rotated triangle, Crystal, and the AIAI-2018 fractal (especially created for this paper). They are shown in Figs. 1 to 3, respectively. The input fractal images are displayed twice in each figure, one in red and another with one color for each individual contractive function. As the reader can see, the three fractals are comprised of 3, 4, and 26 functions, respectively. The application of our method to these input images returns the IFS minimizing the S index, which are then used to render the reconstructed fractal images, shown in blue and with different colors as above.

As the reader can see, although the matching is not optimal, our method captures the underlying structure of the fractal images with good visual quality. This is a remarkable result because our initial population is totally random, meaning that their corresponding images at early generations are all totally different from the given image. Our method is able to obtain a final image that replicates well the input image and is also a self-similar fractal for all instances number of contractive functions η, number of free variables of the optimization problem, and best and mean value of the S index for 20 independent executions of the method. As the reader can see, the similarity index for the best execution yields errors ranging from 20% to 30%, depending on the example. Although the reconstructed images are perfectly recognizable in all cases, this similarity error increases with the complexity of the model, with the third ex-ample exhibiting the larger value. This result is very reasonable because this example requires to solve an optimization problem with many more variables than the other two examples. In addition, the numerical values of the similarity index used in this work indicate that the results are not optimal yet, suggesting that the method might arguably be further improved.

All computations in this paper have been performed on a 2.6 GHz. Intel Core i7 processor with 16 GB. of RAM. The source code has been implemented by the authors in the native programming language of the popular scientific program Matlab version 2015a and using the numerical libraries for fractals in [START_REF] Gálvez | IFS Matlab generator: a computer tool for displaying IFS fractals[END_REF][START_REF] Gálvez | Matlab-based KETpic add-on for generating and rendering IFS fractals[END_REF][START_REF] Gálvez | KETpic Matlab binding for efficient handling of fractal images[END_REF][START_REF] Gálvez | IFSGen4LaTeX: Interactive graphical user interface for generation and visualization of iterated function systems in L A T E X[END_REF]. Regarding the CPU times, they depend on the complexity of the model and its number of contractive functions. In general, we noticed that the method is slow and time-consuming. For illustration, each single execution takes about 25 45 minutes for the first two examples, and more than 1 hour for the third one.

Conclusions and Future Work

In this paper we introduced a new hybrid method to solve the following optimization problem: given any binary self-similar fractal image, the goal is to determine an IFS whose attractor is a good approximation of this input image. This problem, called the IFS inverse problem, is known to be a very difficult multivariate nonlinear continuous optimization problem. In this new hybrid method, a modification of the original cuckoo search method for global optimization called improved cuckoo search (ICS) is coupled with the Luus-Jakoola heuristics for local search. This hybrid methodology is applied to three fractal examples: rotated triangle, crystal, and the AIAI-2018 fractal. The method replicates the input images very well, yielding visually satisfactory results in all cases.

The numerical results show however that our final solutions are not optimal yet, so the method might be improved in several ways. On one hand, we want to modify our fitness function to obtain a better measure of the quality of the reconstructed fractal. On the other hand, we would like to obtain automatically the optimal value of the number of contractive functions for the IFS. We also wish to extend our results to the cases of images that are neither binary nor self-similar. Reducing our CPU times is also one of our future goals in the field.

Fig. 1 .

 1 Fig. 1. Example of the rotated triangle fractal: (left) original (top) and reconstructed image (bottom); (right) their different contractive functions with different colors.

Fig. 2 .

 2 Fig. 2. Example of the Crystal fractal: (left) original (top) and reconstructed image (bottom); (right) their different contractive functions with different colors.

Fig. 3 .

 3 Fig. 3. Example of the AIAI-2018 fractal (from top to bottom): original image in red, original image with different colors for each contractive function, reconstructed image in blue, and reconstructed image with different colors for each contractive function.

Table 1 .

 1 Cuckoo search algorithm via Lévy flights as originally proposed in[START_REF] Yang | Cuckoo search via Lévy flights[END_REF][START_REF] Yang | Engineering optimization by cuckoo search[END_REF]. ÔxÕ, x Ôx1, . . . , xDÕ T Generate initial population of n host nests xi Ôi 1, 2, . . . , nÕ while Ôt M axGenerationÕ or (stop criterion) Get a cuckoo (say, i) randomly by Lévy flights Evaluate its fitness Fi Choose a nest among n (say, j) randomly if (Fi FjÕ Replace j by the new solution end A fraction (pa) of worse nests are abandoned and new ones are built via Lévy flights Keep the best solutions (or nests with quality solutions) Rank the solutions and find the current best end while Postprocess results and visualization end

	Algorithm: Cuckoo Search via Lévy Flights
	begin
	Objective function f

Table 2 .

 2 Numerical results of the best and mean values of the S index for the examples in Figs. 1 to 3 with the proposed method.

	Example	η # free variables S (best) S (mean)
	Rotated triangle fractal 3	21	0.1952	0.2113
	Crystal fractal	4	28	0.2038	0.2194
	AIAI-2018 fractal	26	182	0.2974	0.3125
	in our benchmark. Our graphical results indicate that our method performs very
	well, as it provides visually satisfactory solutions for the IFS inverse problem.
	This good visual appearance is confirmed by our numerical results, reported
	in

Table 2 .

 2 For each fractal example (in rows), the table shows (in columns):

Acknowledgements

This research work has received funding from the project PDE-GIR of the European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 778035, the Spanish Ministry of Economy and Competitiveness (Computer Science National Program) under grant #TIN2017-89275-R of the Agencia Estatal de Investigación and European Funds FEDER (AEI/FEDER, UE), and the project #JU12, jointly supported by public body SODERCAN and European Funds FEDER (SODERCAN/FEDER UE). We also thank Toho University and the University of Cantabria for their support for this research work.