Training deep convolutional architectures for vision

Les tâches de vision artificielle telles que la reconnaissance d’objets demeurent irrésolues à ce jour. Les algorithmes d’apprentissage tels que les Réseaux de Neurones Artificiels (RNA), représentent une approche prometteuse permettant d’apprendre des caractéristiques utiles pour ces tâches. Ce processus d’optimisation est néanmoins difficile. Les réseaux profonds à base de Machine de Boltzmann Restreintes (RBM) ont récemment été proposés afin de guider l’extraction de représentations intermédiaires, grâce à un algorithme d’apprentissage non-supervisé. Ce mémoire présente, par l’entremise de trois articles, des contributions à ce domaine de recherche. Le premier article traite de la RBM convolutionelle. L’usage de champs réceptifs locaux ainsi que le regroupement d’unités cachées en couches partageant les même paramètres, réduit considérablement le nombre de paramètres à apprendre et engendre des détecteurs de caractéristiques locaux et équivariant aux translations. Ceci mène à des modèles ayant une meilleure vraisemblance, comparativement aux RBMs entraînées sur des segments d’images. Le deuxième article est motivé par des découvertes récentes en neurosciences. Il analyse l’impact d’unités quadratiques sur des tâches de classification visuelles, ainsi que celui d’une nouvelle fonction d’activation. Nous observons que les RNAs à base d’unités quadratiques utilisant la fonction softsign, donnent de meilleures performances de généralisation. Le dernière article quand à lui, offre une vision critique des algorithmes populaires d’entraînement de RBMs. Nous montrons que l’algorithme de Divergence Contrastive (CD) et la CD Persistente ne sont pas robustes : tous deux nécessitent une surface d’énergie relativement plate afin que leur chaîne négative puisse mixer. La PCD à "poids rapides" contourne ce problème en perturbant légèrement le modèle, cependant, ceci génère des échantillons bruités. L’usage de chaînes tempérées dans la phase négative est une façon robuste d’adresser ces problèmes et mène à de meilleurs modèles génératifs.

Échantillonnage dynamique de champs markoviens

L'un des modèles d'apprentissage non-supervisé générant le plus de recherche active est la machine de Boltzmann --- en particulier la machine de Boltzmann restreinte, ou RBM. Un aspect important de l'entraînement ainsi que l'exploitation d'un tel modèle est la prise d'échantillons. Deux développements récents, la divergence contrastive persistante rapide (FPCD) et le herding, visent à améliorer cet aspect, se concentrant principalement sur le processus d'apprentissage en tant que tel. Notamment, le herding renonce à obtenir un estimé précis des paramètres de la RBM, définissant plutôt une distribution par un système dynamique guidé par les exemples d'entraînement. Nous généralisons ces idées afin d'obtenir des algorithmes permettant d'exploiter la distribution de probabilités définie par une RBM pré-entraînée, par tirage d'échantillons qui en sont représentatifs, et ce sans que l'ensemble d'entraînement ne soit nécessaire. Nous présentons trois méthodes: la pénalisation d'échantillon (basée sur une intuition théorique) ainsi que la FPCD et le herding utilisant des statistiques constantes pour la phase positive. Ces méthodes définissent des systèmes dynamiques produisant des échantillons ayant les statistiques voulues et nous les évaluons à l'aide d'une méthode d'estimation de densité non-paramétrique. Nous montrons que ces méthodes mixent substantiellement mieux que la méthode conventionnelle, l'échantillonnage de Gibbs.

Apprentissage machine efficace : théorie et pratique

