Modelling the dynamics of genetic algorithms using statistical mechanics

A formalism for modelling the dynamics of Genetic Algorithms (GAs) using methods from statistical mechanics, originally due to Prugel-Bennett and Shapiro, is reviewed, generalized and improved upon. This formalism can be used to predict the averaged trajectory of macroscopic statistics describing the GA's population. These macroscopics are chosen to average well between runs, so that fluctuations from mean behaviour can often be neglected. Where necessary, non-trivial terms are determined by assuming maximum entropy with constraints on known macroscopics. Problems of realistic size are described in compact form and finite population effects are included, often proving to be of fundamental importance. The macroscopics used here are cumulants of an appropriate quantity within the population and the mean correlation (Hamming distance) within the population. Including the correlation as an explicit macroscopic provides a significant improvement over the original formulation. The formalism is applied to a number of simple optimization problems in order to determine its predictive power and to gain insight into GA dynamics. Problems which are most amenable to analysis come from the class where alleles within the genotype contribute additively to the phenotype. This class can be treated with some generality, including problems with inhomogeneous contributions from each site, non-linear or noisy fitness measures, simple diploid representations and temporally varying fitness. The results can also be applied to a simple learning problem, generalization in a binary perceptron, and a limit is identified for which the optimal training batch size can be determined for this problem. The theory is compared to averaged results from a real GA in each case, showing excellent agreement if the maximum entropy principle holds. Some situations where this approximation brakes down are identified. In order to fully test the formalism, an attempt is made on the strong sc np-hard problem of storing random patterns in a binary perceptron. Here, the relationship between the genotype and phenotype (training error) is strongly non-linear. Mutation is modelled under the assumption that perceptron configurations are typical of perceptrons with a given training error. Unfortunately, this assumption does not provide a good approximation in general. It is conjectured that perceptron configurations would have to be constrained by other statistics in order to accurately model mutation for this problem. Issues arising from this study are discussed in conclusion and some possible areas of further research are outlined.

Bandwidth management of WiMAX systems and performance modeling

WiMAX has been introduced as a competitive alternative for metropolitan broadband wireless access technologies. It is connection oriented and it can provide very high data rates, large service coverage, and flexible quality of services (QoS). Due to the large number of connections and flexible QoS supported by WiMAX, the uplink access in WiMAX networks is very challenging since the medium access control (MAC) protocol must efficiently manage the bandwidth and related channel allocations. In this paper, we propose and investigate a cost-effective WiMAX bandwidth management scheme, named the WiMAX partial sharing scheme (WPSS), in order to provide good QoS while achieving better bandwidth utilization and network throughput. The proposed bandwidth management scheme is compared with a simple but inefficient scheme, named the WiMAX complete sharing scheme (WCPS). A maximum entropy (ME) based analytical model (MEAM) is proposed for the performance evaluation of the two bandwidth management schemes. The reason for using MEAM for the performance evaluation is that MEAM can efficiently model a large-scale system in which the number of stations or connections is generally very high, while the traditional simulation and analytical (e.g., Markov models) approaches cannot perform well due to the high computation complexity. We model the bandwidth management scheme as a queuing network model (QNM) that consists of interacting multiclass queues for different service classes. Closed form expressions for the state and blocking probability distributions are derived for those schemes. Simulation results verify the MEAM numerical results and show that WPSS can significantly improve the network's performance compared to WCPS.

A Bayesian modeling approach to multi-dimensional sentiment distributions prediction

Sentiment analysis has long focused on binary classification of text as either positive or negative. There has been few work on mapping sentiments or emotions into multiple dimensions. This paper studies a Bayesian modeling approach to multi-class sentiment classification and multidimensional sentiment distributions prediction. It proposes effective mechanisms to incorporate supervised information such as labeled feature constraints and document-level sentiment distributions derived from the training data into model learning. We have evaluated our approach on the datasets collected from the confession section of the Experience Project website where people share their life experiences and personal stories. Our results show that using the latent representation of the training documents derived from our approach as features to build a maximum entropy classifier outperforms other approaches on multi-class sentiment classification. In the more difficult task of multi-dimensional sentiment distributions prediction, our approach gives superior performance compared to a few competitive baselines. © 2012 ACM.

