Hengxun Li

Chun Liao
email: liaochun@iie.ac.cn

Guangjun Hu

Ning Wang

A Cyclic Cascaded CRFs Model for Opinion Targets Identification Based on Rules and Statistics

Keywords: opinion targets identification, cyclic cascaded CRFs model, rulebased, statistic-based

Opinion sentences on e-commerce platform, microblog and forum contain lots of emotional information. And opinion targets identification plays an import role in huge potential commercial value mining, especially in sales decision making and development trend forecasting. Traditional CRFs-based method has achieved a pretty good result to a certain extent. However, its discovery ability of out-of-vocabulary words and optimization of the mining model are both insufficient. We propose a novel cyclic cascaded CRFs model for opinion targets identification which incorporates rule-based and statistic-based methods. The approach acquires candidate opinion targets through part-of-speech, syntactic and semantic rules, and integrates them in a cyclic cascaded CRFs model for the accurate opinion targets identification. Experimental results on COAE2014 dataset show the outperformance of this method.

Introduction

With the development of the Internet, social platform has gradually integrated into people's lives, resulting in the increasing expansion of mass information. More and more opinion sentences on the Internet are generating. For the government, business or individual, the study of these opinion words is of great significance. Compared with regular grammar and news text, opinion sentences on social plat-form are more colloquial, interactive, and also contain a large number of advertisements and junk information. These bring new challenge to opinion targets identification, and how to effectively extract the useful information has become more and more important.

Sentiment analysis, also called opinion mining, is to process, induce and infer the subjective texts [START_REF] Zhao | Sentiment Analysis[J][END_REF]. Sentimental elements extraction is the basis of sentiment analysis. Sentimental elements extraction is to extract the opinion elements in the sentence, including opinion words (such as "好"), opinion targets (such as "三星手机"), opinion holder (such as "张三" in the sentence "张三认为……"). In this paper, we mainly study opinion targets identification.

Traditional CRFs-based method has achieved a pretty good result to a certain extent.

However, its discovery ability of out-of-vocabulary words and optimization of the mining model are both insufficient. We propose a novel cyclic cascaded CRFs model for opinion targets identification which incorporates rule-based and statistic-based methods. The approach acquires candidate opinion targets through part-of-speech, syntactic and semantic rules, and integrates them in a cyclic cascaded CRFs model for the accurate opinion targets identification.

Existing opinion targets identification methods cannot comprehensively discovery the out-of-vocabulary words, and do not optimize the mining model. To address these shortcomings, it is intuitive to consider the combination of rule-based and statisticbased methods, and at the same time take special features of opinion sentences on social platform into consideration. In this paper, we propose a novel cyclic cascaded CRFs model for opinion targets identification which incorporates rule-based and statistic-based methods. The approach acquires candidate opinion targets through partof-speech, syntactic and semantic rules, and integrates them in a cyclic cascaded CRFs model for the accurate opinion targets identification. In experiments on the COAE 2014 dataset we find that our method can substantially extract opinion targets more effectively under different evaluation metrics.

Related Work

The methods of opinion targets extraction are mainly divided into two categories: unsupervised and supervised methods. In the unsupervised methods, Hu and Liu [START_REF] Hu | Mining and summarizing customer reviews[END_REF] used association rules to excavate opinion targets and regarded the top-frequency words as opinion targets. Li and Zhou [START_REF] Li | A unified graph model for sentencebased opinion retrieval[C]// Meeting of the Association for Computational Linguistics[END_REF]extracted tuples like <emotional words, opinion targets> based on emotional and topic-related lexicons. Popescu and Nguyen [START_REF] Popescu | Extracting Product Features and Opinions from Reviews[M]// Natural Language Processing and Text Mining[END_REF] extracted properties of products with mutual information. Yao [START_REF] Yao | Research on Semantic Orientation Analysis for Topics in Chinese Sentences[END_REF] used domain ontology to extract the topics and their attributes from a sentence, and summed up the subject-predicate structure rules based on syntactic analysis for opinion targets identification. Liu [START_REF] Liu | Comment Target Extraction and Sentiment Classification[END_REF] used syntactic analysis to obtain the candidates , and then combined PMI with noun pruning algorithm to decide the final opinion targets. Besides, in the supervised methods, Zhuang [START_REF] Zhuang | Movie review mining and summarization[END_REF] proposed a multi-knowledge-based approach which integrated WordNet, statistical analysis and movie knowledge. Jakob [START_REF] Jakob | Extracting opinion targets in a singleand cross-domain set-ting with conditional random fields[END_REF] modelled the task as a sequence labelling question and employed CRFs for opinion targets extraction. Wang [START_REF] Rongyang | Feature Engineering for CRFs Based Opinion Target Extraction[END_REF] proposed a method of opinion targets identification based on CRFs, and selected morphology, dependency, relative position and semantics as features.

However, existing opinion targets extraction methods only took lexical-related features into account. Consequently, considering the specific features of Chinese microblog, we propose a new method for opinion targets extraction towards microblog using syntax and semantics in which we adopt a new approach of PDSP for domain lexicon construction and select groups of features for CRFs.

Candidate Opinion Targets Identification Based on Rules

The task of candidate opinion targets identification is automatically extracting the opinion targets using rule-based methods. Considering the importance of syntax and semantics in opinion targets identification, we propose a method of candidate opinion targets identification which incorporates POS, dependency structure and semantic role. Opinion targets are usually nouns or noun phrases. Through statistics on corpus, we design six templates based on Part-of-Speech which are shown in Table 1 where n, adj, adv, aw,cmp and OTrepresents for noun,adjective, degree adverb, advocating word, comparative word and opinion target. Here we get adv and aw from Hownet , and acquire cmp from [START_REF] Zhang | Chinese Comparative Sentence Identification Based on Multi-feature Fusion[END_REF]. As we all know, when we express opinions towards a product, we need some opinion words which usually have strong semantic relation with the opinion targets. Therefore, we collect opinion words from Hownet and NTUSD1 andperform HIT-LTP2 for dependency parsingto discuss the relation "ATT" and "SBV" between opinion words and opinion targets,relation "COO" between already known opinion targets and unknown opinion targets.

As a necessary part of shallow semantic parsing, sematic role [START_REF] Hacioglu | Semantic role labelling using dependency trees[END_REF] occupies an important position in lexical and semantic analysis. People usually express opinions through opinion words in opinion sentences. And adjective andverb are two main forms of opinion words. Through investigation, we find when the opinion word are adjective, A0(agent) is opinion target. Furthermore, when the opinion word are verb, A1(patient) is opinion target.

CCCRFs: A Cyclic Cascaded CRFs Model for Opinion Targets Identification

In this paper, we propose a novel cyclic cascaded CRFs model for opinion targets identification which incorporates rule-based and statistic-based methods. The approach first acquires candidate opinion targets through method in 3. And then, this model adopts two-layer cascaded CRFs. In the first layer, we select opinion words and manual features for opinion words identification. And in the second layer, the outputs of the first layer are added as input and we select opinion words, candidate opinion targets and manual features for opinion targets identification. In each iteration, we choose sentences whose confidence value is larger than C as training data. And the remaining sentences are regarded as testing data.

Cascaded CRFs Model

CRFs(Conditional Random Fields, CRFs) is proposed by Lafferty [START_REF] Lafferty | Conditional Random Fields: Probabilistic Models For Segmenting And Labelling Sequence Data[END_REF] in 2001. Its chain structure is shown in Figure 1.

Fig.1. CRFs Model

Given a set of input random observed variables, this conditional probability distribution model can generate another set of implicit output random variables by training the model. CRFs are often used for sequence labelling tasks, such as part-ofspeech tagging, named entity recognition and so on.

However, in the actual labelling process, we find it exists nesting phenomenon. For example, in Chinese named entity recognition, other named entities elements, such as names, places will be included in organization name. And this situation has led to incorrect identification. To solve this problem, you need to refine these tasks, step by step and gradually completed. In this paper, we adopt CCRFs(Cascaded Conditional Random Fields) as shown in Figure 2 to solve the above problems.

CCRFs reduced the coupling relationship between different layers of the model. Each layer of the model can be built independently, and each sub task can be done independently without interfering with each other. The complexity has linear relationship with the number of the model layers. Before the high-level model, some of the necessary pre-treatment can be carried out in the output of the underlying model and filter some errors. Consequently, CCRFs can avoid error propagation and diffusion and further improve the performance.

Cyclic Model

