Particle Competition and Cooperation in Networks for Semi-Supervised Learning

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Particle Competition and Cooperation in Networks for Semi-Supervised Learning with Concept Drift

Concept drift is a problem of increasing importance in machine learning and data mining. Data sets under analysis are no longer only static databases, but also data streams in which concepts and data distributions may not be stable over time. However, most learning algorithms produced so far are based on the assumption that data comes from a fixed distribution, so they are not suitable to handle concept drifts. Moreover, some concept drifts applications requires fast response, which means an algorithm must always be (re) trained with the latest available data. But the process of labeling data is usually expensive and/or time consuming when compared to unlabeled data acquisition, thus only a small fraction of the incoming data may be effectively labeled. Semi-supervised learning methods may help in this scenario, as they use both labeled and unlabeled data in the training process. However, most of them are also based on the assumption that the data is static. Therefore, semi-supervised learning with concept drifts is still an open challenge in machine learning. Recently, a particle competition and cooperation approach was used to realize graph-based semi-supervised learning from static data. In this paper, we extend that approach to handle data streams and concept drift. The result is a passive algorithm using a single classifier, which naturally adapts to concept changes, without any explicit drift detection mechanism. Its built-in mechanisms provide a natural way of learning from new data, gradually forgetting older knowledge as older labeled data items became less influent on the classification of newer data items. Some computer simulation are presented, showing the effectiveness of the proposed method.

Particle competition and cooperation to prevent error propagation from mislabeled data in semi-supervised learning

Semi-supervised learning is applied to classification problems where only a small portion of the data items is labeled. In these cases, the reliability of the labels is a crucial factor, because mislabeled items may propagate wrong labels to a large portion or even the entire data set. This paper aims to address this problem by presenting a graph-based (network-based) semi-supervised learning method, specifically designed to handle data sets with mislabeled samples. The method uses teams of walking particles, with competitive and cooperative behavior, for label propagation in the network constructed from the input data set. The proposed model is nature-inspired and it incorporates some features to make it robust to a considerable amount of mislabeled data items. Computer simulations show the performance of the method in the presence of different percentage of mislabeled data, in networks of different sizes and average node degree. Importantly, these simulations reveals the existence of the critical points of the mislabeled subset size, below which the network is free of wrong label contamination, but above which the mislabeled samples start to propagate their labels to the rest of the network. Moreover, numerical comparisons have been made among the proposed method and other representative graph-based semi-supervised learning methods using both artificial and real-world data sets. Interestingly, the proposed method has increasing better performance than the others as the percentage of mislabeled samples is getting larger. © 2012 IEEE.

Fuzzy community structure detection by particle competition and cooperation

Identification and classification of overlapping nodes in networks are important topics in data mining. In this paper, a network-based (graph-based) semi-supervised learning method is proposed. It is based on competition and cooperation among walking particles in a network to uncover overlapping nodes by generating continuous-valued outputs (soft labels), corresponding to the levels of membership from the nodes to each of the communities. Moreover, the proposed method can be applied to detect overlapping data items in a data set of general form, such as a vector-based data set, once it is transformed to a network. Usually, label propagation involves risks of error amplification. In order to avoid this problem, the proposed method offers a mechanism to identify outliers among the labeled data items, and consequently prevents error propagation from such outliers. Computer simulations carried out for synthetic and real-world data sets provide a numeric quantification of the performance of the method. © 2012 Springer-Verlag.

Particle competition and cooperation for semi-supervised learning with label noise

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Particle Competition and Cooperation in Networks for Semi-Supervised Learning

Semi-supervised learning is one of the important topics in machine learning, concerning with pattern classification where only a small subset of data is labeled. In this paper, a new network-based (or graph-based) semi-supervised classification model is proposed. It employs a combined random-greedy walk of particles, with competition and cooperation mechanisms, to propagate class labels to the whole network. Due to the competition mechanism, the proposed model has a local label spreading fashion, i.e., each particle only visits a portion of nodes potentially belonging to it, while it is not allowed to visit those nodes definitely occupied by particles of other classes. In this way, a "divide-and-conquer" effect is naturally embedded in the model. As a result, the proposed model can achieve a good classification rate while exhibiting low computational complexity order in comparison to other network-based semi-supervised algorithms. Computer simulations carried out for synthetic and real-world data sets provide a numeric quantification of the performance of the method.