Feature LDA:a supervised topic model for automatic detection of web API documentations from the web

Web APIs have gained increasing popularity in recent Web service technology development owing to its simplicity of technology stack and the proliferation of mashups. However, efficiently discovering Web APIs and the relevant documentations on the Web is still a challenging task even with the best resources available on the Web. In this paper we cast the problem of detecting the Web API documentations as a text classification problem of classifying a given Web page as Web API associated or not. We propose a supervised generative topic model called feature latent Dirichlet allocation (feaLDA) which offers a generic probabilistic framework for automatic detection of Web APIs. feaLDA not only captures the correspondence between data and the associated class labels, but also provides a mechanism for incorporating side information such as labelled features automatically learned from data that can effectively help improving classification performance. Extensive experiments on our Web APIs documentation dataset shows that the feaLDA model outperforms three strong supervised baselines including naive Bayes, support vector machines, and the maximum entropy model, by over 3% in classification accuracy. In addition, feaLDA also gives superior performance when compared against other existing supervised topic models.

Strategic sourcing:a combined QFD and AHP approach in manufacturing

Purpose – This paper aims to develop an integrated analytical approach, combining quality function deployment (QFD) and analytic hierarchy process (AHP) approach, to enhance the effectiveness of sourcing decisions. Design/methodology/approach – In the approach, QFD is used to translate the company stakeholder requirements into multiple evaluating factors for supplier selection, which are used to benchmark the suppliers. AHP is used to determine the importance of evaluating factors and preference of each supplier with respect to each selection criterion. Findings – The effectiveness of the proposed approach is demonstrated by applying it to a UK-based automobile manufacturing company. With QFD, the evaluating factors are related to the strategic intent of the company through the involvement of concerned stakeholders. This ensures successful strategic sourcing. The application of AHP ensures consistent supplier performance measurement using benchmarking approach. Research limitations/implications – The proposed integrated approach can be principally adopted in other decision-making scenarios for effective management of the supply chain. Practical implications – The proposed integrated approach can be used as a group-based decision support system for supplier selection, in which all relevant stakeholders are involved to identify various quantitative and qualitative evaluating criteria, and their importance. Originality/value – Various approaches that can deal with multiple and conflicting criteria have been adopted for the supplier selection. However, they fail to consider the impact of business objectives and the requirements of company stakeholders in the identification of evaluating criteria for strategic supplier selection. The proposed integrated approach outranks the conventional approaches to supplier selection and supplier performance measurement because the sourcing strategy and supplier selection are derived from the corporate/business strategy.

Oblique matching pursuit

A method for selecting a suitable subspace for discriminating signal components through an oblique projection is proposed. The selection criterion is based on the consistency principle introduced by Unser and Aldroubi and extended by Elder. An effective implementation of this principle for the purpose of subspace selection is achieved by updating of the dual vectors yielding the corresponding oblique projector. © 2007 IEEE.

Online learning in discrete hidden Markov models

We present and analyze three different online algorithms for learning in discrete Hidden Markov Models (HMMs) and compare their performance with the Baldi-Chauvin Algorithm. Using the Kullback-Leibler divergence as a measure of the generalization error we draw learning curves in simplified situations and compare the results. The performance for learning drifting concepts of one of the presented algorithms is analyzed and compared with the Baldi-Chauvin algorithm in the same situations. A brief discussion about learning and symmetry breaking based on our results is also presented. © 2006 American Institute of Physics.

Classifier PGN: Classification with High Confidence Rules

ACM Computing Classification System (1998): H.2.8, H.3.3.

Landscape genetics of Phaedranassa herb. (Amaryllidaceae) in Ecuador

