Online discovery of similarity mappings

We consider the problem of choosing, sequentially, a map which assigns elements of a set A to a few elements of a set B. On each round, the algorithm suffers some cost associated with the chosen assignment, and the goal is to minimize the cumulative loss of these choices relative to the best map on the entire sequence. Even though the offline problem of finding the best map is provably hard, we show that there is an equivalent online approximation algorithm, Randomized Map Prediction (RMP), that is efficient and performs nearly as well. While drawing upon results from the "Online Prediction with Expert Advice" setting, we show how RMP can be utilized as an online approach to several standard batch problems. We apply RMP to online clustering as well as online feature selection and, surprisingly, RMP often outperforms the standard batch algorithms on these problems.

Exponentiated gradient algorithms for conditional random fields and max-margin Markov Networks

Log-linear and maximum-margin models are two commonly-used methods in supervised machine learning, and are frequently used in structured prediction problems. Efficient learning of parameters in these models is therefore an important problem, and becomes a key factor when learning from very large data sets. This paper describes exponentiated gradient (EG) algorithms for training such models, where EG updates are applied to the convex dual of either the log-linear or max-margin objective function; the dual in both the log-linear and max-margin cases corresponds to minimizing a convex function with simplex constraints. We study both batch and online variants of the algorithm, and provide rates of convergence for both cases. In the max-margin case, O(1/ε) EG updates are required to reach a given accuracy ε in the dual; in contrast, for log-linear models only O(log(1/ε)) updates are required. For both the max-margin and log-linear cases, our bounds suggest that the online EG algorithm requires a factor of n less computation to reach a desired accuracy than the batch EG algorithm, where n is the number of training examples. Our experiments confirm that the online algorithms are much faster than the batch algorithms in practice. We describe how the EG updates factor in a convenient way for structured prediction problems, allowing the algorithms to be efficiently applied to problems such as sequence learning or natural language parsing. We perform extensive evaluation of the algorithms, comparing them to L-BFGS and stochastic gradient descent for log-linear models, and to SVM-Struct for max-margin models. The algorithms are applied to a multi-class problem as well as to a more complex large-scale parsing task. In all these settings, the EG algorithms presented here outperform the other methods.

Optimization algorithms and ODE's in MDO

There is a need for a stronger theoretical understanding of Multidisciplinary Design Optimization (MDO) within the field. Having developed a differential geometry framework in response to this need, we consider how standard optimization algorithms can be modeled using systems of ordinary differential equations (ODEs) while also reviewing optimization algorithms which have been derived from ODE solution methods. We then use some of the framework's tools to show how our resultant systems of ODEs can be analyzed and their behaviour quantitatively evaluated. In doing so, we demonstrate the power and scope of our differential geometry framework, we provide new tools for analyzing MDO systems and their behaviour, and we suggest hitherto neglected optimization methods which may prove particularly useful within the MDO context. Copyright © 2013 by ASME.

Regional ocean-colour chlorophyll algorithms for the Red Sea

The Red Sea is a semi-enclosed tropical marine ecosystem that stretches from the Gulf of Suez and Gulf of Aqaba in the north, to the Gulf of Aden in the south. Despite its ecological and economic importance, its biological environment is relatively unexplored. Satellite ocean-colour estimates of chlorophyll concentration (an index of phytoplankton biomass) offer an observational platform to monitor the health of the Red Sea. However, little is known about the optical properties of the region. In this paper, we investigate the optical properties of the Red Sea in the context of satellite ocean-colour estimates of chlorophyll concentration. Making use of a new merged ocean-colour product, from the European Space Agency (ESA) Climate Change Initiative, and in situ data in the region, we test the performance of a series of ocean-colour chlorophyll algorithms. We find that standard algorithms systematically overestimate chlorophyll when compared with the in situ data. To investigate this bias we develop an ocean-colour model for the Red Sea, parameterised to data collected during the Tara Oceans expedition, that estimates remote-sensing reflectance as a function of chlorophyll concentration. We used the Red Sea model to tune the standard chlorophyll algorithms and the overestimation in chlorophyll originally observed was corrected. Results suggest that the overestimation was likely due to an excess of CDOM absorption per unit chlorophyll in the Red Sea when compared with average global conditions. However, we recognise that additional information is required to test the influence of other potential sources of the overestimation, such as aeolian dust, and we discuss uncertainties in the datasets used. We present a series of regional chlorophyll algorithms for the Red Sea, designed for a suite of ocean-colour sensors, that may be used for further testing.

