Sampling and learning the Mallows and Generalized Mallows models under the Cayley distance

[EN]The Mallows and Generalized Mallows models are compact yet powerful and natural ways of representing a probability distribution over the space of permutations. In this paper we deal with the problems of sampling and learning (estimating) such distributions when the metric on permutations is the Cayley distance. We propose new methods for both operations, whose performance is shown through several experiments. We also introduce novel procedures to count and randomly generate permutations at a given Cayley distance both with and without certain structural restrictions. An application in the field of biology is given to motivate the interest of this model.

Sampling and learning the Mallows and Weighted Mallows models under the Hamming distance

[EN]In this paper we deal with distributions over permutation spaces. The Mallows model is the mode l in use. The associated distance for permutations is the Hamming distance.

Sampling and learning the Mallows model under the Ulam distance

[EN]In this paper we deal with probability distributions over permutation spaces. The Probability model in use is the Mallows model. The distance for permutations that the model uses in the Ulam distance.

Extending Distance-based Ranking Models In Estimation of Distribution Algorithms

Recently, probability models on rankings have been proposed in the field of estimation of distribution algorithms in order to solve permutation-based combinatorial optimisation problems. Particularly, distance-based ranking models, such as Mallows and Generalized Mallows under the Kendall’s-t distance, have demonstrated their validity when solving this type of problems. Nevertheless, there are still many trends that deserve further study. In this paper, we extend the use of distance-based ranking models in the framework of EDAs by introducing new distance metrics such as Cayley and Ulam. In order to analyse the performance of the Mallows and Generalized Mallows EDAs under the Kendall, Cayley and Ulam distances, we run them on a benchmark of 120 instances from four well known permutation problems. The conducted experiments showed that there is not just one metric that performs the best in all the problems. However, the statistical test pointed out that Mallows-Ulam EDA is the most stable algorithm among the studied proposals.

Language distance and non-native syntactic processing: Evidence from event-related potentials

[EN] In this study, we explore native and non-native syntactic processing, paying special attention to the language distance factor. To this end, we compared how native speakers of Basque and highly proficient non-native speakers of Basque who are native speakers of Spanish process certain core aspects of Basque syntax. Our results suggest that differences in native versus non-native language processing strongly correlate with language distance: native/non-native processing differences obtain if a syntactic parameter of the non-native grammar diverges from the native grammar. Otherwise, non-native processing will approximate native processing as levels of proficiency increase. We focus on three syntactic parameters: (i) the head parameter, (ii) argument alignment (ergative/accusative), and (iii) verb agreement. The first two diverge in Basque and Spanish, but the third is the same in both languages. Our results reveal that native and non-native processing differs for the diverging syntactic parameters, but not for the convergent one. These findings indicate that language distance has a significant impact in non-native language processing.

Contributions on distance-based algorithms, multi-classifier construction and pairwise classification

179 p.

Effects of Spring Temperatures on the Strength of Selection on Timing of Reproduction in a Long-Distance Migratory Bird

Climate change has differentially affected the timing of seasonal events for interacting trophic levels, and this has often led to increased selection on seasonal timing. Yet, the environmental variables driving this selection have rarely been identified, limiting our ability to predict future ecological impacts of climate change. Using a dataset spanning 31 years from a natural population of pied flycatchers (Ficedula hypoleuca), we show that directional selection on timing of reproduction intensified in the first two decades (1980-2000) but weakened during the last decade (2001-2010). Against expectation, this pattern could not be explained by the temporal variation in the phenological mismatch with food abundance. We therefore explored an alternative hypothesis that selection on timing was affected by conditions individuals experience when arriving in spring at the breeding grounds: arriving early in cold conditions may reduce survival. First, we show that in female recruits, spring arrival date in the first breeding year correlates positively with hatch date; hence, early-hatched individuals experience colder conditions at arrival than late-hatched individuals. Second, we show that when temperatures at arrival in the recruitment year were high, early-hatched young had a higher recruitment probability than when temperatures were low. We interpret this as a potential cost of arriving early in colder years, and climate warming may have reduced this cost. We thus show that higher temperatures in the arrival year of recruits were associated with stronger selection for early reproduction in the years these birds were born. As arrival temperatures in the beginning of the study increased, but recently declined again, directional selection on timing of reproduction showed a nonlinear change. We demonstrate that environmental conditions with a lag of up to two years can alter selection on phenological traits in natural populations, something that has important implications for our understanding of how climate can alter patterns of selection in natural populations.