The selection of training data is always a focus of machine learning methods. In order to improve the recall rate of this method, we add cyclic method under CCRFs through screening each experimental results. Figure 3 is the flowchart of Cyclic Cascaded CRFs Model. If the confidence C is greater than threshold, we add them into training corpus circularly. If not, we treat them as testing data. Then, this model loops as this until the iteration number reaching a certain value N. In cyclic model, for every opinion targets identification results, its confidence degrees C, can be calculated as follows.

C = 𝐶 1 × 𝐶 2 (1)
𝐶 1 is the confidence value of first layer in CCRF, and 𝐶 2 is the confidence value of second layer in CCRFs. These can be acquired from CRFs tool.

We selected sentences whose confidence value larger than M into training set, and the remainder continued as the testing data. Then we re-trained the model, and extract the results for N times iteration to get the final results.

Training Data

Testing Data

Feature Selection

In feature selection, we refer to the features which are employed by Jakob [START_REF] Jakob | Extracting opinion targets in a singleand cross-domain set-ting with conditional random fields[END_REF] and Lu [START_REF] Lu | Identifying opinion holders and targets with dependency parser in Chinese news texts[END_REF] in English and meanwhile put forward some new features based on the specific grammar of Chinese. Generally, we think opinion targets extraction is primarily related with four kinds of features which are named as lexical features, dependency features, relative position features and semantic features.

As words with the same Part-of-Speech usually appear around the opinion targets, we select the current word itself and the POS of current word as lexical features. Dependency parsing reflects the semantic dependency relations between core word and its subsidiaries words [START_REF] Li | Learning question classifiers[END_REF]. Consequently, we select whether the dependency between current word and core word exists, the dependency type, parent word and the POS of parent word as the dependency features. As we all know, since words which appear around emotional words are more likely to be opinion targets, we determine the boolean value by judging whether the distance between current word and emotional word is less than 5. Considering there is a strong relationship between the sematic roles and POS of emotional words, we select the sematic role name of current word and POS of emotional word in this sentence for CRFs.

Experiments and Analysis

In experiments, we firstly obtained candidate opinion targets through method in section 3, and then we employed CCCRFs with the candidate opinion targets and features in section 4 together to extract opinion targets.

5.1.Dataset

Through filtration, we finally obtain 5,000 normalized sentences with opinion orientation from COAE2014. And we perform segmentation, part-of-speech, syntactic parsing and semantic role labelling through LTP [START_REF] Che | Ltp: A chinese language technology platform[END_REF].In this paper, we conduct experiments on such a dataset and assess it with traditional Precision, Recall and Fmeasure under strict and lenient evaluations which respectively represents the extraction result is exactly the same or overlapped with the labelled one.

Parameter selection

In this section, we make comparing experiment on parameter selection of cyclic cascaded CRFs model. And the experiment results between loop number N and confidence value C in cyclic cascaded CRFs model are in Figure 4. From this figure we find that, it performs best when the confidence value C=0.9 and loop number N=4. We also find the curve is slowly tend to be stable under four confidence value C with the increase of loop number N. As the confidence value C increases, opinion sentences have been added to the training corpus completely and the training corpus is no longer increased, so the model tends to a stable state. Consequently, this experiment not only demonstrated the effectiveness of cyclic cascaded CRFs model, but also revealed the importance of parameter selection to opinion targets identification.

Comparing results with different methods of opinion targets identification

In this section, we compare different methods of opinion targets identification, rulebased method, CRFs-based method, cascaded CRFs-based method and cyclic cascaded CRFs-based method. To verify the effectiveness of cyclic cascaded CRFs model for opinion targets identification, we conduct experiments under different methods of opinion targets identification and obtain the experimental results as shown in Table 2 It can be seen that the effect of opinion targets identification is highly improved after adopting cyclic cascaded CRFs model, which is mainly because this method not only uses candidate opinion targets identification in section 3to obtain candidate opinion targets, but also adopts machine learning method of CCCRFs to make up for the defect of rule-based method and so as to reach a higher precision, recall and F-measure. So this experiment strongly demonstrates the effectiveness and applicability of cyclic cascaded CRFs model.

Conclusions and Future Work

In this paper we propose a cyclic cascaded CRFs model for opinion targets identification which takes rules and statistics into consideration. We combine the candidate opinion targets extraction into a cyclic cascaded CRFs model to get the final opinion targets. The experimental results show that it performs better than other baseline approaches.

In the future work, we will take the following points into consideration:

-Considering the various expressions of Chinese microblog, we should excavate more rules and extract the kernel sentence for opinion targets extraction.

-In this paper, we perform opinion targets extraction on sentence level. We will investigate the effect of opinion targets extraction on corpus level.

Fig. 3 .

 3 Fig.3. Cyclic Cascaded CRFs Model

Fig. 4 .

 4 Fig.4.Comparing experiments between loop number and confidence value in cyclic cascadedCRFs model

Table 1 .

 1 Part-of-Speech sequence templates

	Template	Example	Template	Example
	n+adv+adj	屏幕/OT 很好	adj+的+n	轻薄的机身/OT
	n+adj	外观/OT 漂亮	n+cmp+n	iphone/OT 不如三星/OT
	aw+n	认为蒙牛/OT	n+n	蒙牛牛奶/OT

Table 2 .

 2 . And the rule, CRFs, CCRFs and CCCRFs respectively represent for rule-based method, CRFs-based method, cascaded CRFs-based method and cyclic cascaded CRFs-based method. Results of opinion targets identification with different methods

	Method	Precision	Strict Evaluation Recall F-measure Precision Recall Lenient evaluation F-measure
	Rule	0.5870	0.3206	0.4147	0.6025	0.3971	0.4787
	CRFs	0.6780	0.4325	0.5281	0.7115	0.4600	0.5490
	CCRFs	0.6985	0.4595	0.5403	0.7674	0.4935	0.5729
	CCCRFs	0.7085	0.4752	0.5689	0.7803	0.5025	0.6113

http://www.datatang.com/data/11837

http://www.ltp-cloud.com/


Hang Gao
email: gao.hang@aliyun.com

Yuxing Peng
email: pengyuxing@aliyun.com

Songlei Jian
email: jiansonglei@aliyun.com

Incomplete Multi-View Clustering

Keywords: multi-view clustering, incomplete view clustering, spectral clustering

Real data often consists of multiple views (or representations). By exploiting complementary and consensus grouping information of multiple views, multi-view clustering becomes a successful practice for boosting clustering accuracy in the past decades. Recently, researchers have begun paying attention to the problem of incomplete view. Generally, they assume at least there is one complete view or only focus on two view problems. However, above assumption is often broken in real tasks. In this work, we propose an IVC algorithm for clustering with more than two incomplete views. Compared with existing works, our proposed algorithm (1) does not require any view to be complete, (2) does not limit the number of incomplete views, and (3) can handle similarity data as well as feature data. The proposed algorithm is based on the spectral graph theory and the kernel alignment principle. By aligning projections of individual views with the projection integration of all views, IVC exchanges the complementary grouping information of incomplete views. Consequently, projections of individual views are made complete and thereby resulting the consensus with accurate grouping information. Experiments on synthetic and real datasets demonstrate the effectiveness of IVC.

Introduction

Many datasets in real world are naturally comprised of heterogeneous views (or representations). Clustering with such type of data is commonly referred to as multi-view Clustering. With the assumption of complementary data representation and consensus decision of clusterings, multi-view clustering has the potential to dramatically increase the learning accuracy over single view clustering [START_REF] Bickel | Multi-view clustering[END_REF]. The main problem in multi-view clustering is how to integrate grouping information of individual views. Existing works can be roughly classified into three categories.

(1) Multi-kernel learning based approach. The most representative work of this category is Multi-kernel Kmeans [START_REF] Tzortzis | Kernel-based weighted multi-view clustering[END_REF]. It first uses kernel representation for each view, and then it incorporates different views by seeking optimal combination of multiple kernels of different views. (2) Subspace learning based approach. It obtains a latent consensus subspace shared by multiple views and cluster the instantces on the latent subspace. There are many research works in this category, including CCA-based methods [START_REF] Chaudhuri | Multi-view clustering via canonical correlation analysis[END_REF], spectral graph based methods [START_REF] Virginia R De Sa | Spectral clustering with two views[END_REF][START_REF] Kumar | A co-training approach for multi-view spectral clustering[END_REF][START_REF] Kumar | Co-regularized multi-view spectral clustering[END_REF], matrix factorization based methods [START_REF] Liu | Multi-view clustering via joint nonnegative matrix factorization[END_REF][START_REF] Guo | Convex subspace representation learning from multi-view data[END_REF]. [START_REF] Chaudhuri | Multi-view clustering via canonical correlation analysis[END_REF] Ensemble learning based approach. [START_REF] Bruno | Multiview clustering: A late fusion approach using latent models[END_REF] takes a decision in each individual view separately and then combines all decisions of distinct views to establish a consensus decision by determining cluster agreements/disagreements.