Malgré des progrès constants en termes de capacité de calcul, mémoire et quantité de données disponibles, les algorithmes d'apprentissage machine doivent se montrer efficaces dans l'utilisation de ces ressources. La minimisation des coûts est évidemment un facteur important, mais une autre motivation est la recherche de mécanismes d'apprentissage capables de reproduire le comportement d'êtres intelligents. Cette thèse aborde le problème de l'efficacité à travers plusieurs articles traitant d'algorithmes d'apprentissage variés : ce problème est vu non seulement du point de vue de l'efficacité computationnelle (temps de calcul et mémoire utilisés), mais aussi de celui de l'efficacité statistique (nombre d'exemples requis pour accomplir une tâche donnée). Une première contribution apportée par cette thèse est la mise en lumière d'inefficacités statistiques dans des algorithmes existants. Nous montrons ainsi que les arbres de décision généralisent mal pour certains types de tâches (chapitre 3), de même que les algorithmes classiques d'apprentissage semi-supervisé à base de graphe (chapitre 5), chacun étant affecté par une forme particulière de la malédiction de la dimensionalité. Pour une certaine classe de réseaux de neurones, appelés réseaux sommes-produits, nous montrons qu'il peut être exponentiellement moins efficace de représenter certaines fonctions par des réseaux à une seule couche cachée, comparé à des réseaux profonds (chapitre 4). Nos analyses permettent de mieux comprendre certains problèmes intrinsèques liés à ces algorithmes, et d'orienter la recherche dans des directions qui pourraient permettre de les résoudre. Nous identifions également des inefficacités computationnelles dans les algorithmes d'apprentissage semi-supervisé à base de graphe (chapitre 5), et dans l'apprentissage de mélanges de Gaussiennes en présence de valeurs manquantes (chapitre 6). Dans les deux cas, nous proposons de nouveaux algorithmes capables de traiter des ensembles de données significativement plus grands. Les deux derniers chapitres traitent de l'efficacité computationnelle sous un angle différent. Dans le chapitre 7, nous analysons de manière théorique un algorithme existant pour l'apprentissage efficace dans les machines de Boltzmann restreintes (la divergence contrastive), afin de mieux comprendre les raisons qui expliquent le succès de cet algorithme. Finalement, dans le chapitre 8 nous présentons une application de l'apprentissage machine dans le domaine des jeux vidéo, pour laquelle le problème de l'efficacité computationnelle est relié à des considérations d'ingénierie logicielle et matérielle, souvent ignorées en recherche mais ô combien importantes en pratique.

Approccio meccanico statistico allo studio delle Macchine di Boltzmann Ristrette

La Macchina di Boltzmann Ristretta (RBM) è una rete neurale a due strati utilizzata principalmente nell'apprendimento non supervisionato. La sua capacità nel rappresentare complesse relazioni insite nei dati attraverso distribuzioni di tipo Boltzmann Gibbs la rende un oggetto particolarmente interessante per un approfondimento teoretico in ambito fisico matematico. In questa tesi vengono presentati due ambiti di applicazione della meccanica statistica all'apprendimento automatico. 1) La similarità della RBM a unità binarie con il modello di Ising permette di sfruttare un'espansione alle alte temperature per approssimare l'energia libera, termine presente nel gradiente della likelihoood e difficile da trattare numericamente. I risultati ottenuti con questa tecnica sul dataset MNIST sono paragonabili a quelli ottenuti dalla Contrastive Divergence, che utilizza invece metodi di Monte Carlo. 2) L'equivalenza statistica della variante ibrida di RBM con il modello di Hopfield permette di studiare la taglia del training set necessaria per l'apprendimento attraverso l'analisi del problema inverso, in cui i ruoli di spin e pattern sono invertiti. Viene quindi presentato un metodo basato sulla teoria di Gauge che permette di derivare il diagramma di fase del modello di Hopfield duale sulla linea di Nishimori in funzione della temperatura e del rapporto tra numero di campioni e dimensione del sistema.

Allopatric speciation in ticks: genetic and reproductive divergence between geographic strains of Rhipicephalus (Boophilus) microplus

Background: The cattle tick, Rhipicephalus (Boophilus) microplus, economically impact cattle industry in tropical and subtropical regions of the world. The morphological and genetic differences among R. microplus strains have been documented in the literature, suggesting that biogeographical and ecological separation may have resulted in boophilid ticks from America/Africa and those from Australia being different species. To test the hypothesis of the presence of different boophilid species, herein we performed a series of experiments to characterize the reproductive performance of crosses between R. microplus from Australia, Africa and America and the genetic diversity of strains from Australia, Asia, Africa and America. Results: The results showed that the crosses between Australian and Argentinean or Mozambican strains of boophilid ticks are infertile while crosses between Argentinean and Mozambican strains are fertile. These results showed that tick strains from Africa (Mozambique) and America (Argentina) are the same species, while ticks from Australia may actually represent a separate species. The genetic analysis of mitochondrial 12S and 16S rDNA and microsatellite loci were not conclusive when taken separately, but provided evidence that Australian tick strains were genetically different from Asian, African and American strains. Conclusion: The results reported herein support the hypothesis that at least two different species share the name R. microplus. These species could be redefined as R. microplus (Canestrini, 1887) (for American and African strains) and probably the old R. australis Fuller, 1899 (for Australian strains), which needs to be redescribed. However, experiments with a larger number of tick strains from different geographic locations are needed to corroborate these results.