Speciation can be understood as a continuum occurring at different levels, from population to species. The recent molecular revolution in population genetics has opened a pathway towards understanding species evolution. At the same time, speciation patterns can be better explained by incorporating a geographic context, through the use of geographic information systems (GIS). Phaedranassa (Amaryllidaceae) is a genus restricted to one of the world’s most biodiverse hotspots, the Northern Andes. I studied seven Phaedranassa species from Ecuador. Six of these species are endemic to the country. The topographic complexity of the Andes, which creates local microhabitats ranging from moist slopes to dry valleys, might explain the patterns of Phaedranassa species differentiation. With a Bayesian individual assignment approach, I assessed the genetic structure of the genus throughout Ecuador using twelve microsatellite loci. I also used bioclimatic variables and species geographic coordinates under a Maximum Entropy algorithm to generate distribution models of the species. My results show that Phaedranassa species are genetically well-differentiated. Furthermore, with the exception of two species, all Phaedranassa showed non-overlapping distributions. Phaedranassa viridiflora and P. glauciflora were the only species in which the model predicted a broad species distribution, but genetic evidence indicates that these findings are likely an artifact of species delimitation issues. Both genetic differentiation and nonoverlapping geographic distribution suggest that allopatric divergence could be the general model of genetic differentiation. Evidence of sympatric speciation was found in two geographically and genetically distinct groups of P. viridiflora. Additionally, I report the first register of natural hybridization for the genus. The findings of this research show that the genetic differentiation of species in an intricate landscape as the Andes does not necessarily show a unique trend. Although allopatric speciation is the most common form of speciation, I found evidence of sympatric speciation and hybridization. These results show that the processes of speciation in the Andes have followed several pathways. The mixture of these processes contributes to the high biodiversity of the region.

Energy-efficient self -organization of wireless acoustic sensor networks for ground target tracking

With the developments in computing and communication technologies, wireless sensor networks have become popular in wide range of application areas such as health, military, environment and habitant monitoring. Moreover, wireless acoustic sensor networks have been widely used for target tracking applications due to their passive nature, reliability and low cost. Traditionally, acoustic sensor arrays built in linear, circular or other regular shapes are used for tracking acoustic sources. The maintaining of relative geometry of the acoustic sensors in the array is vital for accurate target tracking, which greatly reduces the flexibility of the sensor network. To overcome this limitation, we propose using only a single acoustic sensor at each sensor node. This design greatly improves the flexibility of the sensor network and makes it possible to deploy the sensor network in remote or hostile regions through air-drop or other stealth approaches. Acoustic arrays are capable of performing the target localization or generating the bearing estimations on their own. However, with only a single acoustic sensor, the sensor nodes will not be able to generate such measurements. Thus, self-organization of sensor nodes into virtual arrays to perform the target localization is essential. We developed an energy-efficient and distributed self-organization algorithm for target tracking using wireless acoustic sensor networks. The major error sources of the localization process were studied, and an energy-aware node selection criterion was developed to minimize the target localization errors. Using this node selection criterion, the self-organization algorithm selects a near-optimal localization sensor group to minimize the target tracking errors. In addition, a message passing protocol was developed to implement the self-organization algorithm in a distributed manner. In order to achieve extended sensor network lifetime, energy conservation was incorporated into the self-organization algorithm by incorporating a sleep-wakeup management mechanism with a novel cross layer adaptive wakeup probability adjustment scheme. The simulation results confirm that the developed self-organization algorithm provides satisfactory target tracking performance. Moreover, the energy saving analysis confirms the effectiveness of the cross layer power management scheme in achieving extended sensor network lifetime without degrading the target tracking performance.

Influence of Restaurant Reviews Upon Consumers

It is generally believed that restaurant reviews can influence consumers' decisions in choosing a restaurant. A survey administered to a sample of 420 college faculty and staff members suggests that while most restaurant patrons may read reviews, they are not used as the sole selection criterion. Recommendations of friends, the restaurant's current reputation, and perceived value may have greater influence upon the choice than does a re- view. The authors discuss the implications of both favorable and unfavorable reviews.

Energy-Efficient Self-Organization of Wireless Acoustic Sensor Networks for Ground Target Tracking