Traditional research assumes data are complete in all views. However, in many real applications, parts of instances are not available in some views. For example, in a news story clustering task, articles are collected from different on-line news sources. Only a part of news are reported in all views. No single source includes all news. Another example is image clustering. Images are based on multiple visual and textual features. Some images have only a fraction of visual or textual feature sets.

Recently, a few attempts have been made for multi-view clustering with incomplete views. The first work to deal with incomplete view clustering was proposed in [START_REF] Trivedi | Multiview clustering with incomplete views[END_REF]. It uses one view's kernel representation as the similarity matrix and complete the incomplete view's kernel using Laplacian regularization. However, this approach requires that there exists at least one complete view containing all the instances. Shao et.al [START_REF] Shao | Clustering on multiple incomplete datasets via collective kernel learning[END_REF] relax the above constraint. They collectively complete the kernel matrices of incomplete datasets by optimizing the alignment of shared instances of the datasets. Furthermore, a clustering algorithm is proposed based on the kernel canonical correlation analysis . However, this approach focus on two view problem. It can not exploit relation among more than two views. Li et.al proposed a Partial view clustering algorithm (PVC) [START_REF] Shao-Yuan | Partial multi-view clustering[END_REF]. Based on non-negative matrix factorization (NMF), PVC works by establishing a latent subspace where the instances corresponding to the same example in different views are close to each other. PVC concentrates on two views problem. Extending PVC to more views suffers from computational problem. In most recently, Shao et.al developed an incomplete view clustering algorithm (MIC) [START_REF] Shao | Multiple incomplete views clustering via weighted nonnegative matrix factorization with l2,1 regularization[END_REF]. MIC handles the situation of more than two incomplete views. With joint weighted non-negative matrix factorization, it learns a L 2,1 regularized latent subspace for multiple views. With mean value imputation initialization, MIC gives lower weights to the incomplete instances than the complete instances. During optimization, MIC pushes multiple views towards a consensus matrix iteratively. But, there are some limitations about MIC. It converges slowly and contains too many parameters, which makes it difficult to operate. Moreover, both PVC and MIC are NMF based method. Both of them inherit the limitations of NMF:

(1) It cannot well deal with data with negative feature values. while in many real applications, the non-negative constraints can not be satisfied. (2) It is essentially linear, and thus cannot disclose non-linear structures hidden in data, which limits its learning ability. (3) It only deals with feature values, while in some applications we know the similarities (relationships) of instances while the detailed feature values are unavailable. Yin et al. [START_REF] Yin | Incomplete multi-view clustering via subspace learning[END_REF] proposed a subspace learning algorithm. It utilizes a regression-like objective to learn a latent consensus representation. Besides, it explores the inter-view and intra-view relationship of the data examples by a graph regularization. However, it converges too slowly. It achieves optimal results with about one hundred iterations. This make it difficult to extend to more than two views.

In this paper, we focus on the problem of incomplete view clustering with more than two views. We propose a novel incomplete multi-view clustering (IVC) algorithm. Aiming at completing incomplete views, IVC first integrate inidividual views by collective specrtal decomposition. Then, IVC aligns each individual with the integration respectively. In this way, complementary grouping information is shared among views and missing values of incomplete views are estimated. With estimated individual views, IVC constructs the latent consensus space. At last, clustering solution is obtained by applying the standard spectral clustering on the consensus space. As compared with previous works, the proposed algorithm has several advantages: (1) It does not require any view to be complete.

(2) It does not limit the number of incomplete views. ( 3) It can handle similarity data (or kernel data) as well as feature data. ( 4) Since it has few parameters to be set, it is easy-implemented. ( 5) Due to the non-iterative optimization, it is efficient than most iterative algorithms such as MIC. Moreover, it shows better performance. We demonstrate it in the experiment.

The rest of this paper is organized as follows: In section 2, we give a brief review of the spectral clustering and the kernel alignment principle which is our basis. Section 3 presents details of the proposed algorithm. In section 4, we validate the proposed algorithm. Section 5 concludes the paper.

Preliminary

In this section, we give a brief review of the spectral clustering and the kernel alignment principle, which provide the necessary background and pave the way to the proposed algorithm.

Spectral Clustering

Spectral clustering is a theoretically sound and empirically successful clustering algorithm. It treats clustering as a graph partitioning problem. By making use of the spectrum graph theory, it project original data in a low-dimensional space that contains more discriminative grouping information. Algorithm 1 briefly descibe the spectral clustering algorithm [START_REF] Andrew | On spectral clustering: Analysis and an algorithm[END_REF] which is the basis of our work.

The equivalent optimization fomular of algorithm 1 is Equation 1.

max

U∈ N ×M T race U T LU , s.t.U T U = I (1)

Kernel Alignment

Kernel alignment is a measurement of similarity (or dissimilarity) between different kernels. Let S (1) and S (2) be two positive definite kernel matrices such that S (1) F = 0 and S (2) F = 0. Then, the dissimilarity between S (1) and S (2) is defined by Equation (2) [START_REF] Igel | Gradient-based optimization of kernel-target alignment for sequence kernels applied to bacterial gene start detection[END_REF], where S (1) , S (2)

F = N i=1 N j=1 S (1) i,j S (2)
i,j .

Algorithm 1 Normalized Spectral Clustering

Require: Similarity matrix: S ∈ N ×N , Number of clusters: K; 1: Compute the symmetrical normalized lapacian matrix L = D (-1/2) SD (-1/2) . 2: Compute the first K largest eigenvectors u1, u2, ...u K of L. 3: Let U ∈ N ×K be the matrix containing the first k eigenvectors u1, u2, ...u K . 4: Normalize the rows of matrix U by scaling the norm to be 1. 5: For i = 1, 2, ..., n, let y i ∈ K be the vector corresponding to the i-th row of U. 6: Cluster the points {y i }i=1,2,...,N with K-means algorithm into cluster C1, C2, ...C K . 7: return {C i }, i = 1, 2, ...K; ρ(S (1) , S (2) ) = S (1) , S

F S (1) F S (2) F (2)
,

Proposed Methods

In this section, we present the detail of the incomplete view clustering (IVC) algorithm. We first describe the IVC framework and present its objectives, and then describe the optimization procedures.

Model Description

Given V incomplete views and the similarity matrices are S (i) , i = 1, 2, ..., V . The cluster number is K. Incomplete views contain different numbers of observed values. In order to make these kernel matrices co-operable (or with the same size N ), we initialize incomplete kernels by filling missing entries with the corresponding average of the column ( i.e. early estimation). First, we exploit the discriminative grouping information of each individual view by spectral decomposition on its similarity matrix S (i) , i = 1, 2, ..., V . max

U (i) ∈ N ×K T race U (i) T L (i) U (i) , s.t. U (i) T U (i) = I (3)
Note that U (i) is a recasted matrix of the original feature matrix. Each row of U (i) is a new representation of an instance with lower dimension and more discriminative grouping information. Next, in order to make different views consistent, we push them towards a latent consensus matrix U * . Because U (i) is a projection of original feature matrix, S (i) = U (i) U (i) T can be seen as a new kernel representation. Similarly, the latent consensus kernel can be decomposed as S * = U * U * T , where U * is the latent projected matrix. Note that U (i) s are derieved by kernels with early estimation. We call U * as early consensus projection.

Borrowing the idea from kernel alignment, we measure the dissimilarity between early consensus and each view by Equation (4).

ρ(U * , U (i) ) = U * U * T U * U * T 2 F - U (i) U (i) T U (i) U (i) T 2 F 2 F (4)
Minimizing the sum of dissimilarities between early consensus and all individuals, we get objective function [START_REF] Kumar | A co-training approach for multi-view spectral clustering[END_REF], where λ i is the tradeoff between different views and expresses the importance of view i in clustering.

max

U * ∈ N ×K i λ i ρ(U * , U (i) ), (5)
Since that max

U (i) U (i) T 2 F = K , U * U * T 2 F = K,
U * ∈ N ×K i λ i T race(U (i) U (i) T U * U * T ) (6)
Now, we retransmit the early consensus back to individuals. Specifically, we reorder each individual view as

U (i) = U (i) a U (i) e
, where U . Then, we update each

U (i)
e by aligning U (i) with U ( * ) . According to Equation (4), we get the objective function [START_REF] Liu | Multi-view clustering via joint nonnegative matrix factorization[END_REF]. max