Direct measurement of phase of foreward-scattered light using polarization heterodyne interferometer

We describe direct measurement of phase of ballistic photons transmitted through objects hidden in a turbid medium using a polarization interferometer employing a rotating analyzer. The unwrapped phase difference measurements from interferometry was possible for medium levels of turbidity and accurate phase measurement from the sinusoidal intensity was not detectable when l/l* is increased beyond 4.3. The measured phase on reconstruction using standard tomographic algorithms resulted in the recovery of the refractive index profile of the object hidden in the turbid medium.

Recyclage des candidats dans l'algorithme Metropolis à essais multiples

Les méthodes de Monte Carlo par chaînes de Markov (MCCM) sont des méthodes servant à échantillonner à partir de distributions de probabilité. Ces techniques se basent sur le parcours de chaînes de Markov ayant pour lois stationnaires les distributions à échantillonner. Étant donné leur facilité d’application, elles constituent une des approches les plus utilisées dans la communauté statistique, et tout particulièrement en analyse bayésienne. Ce sont des outils très populaires pour l’échantillonnage de lois de probabilité complexes et/ou en grandes dimensions. Depuis l’apparition de la première méthode MCCM en 1953 (la méthode de Metropolis, voir [10]), l’intérêt pour ces méthodes, ainsi que l’éventail d’algorithmes disponibles ne cessent de s’accroître d’une année à l’autre. Bien que l’algorithme Metropolis-Hastings (voir [8]) puisse être considéré comme l’un des algorithmes de Monte Carlo par chaînes de Markov les plus généraux, il est aussi l’un des plus simples à comprendre et à expliquer, ce qui en fait un algorithme idéal pour débuter. Il a été sujet de développement par plusieurs chercheurs. L’algorithme Metropolis à essais multiples (MTM), introduit dans la littérature statistique par [9], est considéré comme un développement intéressant dans ce domaine, mais malheureusement son implémentation est très coûteuse (en termes de temps). Récemment, un nouvel algorithme a été développé par [1]. Il s’agit de l’algorithme Metropolis à essais multiples revisité (MTM revisité), qui définit la méthode MTM standard mentionnée précédemment dans le cadre de l’algorithme Metropolis-Hastings sur un espace étendu. L’objectif de ce travail est, en premier lieu, de présenter les méthodes MCCM, et par la suite d’étudier et d’analyser les algorithmes Metropolis-Hastings ainsi que le MTM standard afin de permettre aux lecteurs une meilleure compréhension de l’implémentation de ces méthodes. Un deuxième objectif est d’étudier les perspectives ainsi que les inconvénients de l’algorithme MTM revisité afin de voir s’il répond aux attentes de la communauté statistique. Enfin, nous tentons de combattre le problème de sédentarité de l’algorithme MTM revisité, ce qui donne lieu à un tout nouvel algorithme. Ce nouvel algorithme performe bien lorsque le nombre de candidats générés à chaque itérations est petit, mais sa performance se dégrade à mesure que ce nombre de candidats croît.

A Government-Binding Based Parser for Warlpiri, a Free-Word Order Language

Free-word order languages have long posed significant problems for standard parsing algorithms. This thesis presents an implemented parser, based on Government-Binding (GB) theory, for a particular free-word order language, Warlpiri, an aboriginal language of central Australia. The words in a sentence of a free-word order language may swap about relatively freely with little effect on meaning: the permutations of a sentence mean essentially the same thing. It is assumed that this similarity in meaning is directly reflected in the syntax. The parser presented here properly processes free word order because it assigns the same syntactic structure to the permutations of a single sentence. The parser also handles fixed word order, as well as other phenomena. On the view presented here, there is no such thing as a "configurational" or "non-configurational" language. Rather, there is a spectrum of languages that are more or less ordered. The operation of this parsing system is quite different in character from that of more traditional rule-based parsing systems, e.g., context-free parsers. In this system, parsing is carried out via the construction of two different structures, one encoding precedence information and one encoding hierarchical information. This bipartite representation is the key to handling both free- and fixed-order phenomena. This thesis first presents an overview of the portion of Warlpiri that can be parsed. Following this is a description of the linguistic theory on which the parser is based. The chapter after that describes the representations and algorithms of the parser. In conclusion, the parser is compared to related work. The appendix contains a substantial list of test cases ??th grammatical and ungrammatical ??at the parser has actually processed.