With the developments in computing and communication technologies, wireless sensor networks have become popular in wide range of application areas such as health, military, environment and habitant monitoring. Moreover, wireless acoustic sensor networks have been widely used for target tracking applications due to their passive nature, reliability and low cost. Traditionally, acoustic sensor arrays built in linear, circular or other regular shapes are used for tracking acoustic sources. The maintaining of relative geometry of the acoustic sensors in the array is vital for accurate target tracking, which greatly reduces the flexibility of the sensor network. To overcome this limitation, we propose using only a single acoustic sensor at each sensor node. This design greatly improves the flexibility of the sensor network and makes it possible to deploy the sensor network in remote or hostile regions through air-drop or other stealth approaches. Acoustic arrays are capable of performing the target localization or generating the bearing estimations on their own. However, with only a single acoustic sensor, the sensor nodes will not be able to generate such measurements. Thus, self-organization of sensor nodes into virtual arrays to perform the target localization is essential. We developed an energy-efficient and distributed self-organization algorithm for target tracking using wireless acoustic sensor networks. The major error sources of the localization process were studied, and an energy-aware node selection criterion was developed to minimize the target localization errors. Using this node selection criterion, the self-organization algorithm selects a near-optimal localization sensor group to minimize the target tracking errors. In addition, a message passing protocol was developed to implement the self-organization algorithm in a distributed manner. In order to achieve extended sensor network lifetime, energy conservation was incorporated into the self-organization algorithm by incorporating a sleep-wakeup management mechanism with a novel cross layer adaptive wakeup probability adjustment scheme. The simulation results confirm that the developed self-organization algorithm provides satisfactory target tracking performance. Moreover, the energy saving analysis confirms the effectiveness of the cross layer power management scheme in achieving extended sensor network lifetime without degrading the target tracking performance.

Ecologia e história natural de população Hemidactylus agrius (Squamata: Gekkonidae) em área de Caatinga, com avaliação da distribuição das espécies nativas do gênero no nordeste do Brasil

The genus Hemidactylus Oken, 1817 has cosmopolite distribution, with three species occurring in Brazil, two of them native, H. brasilianus and H. agrius, and one exotic, H. mabouia. Considering the studies about ecology of lizards conducted in the Ecological Station of the Seridó, from 2001 to 2011, this study aimed (1) to re-evaluate the occurrence of the species of Hemidactylus in this ESEC; (2) to analyze ecological and biological aspects of the H. agrius population; and (3) to investigate the current and potential distribution of the native species of the genus in northeastern Brazil, analyzing the suitability of ESEC to this taxon. For the first two objectives, a sampling area consisting of five transects of 200 x 20 m, was inspected in alternating daily shifts for three consecutive days, from August 2012 to August 2013. For the latter objective, occurrence points of H. agrius and H. brasilianus from literature and from the database of Herpetological Collections of the UFRN and the UNICAMP were consulted to build predictive maps via the Maximum Entropy algorithm (MaxEnt). In ESEC Seridó, 62 H. agrius individuals were collected (25 females, 18 males and 19 juveniles), and two neonates were obtained from a communal nest incubated in the laboratory. No record was made for the other two species of the genus. Hemidactylus agrius demonstrated to be a nocturnal species specialized in habitats with rocky outcrops; but this species is generalist regarding microhabitat use. In the population studied, females had an average body length greater than males, and showed higher frequencies of caudal autotomy. Regarding diet, H. agrius is a moderately generalist species that consumes arthropods, especially insect larvae, Isoptera and Araneae; and vertebrates, with a case of cannibalism registered in the population. With respect to seasonal differences, only the number of food items ingested differed between seasons. The diet was similar between sexes, but ontogenetic differences were recorded for the total volume and maximum length of the food items. Significant relationships were found between lizard body/head size measurements and the maximum length of prey consumed. Cases of polydactyly and tail bifurcation were recorded in the population, with frequencies of 1.6% and 3.1%, respectively. In relation xv to the occurrence points of the native species, 27 were identified, 14 for H. agrius and 13 for H. brasilianus. The first species presented restricted distribution, while the second showed a wide distribution. In both models generated, the ESEC Seridó area showed medium to high suitability. The results of this study confirm the absence of H. brasilianus and H. mabouia this ESEC, and reveal H. agrius as a dietary opportunist and cannibal species. Further, the results confirm the distribution patterns shown by native species of Hemidactylus, and point ESEC Seridó as an area of probable occurrence for the species of the genus, the establishing of H. brasilianus and H. mabouia are probably limited by biotic factors, a fact yet little understood