U (i) e T race( U * a U * e U * a U * e T U (i) a U (i) e U (i) a U (i) e T ) (7)
In this way, complementary grouping information is exchanged among incomplete individuals. With updated U (i) s, we construct the final consensus U * f by Equation ( 6). U * f contains more accurate grouping information than U * . At last, we apply standard K-means clustering on U * f to get the final decision.

Model Training

In this subsection, we demonstrate how does IVC optimizes Equation ( 6) and Equation [START_REF] Liu | Multi-view clustering via joint nonnegative matrix factorization[END_REF].

By the cyclic property of the trace, we transform optimization problem ( 6) into [START_REF] Guo | Convex subspace representation learning from multi-view data[END_REF], which is equivalent to a standard spectral clustering with graph laplacian v λ v U (v) .U (v) T . The solution of U ( * ) is just the optimal consensus eigen vectors of all individual views. max

U * ∈ n×K T race(U * T ( v λ i U (i) U (i) T )U * ) s.t. U * T U * = I (8)
Transforming and expanding Equation [START_REF] Liu | Multi-view clustering via joint nonnegative matrix factorization[END_REF] as Equation ( 9), then, taking its derivative w.r.t.

U (i)
e and setting it to zero, we get the solution as in Equation [START_REF] Trivedi | Multiview clustering with incomplete views[END_REF]. To the ends,

U (i) e is calculated. max U (i) e T race( U * a U * a T U * a U * e T U * e U * a T U * e U * e T U (i) a U (i) a T U (i) a U (i) e T U (i) e U (i) a T U (i) e U (i) e T ) (9)
U (i) e = -(U * a U * e T + U * e U * a T + +2U * e U * e T ) -1 × (U * e U * a T U (i) a + U * a U * a T U (i) a + U * e U * e T U (i) a + U * e U * a T U (i) a ) (10)
The specific procedure of IVC is summarized in algorithm 2. IVC first initializes incomplete kernels with early estimation. Then, it projects each individual view into a more discriminative space by spectral decomposition. Next, IVC establishes the early consensus projection, and thereby updating individual projections. With these updated individual projections, IVC constructs the final consensus projection.

Algorithm 2 The Proposed algorithm

Require:

Similarity matrices: S (i) , i = 1, 2, ...V ; Number of clusters: K; 1: Initialize all individual K (i) s with early estimation; 2: Do spectral decomposition for all S (i) s by Equation (3); 3: Calculate consensus eigenvectors U ( * ) by Equation ( 8

Experiment

Comparison methods

We compare the proposed IVC with several state-of-art methods. The details of comparison methods are as follows: different visual features using color, shape, and texture. χ2 distance matrices for different flower features (color, shape, texture) are used as three different views.

Reuters Multilingual Dataset (Reuters) 2 : This dataset contains six samples of 1200 documents, balanced over the 6 labels (E21, CCAT, M11, G-CAT, C15, ECAT). Each sample is made of 5 views (EN, FR, GR, IT, SP) on the same documents. The documents were initially in English, and the FR, GR, IT, and SP views corresponds to the words of their traductions respectively in French, German, Italian and Spanish.

Multi-feature digit Dataset (Mfeat) [START_REF] Lichman | UCI machine learning repository[END_REF]: This dataset consists of features of handwritten numerals ('0'-'9') extracted from a collection of Dutch utility maps. 200 patterns per class (for a total of 2,000 patterns) have been digitized in binary images. These digits are represented in terms of the following five feature sets (files): mfeat-fou, mfeat-fac, mfeat-kar, mfeat-pix, and mfeat-zer.

All original datasets are complete. We simulate incomplete views for them. In specific, we set incomplete ratio from 0% to 90% with 10% as interval. Incomplete instances are distributed evenly in all views. Note that for each instance, it is available in at least one view.

Results

The NMIs of four datasets are plotted in Figure 1. For synthetic data, IVC shows the best NMI. IVC, MIC and Concat preform stable even when the incomplete ratio is close to 90%. While the NMIs of other methods drops sharply as incomplete ratio rises.

For Flowers17, all methods present the downward trends as incomplete ratio increasing. IVC shows relatively better NMI than others. MvSpec is the second best method. Note that MIC shows worst performance. The possible reason is that NMF-based method is not suitable for similarity data. (we apply MIC on kernel data of Flower17 as in original paper [START_REF] Shao | Multiple incomplete views clustering via weighted nonnegative matrix factorization with l2,1 regularization[END_REF]).

As Flowers17, similar results for Reuters. IVC demonstrates slight advantage over MIC and more obvious advantage over others.

For Mfeat, in case of low incomplete ratio (i.e. when incomplete ratio is below 20%), all methods except Concate show close NMIs. As the incomplete ratio arises, IVC shows more and more obvious superiority over others. It can be summarized that although views are incomplete, their integration can still be more useful than single complete view. Among above multi-view methods, IVC achieves most accurate clustering for incomplete views in most cases.

Conclusion

In this paper, we propose the IVC algorithm for multiple incomplete view clustering. IVC initializes incomplete views with early estimation. Based on the spectral graph theory, IVC projects original data into a new space with more discriminative grouping information. Then, individual projections are integrated. By aligning individual projections with the projection integration, estimated part of individual projections are updated to be more accurate. With those updated individual projections, final consensus is established and thereby standard K-Means is applied on. Compared with existing works, our proposed algorithm (1) does not require any view to be complete, (2) does not limit the number of incomplete views, and (3) can handle similarity data as well as feature data. Experimental results validate the effectiveness of the IVC algorithm.

  by ignoring constant factors and trace property ( trace(AA T ) = A 2 F ), we rewrite the objective function (5) as follows.

a

  is the part derived by available (observed) values, while U (i) e is the part derived by estimated (or missing) values. Correspondingly, we reorder U * as U * a U * e

); 4 :

 4 Update each individual U (i) e by Equation (10); 5: Construct U * f with updated U (i) s by Equation (8); 6: Do K-means clustering with final consensus projection U * f ; 7: return {C j }, j = 1, 2, ...K;

Fig. 1

 1 Fig. 1. NMIs

Table 1 .

 1 Details of the datasets

	Dataset # Instance # Views # Clusters
	Synth	1000	3	2
	Flowers	1360	3	17
	Reuters	1200	5	6
	Mfeat	2000	5	10

http://www.robots.ox.ac.uk/ vgg/data/

http://lig-membres.imag.fr/grimal/data.html

Acknowledgement

This work is supported by the Major State Basic Research Development Program of China (973 Program) under the Grant No.2014CB340303, and the Natural Science Foundation under Grant No.61402490.

IVC: IVC is the proposed approach in this work. We set equal default value for λ i to be 1. Without prior knowledge, we treat all views equally. MIC: Multiple incomplete view clustering [START_REF] Shao | Multiple incomplete views clustering via weighted nonnegative matrix factorization with l2,1 regularization[END_REF] is one of the most recent work. It applies weighted joint non-negative matrix with L 2,1 regularization. The default co-regularization parameter set α i and the robust parameter set β i are all set to be 0.01 for all the views as in the original paper. MVSpec: MVSpec is a weighted multi-kernel learning and specrtal graph theory based algorithm for multi-view clustering. It represents views through kernel matrices and optimize the intra-cluster variance function. We set the parameter p and initial weights as its original paper [START_REF] Tzortzis | Kernel-based weighted multi-view clustering[END_REF] . KADD: Integrating multiple kernels by adding them, and then running standard spectral clustering on the corresponding Laplacian. As suggested in earlier findings [START_REF] Cortes | Learning non-linear combinations of kernels[END_REF], even this seemingly simple approach often result in near optimal clustering as compared to more sophisticated approaches. Concat: Feature concatenation is the most simple and intuitive way to integrate all the views. It concatenates features of all views and runs K-means clustering on the concatenated feature set.

We also report the best performance of complete single view. Note that the compared methods such as KADD, Concat, and MVSpec cannot directly deal with incomplete views. Therefore, we pre-process the incomplete views by mean imputation for these methods. We evaluate above methods by the normalized mutual information (NMI). Besides, we use k-means to get the clustering solution at the end, we run k-means 10 times and report the average performance.

Datasets

In this paper, we use one synthetic dataset and three real-world datasets to evaluate the comparison methods. The details of four datasets are as follows. Table 1 presents the statistics of the datasets.

Synthetic Dataset: This dataset contains three views. For each view, we sample points from a two component Gaussian mixture model as instances. There are two clusters (i.e. cluster A and cluster B). Both the features and views are correlated. Specifically, the cluster means and the covariances for the three views are listed below.