Modeling the role of competition and cooperation in the evolution of katydid acoustic synchrony

The precise timing of individual signals in response to those of signaling neighbors is seen in many animal species. Synchrony is the most striking of the resultant timing patterns. One of the best examples of acoustic synchrony is in katydid choruses where males produce chirps with a high degree of temporal overlap. Cooperative hypotheses that speculate on the evolutionary origins of acousti synchrony include the preservation of the species-specific call pattern, reduced predation risks, and increased call intensity. An alternative suggestion is that synchrony evolved as an epiphenomenon of competition between males in response to a female preference for chirps that lead other chirps. Previous models investigating the evolutionary origins of synchrony focused only on intrasexual competitive interactions. We investigated both competitive and cooperative hypotheses for the evolution of synchrony in the katydid Mecopoda ``Chirper'' using physiologically and ecologically realistic simulation models incorporating the natural variation in call features, ecology, female preferences, and spacing patterns, specifically aggregation. We found that although a female preference for leading chirps enables synchronous males to have some selective advantage, it is the female preference for the increased intensity of aggregations of synchronous males that enables synchrony to evolve as an evolutionarily stable strategy.

Competition and cooperation between international courts: a critical approach to the new paradigms of cross-border dispute resolution model

This article examines the arising cross-border dispute resolution models (Cooperation and Competition among national Courts) from a critical perspective. Although they have been conceived to surpass the ordinary solution of a Modern paradigm (exclusive jurisdiction, choice of court, lis pendens, forum non conveniens, among others), they are insufficient to deal with problems raised with present globalization, as they do not abandon aspects of that paradigm, namely, (i) statebased Law; and (ii) standardization of cultural issues.

Trust, Competition and Cooperation in Autism Spectrum Disorder

Objective: Impaired social interactions and repetitive behavior are key features of autism spectrum disorder (ASD). In the present study we compared social decision-making in subjects with and without ASD. Subjects performed five social decision-making games in order to assess trust, fairness, cooperation & competition behavior and social value orientation. Methods: 19 adults with autism spectrum disorder and 17 controls, matched for age and education, participated in the study. Each subject performed five social decision-making tasks. In the trust game, subjects could maximize their gain by sharing some of their money with another person. In the punishment game, subjects played two versions of the Dictator’s Dilemma. In the dictator condition they could share an amount of 0-100 points with another person. In the punishment condition, the opponent was able to punish the subject if he/she was not satisfied with the amount of points received. In the cooperation game, subjects played with a small group of 3 people. Each of them could (anonymously) select an amount of 5, 7.5 or 10 Swiss francs. The goal of the game was to achieve a high group minimum. In the competition game, subjects performed a dexterity task. Before performing the task, they were asked whether they wanted to compete (winner takes it all) or cooperation (sharing the joint achieved amount of points) with a randomly selected person. Lastly, subjects performed a social value orientation task where they were playing for themselves and for another person. Results: There was no overall difference between healthy controls an ASD subjects in investment in the trust game. However, healthy controls increased their investment over number of trials whereas ASD subjects did not. A similar pattern was found for the punishment game. Furthermore, ASD subjects revealed a decreased investment in the dictator condition of the punishment game. There were no mean differences in competition behavior and social value orientation. Conclusions: The results provide evidence for differences between ASD subjects and healthy controls in social decision-making. Subjects with ASD showed a more consistent behavior than healthy controls in the trust game and the dictator dilemma. The present findings provide evidence for impaired social learning in ASD.

Competition and cooperation between antiferrodistortive and ferroelectric instabilities in the model perovskite SrTiO₃

We use density functional theory to explore the interplay between octahedral rotations and ferroelectricity in the model compound SrTiO3. We find that over the experimentally relevant range octahedral rotations suppress ferroelectricity as is generally assumed in the literature. Somewhat surprisingly, we observe that at larger angles the previously weakened ferroelectric instability strengthens significantly. By analyzing geometry changes, energetics, force constants and charges, we explain the mechanisms behind this transition from competition to cooperation with increasing octahedral rotation angle.