Mapped cetacean habitat suitability and richness in the Azores, links to ArcGIS files

Marine spatial planning and ecological research call for high-resolution species distribution data. However, those data are still not available for most marine large vertebrates. The dynamic nature of oceanographic processes and the wide-ranging behavior of many marine vertebrates create further difficulties, as distribution data must incorporate both the spatial and temporal dimensions. Cetaceans play an essential role in structuring and maintaining marine ecosystems and face increasing threats from human activities. The Azores holds a high diversity of cetaceans but the information about spatial and temporal patterns of distribution for this marine megafauna group in the region is still very limited. To tackle this issue, we created monthly predictive cetacean distribution maps for spring and summer months, using data collected by the Azores Fisheries Observer Programme between 2004 and 2009. We then combined the individual predictive maps to obtain species richness maps for the same period. Our results reflect a great heterogeneity in distribution among species and within species among different months. This heterogeneity reflects a contrasting influence of oceanographic processes on the distribution of cetacean species. However, some persistent areas of increased species richness could also be identified from our results. We argue that policies aimed at effectively protecting cetaceans and their habitats must include the principle of dynamic ocean management coupled with other area-based management such as marine spatial planning.

Learning and Exploiting Camera Geometry for Computer Vision

This work explores the use of statistical methods in describing and estimating camera poses, as well as the information feedback loop between camera pose and object detection. Surging development in robotics and computer vision has pushed the need for algorithms that infer, understand, and utilize information about the position and orientation of the sensor platforms when observing and/or interacting with their environment.

The first contribution of this thesis is the development of a set of statistical tools for representing and estimating the uncertainty in object poses. A distribution for representing the joint uncertainty over multiple object positions and orientations is described, called the mirrored normal-Bingham distribution. This distribution generalizes both the normal distribution in Euclidean space, and the Bingham distribution on the unit hypersphere. It is shown to inherit many of the convenient properties of these special cases: it is the maximum-entropy distribution with fixed second moment, and there is a generalized Laplace approximation whose result is the mirrored normal-Bingham distribution. This distribution and approximation method are demonstrated by deriving the analytical approximation to the wrapped-normal distribution. Further, it is shown how these tools can be used to represent the uncertainty in the result of a bundle adjustment problem.

Another application of these methods is illustrated as part of a novel camera pose estimation algorithm based on object detections. The autocalibration task is formulated as a bundle adjustment problem using prior distributions over the 3D points to enforce the objects' structure and their relationship with the scene geometry. This framework is very flexible and enables the use of off-the-shelf computational tools to solve specialized autocalibration problems. Its performance is evaluated using a pedestrian detector to provide head and foot location observations, and it proves much faster and potentially more accurate than existing methods.

Finally, the information feedback loop between object detection and camera pose estimation is closed by utilizing camera pose information to improve object detection in scenarios with significant perspective warping. Methods are presented that allow the inverse perspective mapping traditionally applied to images to be applied instead to features computed from those images. For the special case of HOG-like features, which are used by many modern object detection systems, these methods are shown to provide substantial performance benefits over unadapted detectors while achieving real-time frame rates, orders of magnitude faster than comparable image warping methods.

The statistical tools and algorithms presented here are especially promising for mobile cameras, providing the ability to autocalibrate and adapt to the camera pose in real time. In addition, these methods have wide-ranging potential applications in diverse areas of computer vision, robotics, and imaging.