B = 0.5, 0.2 0.2, 0.5 [START_REF] Shao | Clustering on multiple incomplete datasets via collective kernel learning[END_REF] Oxford Flowers Dataset (Flowers17) 1 : This dataset is composed of 17 flower categories, with 80 images for each category. Each image is described by


Quansheng Dou

Zhongzhi Shi

Yuehao Pan
email: pan_yhao@yeah.net

Noisy Control About Discrete Liner Consensus Protocol

Keywords: Multi-agent system, Graph theory, Consensus protocol, Noisy control

scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

In recent years, more and more researchers in the control community have focused their attention on distributed coordination of multi-agent systems due to its broad applications in many fields such as sensor networks, e.g. UAV (Unmanned Air Vehicles), MRS (mobilerobots systems), robotic teams.

In the cooperative control, a key problem is to design distributed protocols suchthat group of agents can achieve consensus through local communications. So far, numerous interesting results for consensus problem have been obtained for both discrete-time and continuous-timemulti-agent systemin the past decade.Reynoldssystematically studied and simulated the behavior of biological group such as birds and fishes, and proposed Boidmodel [START_REF] Reynolds | herds, and schools: a distributed behavioral model[END_REF]which still has a broad impact in the field of Swarm Intelligence.Vicsekmodel [START_REF] Vicsek | Novel type of phase transition in a system of selfdriven particles[END_REF]is proposed based on statistical mechanics theory in which the movement rate of Agent on two-dimensional plane remains unchanged, and the N agents on the 2-D plane determine their motion direction according to the directions of their neighbor agents.One of the most promising tools are the linear consensus algorithms, which aresimple distributed algorithms which require only minimal computation, communicationand synchronization to compute averages of local quantities that reside ineach device. These algorithms have their roots in the analysis ofMarkov chains [START_REF] Seneta | Non-negative Matrices and Markov Chains[END_REF]and have been deeply studied within the computer science community for load balancingand within the linear algebra community for the asynchronous solutionof linear systems [START_REF] Frommer | On asynchronous iterations[END_REF][START_REF] Strikwerda | A probabilistic analysis of asynchronous iteration[END_REF]. For linear consensus problem, Olfati-Saber et al. established a relatively complete theoretical framework based on graph theory and kinetic theory, and systematically analyzed the different types of consistency issues based on the framework [START_REF] Olfati-Saber | Consensus and cooperation in networked multi-agent systems[END_REF][START_REF] Olfati-Saber | Evolutionary Dynamics of Behavior in Social Networks[END_REF][START_REF] Olfati-Saber | Coupled Distributed Estimation and Control for Mobile Sensor Networks[END_REF][START_REF] Olfati-Saber | Flocking for multi-agent dynamic systems: algorithms and theory[END_REF]. Based on the study of Olfati-Saber, Yu [START_REF] Yu | A Self-Adaptive Framework for Modular Robots in Dynamic Environment: Theory and Applications[END_REF][START_REF] Yu | Biologically-Inspired Control for Self-Adaptive Multiagent Systems[END_REF][START_REF] Yu | Biologically-Inspired Control for Multi-Agent Self-Adaptive Tasks[END_REF] et al. discussed three necessary and sufficient conditions for the algorithm to converge to a consistent state when the states of agents has nothing to do with the data transferred, and conducted a meaningful analysis of its correctness, effectiveness and efficiency with the verification in several specific applications. For multi-Agent consensus and synchronization problems of complex networks, Li etal. in their rather deep discussion proposed multi-Agent control architecture based on higher order linear system with a series of fruitful results [START_REF] Li | Consensus of multi-agent systems and synchronization of complex networks: a unified viewpoint[END_REF][START_REF] Li | G Dynamic consensus of linear multi-agent systems[END_REF][START_REF] Li | Distributed tracking control for linear multiagent systems with a leader of bounded unknown input. Automatic Control[END_REF]. In [START_REF] Minh | Distributed Design of Finite-time Average Consensus Protocols[END_REF] average consensus issues are discussed, with the consensus algorithm formulated as matrix factorization problem,machine learning methods are proposed to solve matrix decomposition problem.

For most of consensus results in the literature, it is usually assumed that each agent can obtain its neighbor's information precisely. Since real networks are often in uncertain communication environments, it is necessary to consider consensus problems under measurement noises. Such consensus problems have been studied , Some research [START_REF] Ni | Consensus seeking in multi-agent systems with multiplicative measurement noises[END_REF][START_REF] Djaidja | Leaderless consensus seeking in multi-agent systems under multiplicative measurement noises and switching topologies[END_REF][START_REF] Djaidja | Leader-following consensus for single-integratormulti-agent systems withmultiplicative noises in directed topologies[END_REF] have addressed the consensus problem of multi-agents system under multiplicative measurement noises, where the noises' intensities are considered proportional to the relative states.In [START_REF] Huang | Coordination and consensus of networked agents with noisy measurements:stochastic algorithms and asymptotic behavior[END_REF][START_REF] Huang | Stochastic consensus seeking with noisy and directed interagent communication:fixed and randomly varying topologies[END_REF] the authors studied consensus problems when there exist noisy measurements of the states of neighbors, and a stochastic approximation approach was applied to obtain mean square and almost sure convergence in models with fixed network topologies or with independent communications failures. Necessary and/or sufficient conditions for stochastic consensus of multi-agent systems were established for the case of fixed topology and time varying topologies in [START_REF] Li | Mean square average-consensus under measurement noises and fixed topologies: necessary and sufficient conditions[END_REF][START_REF] Li | Consensus conditions of multi-agent systems with time-varying topologies and stochastic communication noises[END_REF]. Liu et al. studied signal delay of linear consensus protocol [START_REF] Wen | Flocking of multi-agent dynamical systems with intermittent nonlinear velocity measurements[END_REF], and presented strong consensus and mean square consensus concept under the conditions of the fixed topology and the presence of noise and delay between agents, and gave theoretically necessary and sufficient conditions of strong consensus and mean square under Non_Leader_Follower and Leader_Follower modes. The distributed consensus problem for linear discrete-time multi-agent systems with delays and noises was investigated in [START_REF] Liu | Distributed consensus for multi-agent systems with delays and noises in transmission channels[END_REF] by introducing a novel technique to overcome the difficulties induced by the delays and noises. In [START_REF] Chen | On the cluster consensus of discrete-time multi-agent systems[END_REF], a novel kindof cluster consensus of multi-agents systems with several different subgroups was considered based on Markov chains and nonnegative matrix analysis.

In this paper, we discussed the noise problem of the linear consensus protocol, and gave a sufficient condition that ensure the noise of linear consensus protocolis controllable. The remainder of this paper is organized as follows. Somepreliminaries and definitions are given in Section 2. in section 3, we pointed out that noise of DLCP is uncontrollable. in section 4,we proposed the strategy of usingnoisesuppression functionto control noise, and put forward theorem1 about a reasonable range of noisesuppression function ; Section 5 is devoted to show the conclusions ofthis paper.

Preliminaries

Consider n agents distributed according to a directed graph

   , consisting of a set of nodes    1,2,.
..,n and a set of edges  . In the digraph, an edge from node i to node j is denoted as an ordered pair (i, j) where i ≠ j (so there is no edge between a node and itself). A path (from i1 to il ) consists of a sequence of nodes i1, i2,

• • • , il , l ≥ 2, such that (ik, ik+1)  for k = 1• • • , l-1.
We say node i is connected to node j(i ≠ j) if there exists a path from i to j. For convenience of exposition, the two names, agent and node, will be used alternatively. The agent

Ak (resp., node k) is a neighbor of Ai (resp., node i) if (k, i) where k ≠ i. Denote the neighbors of node i by i = {k|(k, i)  }.
For agent Ai, we denote its state at time t by xi(t) ∈ , where t ∈  ,  = {0,1,2, • • • }. For each i ∈ , agent Ai receives information from its neighbors.

Definition 1:(Discrete Linear Consensus Protocol DLCP)The so-called linear consensus protocol is given by the following (1):

                       1, i i ij j i jt i x t x t t x t x t i j (1)
Where     0 ij t is a real-valued function with variable t and

      1 1 n ij j t
, it is used to characterize the extent of the impact at time t from agent j to agent i .

                     1 and 0 otherwise ij n ij ij j i t if j i j l t t if i j let          1 ,..., T n k x k x k X
, n denote an n order unit matrix, the matrix form of (1):

       1 t t t XX (2) where      n tt . Suppose    2 ~,
rN is a random number that satisfies the normal distribution, let

  var r represent variance  2 of r , if    1 ,..., T n rr R is a random vector, then   var R represent the covariance matrix of R,    var i R