Image classification for a large number of object categories

L'increment de bases de dades que cada vegada contenen imatges més difícils i amb un nombre més elevat de categories, està forçant el desenvolupament de tècniques de representació d'imatges que siguin discriminatives quan es vol treballar amb múltiples classes i d'algorismes que siguin eficients en l'aprenentatge i classificació. Aquesta tesi explora el problema de classificar les imatges segons l'objecte que contenen quan es disposa d'un gran nombre de categories. Primerament s'investiga com un sistema híbrid format per un model generatiu i un model discriminatiu pot beneficiar la tasca de classificació d'imatges on el nivell d'anotació humà sigui mínim. Per aquesta tasca introduïm un nou vocabulari utilitzant una representació densa de descriptors color-SIFT, i desprès s'investiga com els diferents paràmetres afecten la classificació final. Tot seguit es proposa un mètode par tal d'incorporar informació espacial amb el sistema híbrid, mostrant que la informació de context es de gran ajuda per la classificació d'imatges. Desprès introduïm un nou descriptor de forma que representa la imatge segons la seva forma local i la seva forma espacial, tot junt amb un kernel que incorpora aquesta informació espacial en forma piramidal. La forma es representada per un vector compacte obtenint un descriptor molt adequat per ésser utilitzat amb algorismes d'aprenentatge amb kernels. Els experiments realitzats postren que aquesta informació de forma te uns resultats semblants (i a vegades millors) als descriptors basats en aparença. També s'investiga com diferents característiques es poden combinar per ésser utilitzades en la classificació d'imatges i es mostra com el descriptor de forma proposat juntament amb un descriptor d'aparença millora substancialment la classificació. Finalment es descriu un algoritme que detecta les regions d'interès automàticament durant l'entrenament i la classificació. Això proporciona un mètode per inhibir el fons de la imatge i afegeix invariança a la posició dels objectes dins les imatges. S'ensenya que la forma i l'aparença sobre aquesta regió d'interès i utilitzant els classificadors random forests millora la classificació i el temps computacional. Es comparen els postres resultats amb resultats de la literatura utilitzant les mateixes bases de dades que els autors Aixa com els mateixos protocols d'aprenentatge i classificació. Es veu com totes les innovacions introduïdes incrementen la classificació final de les imatges.

The evaluation of CloudSat and CALIPSO ice microphysical products using ground-based cloud radar and lidar observations

In this paper, the statistical properties of tropical ice clouds (ice water content, visible extinction, effective radius, and total number concentration) derived from 3 yr of ground-based radar–lidar retrievals from the U.S. Department of Energy Atmospheric Radiation Measurement Climate Research Facility in Darwin, Australia, are compared with the same properties derived using the official CloudSat microphysical retrieval methods and from a simpler statistical method using radar reflectivity and air temperature. It is shown that the two official CloudSat microphysical products (2B-CWC-RO and 2B-CWC-RVOD) are statistically virtually identical. The comparison with the ground-based radar–lidar retrievals shows that all satellite methods produce ice water contents and extinctions in a much narrower range than the ground-based method and overestimate the mean vertical profiles of microphysical parameters below 10-km height by over a factor of 2. Better agreements are obtained above 10-km height. Ways to improve these estimates are suggested in this study. Effective radii retrievals from the standard CloudSat algorithms are characterized by a large positive bias of 8–12 μm. A sensitivity test shows that in response to such a bias the cloud longwave forcing is increased from 44.6 to 46.9 W m−2 (implying an error of about 5%), whereas the negative cloud shortwave forcing is increased from −81.6 to −82.8 W m−2. Further analysis reveals that these modest effects (although not insignificant) can be much larger for optically thick clouds. The statistical method using CloudSat reflectivities and air temperature was found to produce inaccurate mean vertical profiles and probability distribution functions of effective radius. This study also shows that the retrieval of the total number concentration needs to be improved in the official CloudSat microphysical methods prior to a quantitative use for the characterization of tropical ice clouds. Finally, the statistical relationship used to produce ice water content from extinction and air temperature obtained by the Cloud-Aerosol Lidar and Infrared Pathfinder Satellite Observation (CALIPSO) satellite is evaluated for tropical ice clouds. It is suggested that the CALIPSO ice water content retrieval is robust for tropical ice clouds, but that the temperature dependence of the statistical relationship used should be slightly refined to better reproduce the radar–lidar retrievals.

