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

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.

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)

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.

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.

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.

Interference competition and high temperature reduce the ‘virulence’ of fig wasps and contribute to stability of a fig-wasp mutualism

Fig trees are pollinated by fig wasps, which also oviposit in female flowers. The wasp larvae gall and eat developing seeds. Although fig trees benefit from allowing wasps to oviposit, because the wasp offspring disperse pollen, figs must prevent wasps from ovipositing in all flowers, or seed production would cease, and the mutualism would go extinct. In Ficus racemosa, we find that syconia (‘figs’) that have few foundresses (ovipositing wasps) are underexploited in the summer (few seeds, few galls, many empty ovules) and are overexploited in the winter (few seeds, many galls, few empty ovules). Conversely, syconia with many foundresses produce intermediate numbers of galls and seeds, regardless of season. We use experiments to explain these patterns, and thus, to explain how this mutualism is maintained. In the hot summer, wasps suffer short lifespans and therefore fail to oviposit in many flowers. In contrast, cooler temperatures in the winter permit longer wasp lifespans, which in turn allows most flowers to be exploited by the wasps. However, even in winter, only in syconia that happen to have few foundresses are most flowers turned into galls. In syconia with higher numbers of foundresses, interference competition reduces foundress lifespans, which reduces the proportion of flowers that are galled. We further show that syconia encourage the entry of multiple foundresses by delaying ostiole closure. Taken together, these factors allow fig trees to reduce galling in the wasp-benign winter and boost galling (and pollination) in the wasp-stressing summer. Interference competition has been shown to reduce virulence in pathogenic bacteria. Our results show that interference also maintains cooperation in a classic, cooperative symbiosis, thus linking theories of virulence and mutualism. More generally, our results reveal how frequency-dependent population regulation can occur in the fig-wasp mutualism, and how a host species can ‘set the rules of the game’ to ensure mutualistic behavior in its symbionts.