denotes the variance of the ith compo-

nents of R, i.e        var var i i r R is ith element of diagonal of matrix   var R .
If the received message of Agent i contains a mutually independent and normally distributed noise interference, (1) can be rewritten as:

                            1, i i i ij j j i jt x t x t t x t r t x t i j ( 3
)
where

     2 ~0, jj r t N
is a random number and satisfies normal distribution, which represents the noise carried by the status information

  j xt . Let          1 ,..., T n t r t r t

R

, thus(3)can be rewritten in matrix form:

             1 t t t t t X X R (4)
In the above equation,

            t t diag t ,      diag t is the diagonal matrix of    t , so we can further get:                                      1 01 10 tt t m k j t m t k j t m t m t t X X R R (5)
In order to facilitate the description, let

           1 t n j t m j when  0 m
,then [START_REF] Strikwerda | A probabilistic analysis of asynchronous iteration[END_REF] can be simplified as:

                                0 01 10 tt t m k j t m t k j t m t m X X R let          t m = t m t m R ,                  0 1 t t m j t m t j t m Y ,          0 0 t k tk BX thus we get:          1 t t t X B Y (6)
Analyzing the random part  

Noise Uncontrollability of Discrete Linear Consistency Protocol

For any initial state   0 X , assuming that the consistency protocol in (2) converge to a consistent state * X associated with   0 X , under this condition, we discuss the impact of the noise on the protocol.

Lemma1: Suppose   t Y is random part of consensus protocol (6), when  t ,         lim var t i t Y for any initial state   0 X ,  1,..., in . Proof: let          1 () t j t m y t,m j t m ,then          0 , t m t y t m Y we have:             2 var , 1 var 1 t T j t m y t m t m j t m t m                                 ...
    lim var , t y t m                     lim ... 1 var 1 ... TT t t t m t m t m t                 12 lim , ,... 1 ... TT n t m m m t m t V V V                    12 lim ... 1 , ,... T T n t t t m m m m V V V        nn m
Where,      ,..., y t,m , So it will not converge, i.e. the consensus protocol ( 6) is noise uncon- trollable.

T i i i m v v V is a constant vector related to m ,       nn m is a con- stant matrix, and     0 m . So that:                                 

Noise Suppression Discrete Linear Consensus Protocol(NS-DLCP)

We reconstruct the state transition matrix [START_REF] Olfati-Saber | Evolutionary Dynamics of Behavior in Social Networks[END_REF] Here we call [START_REF] Olfati-Saber | Evolutionary Dynamics of Behavior in Social Networks[END_REF] as Noise Suppression Consensus Protocol(NS-CP), then we rewrite [START_REF] Olfati-Saber | Evolutionary Dynamics of Behavior in Social Networks[END_REF] as the relation between    1 Xt and the initial state   0 X , and consider the noise carried by Agent , then [START_REF] Olfati-Saber | Evolutionary Dynamics of Behavior in Social Networks[END_REF] is rewritten as:

  t , let          t t t , where     : ++ t is a function whose independent variable is t ,     0 t and when  t ,     0 t , we call    t as noise suppression function, Let          n t t t , replace   t in (2) with    t ,we get:         1 t t t XX
                                   0 01 10 tt t m k j t m t k j t m t m X X R (8)
Similarly, let

            t m t m t m R ,                          0 1 t t m j t m t j t m Y ,            0 0 t k t k B X
then ( 8) is simplified as:

          1 t t t X B Y (9)
Lemma2: Suppose consensus protocol (2) can converge to a consistent state * X under the noise-free conditions, if noise suppression function    t is the low-order in-

finitesimal of 1 t , then      * lim t t BX .
Proof: Study formula (10), we have       1 tt XB in the case without noise, from the conclusion in [START_REF] Yu | Biologically-Inspired Control for Self-Adaptive Multiagent Systems[END_REF] we know that

            ** 2 1 t t t X X X X for any determined t , where     2 t is the second largest eigenvalues of matrix         1 2 T tt , let    2 t be the second smallest eigenvalues of         1 2 T tt , obviously,            22 1 t t t , thus:                   ** 2 1 10 t k t k k B X X X (10)
Let  * 2 be the smallest one in the second smallest eigenvalues of

        1 2 T tt
, according to the known conditions that

         1 O t O t ,
                    * 22 1 0 1 1 t t k k k t
, when  t ,from squeeze theorem we can obtain:

           2 1 lim 1 0 t t k kk
, that means:

                      ** 2 1 0 lim lim 1 0 0 t tt k t k k B X X X
Then we have

       var tm               var T t m t m t m R                  2 var T t m t m t m t m R                    2 var T t m t m t m t m R            2 var t m t m R let             1 () t j t m y t,m j t m ,then           0 , t m t y t m Y
Study the norm of the variance matrix of  () y t,m , we have:

  var ( ) y t,m                           ... 1 var 1 ... TT t t m t m t m t                            ... 1 var 1 ... 1 TT t t m t m t m t m                  2 var var t m t m t m R In fact,        var , i y t m
is exactly the ith element of the diagonal of the variance matrix then NS-SDLC ( 9) is noise controllable.

     var , y t m , denote            max var , i y t m , obviously            2 var , i y t m t m , then                                      2

Conclusion

Bases on the above theoretical results and discussion, table1 summarized the main conclusions of this paper.

Definition 2 :

 2 (Weighted Laplacian Matrix)The matrix  matrix of graph ,where

Table 1 .

 1 Main conclusions of this paper Yε(t) is unbounded. In this case, linear consensus protocol is noise uncontrollable. II. When O(ε(t))≥O( t-1), the variance of its random part Yε(t) is bounded, but the determined part Bε(t) of linear consensus protocol can't converge to consistent state vectors * X , under this circumstances, linear consensus protocol is also noise uncontrollable. III. If O( t-0.5)<O(ε(t))< O( t-1), Bε(t) will converge to consistent state vectors * X and the variance of Yε(t) is bounded, so linear consensus protocol is noise controllable. At this time, every Agent's state will be a normal distribution with center x*.

	No.	ε(t)	limBε(t)	t→∞,i=1,…,n lim[var(Yε(t))]i The final state xi of Agent i
	Case.1	ε(t)=1	X *	∞	Diverge(Noise uncontrollable)
	Case.2	O(ε(t))≤O( t -0.5 )	X *	∞	Diverge(Noise uncontrollable)
	Case.3	O( t -0.5 )<O(ε(t))< O( t -1 )	X *	Bounded	Normal distribution with cen-ter x * (Noise controllable)
	Case.4	O(ε(t))≥O( t -1 )	Unconsistent state vectors X ^	Bounded	Normal distribution with cen-ter xi ^(Noise uncontrollable)
		Our main conclusions are:
		I. if ε(t)=1 (Equivalent to    t is useless) or O(ε(t))≤O( t-0.5), the determined part
	Bε(t) of linear consensus protocol (9) can converge to consistent state vectors * X , but

Acknowledgments. This work was partially supported by the National Natural Science Foundation of China (No.61272244,61175053,61173173,61035003,61202212), National Key Basic Research Program of China (No. 2013CB329502)


Zhongzhi Shi
email: shizz@ics.ict.ac.cn

Gang Ma

Shu Wang
email: wangs@ics.ict.ac.cn

Jianqing Li

Brain-Machine Collaboration for Cyborg Intelligence

Keywords: cyborg intelligence, brain-machine collaboration, motivation driven collaboration, motivation learning, mind model CAM

de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Cyborg intelligence aims to integrate AI with biological intelligence by closely and deeply connecting computer and biological beings. The term cyborg was presented by Clynes and Kline in 1960 [START_REF] Clynes | Cyborgs and Space[END_REF], to describe a being with both organic and computing components. Combined with electronic sensing and navigation technology, a guided rat can be developed into an effective 'robot' that will possess several natural advantages over current mobile robots [START_REF] Talwar | Behavioural neuroscience: Rat navigation guided by remote control[END_REF]. Supported by the National Program on Key Basic Research Project we are engaging in the research on Computational Theory and Method of Perception and Cognition of Brain-Machine Integration. The main goal is the exploration of cyborg intelligence through brain-machine integration, enhancing strengths and compensating for weaknesses by combining the biological cognition capability with the computer computational capability. To make this integration effective and co-adaptive, multi-agents should work collaboratively on environment perception, information processing, and command execution.