Competition for Cooperation: variability, benefits and heritability of relational wealth in hunter-gatherers

Many defining human characteristics including theory of mind, culture and language relate to our sociality, and facilitate the formation and maintenance of cooperative relationships. Therefore, deciphering the context in which our sociality evolved is invaluable in understanding what makes us unique as a species. Much work has emphasised group-level competition, such as warfare, in moulding human cooperation and sociality. However, competition and cooperation also occur within groups; and inter-individual differences in sociality have reported fitness implications in numerous non-human taxa. Here we investigate whether differential access to cooperation (relational wealth) is likely to lead to variation in fitness at the individual level among BaYaka hunter-gatherers. Using economic gift games we find that relational wealth: a) displays individual-level variation; b) provides advantages in buffering food risk, and is positively associated with body mass index (BMI) and female fertility; c) is partially heritable. These results highlight that individual-level processes may have been fundamental in the extension of human cooperation beyond small units of related individuals, and in shaping our sociality. Additionally, the findings offer insight in to trends related to human sociality found from research in other fields such as psychology and epidemiology.

Semi-supervised learning with concept drift using particle dynamics applied to network intrusion detection data

Concept drift, which refers to non stationary learning problems over time, has increasing importance in machine learning and data mining. Many concept drift applications require fast response, which means an algorithm must always be (re)trained with the latest available data. But the process of data labeling is usually expensive and/or time consuming when compared to acquisition of unlabeled data, thus usually only a small fraction of the incoming data may be effectively labeled. Semi-supervised learning methods may help in this scenario, as they use both labeled and unlabeled data in the training process. However, most of them are based on assumptions that the data is static. Therefore, semi-supervised learning with concept drifts is still an open challenging task in machine learning. Recently, a particle competition and cooperation approach has been developed to realize graph-based semi-supervised learning from static data. We have extend that approach to handle data streams and concept drift. The result is a passive algorithm which uses a single classifier approach, naturally adapted to concept changes without any explicit drift detection mechanism. It has built-in mechanisms that provide a natural way of learning from new data, gradually "forgetting" older knowledge as older data items are no longer useful for the classification of newer data items. The proposed algorithm is applied to the KDD Cup 1999 Data of network intrusion, showing its effectiveness.

Inhibition of coxsackie B virus infection by soluble forms of its receptors: Binding affinities, altered particle formation, and competition with cellular receptors

We previously reported that soluble decay-accelerating factor (DAF) and coxsackievirus-adenovirus receptor (CAR) blocked coxsackievirus 133 (CVB3) myocarditis in mice, but only soluble CAR blocked CVB3-mediated pancreatitis. Here, we report that the in vitro mechanisms of viral inhibition by these soluble receptors also differ. Soluble DAF inhibited virus infection through the formation of reversible complexes with CVB3, while binding of soluble CAR to CVB induced the formation of altered (A) particles with a resultant irreversible loss of infectivity. A-particle formation was characterized by loss of VP4 from the virions and required incubation of CVB3-CAR complexes at 37 degrees C. Dimeric soluble DAF (DAF-Fc) was found to be 125-fold-more effective at inhibiting CVB3 than monomeric DAF, which corresponded to a 100-fold increase in binding affinity as determined by surface plasmon resonance analysis. Soluble CAR and soluble dimeric CAR (CAR-Fc) bound to CVB3 with 5,000- and 10,000-fold-higher affinities than the equivalent forms of DAF. While DAF-Fc was 125-fold-more effective at inhibiting virus than monomeric DAF, complement regulation by DAF-Fc was decreased 4 fold. Therefore, while the virus binding was a cooperative event, complement regulation was hindered by the molecular orientation of DAF-Fc, indicating that the regions responsible for complement regulation and virus binding do not completely overlap. Relative contributions of CVB binding affinity, receptor binding footprint on the virus capsid, and induction of capsid conformation alterations for the ability of cellular DAF and CAR to act as receptors are discussed.