Towards expressive rule induction on IP network event streams

In order to gain insights into events and issues that may cause errors and outages in parts of IP networks, intelligent methods that capture and express causal relationships online (in real-time) are needed. Whereas generalised rule induction has been explored for non-streaming data applications, its application and adaptation on streaming data is mostly undeveloped or based on periodic and ad-hoc training with batch algorithms. Some association rule mining approaches for streaming data do exist, however, they can only express binary causal relationships. This paper presents the ongoing work on Online Generalised Rule Induction (OGRI) in order to create expressive and adaptive rule sets real-time that can be applied to a broad range of applications, including network telemetry data streams.

Semantic mapping using mobile robots

Robotic mapping is the process of automatically constructing an environment representation using mobile robots. We address the problem of semantic mapping, which consists of using mobile robots to create maps that represent not only metric occupancy but also other properties of the environment. Specifically, we develop techniques to build maps that represent activity and navigability of the environment. Our approach to semantic mapping is to combine machine learning techniques with standard mapping algorithms. Supervised learning methods are used to automatically associate properties of space to the desired classification patterns. We present two methods, the first based on hidden Markov models and the second on support vector machines. Both approaches have been tested and experimentally validated in two problem domains: terrain mapping and activity-based mapping.

Ação pública na formação e transformação do destino turístico de Porto de Galinhas: um estudo dos referenciais no período de 1970 a 2010

The central interest of this thesis is to comprehend how the public action impels the formation and transformation of the tourist destinies. The research was based on the premise that the public actions are the result of the mediation process of state and non-state actors considered important in a section, which interact aiming for prevailing their interests and world visions above the others. The case of Porto de Galinhas beach, in Pernambuco, locus of the investigation of this thesis, allowed the analysis of a multiplicity of actors on the formation and implementation of local actions toward the development of the tourism between the years 1970 and 2010, as well as permitted the comprehension of the construction of the referential on the interventions made. This thesis, of a qualitative nature, has as theoretical support the cognitive approach of analysis of the public policies developed in France, and it has as main exponents the authors Bruno Jobert and Pierre Muller. This choice was made by the emphasis on the cognitive and normative factors of the politics, which aspects are not very explored in the studies of public policies in Brazil. As the source of the data collection, documental, bibliographic and field researches were utilized to the (re)constitution of the formation and transformation in the site concerned. The analysis techniques applied were the content and the documental analysis. To trace the public action referential, it started by the characterization of the touristic section frontiers and the creation of images by the main international body: the World Tourism Organization, of which analysis of the minutes of the meetings underscored guidelines to the member countries, including Brazil, which compounds the global-sectorial reference of the section. As from the analysis of the evolution of the tourism in the country, was identified that public policies in Brazil passed by transformations in their organization over the years, indicating changes in the referential that guided the interventions. These guidelines and transformations were identified in the construction of the tourist destination of Porto de Galinhas, of which data was systematized and presented in four historical periods, in which were discussed the values, the standard, the algorithms, the images and the important mediators. It has been revealed that the State worked in different roles in the decades analyzed in local tourism. From the 1990s, however, new actors were inserted in the formulation and implementation of policies developed, especially for local hotelkeepers. These, through their association, establishes a leadership relation in the local touristic section, thereby, they could set their hegemony and spread their own interest. The leadership acquired by a group of actors, in the case of Porto de Galinhas, does not mean that trade within the industry were neutralized, but that there is a cognitive framework that confronts the actors involved. In spite of the advances achieved by the work of the mediators in the last decades, that resulted in an amplification and diversification of the activity in the area, as well as the consolidation at the beach, as a tourist destiny of national standout, the position of the place is instable, concerned to the competitiveness, once that there is an situation of social and environmental unsustainability