Collaborations occur over time as organizations interact formally and informally through repetitive sequences of negotiation, development of commitments, and execution of those commitments. Both cooperation and coordination may occur as part of the early process of collaboration, collaboration represents a longer-term integrated process. Gray describes collaboration as "a process through which parties who see different aspects of a problem can constructively explore their differences and search for solutions that go beyond their own limited vision of what is possible." [START_REF] Gray | Collaborating: Finding Common Ground for Multiparty Problems[END_REF] In multi-agent system no single agent owns all knowledge required for solving complex tasks. Agents work together to achieve common goals, which are beyond the capabilities of individual agent. Each agent perceives information from the environment with sensors and find out the number of cognitive tasks, even same task of having different information and the possible combination of tasks for execution for certain interval of time, pick out or select the particular combination for execution in an interval of time, and finally outputs the required effective actions to the environment.

As an internal mental model of agent, BDI model has been well recognized in philosophical and artificial intelligence area. Bratman's philosophical theory was formalized by Cohen and Levesque [START_REF] Cohen | Intention is choice with commitment[END_REF] and other researchers. A cognitive model for multi-agent collaboration should consider external perception and internal mental state of agents. Awareness is knowledge created through interaction between an agent and its environment. In multi-agent system group awareness is an understanding of the activities of others and provides a context for own activity. Group awareness can be divided into basic questions about who is collaborating, what they are doing, and where they are working. Gutwin etc. proposed a conceptual framework of workspace awareness that structures thinking about groupware interface support. They list elements for the conceptual framework [START_REF] Gutwin | The Importance of Awareness for Team Cognition in Distributed Collaboration[END_REF]. Workspace awareness in a particular situation is made up of some combination of these elements.

Collaboration is goal-oriented and aided by motivation. Psychologists define motivation as an internal process that activates, guides, and maintains behavior over time. Mook defined motivation as "the cause of action" briefly [START_REF] Mook | Motivation: The Organization of Action[END_REF]. Maslow proposed hierarchy of needs which was one of first unified motivation theories [START_REF] Maslow | Motivation and Personality[END_REF]. MicroPsi concerns modeling a motivational system to solve in the pursuit of a given set of goals, which reflects cognitive, social and physiological needs, and can account for individual variance and personality traits [START_REF] Bach | Principles of Synthetic Intelligence -An architecture of motivated cognition[END_REF].

In this paper, a collaborative agent model for cyborg intelligence will be proposed in terms of external environment awareness and internal mental state. The agent intention is driven by motivation which is generated dynamically.

Cyborg Intelligence

Cyborg intelligence is dedicated to integrating AI with biological intelligence by tightly connecting machines and biological beings, for example, via brain-machine interfaces (BMIs) [START_REF] Wu | Cyborg Intelligence: Towards Bio-Machine Intelligent Systems[END_REF]. Figure 1 shows the physical implementation of the rat-robot navigation system [START_REF] Yu | Automatic training of ratbot for navigation[END_REF]. In the automatic navigation of rats, five bipolar stimulating electrodes separately are implanted in medial forebrain bundle (MFB), somatosensory cortices (SI), and periaqueductal gray matter (PAG) of the rat brain. There is also a backpack fixed on the rat to receive the wireless commands.

Fig. 1. Rat cyborg

There are two components which are necessary to implement the automatic navigation. Firstly, the communication between a computer and a rat needs to be solved. The stimulation signals are delivered by a wireless backpack stimulator which is comprised of stimulating circuit, control processor and Bluetooth transceivers. The control processor receives the computer instructions through the Bluetooth transceivers. Then it sends commands to the stimulator to control the rat behaviors. By receiving commands from the machine, the rat can perform a lot of navigation tasks, e.g. walking around mazes, climbing bridges, and stopping at a special place. Secondly, a video camera device used to capture the rat movement is installed above the scenario. With the video captured by the birdeye camera, the machine can establish a map of the environment and analyze the real time kinetic state of the rat.

In brain-machine integration, each rat brain and computer can be viewed as an agent playing special role and work together for a sharing goal. The agent cognitive model is illustrated in Figure 2, which agents deliberate the external perception and the internal mental state for decision-making. The model is represented as a 4-tuple: Awareness, Belief, Goal, Plan. Awareness is described by the basic elements and relationships related to the agent's setting. Belief can be viewed as the agent's knowledge about its environment and itself. Goal represents the concrete motivations that influence an agent's behaviors. Plan is used to achieve the agent's goals. Moreover, an important module motivation-driven intention is used to drive the collaboration of cyborg intelligent system.

Fig. 2. Agent cognitive model 3 Environment Awareness

The environment is the complex combination of physical conditions and agents responses. Cyborg intelligent systems require bidirectional information perception between rat brain and computer. Awareness is the state or ability to perceive, to feel events, objects or sensory patterns, and cognitive reaction to a condition or event.

Awareness has four basic characteristics:

 Awareness is knowledge about the state of a particular environment.  Environments change over time, so awareness must be kept up to date.  Agents maintain their awareness by interacting with the environment.  Awareness establishes usually an event.

Reasoning interpreter c) Operation relationships describe the operation set of agent. d) Activity relationships describe activity of the role at a time. e) Cooperation relationships describe the interactions between agents. A partnership can be investigated through cooperation activities relevance between agents to ensure the transmission of information between different perception of the role and tasks for maintenance of the entire multi-agent perception.

Motivationdriven intention

Based on the integration of Marr visual theory and Gestalt whole perception theory, applying statistical learning and deep learning and other methods to analyze visual information of environment and generate high-level semantics. The convolutional generative stochastic model (CGSM) is proposed for the visual awareness [START_REF] Ma | An Environment Visual Awareness Approach in Cognitive Model ABGP[END_REF]. The Generative Stochastic Networks (GSN) is based on learning the transition operator of a Markov chain whose stationary distribution estimates the data distribution. GSN has the capability to obtain a generative model of the data distribution without explicitly specifying a probabilistic graphical model, and allows learning deep generative model through global training via back-propagation. In order to seek a visual awareness path with a stronger robustness and a better hierarchy feature representation with gradually more global representation in the higher levels, the CGSM model can be stacked through multi convolutional generative stochastic layers. The mean-pooling is applied to CGSM so as to the downward pass operation can be successfully implemented. The layer-wise sampling like deep Boltzmann machine network will be adopted in the computational graph. CGSM has a strong robustness for noisy data, and is better to serve as a visual awareness pathway.

Motivation Driven Collaboration

Motivation is an internal motive force and subjective reasons, which direct drive the individual activities to achieve a certain purpose, and the psychological state initiated and maintained by individual activities. Psychologists define motivation as the process that initiates, guides, and maintains goal-oriented behaviors. All kinds of behaviors and activities of the people can't be separated from the motivation. Motivation has the following functions: a) Arouse the start function of the action. Personally, all the power of his actions must be through his mind, must be changed to his desire for motivation, in order to make him act up.

b) A directing function that focuses an individual's behavior towards or away from specific goals.

c) An organizing function that influences the combination of behavioral components into coherent, goal-oriented behavioral sequences.

d) Strengthen function of motivation. One's experience of successes and failures on the activity, have certain influence on his activity ambition. In other words, how is the behavioral result, influencing people's motivation? Therefore the motivation plays a regulation control appearing in the form of positive or negative reinforcement role in people's behavior.

Consider the dual nature of motivation, that is implicit and explicit, the motivation process is complexity. In general, implicit motivational processes are primary and more essential than explicit motivational processes. Here we only focus on explicit motivation and hypothesize that the explicit motivational representations consist mainly of explicit goals of an agent. Explicit goals provide specific and tangible motivations for actions. Explicit goals also allow more behavioral flexibility and formation of expectancies. In cyborg intelligent system we have developed two approaches for brain computer integration, that is, needs based motivation and curiosity based motivation.

Needs based motivation

In 1943, humanistic psychologist Maslow put forward the demand theory of motivation. Maslow's assumption that people in need, the sequence of human motivation, from the most basic physiological and safety needs, through a series of love and respect, the complex needs of self-realization, and need level has great intuitive appeal [START_REF] Maslow | Motivation and Personality[END_REF]. Over the years, people have proposed a lot of theories of motivation, each theory has a certain degree of concern. These theories are very different in many ways, but they all come from a similar consideration, namely behavioral arousing, point to and keep, these three points are the core of any kind of motivation.