Lineage divergence detected in the malaria vector Anopheles marajoara (Diptera: Culicidae) in Amazonian Brazil

Background: Cryptic species complexes are common among anophelines. Previous phylogenetic analysis based on the complete mtDNA COI gene sequences detected paraphyly in the Neotropical malaria vector Anopheles marajoara. The ""Folmer region"" detects a single taxon using a 3% divergence threshold. Methods: To test the paraphyletic hypothesis and examine the utility of the Folmer region, genealogical trees based on a concatenated (white + 3' COI sequences) dataset and pairwise differentiation of COI fragments were examined. The population structure and demographic history were based on partial COI sequences for 294 individuals from 14 localities in Amazonian Brazil. 109 individuals from 12 localities were sequenced for the nDNA white gene, and 57 individuals from 11 localities were sequenced for the ribosomal DNA (rDNA) internal transcribed spacer 2 (ITS2). Results: Distinct A. marajoara lineages were detected by combined genealogical analysis and were also supported among COI haplotypes using a median joining network and AMOVA, with time since divergence during the Pleistocene (< 100,000 ya). COI sequences at the 3' end were more variable, demonstrating significant pairwise differentiation (3.82%) compared to the more moderate 2.92% detected by the Folmer region. Lineage 1 was present in all localities, whereas lineage 2 was restricted mainly to the west. Mismatch distributions for both lineages were bimodal, likely due to multiple colonization events and spatial expansion (similar to 798 - 81,045 ya). There appears to be gene flow within, not between lineages, and a partial barrier was detected near Rio Jari in Amapa state, separating western and eastern populations. In contrast, both nDNA data sets (white gene sequences with or without the retention of the 4th intron, and ITS2 sequences and length) detected a single A. marajoara lineage. Conclusions: Strong support for combined data with significant differentiation detected in the COI and absent in the nDNA suggest that the divergence is recent, and detectable only by the faster evolving mtDNA. A within subgenus threshold of >2% may be more appropriate among sister taxa in cryptic anopheline complexes than the standard 3%. Differences in demographic history and climatic changes may have contributed to mtDNA lineage divergence in A. marajoara.

Genome-wide SNP genotyping highlights the role of natural selection in Plasmodium falciparum population divergence

Background: The malaria parasite Plasmodium falciparum exhibits abundant genetic diversity, and this diversity is key to its success as a pathogen. Previous efforts to study genetic diversity in P. falciparum have begun to elucidate the demographic history of the species, as well as patterns of population structure and patterns of linkage disequilibrium within its genome. Such studies will be greatly enhanced by new genomic tools and recent large-scale efforts to map genomic variation. To that end, we have developed a high throughput single nucleotide polymorphism (SNP) genotyping platform for P. falciparum. Results: Using an Affymetrix 3,000 SNP assay array, we found roughly half the assays (1,638) yielded high quality, 100% accurate genotyping calls for both major and minor SNP alleles. Genotype data from 76 global isolates confirm significant genetic differentiation among continental populations and varying levels of SNP diversity and linkage disequilibrium according to geographic location and local epidemiological factors. We further discovered that nonsynonymous and silent (synonymous or noncoding) SNPs differ with respect to within-population diversity, interpopulation differentiation, and the degree to which allele frequencies are correlated between populations. Conclusions: The distinct population profile of nonsynonymous variants indicates that natural selection has a significant influence on genomic diversity in P. falciparum, and that many of these changes may reflect functional variants deserving of follow-up study. Our analysis demonstrates the potential for new high-throughput genotyping technologies to enhance studies of population structure, natural selection, and ultimately enable genome-wide association studies in P. falciparum to find genes underlying key phenotypic traits.

CHARACTERIZATION OF EXPONENTIAL DIVERGENCE OF THE KALMAN FILTER FOR TIME-VARYING SYSTEMS

This paper studies semistability of the recursive Kalman filter in the context of linear time-varying (LTV), possibly nondetectable systems with incorrect noise information. Semistability is a key property, as it ensures that the actual estimation error does not diverge exponentially. We explore structural properties of the filter to obtain a necessary and sufficient condition for the filter to be semistable. The condition does not involve limiting gains nor the solution of Riccati equations, as they can be difficult to obtain numerically and may not exist. We also compare semistability with the notions of stability and stability w.r.t. the initial error covariance, and we show that semistability in a sense makes no distinction between persistent and nonpersistent incorrect noise models, as opposed to stability. In the linear time invariant scenario we obtain algebraic, easy to test conditions for semistability and stability, which complement results available in the context of detectable systems. Illustrative examples are included.

Avoiding Divergence in the Shalvi-Weinstein Algorithm

The most popular algorithms for blind equalization are the constant-modulus algorithm (CMA) and the Shalvi-Weinstein algorithm (SWA). It is well-known that SWA presents a higher convergence rate than CMA. at the expense of higher computational complexity. If the forgetting factor is not sufficiently close to one, if the initialization is distant from the optimal solution, or if the signal-to-noise ratio is low, SWA can converge to undesirable local minima or even diverge. In this paper, we show that divergence can be caused by an inconsistency in the nonlinear estimate of the transmitted signal. or (when the algorithm is implemented in finite precision) by the loss of positiveness of the estimate of the autocorrelation matrix, or by a combination of both. In order to avoid the first cause of divergence, we propose a dual-mode SWA. In the first mode of operation. the new algorithm works as SWA; in the second mode, it rejects inconsistent estimates of the transmitted signal. Assuming the persistence of excitation condition, we present a deterministic stability analysis of the new algorithm. To avoid the second cause of divergence, we propose a dual-mode lattice SWA, which is stable even in finite-precision arithmetic, and has a computational complexity that increases linearly with the number of adjustable equalizer coefficients. The good performance of the proposed algorithms is confirmed through numerical simulations.

Genetic divergence is not the same as phenotypic divergence

Far too often, phenotypic divergence has been misinterpreted as genetic divergence, and based on phenotypic divergence, genetic divergence has been indicated. We have attempted to disprove this statement and call for the differentiation of phenotypic and genotypic variation.

Extensive chromosomal variation associated with taxon divergence and host specificity in the gall-inducing scale insect Apiomorpha munita (Schrader) (Hemiptera : Sternorrhyncha : Coccoidea : Eriococcidae)

Apiomorpha Rubsaamen (Hemiptera: Coccoidea: Eriococcidae) is one of the most chromosomally diverse of all animal genera. There is extensive karyotypic variation within many of the morphologically defined species, including A. munita (Schrader) which is here reported to have diploid chromosome counts ranging from 6 to more than 100. Each of the three morphologically defined subspecies of A. munita also displays considerable chromosomal variation: A. m. tereticornuta Gullan (2n =6, 8, 20, 22 or 24), A. m. malleensis Gullan (2n =6, 20, 22, 24 or 26), and A. m. munita (Schrader) (2n=54 or >100). Apiomorpha munita appears to occur only on eucalypts of the informal subgenus Symphyomyrtus, with each of the subspecies of A. munita restricted to discrete symphyomyrt sections. Several different karyotypic forms within each subspecies of A. munita appear to be restricted to only one or a few eucalypt species or series. The association between apparent host specificity and chromosomal rearrangements in A. munita suggests that both may be playing an active role in taxon divergence in Apiomorpha. (C) 2001 The Linnean Society of London.

Choices associated with automobiles for Men and Women: convergence or divergence?

The increase of the women purchase power has led some companies to adopt strategies of products differentiation as well as to produce specific products to the female public. The auto industry is not immune to this phenomenon, once the women represent, approximately half of the automobile sales in the country. Considering the consumption and the behavior differences between women and men, it has set the following question: are there differences between the choices associated to the automobile by men and the choices associated to the automobile by women? It has been presented to the participants items found in the people`s day-by-day, which are valorized by them, and the participants have been asked to choose and associate these items to the automobile. The results analysis revealed there are more similarities than differences between choices associated to the automobile by men ad choices associated to the automobile by women. The similarity between the choices suggests that the representations, the meanings and values assigned. to the car by men ana women are similar and thus the strategy of product differentiation does not apply to the automotive industry

Intra- and interspecific divergence in the nuclear sequences of the clock gene period in species of the Drosophila buzzatii cluster

We have measured nucleotide variation in the CLOCK/CYCLE heterodimer inhibition domain (CCID) of the clock X-linked gene period in seven species belonging to the Drosophila buzzatii cluster, namely D. buzzatii, Drosophila koepferae, Drosophila antonietae, Drosophila serido, Drosophila gouveai, Drosophila seriema and Drosophila borborema. We detected that the purifying selection is the main force driving the sequence evolution in period, in agreement with the important role of CCID in clock machinery. Our survey revealed that period provides valuable phylogenetic information that allowed to resolve phylogenetic relationships among D. gouveai, D. borborema and D. seriema, which composed a polytomic clade in preliminary studies. The analysis of patterns of intraspecific variation revealed two different lineages of period in D. koepferae, probably reflecting introgressive hybridization from D. buzzatii, in concordance with previous molecular data.

Allozymatic divergence between border populations of two cryptic species of the Drosophila buzzatii cluster species (Diptera: Drosophilidae)

Drosophila antonietae and Drosophila gouveai are allopatric, cactophilic, cryptic and endemic of South America species, which aedeagus morphology is considered the main diagnostic character. In this work, single close populations from the edge distributions of each species, located in an ""introgressive corridor"", were analyzed regarding temporal isozenzymatic genetic variability. Isocitrate dehydrogenase (Idh) appeared as a diagnostic locus between D. antonieate and D. gouveai because each population was fixed for different alleles. Moreover, several polymorphic loci showed accentuated divergence in the allele frequency, as evidenced by Nei`s l(0.3188) and D (1.1432), and also by Reynolds` genetic distance and identity (1.3207 and 0.7331, respectively). Our results showed that, in spite of the very similar external morphology, related evolutionary histories, close distributions, and events of introgression in the studied area, these cryptic species have high allozymatic differentiation, and this is discussed here. (C) 2010 Elsevier Ltd. All rights reserved.

Phylogeography of the cactophilic species Drosophila gouveai: demographic events and divergence timing in dry vegetation enclaves in eastern Brazil

Aim The aim of this study was to assess the causal mechanisms underlying populational subdivision in Drosophila gouveai, a cactophilic species associated with xeric vegetation enclaves in eastern Brazil. A secondary aim was to investigate the genetic effects of Pleistocene climatic fluctuations on these environments. Location Dry vegetation enclaves within the limits of the Cerrado domain in eastern Brazil. Methods We determined the mitochondrial DNA haplotypes of 55 individuals (representing 12 populations) based on sequence data of a 483-bp fragment from the cytochrome c oxidase subunit II (COII) gene. Phylogenetic and coalescent analyses were used to test for the occurrence of demographic events and to infer the time of divergence amongst genetically independent groups. Results Our analyses revealed the existence of two divergent subclades (G1 and G2) plus an introgressed clade restricted to the southernmost range of D. gouveai. Subclades G1 and G2 displayed genetic footprints of range expansion and segregated geographical distributions in south-eastern and some central highland regions, east and west of the Parana River valley. Molecular dating indicated that the main demographic and diversification events occurred in the late to middle Pleistocene. Main conclusions The phylogeographical and genetic patterns observed for D. gouveai in this study are consistent with changes in the distribution of dry vegetation in eastern Brazil. All of the estimates obtained by molecular dating indicate that range expansion and isolation pre-dated the Last Glacial Maximum, occurring during the late to middle Pleistocene, and were probably triggered by climatic changes during the Pleistocene. The current patchy geographical distribution and population subdivision in D. gouveai is apparently closely linked to these past events.