On the solution of bounded and unbounded mixed complementarity problems

A reformulation of the bounded mixed complementarity problem is introduced. It is proved that the level sets of the objective function are bounded and, under reasonable assumptions, stationary points coincide with solutions of the original variational inequality problem. Therefore, standard minimization algorithms applied to the new reformulation must succeed. This result is applied to the compactification of unbounded mixed complementarity problems. © 2001 OPA (Overseas Publishers Association) N.V. Published by license under the Gordon and Breach Science Publishers imprint, a member of the Taylor & Francis Group.

Data dissemination over complex networks through gossip

This thesis offers a practical and theoretical evaluations about gossip-epidemic algorithms, comparing those most common in the literature with new proposed algorithms and analyzing their behavior. Tests have been executed using one hundred graphs that has been randomly generated by Large Unstructured NEtwork Simulator (LUNES), a simulation software provided by Parallel and Distributed Simulation Research Group (PADS), of the Department of Computer Science, Università di Bologna and simulated using Advanced RTI System (ARTÌS), based on the High Level Architecture standard. Literatures algorithms have been analyzed and taken as base for new algorithms.

Mg/Ca ratios in planktonic foraminifera

The primary Mg/Ca ratio of foraminiferal shells is a potentially valuable paleoproxy for sea surface temperature (SST) reconstructions. However, the reliable extraction of this ratio from sedimentary calcite assumes that we can overcome artifacts related to foraminiferal ecology and partial dissolution, as well as contamination by secondary calcite and clay. The standard batch method for Mg/Ca analysis involves cracking, sonicating, and rinsing the tests to remove clay, followed by chemical cleaning, and finally acid-digestion and single-point measurement. This laborious procedure often results in substantial loss of sample (typically 30-60%). We find that even the earliest steps of this procedure can fractionate Mg from Ca, thus biasing the result toward a more variable and often anomalously low Mg/Ca ratio. Moreover, the more rigorous the cleaning, the more calcite is lost, and the more likely it becomes that any residual clay that has not been removed by physical cleaning will increase the ratio. These potentially significant sources of error can be overcome with a flow-through (FT) sequential leaching method that makes time- and labor-intensive pretreatments unnecessary. When combined with time-resolved analysis (FT-TRA) flow-through, performed with a gradually increasing and highly regulated acid strength, produces continuous records of Mg, Sr, Al, and Ca concentrations in the leachate sorted by dissolution susceptibility of the reacting material. Flow-through separates secondary calcite from less susceptible biogenic calcite and clay, and further resolves the biogenic component into primary and more resistant fractions. FT-TRA reliably separates secondary calcite (which is not representative of original life habitats) from the more resistant biogenic calcite (the desired signal) and clay (a contaminant of high Mg/Ca, which also contains Al), and further resolves the biogenic component into primary and more resistant fractions that may reflect habitat or other changes during ontogeny. We find that the most susceptible fraction of biogenic calcite in surface dwelling foraminifera gives the most accurate value for SST and therefore best represents primary calcite. Sequential dissolution curves can be used to correct the primary Mg/Ca ratio for clay, if necessary. However, the temporal separation of calcite from clay in FT-TRA is so complete that this correction is typically <=2%, even in clay-rich sediments. Unlike hands-on batch methods, that are difficult to reproduce exactly, flow-through lends itself to automation, providing precise replication of treatment for every sample. Our automated flow-through system can process 22 samples, two system blanks, and 48 mixed standards in <12 hours of unattended operation. FT-TRA thus represents a faster, cheaper, and better way to determine Mg/Ca ratios in foraminiferal calcite.