Bach proposed the MicroPsi architecture of motivated cognition based on situated agents [START_REF] Bach | Principles of Synthetic Intelligence -An architecture of motivated cognition[END_REF]. MicroPsi explores the combination of a neuro-symbolic cognitive architecture with a model of autonomous, polytelic motivation. The needs of MicoPsi cognitive system fall into three groups: physiological needs, social needs and cognitive [START_REF] Bach | Modeling Motivation in MicroPsi 2[END_REF]. Physiological needs regulate the basic survival of the organism and reflect demands of the metabolism and physiological well-being. Social needs direct the behavior towards other individuals and groups. They According to brain computer integration requirements, a motivation could be represented as a 3-tuples {N,G,I}, where N means needs, G is goal, I means the motivation intensity [START_REF] Shi | A Motivational System For Mind Model CAM[END_REF]. There are three type of needs in the cyborg system: a. Perception needs: Acquire environment information through vision, audition, touch, taste, smell. b. Adaptation needs: Adapt environment condition and optimize impaction of action.

c. Cooperation needs: Promise to reward a cooperation action between brain and machine.

A motivation is activated by motivational rules which structure has following format:

R=(P, D, Strength(P|D)) where, P indicates the conditions of rule activation; D is a set of actions for the motivation; Strength(P|D) is a value within interval [0,1].

Curiosity based motivation

Curiosity based motivation is through motivation learning algorithm to build a new motivation. Agent creates internal representations of observed sensory inputs and links them to learned actions that are useful for its operation. If the result of the machine's action is not relevant to its current goal, no motivation learning takes place. This screening of what to learn is very useful since it protects machine's memory from storing unimportant observations, even though they are not predictable by the machine and may be of sufficient interest for novelty based learning. Novelty based learning still can take place in such a system, when the system is not triggered by other motivations.

Motivation learning requires a mechanism for creating abstract motivations and related goals. Once implemented, such a mechanism manages motivations, as well as selects and supervises execution of goals. Motivations emerge from interaction with the environment, and at any given stage of development, their operation is influenced by competing event and attention switching signals.

The learning process for motivations to obtain the sensory states by observing, then the sensed states are transformed mutually by the events. Where to find novelty to motivate an agent's interestingness will play an important role. Once the interestingness is stimulated, the agent's attention may be selected and focused on one aspect of the environment. Therefore, it will be necessary to define observations, events, novelty, interestingness and attention before descripting the motivation learning algorithm.

Definition 1: Observation Functions Observation functions define the combinations of sensations from the sensed state that will motivate further reasoning. Observations containing fewer sensations affect an agent's attention focus by making it possible for the agent to restrict its attention to a subset of the state space. Where, a typical observation function can be given as:

𝐎 S(t) = {(o 1(t) , o 2(t) , ⋯ , o L(t) , ⋯ )|o L(t) = s L(t) (∀L)} (1)
The equation defines observation function 𝐎 S(t) in which each observation focuses on every element of the sensed state at time t.

Definition 2: Difference Function A difference function  assigns a value to the difference between two sensations S L(t) and S L(t ′ ) in the sensed states S (t) and S (t') as follows:

∆ (s L(t) , s L(t ′ ) ) = { s L(t) ; if ¬∃s L(t ′ ) s L(t ′ ) ; if ¬∃s L(t) s L(t) -s L(t ′ ) ; if s L(t) -s L(t ′ ) ≠ 0 0; otherwise (2)
Difference function offers the information about the change between successive sensations it calculates the magnitude of the change.

Definition 3: Event Function Event functions define which combinations of difference variables an agent recognizes as events, each of which contains only one non-zero difference variable. Event function can be defined as following formula:

𝐄 S(t) = {E L(t) = (
Events may be of varying length or even empty, depending on the number of sensations to change.

Definition 4: Novelty Detection Function

The novelty detection function, N, takes the conceptual state of the agent, c ∈ 𝐂, and compares it with memories of previous experiences, m ∈ 𝐌, constructed by long term memory to produce a novelty state, n ∈ 𝐍: 𝐍 ∶ 𝐂 × 𝐌 → 𝐍 (5) Novelty can be detected by introspective search comparing the current conceptual state of an agent with memories of previous experiences [START_REF] Shi | Computational Cognitive Models for Brain-Machine Collaborations[END_REF].

Definition 5: Interestingness Function

The interestingness function determines a value for the interestingness of a situation, i ∈ 𝐈, basing on the novelty detected, n ∈ 𝐍: 𝐈 ∶ 𝐍 → 𝐈 (6) Definition 6: Attention Selection Selective attention enables you to focus on an item while mentally identifying and distinguishing the non-relevant information. In cyborg we adopt maximal interestingness strategy to select attentions to create a motivation.

The following describes the basic steps of novelty based motivation learning and goal creation algorithm in the cyborg system.

Motivation learning algorithm

Motivation execution

Motivation execution flow is shown in Figure 3. The awareness gets information from the environment and places it into the event list. Select one event from event list and identify it. If the event is a normal event then retrieval the motivation base and select one motivation to activate the intention. If the event is a new one and never happened previously, then call motivation learning to generate a new motivation. The new motivation will activate the intention. Based on the intention plan execution will be caused and generate a series actions to accomplish the desired goal, which requires the cooperation of the reasoning machine. This means that the system will find one or more of schemes which are made in the past. It is possible to find a solution that is not the only solution when it is used to reason about an existing object. At this time, the inference engine needs to select according to its internal rules. The selection criteria need to specify before. Different selection criteria will lead to the agent different behavioral responses at the decision-making. After choosing a good plan, the system will need to link up the goal and the plan in advance. This will make the planning a detailed understanding of the objectives, and there is sufficient information to be able to use for making planning of the goal.

Fig. 3. Motivation execution

In cyborg system, the realization of the motivation module is through agent model ABGP. The current belief of the belief memory storage contains the agent motivation base. A desire is a goal or a desired final state. Intention is the need for the smart body to choose the current implementation of the goal. In agent, the goal is a directed acyclic graph by the sub goal composition, and realizes in step by step. According to a directed acyclic graph a sub goal is represented by a path to complete, the total goal will finish when all sub goals are completed.

Collaboration

In brain-machine integration rat brain should work with machine collaboratively. Here rat brain and machine can be abstracted as agent, so the collaboration can be viewed as joint intention [START_REF] Shi | Computational Cognitive Models for Brain-Machine Collaborations[END_REF]. Joint intention is about what the team members want to achieve. Each team member knows the intention specifically and achieves it by collaboration.

In the joint intention theory, a team is defined as "a set of agents having a shared objective and a shared mental state". The team as a whole holds joint intentions, and each team member must inform others whenever it detects the goal state change, such as goal is achieved or the goal is no longer relevant.

For the joint intention, rat agent and machine agent have three basic knowledge: first, each one should select its intention; second, each one knows its cooperator who also select the same intention; and last, each one knows they are a team. They can know each other through agent communication.

Conclusions

This paper described cyborg intelligence which integrates the best of both machine and biological intelligences via brain-machine integration. To make this integration effective and co-adaptive biological brain and machine should work collaboratively. Both environment awareness based collaboration and motivation based collaboration are presented in the paper. The motivation leaning algorithm is explored in terms of event curiosity, which is useful for sharing common interest situations. Under situations appear repeatedly the motivation is selected by knowledge rules.

The future of cyborg intelligence may lead towards many promising applications, such as neural intervention, medical treatment, and early diagnosis of some neurological and psychiatric disorders. Cyborg intelligence has the potential to make the bionic man reality.

The cyborg intelligence is one approach to reach the human-level intelligence. A lot of basic issues of brain-like general intelligent systems are explored in the book [START_REF] Shi | Mind Computation[END_REF] in detail.

  collaborative awareness model is defined as 2-tuples: {Element, Relation}, where Element of awareness is described as follows: a) Who: describes the existence of agent and identity the role, answer question who is participating? b) What: shows agent's actions and abilities, answer question what are they doing? And what can they do? Also can show intentions to answer question what are they going to do? c) Where: indicates the location of agents, answer question where are they? d) When: shows the time point of agent behavior, answer question when can action execute? Basic relationships contain task relationship, role relationship, operation relationship, activity relationship and cooperation relationships. a) Task relationships define task decomposition and composition relationships. Task involves activities with a clear and unique role attribute b) Role relationships describe the role relationship of agents in the multi-agent activities.

  are satisfied and frustrated by social signals and corresponding mental representations. Cognitive needs give rise to open-ended problem solving, skill-acquisition, exploration, play and creativity. Urges reflect various physiological, social and cognitive needs. Cognitive processes are modulated in response to the strength and urgency of the needs.

Environment Awareness Select Motivation Execute Plan Event List Normal Event? Motivation Learning Select Intention Motivation Base Select Motivation Environment No No No No No Yes

Acknowledgements

This work is supported by the National Program on Key Basic Research Project (973) (No. 2013CB329502), National Natural Science Foundation of China (No. 61035003), National Science and Technology Support Program (2012BA107B02).