text:
# regression coefficient sign is opposite of correlation but VIF is low?

I have used best subset regression with various selection criteria (e.g. Mallow's Cp and AIC) to compile a list of possible regression models to explain the response variable "Length". Below is the best model of the bunch,

Length = 5.770 + 0.1180 Max flow field width + 0.02691 time until ff + 0.1897 Duration of FF - 0.0465 Cooling dominate phase

however the coefficient for "cooling dominate phase" is negative in the regression but it has a positive correlation to the response variable. Here is the table correlation coefficients for the response and predictor variables in the model.

The VIF scores are all under 2 but being above 1 it suggests there is some degree of collinearity or multicollinearity happening. Here are the VIF's.

Can I still have confidence in the accuracy of the regression coefficients if the VIF's are low but the sign of a predictor variable coefficient is opposite from its correlation to the response variable?

• "opposite from its correlation to the response variable?" I am not sure what this means. Your outputs do not show any information on the response variable. Are you concern about the -0.17? – Penguin_Knight Mar 12 '18 at 15:13
• You seem undecided about what you want to do: if you're doing multiple regression, then it is pointless to compare its coefficient estimates to a single correlation coefficient (which is a simple regression). Multiple regression and simple regression are two different models and there is no necessary relationship between their results. – whuber Mar 12 '18 at 15:24

It's possible that the regression coefficients from a one-predictor regression and from a multiple-predictor regression being different. The signs do not need to agree, so aren't their magnitudes. So, what you see here is not abnormal.

While the VIF are not "high," the individual $R^2$ are not small. For example, take VIF 1.94:

$$VIF = \frac{1}{1 - R^2_{duration\ of\ FF}}$$

$$1/1.94= 1 - R^2_{duration\ of\ FF}$$

$$R^2_{duration\ of\ FF}= 1 - 1/1.94$$

$$R^2_{duration\ of\ FF}= 0.484$$

About 48% of the variability in "Duration of FF" can be explained by the other three independent predictors. Their correlations are not as weak as you think.

Can I still have confidence in the accuracy of the regression coefficients if the VIF's are low but the sign of a predictor variable coefficient is opposite from its correlation to the response variable?

Since you mentioned you selected many subsets so I guess your doing some sort of predictive model? If so, does this version give you the best prediction?

• @ Penguin_Knight. Thanks for your reply. The tolerance of the predictor variables has one of the things I have been wrestling with. I am trying to come up with a predictive model but also would like to try and identify which set of variables best describe length and what that model is. The one listed in the question is not the best of the predictive models, but is the one that had the best balance between predictive power while still maintaining low VIF scores. – user3169598 Mar 12 '18 at 16:02


text:
# Natural selection

(Redirected from Natural Selection)

Natural selection is the differential survival and reproduction of individuals due to differences in phenotype. It is a key mechanism of evolution, the change in heritable traits of a population over time. Charles Darwin popularised the term "natural selection", and compared it with artificial selection.

Variation exists within all populations of organisms. This occurs partly because random mutations arise in the genome of an individual organism, and offspring can inherit such mutations. Throughout the lives of the individuals, their genomes interact with their environments to cause variations in traits. The environment of a genome includes the molecular biology in the cell, other cells, other individuals, populations, species, as well as the abiotic environment. Individuals with certain variants of the trait may survive and reproduce more than individuals with other, less successful, variants; therefore, the population evolves. Factors that affect reproductive success are also important, including sexual selection (now often included in natural selection) and fecundity selection.

Natural selection acts on the phenotype, or the observable characteristics of an organism, but the genetic (heritable) basis of any phenotype that gives a reproductive advantage may become more common in a population. Over time, this process can result in populations that specialise for particular ecological niches (microevolution) and may eventually result in speciation (the emergence of new species, macroevolution). In other words, natural selection is a key process in the evolution of a population. Natural selection can be contrasted with artificial selection, in which humans intentionally choose specific traits, whereas in natural selection there is no intentional choice.

Natural selection is one of the cornerstones of modern biology. The concept, published by Darwin and Alfred Russel Wallace in a joint presentation of papers in 1858, was elaborated in Darwin's influential 1859 book On the Origin of Species by Means of Natural Selection, or the Preservation of Favoured Races in the Struggle for Life, which described natural selection as analogous to artificial selection, a process by which animals and plants with traits considered desirable by human breeders are systematically favoured for reproduction. The concept of natural selection originally developed in the absence of a valid theory of heredity; at the time of Darwin's writing, science had yet to develop modern theories of genetics. The union of traditional Darwinian evolution with subsequent discoveries in classical genetics formed the modern synthesis of the mid-20th century. The addition of molecular genetics has led to evolutionary developmental biology, which explains evolution at the molecular level. While genotypes can slowly change by random genetic drift, natural selection remains the primary explanation for adaptive evolution.

## Historical development

### Pre-Darwinian theories

Aristotle considered whether different forms could have appeared, only the useful ones surviving.

Several philosophers of the classical era, including Empedocles[1] and his intellectual successor, the Roman poet Lucretius,[2] expressed the idea that nature produces a huge variety of creatures, randomly, and that only those creatures that manage to provide for themselves and reproduce successfully persist. Empedocles' idea that organisms arose entirely by the incidental workings of causes such as heat and cold was criticised by Aristotle in Book II of Physics.[3] He posited natural teleology in its place, and believed that form was achieved for a purpose, citing the regularity of heredity in species as proof.[4][5] Nevertheless, he accepted in his biology that new types of animals, monstrosities (τερας), can occur in very rare instances (Generation of Animals, Book IV).[6] As quoted in Darwin's 1872 edition of The Origin of Species, Aristotle considered whether different forms (e.g., of teeth) might have appeared accidentally, but only the useful forms survived:

So what hinders the different parts [of the body] from having this merely accidental relation in nature? as the teeth, for example, grow by necessity, the front ones sharp, adapted for dividing, and the grinders flat, and serviceable for masticating the food; since they were not made for the sake of this, but it was the result of accident. And in like manner as to the other parts in which there appears to exist an adaptation to an end. Wheresoever, therefore, all things together (that is all the parts of one whole) happened like as if they were made for the sake of something, these were preserved, having been appropriately constituted by an internal spontaneity, and whatsoever things were not thus constituted, perished, and still perish.

— Aristotle, Physics, Book II, Chapter 8[7]

But Aristotle rejected this possibility in the next paragraph, making clear that he is talking about the development of animals as embryos with the phrase "either invariably or normally come about", not the origin of species:

... Yet it is impossible that this should be the true view. For teeth and all other natural things either invariably or normally come about in a given way; but of not one of the results of chance or spontaneity is this true. We do not ascribe to chance or mere coincidence the frequency of rain in winter, but frequent rain in summer we do; nor heat in the dog-days, but only if we have it in winter. If then, it is agreed that things are either the result of coincidence or for an end, and these cannot be the result of coincidence or spontaneity, it follows that they must be for an end; and that such things are all due to nature even the champions of the theory which is before us would agree. Therefore action for an end is present in things which come to be and are by nature.

— Aristotle, Physics, Book II, Chapter 8[8]

The struggle for existence was later described by the Islamic writer Al-Jahiz in the 9th century.[9][10][11]

The classical arguments were reintroduced in the 18th century by Pierre Louis Maupertuis[12] and others, including Darwin's grandfather, Erasmus Darwin.

Until the early 19th century, the prevailing view in Western societies was that differences between individuals of a species were uninteresting departures from their Platonic ideals (or typus) of created kinds. However, the theory of uniformitarianism in geology promoted the idea that simple, weak forces could act continuously over long periods of time to produce radical changes in the Earth's landscape. The success of this theory raised awareness of the vast scale of geological time and made plausible the idea that tiny, virtually imperceptible changes in successive generations could produce consequences on the scale of differences between species.[13]

The early 19th-century zoologist Jean-Baptiste Lamarck suggested the inheritance of acquired characteristics as a mechanism for evolutionary change; adaptive traits acquired by an organism during its lifetime could be inherited by that organism's progeny, eventually causing transmutation of species.[14] This theory, Lamarckism, was an influence on the Soviet biologist Trofim Lysenko's antagonism to mainstream genetic theory as late as the mid 20th century.[15]

Between 1835 and 1837, the zoologist Edward Blyth worked on the area of variation, artificial selection, and how a similar process occurs in nature. Darwin acknowledged Blyth's ideas in the first chapter on variation of On the Origin of Species.[16]

### Darwin's theory

The modern theory of natural selection derives from Charles Darwin's work in the nineteenth century.

In 1859, Charles Darwin set out his theory of evolution by natural selection as an explanation for adaptation and speciation. He defined natural selection as the "principle by which each slight variation [of a trait], if useful, is preserved".[17] The concept was simple but powerful: individuals best adapted to their environments are more likely to survive and reproduce. As long as there is some variation between them and that variation is heritable, there will be an inevitable selection of individuals with the most advantageous variations. If the variations are heritable, then differential reproductive success leads to a progressive evolution of particular populations of a species, and populations that evolve to be sufficiently different eventually become different species.[18][19]

Darwin's ideas were inspired by the observations that he had made on the second voyage of HMS Beagle (1831–1836), and by the work of a political economist, Thomas Robert Malthus, who, in An Essay on the Principle of Population (1798), noted that population (if unchecked) increases exponentially, whereas the food supply grows only arithmetically; thus, inevitable limitations of resources would have demographic implications, leading to a "struggle for existence".[20] When Darwin read Malthus in 1838 he was already primed by his work as a naturalist to appreciate the "struggle for existence" in nature and it struck him that as population outgrew resources, "favourable variations would tend to be preserved, and unfavourable ones to be destroyed. The result of this would be the formation of new species."[21] Darwin wrote:

If during the long course of ages and under varying conditions of life, organic beings vary at all in the several parts of their organisation, and I think this cannot be disputed; if there be, owing to the high geometrical powers of increase of each species, at some age, season, or year, a severe struggle for life, and this certainly cannot be disputed; then, considering the infinite complexity of the relations of all organic beings to each other and to their conditions of existence, causing an infinite diversity in structure, constitution, and habits, to be advantageous to them, I think it would be a most extraordinary fact if no variation ever had occurred useful to each being's own welfare, in the same way as so many variations have occurred useful to man. But if variations useful to any organic being do occur, assuredly individuals thus characterised will have the best chance of being preserved in the struggle for life; and from the strong principle of inheritance they will tend to produce offspring similarly characterised. This principle of preservation, I have called, for the sake of brevity, Natural Selection.

— Darwin summarising natural selection in the fourth chapter of On the Origin of Species [22]

Once he had his theory, Darwin was meticulous about gathering and refining evidence before making his idea public. He was in the process of writing his "big book" to present his research when the naturalist Alfred Russel Wallace independently conceived of the principle and described it in an essay he sent to Darwin to forward to Charles Lyell. Lyell and Joseph Dalton Hooker decided to present his essay together with unpublished writings that Darwin had sent to fellow naturalists, and On the Tendency of Species to form Varieties; and on the Perpetuation of Varieties and Species by Natural Means of Selection was read to the Linnean Society of London announcing co-discovery of the principle in July 1858.[23] Darwin published a detailed account of his evidence and conclusions in On the Origin of Species in 1859. In the 3rd edition of 1861 Darwin acknowledged that others—like William Charles Wells in 1813, and Patrick Matthew in 1831—had proposed similar ideas, but had neither developed them nor presented them in notable scientific publications.[24]

Darwin thought of natural selection by analogy to how farmers select crops or livestock for breeding, which he called "artificial selection"; in his early manuscripts he referred to a "Nature" which would do the selection. At the time, other mechanisms of evolution such as evolution by genetic drift were not yet explicitly formulated, and Darwin believed that selection was likely only part of the story: "I am convinced that Natural Selection has been the main but not exclusive means of modification."[25] In a letter to Charles Lyell in September 1860, Darwin regretted the use of the term "Natural Selection", preferring the term "Natural Preservation".[26]

For Darwin and his contemporaries, natural selection was in essence synonymous with evolution by natural selection. After the publication of On the Origin of Species,[27] educated people generally accepted that evolution had occurred in some form. However, natural selection remained controversial as a mechanism, partly because it was perceived to be too weak to explain the range of observed characteristics of living organisms, and partly because even supporters of evolution balked at its "unguided" and non-progressive nature,[28] a response that has been characterised as the single most significant impediment to the idea's acceptance.[29] However, some thinkers enthusiastically embraced natural selection; after reading Darwin, Herbert Spencer introduced the phrase survival of the fittest, which became a popular summary of the theory.[30][31] The fifth edition of On the Origin of Species published in 1869 included Spencer's phrase as an alternative to natural selection, with credit given: "But the expression often used by Mr. Herbert Spencer of the Survival of the Fittest is more accurate, and is sometimes equally convenient."[32] Although the phrase is still often used by non-biologists, modern biologists avoid it because it is tautological if "fittest" is read to mean "functionally superior" and is applied to individuals rather than considered as an averaged quantity over populations.[33]

### The modern synthesis

Main article: Modern synthesis

Natural selection relies crucially on the idea of heredity, but developed before the basic concepts of genetics. Although the Moravian monk Gregor Mendel, the father of modern genetics, was a contemporary of Darwin's, his work lay in obscurity, only being rediscovered in 1900.[34] Only after the mid-20th century integration of evolution with Mendel's laws of inheritance, the so-called modern synthesis, did scientists generally come to accept natural selection.[35][36] The synthesis grew from advances in different fields. Ronald Fisher developed the required mathematical language and wrote The Genetical Theory of Natural Selection (1930).[37] J. B. S. Haldane introduced the concept of the "cost" of natural selection.[38][39] Sewall Wright elucidated the nature of selection and adaptation.[40] Theodosius Dobzhansky established the idea that mutation, by creating genetic diversity, supplied the raw material for natural selection, in his book Genetics and the Origin of Species (1937).[41][42]

### A second synthesis

Evolutionary developmental biology relates the evolution of form to the precise pattern of gene activity, here gap genes in the fruit fly, during embryonic development.[43]

Ernst Mayr recognised the key importance of reproductive isolation for speciation in his Systematics and the Origin of Species (1942).[44] W. D. Hamilton conceived of kin selection in 1964.[45][46] This synthesis cemented natural selection as the foundation of evolutionary theory, where it remains today. A second synthesis was brought about at the end of the 20th century by advances in molecular genetics, creating the field of evolutionary developmental biology ("evo-devo"), which seeks to explain the evolution of form in terms of the genetic regulatory programs which control the development of the embryo at molecular level. Natural selection is here understood to act on embryonic development to change the morphology of the adult body.[47][48][49][50]

## Terminology

The term natural selection is most often defined to operate on heritable traits, because these directly participate in evolution. However, natural selection is "blind" in the sense that changes in phenotype can give a reproductive advantage regardless of whether or not the trait is heritable. Following Darwin's primary usage, the term is used to refer both to the evolutionary consequence of blind selection and to its mechanisms.[27][37][51][52] It is sometimes helpful to explicitly distinguish between selection's mechanisms and its effects; when this distinction is important, scientists define "(phenotypic) natural selection" specifically as "those mechanisms that contribute to the selection of individuals that reproduce", without regard to whether the basis of the selection is heritable.[53][54][55] Traits that cause greater reproductive success of an organism are said to be selected for, while those that reduce success are selected against.[56]

## Mechanism

### Heritable variation, differential reproduction

During the industrial revolution, pollution killed many lichens, leaving tree trunks dark. A dark (melanic) morph of the peppered moth largely replaced the formerly usual light morph (both shown here). Since the moths are subject to predation by birds hunting by sight, the colour change offers better camouflage against the changed background, suggesting natural selection at work.
Main article: Genetic variation

Natural variation occurs among the individuals of any population of organisms. Some differences may improve an individual's chances of surviving and reproducing, so that its lifetime reproductive rate is increased: it leaves more offspring. If the traits that give these individuals a reproductive advantage are also heritable, that is, passed from parent to offspring, then there will be differential reproduction, that is, a slightly higher proportion of fast rabbits or efficient algae in the next generation. Even if the reproductive advantage is very slight, over many generations any advantageous heritable trait becomes dominant in the population. In this way the natural environment of an organism "selects for" traits that confer a reproductive advantage, causing evolutionary change, as Darwin described.[57] This gives the appearance of purpose, but in natural selection there is no intentional choice. Artificial selection is purposive where natural selection is not, though biologists often use teleological language to describe it.[58]

The peppered moth exists in both light and dark colours in Great Britain, but during the industrial revolution, many of the trees on which the moths rested became blackened by soot, giving the dark-coloured moths an advantage in hiding from predators. This gave dark-coloured moths a better chance of surviving to produce dark-coloured offspring, and in just fifty years from the first dark moth being caught, nearly all of the moths in industrial Manchester were dark. The balance was reversed by the effect of the Clean Air Act 1956, and the dark moths became rare again, demonstrating the influence of natural selection on peppered moth evolution.[59]

### Fitness

Main article: Fitness (biology)

The concept of fitness is central to natural selection. In broad terms, individuals that are more "fit" have better potential for survival, as in the well-known phrase "survival of the fittest", but the precise meaning of the term is much more subtle. Modern evolutionary theory defines fitness not by how long an organism lives, but by how successful it is at reproducing. If an organism lives half as long as others of its species, but has twice as many offspring surviving to adulthood, its genes become more common in the adult population of the next generation. Though natural selection acts on individuals, the effects of chance mean that fitness can only really be defined "on average" for the individuals within a population. The fitness of a particular genotype corresponds to the average effect on all individuals with that genotype.[60]

### Competition

Main article: Competition (biology)

In biology, competition is an interaction between organisms in which the fitness of one is lowered by the presence of another. This may be because both rely on a limited supply of a resource such as food, water, or territory.[61] Competition may be within or between species, and may be direct or indirect.[62] Species less suited to compete should in theory either adapt or die out, since competition plays a powerful role in natural selection, but according to the "room to roam" theory it may be less important than expansion among larger clades.[62][63]

Competition is modelled by r/K selection theory, which is based on Robert MacArthur and E. O. Wilson's work on island biogeography.[64] In this theory, selective pressures drive evolution in one of two stereotyped directions: r- or K-selection.[65] These terms, r and K, can be illustrated in a logistic model of population dynamics:[66]

${\displaystyle {\frac {dN}{dt}}=rN\left(1-{\frac {N}{K}}\right)\qquad \!}$

where r is the growth rate of the population (N), and K is the carrying capacity of its local environmental setting. Typically, r-selected species exploit empty niches, and produce many offspring, each with a relatively low probability of surviving to adulthood. In contrast, K-selected species are strong competitors in crowded niches, and invest more heavily in much fewer offspring, each with a relatively high probability of surviving to adulthood.[66]

### Types of selection

1: directional selection: a single extreme phenotype favoured.
2, stabilizing selection: intermediate favoured over extremes.
3: disruptive selection: extremes favoured over intermediate.
X-axis: phenotypic trait
Y-axis: number of organisms
Group A: original population
Group B: after selection

Natural selection can act on any heritable phenotypic trait,[67] and selective pressure can be produced by any aspect of the environment, including sexual selection and competition with members of the same or other species.[68][69] However, this does not imply that natural selection is always directional and results in adaptive evolution; natural selection often results in the maintenance of the status quo by eliminating less fit variants.[57]

Selection can be classified in several different ways, such as by its effect on a trait, on genetic diversity, by the life cycle stage where it acts, by the unit of selection, or by the resource being competed for.

Selection has different effects on traits. Stabilizing selection acts to hold a trait at a stable optimum, and in the simplest case all deviations from this optimum are selectively disadvantageous. Directional selection favours extreme values of a trait. The uncommon disruptive selection also acts during transition periods when the current mode is sub-optimal, but alters the trait in more than one direction. In particular, if the trait is quantitative and univariate then both higher and lower trait levels are favoured. Disruptive selection can be a precursor to speciation.[57]

Alternatively, selection can be divided according to its effect on genetic diversity. Purifying or negative selection acts to remove genetic variation from the population (and is opposed by de novo mutation, which introduces new variation.[70][71] In contrast, balancing selection acts to maintain genetic variation in a population, even in the absence of de novo mutation, by negative frequency-dependent selection. One mechanism for this is heterozygote advantage, where individuals with two different alleles have a selective advantage over individuals with just one allele. The polymorphism at the human ABO blood group locus has been explained in this way.[72]

Different types of selection act at each life cycle stage of a sexually reproducing organism.[73]

Another option is to classify selection by the life cycle stage at which it acts. Some biologists recognise just two types: viability (or survival) selection, which acts to increase an organism's probability of survival, and fecundity (or fertility or reproductive) selection, which acts to increase the rate of reproduction, given survival. Others split the life cycle into further components of selection. Thus viability and survival selection may be defined separately and respectively as acting to improve the probability of survival before and after reproductive age is reached, while fecundity selection may be split into additional sub-components including sexual selection, gametic selection, acting on gamete survival, and compatibility selection, acting on zygote formation.[73]

Selection can also be classified by the level or unit of selection. Individual selection acts on the individual, in the sense that adaptations are "for" the benefit of the individual, and result from selection among individuals. Gene selection acts directly at the level of the gene. In kin selection and intragenomic conflict, gene-level selection provides a more apt explanation of the underlying process. Group selection, if it occurs, acts on groups of organisms, on the assumption that groups replicate and mutate in an analogous way to genes and individuals. There is an ongoing debate over the degree to which group selection occurs in nature.[74]

Finally, selection can be classified according to the resource being competed for. Sexual selection results from competition for mates. Sexual selection typically proceeds via fecundity selection, sometimes at the expense of viability. Ecological selection is natural selection via any means other than sexual selection, such as kin selection, competition, and infanticide. Following Darwin, natural selection is sometimes defined as ecological selection, in which case sexual selection is considered a separate mechanism.[75]

#### Sexual selection

The peacock's elaborate plumage is mentioned by Darwin as an example of sexual selection,[76] and is a classic example of Fisherian runaway,[77] driven to its conspicuous size and coloration through mate choice by females over many generations.
Main article: Sexual selection

Sexual selection as first articulated by Darwin (using the example of the peacock's tail)[76] refers specifically to competition for mates,[78] which can be intrasexual, between individuals of the same sex, that is male–male competition, or intersexual, where one gender chooses mates, most often with males displaying and females choosing.[79] However, in some species, mate choice is primarily by males, as in some fishes of the family Syngnathidae.[80][81]

Phenotypic traits can be displayed in one sex and desired in the other sex, causing a positive feedback loop called a Fisherian runaway, for example, the extravagant plumage of some male birds such as the peacock.[77] An alternate theory proposed by the same Ronald Fisher in 1930 is the sexy son hypothesis, that mothers want promiscuous sons to give them large numbers of grandchildren and so choose promiscuous fathers for their children. Aggression between members of the same sex is sometimes associated with very distinctive features, such as the antlers of stags, which are used in combat with other stags. More generally, intrasexual selection is often associated with sexual dimorphism, including differences in body size between males and females of a species.[79]

### Natural selection in action

Selection in action: resistance to antibiotics grows though the survival of individuals less affected by the antibiotic. Their offspring inherit the resistance.
Further information: Antimicrobial resistance

Natural selection is seen in action in the development of antibiotic resistance in microorganisms. Since the discovery of penicillin in 1928, antibiotics have been used to fight bacterial diseases. The widespread misuse of antibiotics has selected for microbial resistance to antibiotics in clinical use, to the point that the methicillin-resistant Staphylococcus aureus (MRSA) has been described as a "superbug" because of the threat it poses to health and its relative invulnerability to existing drugs.[82] Response strategies typically include the use of different, stronger antibiotics; however, new strains of MRSA have recently emerged that are resistant even to these drugs.[83] This is an evolutionary arms race, in which bacteria develop strains less susceptible to antibiotics, while medical researchers attempt to develop new antibiotics that can kill them. A similar situation occurs with pesticide resistance in plants and insects. Arms races are not necessarily induced by man; a well-documented example involves the spread of a gene in the butterfly Hypolimnas bolina suppressing male-killing activity by Wolbachia bacteria parasites on the island of Samoa, where the spread of the gene is known to have occurred over a period of just five years [84][85]

## Evolution by means of natural selection

X-ray of the left hand of a ten-year-old boy with polydactyly, caused by a mutant Hox gene
Main articles: Evolution and Darwinism

A prerequisite for natural selection to result in adaptive evolution, novel traits and speciation is the presence of heritable genetic variation that results in fitness differences. Genetic variation is the result of mutations, genetic recombinations and alterations in the karyotype (the number, shape, size and internal arrangement of the chromosomes). Any of these changes might have an effect that is highly advantageous or highly disadvantageous, but large effects are rare. In the past, most changes in the genetic material were considered neutral or close to neutral because they occurred in noncoding DNA or resulted in a synonymous substitution. However, many mutations in non-coding DNA have deleterious effects.[86][87] Although both mutation rates and average fitness effects of mutations are dependent on the organism, a majority of mutations in humans are slightly deleterious.[88]

Some mutations occur in "toolkit" or regulatory genes. Changes in these often have large effects on the phenotype of the individual because they regulate the function of many other genes. Most, but not all, mutations in regulatory genes result in non-viable embryos. Some nonlethal regulatory mutations occur in HOX genes in humans, which can result in a cervical rib[89] or polydactyly, an increase in the number of fingers or toes.[90] When such mutations result in a higher fitness, natural selection favours these phenotypes and the novel trait spreads in the population. Established traits are not immutable; traits that have high fitness in one environmental context may be much less fit if environmental conditions change. In the absence of natural selection to preserve such a trait, it becomes more variable and deteriorate over time, possibly resulting in a vestigial manifestation of the trait, also called evolutionary baggage. In many circumstances, the apparently vestigial structure may retain a limited functionality, or may be co-opted for other advantageous traits in a phenomenon known as preadaptation. A famous example of a vestigial structure, the eye of the blind mole-rat, is believed to retain function in photoperiod perception.[91]

### Speciation

Main article: Speciation

Speciation requires a degree of reproductive isolation—that is, a reduction in gene flow. However, it is intrinsic to the concept of a species that hybrids are selected against, opposing the evolution of reproductive isolation, a problem that was recognised by Darwin. The problem does not occur in allopatric speciation with geographically separated populations, which can diverge with different sets of mutations. E. B. Poulton realized in 1903 that reproductive isolation could evolve through divergence, if each lineage acquired a different, incompatible allele of the same gene. Selection against the heterozygote would then directly create reproductive isolation, leading to the Bateson–Dobzhansky–Muller model, further elaborated by H. Allen Orr and Michael Turelli.[92]

## Genetic basis

### Genotype and phenotype

Natural selection acts on an organism's phenotype, or physical characteristics. Phenotype is determined by an organism's genetic make-up (genotype) and the environment in which the organism lives. When different organisms in a population possess different versions of a gene for a certain trait, each of these versions is known as an allele. It is this genetic variation that underlies differences in phenotype. An example is the ABO blood type antigens in humans, where three alleles govern the phenotype.[93]

Some traits are governed by only a single gene, but most traits are influenced by the interactions of many genes. A variation in one of the many genes that contributes to a trait may have only a small effect on the phenotype; together, these genes can produce a continuum of possible phenotypic values.[94]

### Directionality of selection

Main article: Directional selection

When some component of a trait is heritable, selection alters the frequencies of the different alleles, or variants of the gene that produces the variants of the trait. Selection can be divided into three classes, on the basis of its effect on allele frequencies: directional, stabilizing, and purifying selection.[95] Directional selection occurs when an allele has a greater fitness than others, so that it increases in frequency, gaining an increasing share in the population. This process can continue until the allele is fixed and the entire population shares the fitter phenotype.[96] Far more common is stabilizing selection, which lowers the frequency of alleles that have a deleterious effect on the phenotype – that is, produce organisms of lower fitness. This process can continue until the allele is eliminated from the population. Purifying selection conserves functional genetic features, such as protein-coding genes or regulatory sequences, over time by selective pressure against deleterious variants.[97]

Some forms of balancing selection do not result in fixation, but maintain an allele at intermediate frequencies in a population. This can occur in diploid species (with pairs of chromosomes) when heterozygous individuals (with just one copy of the allele) have a higher fitness than homozygous individuals (with two copies). This is called heterozygote advantage or over-dominance, of which the best-known example is the resistance to malaria in humans heterozygous for sickle-cell anaemia. Maintenance of allelic variation can also occur through disruptive or diversifying selection, which favours genotypes that depart from the average in either direction (that is, the opposite of over-dominance), and can result in a bimodal distribution of trait values. Finally, balancing selection can occur through frequency-dependent selection, where the fitness of one particular phenotype depends on the distribution of other phenotypes in the population. The principles of game theory have been applied to understand the fitness distributions in these situations, particularly in the study of kin selection and the evolution of reciprocal altruism.[98][99]

### Selection, genetic variation, and drift

Main articles: Genetic variation and Genetic drift

A portion of all genetic variation is functionally neutral, producing no phenotypic effect or significant difference in fitness. Motoo Kimura's neutral theory of molecular evolution by genetic drift proposes that this variation accounts for a large fraction of observed genetic diversity.[100] Neutral events can radically reduce genetic variation through population bottlenecks.[101] which among other things can cause the founder effect in initially small new populations.[102] When genetic variation does not result in differences in fitness, selection cannot directly affect the frequency of such variation. As a result, the genetic variation at those sites is higher than at sites where variation does influence fitness.[95] However, after a period with no new mutations, the genetic variation at these sites is eliminated due to genetic drift. Natural selection reduces genetic variation by eliminating maladapted individuals, and consequently the mutations that caused the maladaptation. At the same time, new mutations occur, resulting in a mutation–selection balance. The exact outcome of the two processes depends both on the rate at which new mutations occur and on the strength of the natural selection, which is a function of how unfavourable the mutation proves to be.[103]

Genetic linkage occurs when the loci of two alleles are in close proximity on a chromosome. During the formation of gametes, recombination reshuffles the alleles. The chance that such a reshuffle occurs between two alleles is inversely related to the distance between them. Selective sweeps occur when an allele becomes more common in a population as a result of positive selection. As the prevalence of one allele increases, closely linked alleles can also become more common by "genetic hitchhiking", whether they are neutral or even slightly deleterious. A strong selective sweep results in a region of the genome where the positively selected haplotype (the allele and its neighbours) are in essence the only ones that exist in the population. Selective sweeps can be detected by measuring linkage disequilibrium, or whether a given haplotype is overrepresented in the population. Since a selective sweep also results in selection of neighbouring alleles, the presence of a block of strong linkage disequilibrium might indicate a 'recent' selective sweep near the centre of the block.[104]

Background selection is the opposite of a selective sweep. If a specific site experiences strong and persistent purifying selection, linked variation tends to be weeded out along with it, producing a region in the genome of low overall variability. Because background selection is a result of deleterious new mutations, which can occur randomly in any haplotype, it does not produce clear blocks of linkage disequilibrium, although with low recombination it can still lead to slightly negative linkage disequilibrium overall.[105]

## Impact

Main article: Universal Darwinism

Darwin's ideas, along with those of Adam Smith and Karl Marx, had a profound influence on 19th century thought, including his radical claim that "elaborately constructed forms, so different from each other, and dependent on each other in so complex a manner" evolved from the simplest forms of life by a few simple principles.[106] This inspired some of Darwin's most ardent supporters—and provoked the strongest opposition. Natural selection had the power, according to Stephen Jay Gould, to "dethrone some of the deepest and most traditional comforts of Western thought", such as the belief that humans have a special place in the world.[107]

In the words of the philosopher Daniel Dennett, "Darwin's dangerous idea" of evolution by natural selection is a "universal acid," which cannot be kept restricted to any vessel or container, as it soon leaks out, working its way into ever-wider surroundings.[108] Thus, in the last decades, the concept of natural selection has spread from evolutionary biology to other disciplines, including evolutionary computation, quantum Darwinism, evolutionary economics, evolutionary epistemology, evolutionary psychology, and cosmological natural selection. This unlimited applicability has been called universal Darwinism.[109]

### Origin of life

Main article: Abiogenesis

How life originated from inorganic matter remains an unresolved problem in biology. One prominent hypothesis is that life first appeared in the form of short self-replicating RNA polymers.[110] On this view, life may have come into existence when RNA chains first experienced the basic conditions, as conceived by Charles Darwin, for natural selection to operate. These conditions are: heritability, variation of type, and competition for limited resources. The fitness of an early RNA replicator would likely have been a function of adaptive capacities that were intrinsic (i.e., determined by the nucleotide sequence) and the availability of resources.[111][112] The three primary adaptive capacities could logically have been: (1) the capacity to replicate with moderate fidelity (giving rise to both heritability and variation of type), (2) the capacity to avoid decay, and (3) the capacity to acquire and process resources.[111][112] These capacities would have been determined initially by the folded configurations (including those configurations with ribozyme activity) of the RNA replicators that, in turn, would have been encoded in their individual nucleotide sequences.[113]

### Cell and molecular biology

In 1881, the embryologist Wilhelm Roux published Der Kampf der Theile im Organismus (The Struggle of Parts in the Organism) in which he suggested that the development of an organism results from a Darwinian competition between the parts of the embryo, occurring at all levels, from molecules to organs.[114] In recent years, a modern version of this theory has been proposed by Jean-Jacques Kupiec. According to this cellular Darwinism, random variation at the molecular level generates diversity in cell types whereas cell interactions impose a characteristic order on the developing embryo.[115]

### Social and psychological theory

The social implications of the theory of evolution by natural selection also became the source of continuing controversy. Friedrich Engels, a German political philosopher and co-originator of the ideology of communism, wrote in 1872 that "Darwin did not know what a bitter satire he wrote on mankind, and especially on his countrymen, when he showed that free competition, the struggle for existence, which the economists celebrate as the highest historical achievement, is the normal state of the animal kingdom."[116] Herbert Spencer and the eugenics advocate Francis Galton's interpretation of natural selection as necessarily progressive, leading to supposed advances in intelligence and civilisation, became a justification for colonialism, eugenics, and social Darwinism. For example, in 1940, Konrad Lorenz, in writings that he subsequently disowned, used the theory as a justification for policies of the Nazi state. He wrote "... selection for toughness, heroism, and social utility ... must be accomplished by some human institution, if mankind, in default of selective factors, is not to be ruined by domestication-induced degeneracy. The racial idea as the basis of our state has already accomplished much in this respect."[117] Others have developed ideas that human societies and culture evolve by mechanisms analogous to those that apply to evolution of species.[118]

More recently, work among anthropologists and psychologists has led to the development of sociobiology and later of evolutionary psychology, a field that attempts to explain features of human psychology in terms of adaptation to the ancestral environment. The most prominent example of evolutionary psychology, notably advanced in the early work of Noam Chomsky and later by Steven Pinker, is the hypothesis that the human brain has adapted to acquire the grammatical rules of natural language.[119] Other aspects of human behaviour and social structures, from specific cultural norms such as incest avoidance to broader patterns such as gender roles, have been hypothesised to have similar origins as adaptations to the early environment in which modern humans evolved. By analogy to the action of natural selection on genes, the concept of memes—"units of cultural transmission," or culture's equivalents of genes undergoing selection and recombination—has arisen, first described in this form by Richard Dawkins in 1976[120] and subsequently expanded upon by philosophers such as Daniel Dennett as explanations for complex cultural activities, including human consciousness.[121]

### Information and systems theory

In 1922, Alfred J. Lotka proposed that natural selection might be understood as a physical principle that could be described in terms of the use of energy by a system,[122][123] a concept later developed by Howard T. Odum as the maximum power principle in thermodynamics, whereby evolutionary systems with selective advantage maximise the rate of useful energy transformation.[124]

The principles of natural selection have inspired a variety of computational techniques, such as "soft" artificial life, that simulate selective processes and can be highly efficient in 'adapting' entities to an environment defined by a specified fitness function.[125] For example, a class of heuristic optimisation algorithms known as genetic algorithms, pioneered by John Henry Holland in the 1970s and expanded upon by David E. Goldberg,[126] identify optimal solutions by simulated reproduction and mutation of a population of solutions defined by an initial probability distribution.[127] Such algorithms are particularly useful when applied to problems whose energy landscape is very rough or has many local minima.[128]

## Notes and references

### References

1. ^
2. ^
3. ^
4. ^ Lear 1988, p. 38
5. ^ Henry, Devin (September 2006). "Aristotle on the Mechanism of Inheritance" (PDF). Journal of the History of Biology. Dordrecht, the Netherlands: Springer Science+Business Media. 39 (3): 425–455. doi:10.1007/s10739-005-3058-y. ISSN 0022-5010.
6. ^ Ariew 2002
7. ^ Darwin 1872, p. xiii
8. ^
9. ^ Zirkle, Conway (April 25, 1941). "Natural Selection before the 'Origin of Species'". Proceedings of the American Philosophical Society. Philadelphia, PA: American Philosophical Society. 84 (1): 71–123. ISSN 0003-049X. JSTOR 984852.
10. ^ Agutter & Wheatley 2008, p. 43
11. ^ Muhammad AS Abdel, Haleem (2013). "Pre-Darwinian Muslim Scholars' Views on Evolution" (PDF). Encyclopedia of Sciences and Religions: 74–77 – via Springer.
12. ^ Maupertuis, Pierre Louis (1746). "Les Loix du mouvement et du repos déduites d'un principe metaphysique" ["Derivation of the laws of motion and equilibrium from a metaphysical principle"]. Histoire de l'Académie Royale des Sciences et des Belles Lettres (in French). Berlin: Ambroise Haude: 267–294.
13. ^ Bowler, Peter J. (2003). Evolution: The History of an Idea (3rd ed.). Berkeley, CA: University of California Press. pp. 129–134. ISBN 978-0-520-23693-6. OCLC 43091892.
14. ^ Lamarck 1809
15. ^ Joravsky, David (January 1959). "Soviet Marxism and Biology before Lysenko". Journal of the History of Ideas. Philadelphia, PA: University of Pennsylvania Press. 20 (1): 85–104. doi:10.2307/2707968. ISSN 0022-5037.
16. ^ Darwin 1859, p. 18
17. ^ Darwin 1859, p. 61
18. ^ Darwin 1859, p. 5
19. ^ Hall, Brian K.; Hallgrímsson, Benedikt (2008). Strickberger's Evolution (4th ed.). Jones and Bartlett. pp. 4–6. ISBN 978-0-7637-0066-9. OCLC 796450355.
20. ^ Malthus 1798
21. ^ Darwin 1958, p. 120
22. ^ Darwin 1859, pp. 126–127
23. ^ Wallace 1871
24. ^ Darwin 1861, p. xiii
25. ^ Darwin 1859, p. 6
26. ^ Darwin, Charles (September 28, 1860). "Darwin, C. R. to Lyell, Charles". Darwin Correspondence Project. Cambridge, UK: Cambridge University Library. Letter 2931. Retrieved 2015-08-01.
27. ^ a b Darwin 1859
28. ^ Eisley 1958
29. ^ Kuhn 1996
30. ^ Darwin, Charles (July 5, 1866). "Darwin, C. R. to Wallace, A. R.". Darwin Correspondence Project. Cambridge, UK: Cambridge University Library. Letter 5145. Retrieved 2010-01-12.
31. ^ Stucke, Maurice E. (Summer 2008). "Better Competition Advocacy" (PDF). St. John's Law Review. Jamaica, NY: St. John's University School of Law. 82 (3): 951–1036. ISSN 2168-8796. This survival of the fittest, which I have here sought to express in mechanical terms, is that which Mr. Darwin has called 'natural selection, or the preservation of favoured races in the struggle for life.'Herbert Spencer, Principles of Biology (1864), vol. 1, pp. 444–445
32. ^ Darwin 1872, p. 49.
33. ^ Mills, Susan K.; Beatty, John H. (1979). "The Propensity Interpretation of Fitness" (PDF). Philosophy of Science. Chicago, IL: University of Chicago Press on behalf of the Philosophy of Science Association. 46: 263–286. doi:10.1086/288865. ISSN 0031-8248.
34. ^ Ambrose, Mike. "Mendel's Peas". Norwich, UK: Germplasm Resources Unit, John Innes Centre. Retrieved 2015-05-22.
35. ^ Huxley, Julian (1929–1930). "The A B C of Genetics". The Science of Life. 2. London: Amalgamated Press. OCLC 3171056.
36. ^ National Academy of Sciences (1999). Science and Creationism: A View from the National Academy of Sciences (2nd ed.). Washington, D.C.: National Academy Press. ISBN 978-0-309-06406-4. OCLC 43803228.
37. ^ a b Fisher 1930
38. ^ Haldane 1932
39. ^ Haldane, J. B. S. (December 1957). "The Cost of Natural Selection" (PDF). Journal of Genetics. 55 (3): 511–524. doi:10.1007/BF02984069. ISSN 0022-1333.
40. ^ Wright, Sewall (1932). "The roles of mutation, inbreeding, crossbreeding and selection in evolution". Proceedings of the VI International Congress of Genetrics. 1: 356–366.
41. ^ Dobzhansky 1937
42. ^ Dobzhansky 1951
43. ^ Carroll, Sean B.; Grenier, Jennifer K.; Weatherbee, Scott D. (2005). From DNA to Diversity: Molecular Genetics and the Evolution of Animal Design — Second Edition. Blackwell Publishing. pp. 66–67. ISBN 1-4051-1950-0.
44. ^ Mayr 1942
45. ^ Hamilton, W. (1964). "The genetical evolution of social behaviour. I". Journal of Theoretical Biology. 7 (1): 1–16. doi:10.1016/0022-5193(64)90038-4. PMID 5875341.
46. ^ Hamilton, W. (1964). "The genetical evolution of social behaviour. II". Journal of Theoretical Biology. 7 (1): 17–52. doi:10.1016/0022-5193(64)90039-6. PMID 5875340.
47. ^ Gilbert, Scott F. (2003). "The morphogenesis of evolutionary developmental biology" (PDF). International Journal of Developmental Biology. 47: 467–477.
48. ^ Gilbert, S.F.; Opitz, J.M.; Raff, R.A. (1996). "Resynthesizing Evolutionary and Developmental Biology". Developmental Biology. 173 (2): 357–372. doi:10.1006/dbio.1996.0032. PMID 8605997.
49. ^ Müller, G.B. (2007). "Evo–devo: extending the evolutionary synthesis". Nature Reviews Genetics. 8 (12): 943–949. doi:10.1038/nrg2219.
50. ^ Carroll, Sean B.; Grenier, Jennifer K.; Weatherbee, Scott D. (2005). From DNA to Diversity: Molecular Genetics and the Evolution of Animal Design — Second Edition. Blackwell Publishing. p. 13. ISBN 1-4051-1950-0.
51. ^ Williams 1966
52. ^ Endler 1986
53. ^ Haldane 1954
54. ^ Lande, Russell; Arnold, Stevan J. (November 1983). "The Measurement of Selection on Correlated Characters". Evolution. New York: John Wiley & Sons for the Society for the Study of Evolution. 37 (6): 1210–1226. doi:10.2307/2408842. JSTOR 2408842.
55. ^ Futuyma 2005
56. ^ Sober 1993
57. ^ a b c "Evolution and Natural Selection". University of Michigan. 10 October 2010. Retrieved 9 November 2016.
58. ^ "Teleological Notions in Biology". Stanford Encyclopedia of Philosophy. 18 May 2003. Retrieved 28 July 2016.
59. ^ van't Hof, Arjen E.; Campagne, Pascal; Rigden, Daniel J; et al. (June 2016). "The industrial melanism mutation in British peppered moths is a transposable element". Nature. 534: 102–105. doi:10.1038/nature17951.
60. ^ Orr, H. Allen (August 2009). "Fitness and its role in evolutionary genetics". Nat Rev Genet. 10 (8): 531–539. doi:10.1038/nrg2603. PMC . PMID 19546856.
61. ^ Begon, Townsend & Harper 1996
62. ^ a b Sahney, Sarda; Benton, Michael J.; Ferry, Paul A. (August 23, 2010). "Links between global taxonomic diversity, ecological diversity and the expansion of vertebrates on land" (PDF). Biology Letters. London: Royal Society Publishing. 6 (4): 544–547. doi:10.1098/rsbl.2009.1024. ISSN 1744-9561. PMC . PMID 20106856.
63. ^ Jardine, Phillip E.; Janis, Christine M.; Sahney, Sarda; Benton, Michael J. (December 1, 2012). "Grit not grass: Concordant patterns of early origin of hypsodonty in Great Plains ungulates and Glires". Palaeogeography, Palaeoclimatology, Palaeoecology. Amsterdam, the Netherlands: Elsevier. 365–366: 1–10. doi:10.1016/j.palaeo.2012.09.001. ISSN 0031-0182.
64. ^ MacArthur & Wilson 2001
65. ^ Pianka, Eric R. (November–December 1970). "On r- and K-Selection". The American Naturalist. Chicago, IL: University of Chicago Press on behalf of the American Society of Naturalists. 104 (940): 592–597. doi:10.1086/282697. ISSN 0003-0147. JSTOR 2459020.
66. ^ a b Verhulst, Pierre François (1838). "Notice sur la loi que la population suit dans son accroissement". Correspondance mathématique et physique (in French). Brussels, Belgium: Société belge de librairie. 10: 113–121. OCLC 490225808.
67. ^ Zimmer & Emlen 2013
68. ^ Miller 2000, p. 8
69. ^ Arnqvist, Göran; Rowe, Locke (2005). Sexual Conflict. Princeton University Press. pp. 14–43. ISBN 978-0-691-12218-2. OCLC 937342534.
70. ^ Lemey, Salemi & Vandamme 2009
71. ^ Loewe, Laurence (2008). "Negative Selection". Nature Education. Cambridge, MA: Nature Publishing Group. OCLC 310450541.
72. ^ Villanea, Fernando A.; Safi, Kristin N.; Busch, Jeremiah W. (May 2015). "A General Model of Negative Frequency Dependent Selection Explains Global Patterns of Human ABO Polymorphism". PLOS ONE. 10 (5): e0125003. doi:10.1371/journal.pone.0125003.
73. ^ a b Christiansen 1984, pp. 65–79
74. ^ Wade, Michael J.; et al. (2010). "Multilevel and kin selection in a connected world". Nature. 463: E8–E9. doi:10.1038/nature08809. PMC . PMID 20164866.
75. ^ Mayr 2006
76. ^ a b Darwin, Charles (1859). On the Origin of Species (1st edition). Chapter 4, page 88. "And this leads me to say a few words on what I call Sexual Selection. This depends ..." http://darwin-online.org.uk/content/frameset?viewtype=side&itemID=F373&pageseq=12
77. ^ a b Greenfield, M. D.; Alem, S.; Limousin, D.; Bailey, N. W. (2014). "The dilemma of Fisherian sexual selection: Mate choice for indirect benefits despite rarity and overall weakness of trait-preference genetic correlation". Evolution. 68: 3524–3536. doi:10.1111/evo.12542.
79. ^ a b Hosken, David J.; House, Clarissa M. (January 2011). "Sexual Selection". Current Biology. doi:10.1016/j.cub.2010.11.053.
80. ^ Eens, Marcel; Pinxten, Rianne (October 5, 2000). "Sex-role reversal in vertebrates: behavioural and endocrinological accounts". Behavioural Processes. Amsterdam, the Netherlands: Elsevier. 51 (1–3): 135–147. doi:10.1016/S0376-6357(00)00124-8. ISSN 0376-6357. PMID 11074317.
81. ^ Barlow, George W. (March 2005). "How Do We Decide that a Species is Sex-Role Reversed?". The Quarterly Review of Biology. Chicago, IL: University of Chicago Press. 80 (1): 28–35. doi:10.1086/431022. ISSN 0033-5770. PMID 15884733.
82. ^ Harvey, Fiona; Carson, Mary; O'Kane, Maggie; Wasley, Andrew (18 June 2015). "MRSA superbug found in supermarket pork raises alarm over farming risks". The Guardian.
83. ^ Schito, Gian C. (March 2006). "The importance of the development of antibiotic resistance in Staphylococcus aureus". Clinical Microbiology and Infection. Blackwell Synergy on behalf of the European Society of Clinical Microbiology and Infectious Diseases. 12 (Suppl s1): 3–8. doi:10.1111/j.1469-0691.2006.01343.x. ISSN 1469-0691. PMID 16445718.
84. ^ Charlat, Sylvain; Hornett, Emily A.; Fullard, James H.; et al. (13 July 2007). "Extraordinary Flux in Sex Ratio". Science. Washington, D.C.: American Association for the Advancement of Science. 317 (5835): 214. doi:10.1126/science.1143369. ISSN 0036-8075. PMID 17626876.
85. ^ Moran, Gregory J.; et al. (2006). "Methicillin-Resistant S. aureus Infections among Patients in the Emergency Department". New England Journal of Medicine. 355: 666–674. doi:10.1056/NEJMoa055356.
86. ^ Kryukov, Gregory V.; Schmidt, Steffen; Sunyaev, Shamil (August 1, 2005). "Small fitness effect of mutations in highly conserved non-coding regions". Human Molecular Genetics. Oxford: Oxford University Press. 14 (15): 2221–2229. doi:10.1093/hmg/ddi226. ISSN 0964-6906. PMID 15994173.
87. ^ Bejerano, Gill; Pheasant, Michael; Makunin, Igor; et al. (May 28, 2004). "Ultraconserved Elements in the Human Genome". Science. Washington, D.C.: American Association for the Advancement of Science. 304 (5675): 1321–1325. doi:10.1126/science.1098119. ISSN 0036-8075. PMID 15131266.
88. ^ Eyre-Walker, Adam; Woolfit, Megan; Phelps, Ted (June 2006). "The Distribution of Fitness Effects of New Deleterious Amino Acid Mutations in Humans". Genetics. Bethesda, MD: Genetics Society of America. 173 (2): 891–900. doi:10.1534/genetics.106.057570. ISSN 0016-6731. PMC . PMID 16547091.
89. ^ Galis, Frietson (April 1999). "Why do almost all mammals have seven cervical vertebrae? Developmental constraints, Hox genes, and cancer". Journal of Experimental Zoology. Hoboken, NJ: Wiley-Blackwell. 285 (1): 19–26. doi:10.1002/(SICI)1097-010X(19990415)285:1<19::AID-JEZ3>3.0.CO;2-Z. ISSN 1932-5223. PMID 10327647.
90. ^ Zákány, József; Fromental-Ramain, Catherine; Warot, Xavier; Duboule, Denis (December 9, 1997). "Regulation of number and size of digits by posterior Hox genes: A dose-dependent mechanism with potential evolutionary implications". Proc. Natl. Acad. Sci. U.S.A. Washington, D.C.: National Academy of Sciences. 94 (25): 13695–13700. doi:10.1073/pnas.94.25.13695. ISSN 0027-8424. PMC . PMID 9391088.
91. ^ Sanyal, Somes; Jansen, Harry G.; de Grip, Willem J.; Nevo, Eviatar; et al. (July 1990). "The Eye of the Blind Mole Rat, Spalax ehrenbergi. Rudiment With Hidden Function?". Investigative Ophthalmology & Visual Science. Association for Research in Vision and Ophthalmology. 31 (7): 1398–1404. ISSN 0146-0404. PMID 2142147.
92. ^ Barton, N. H. (June 2010). "What role does natural selection play in speciation?". Philosophical Transactions of the Royal Society B. 365 (1547): 1825–1840. doi:10.1098/rstb.2010.0001.
93. ^ McKusick, Victor A.; Gross, Matthew B. (18 November 2014). "ABO Glycosyltransferase; ABO". Online Mendelian Inheritance in Man. National Library of Medicine. Retrieved 7 November 2016.
94. ^ Falconer & Mackay 1996
95. ^ a b Rice 2004, See especially chapters 5 and 6 for a quantitative treatment
96. ^ Rieseberg, L.H.; Widmer, A.; Arntz, A.M.; Burke, J.M. (2002). "Directional selection is the primary cause of phenotypic diversification" (PDF). PNAS. 99 (19): 12242–12245. doi:10.1073/pnas.192360899.
97. ^ Charlesworth B, Lande R, Slatkin M (1982). "A neo-Darwinian commentary on macroevolution". Evolution. 36 (3): 474. doi:10.2307/2408095.
98. ^ Hamilton, William D. (July 1964). "The genetical evolution of social behaviour. II". Journal of Theoretical Biology. Amsterdam, the Netherlands: Elsevier. 7 (1): 17–52. doi:10.1016/0022-5193(64)90039-6. ISSN 0022-5193. PMID 5875340.
99. ^ Trivers, Robert L. (March 1971). "The Evolution of Reciprocal Altruism". The Quarterly Review of Biology. Chicago, IL: University of Chicago Press. 46 (1): 35–57. doi:10.1086/406755. ISSN 0033-5770. JSTOR 2822435.
100. ^ Kimura, Motoo (1983). The neutral theory of molecular evolution. Cambridge University Press. ISBN 978-0-521-23109-1. OCLC 8776549.
101. ^ Robinson, Richard, ed. (2003). "Population Bottleneck". Genetics. 3. Macmillan Reference USA. ISBN 978-0-02-865609-0. OCLC 3373856121.
102. ^ Campbell, Neil A. (1996). Biology (4th ed.). Benjamin Cummings. p. 423. ISBN 978-0-8053-1940-8. OCLC 3138680061.
103. ^ Lynch, Michael (August 2010). "Evolution of the mutation rate". Trends in Genetics. 26 (8): 345–352. doi:10.1016/j.tig.2010.05.003. PMC . PMID 20594608.
104. ^ Smith, John Maynard; Haigh, John (1974). "The hitch-hiking effect of a favourable gene". Genetics Research. 23 (1): 23–35. doi:10.1017/S0016672300014634. ISSN 1469-5073. PMID 4407212.
105. ^ Keightley, Peter D.; Otto, Sarah P. (September 7, 2006). "Interference among deleterious mutations favours sex and recombination in finite populations". Nature. London: Nature Publishing Group. 443 (7107): 89–92. doi:10.1038/nature05049. ISSN 0028-0836. PMID 16957730.
106. ^ Darwin 1859, p. 489
107. ^ Gould, Stephen Jay (June 12, 1997). "Darwinian Fundamentalism". The New York Review of Books. New York: Rea S. Hederman. 44 (10). ISSN 0028-7504.
108. ^ Dennett 1995
109. ^ von Sydow, M. (2012). From Darwinian Metaphysics towards Understanding the Evolution of Evolutionary Mechanisms. A Historical and Philosophical Analysis of Gene-Darwinism and Universal Darwinism. Universitätsverlag Göttingen. ISBN 978-3-86395-006-4. OCLC 1088022023.
110. ^ Eigen, Manfred; Gardiner, William; Schuster, Peter; et al. (April 1981). "The Origin of Genetic Information". Scientific American. Stuttgart: Georg von Holtzbrinck Publishing Group. 244 (4): 88–92, 96, et passim. doi:10.1038/scientificamerican0481-88. ISSN 0036-8733. PMID 6164094.
111. ^ a b Bernstein, Harris; Byerly, Henry C.; Hopf, Frederick A.; et al. (June 1983). "The Darwinian Dynamic". The Quarterly Review of Biology. Chicago, IL: University of Chicago Press. 58 (2): 185–207. doi:10.1086/413216. ISSN 0033-5770. JSTOR 2828805.
112. ^ a b Michod 1999
113. ^ Orgel, Leslie E. (1987). "Evolution of the Genetic Apparatus: A Review". Cold Spring Harbor Symposia on Quantitative Biology. Cold Spring Harbor, NY: Cold Spring Harbor Laboratory Press. 52: 9–16. doi:10.1101/sqb.1987.052.01.004. ISSN 0091-7451. PMID 2456886.
114. ^ Roux 1881
115. ^ Kupiec, Jean-Jacques (May 3, 2010). "Cellular Darwinism (stochastic gene expression in cell differentiation and embryo development)". SciTopics. Archived from the original on 2010-08-04. Retrieved 2015-08-11.
116. ^ Engels 1964
117. ^ Eisenberg, Leon (September 2005). "Which image for Lorenz?". American Journal of Psychiatry (Letter to the editor). Arlington, VA: American Psychiatric Association. 162 (9): 1760. doi:10.1176/appi.ajp.162.9.1760. ISSN 0002-953X. PMID 16135651. Eisenberg quoting translation of Durch Domestikation verursachte Störungen arteigenen Verhaltens (1940, p. 2) by Konrad Lorenz.
118. ^ Wilson 2002
119. ^ Pinker 1995
120. ^ Dawkins 1976, p. 192
121. ^ Dennett 1991
122. ^ Lotka, Alfred J. (June 1922). "Contribution to the energetics of evolution". PNAS. Washington, D.C.: National Academy of Sciences. 8 (6): 147–151. doi:10.1073/pnas.8.6.147. PMC . PMID 16576642.
123. ^ Lotka, Alfred J. (June 1922). "Natural selection as a physical principle". PNAS. Washington, D.C.: National Academy of Sciences. 8 (6): 151–154. doi:10.1073/pnas.8.6.151. ISSN 0027-8424. PMC . PMID 16576643.
124. ^ Odum, H.T. (1995). Hall, C.A.S., ed. Self-Organization and Maximum Empower. Maximum Power: The Ideas and Applications of H.T. Odum. Colorado University Press.
125. ^ Kauffman 1993
126. ^ Goldberg 1989
127. ^ Mitchell 1996
128. ^ "Genetic Algorithms". Pharmacological Sciences. Retrieved 7 November 2016.

format: plain


text:
CM field to Torus to Abelian Variety? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T07:30:15Z http://mathoverflow.net/feeds/question/31131 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/31131/cm-field-to-torus-to-abelian-variety CM field to Torus to Abelian Variety? Dror Speiser 2010-07-08T23:03:21Z 2010-07-23T23:22:16Z
Given a CM field we can use its maximal order (and a choice of CM type) to construct an abelian variety \$\mathbb{C}^g/\Lambda\$ with complex multiplication by the maximal order.

How do I (or where can I find information on) explicitly write down equations for a projective embedding of this variety, and the action of the CM order on points? Is this implemented anywhere?

For genus one we can use the Eisenstein series to find the coefficients of a Weierstrass model for the elliptic curve. So I'm looking for a generalization of this.
 http://mathoverflow.net/questions/31131/cm-field-to-torus-to-abelian-variety/31255#31255 Answer by SandeepJ for CM field to Torus to Abelian Variety? SandeepJ 2010-07-09T22:39:33Z 2010-07-09T22:39:33Z
This is not the answer. I am adding some relevant papers (some possessing good examples) which won't fit in the comments section.

I have been wanting to know the answer to this question as well. It seems one has to find an ample line bundle, and then calculate the Riemann theta relations which define the projective embedding. The equation(s) of the embedding is decided by relation between the theta functions. The wikipedia page on equations for abelian varieties was written Charles Matthews. Perhaps he might have more to say on this question...

MR0946234 (89i:14038) Barth, Wolf . Abelian surfaces with \$(1,2)\$-polarization. Algebraic geometry, Sendai, 1985, 41--84, Adv. Stud. Pure Math., 10, North-Holland, Amsterdam, 1987.

MR1257320 (95e:14033) Barth, W. ; Nieto, I. Abelian surfaces of type \$(1,3)\$ and quartic surfaces with \$16\$ skew lines. J. Algebraic Geom. 3 (1994), no. 2, 173--222.

MR1336597 (96h:14064) Barth, W. Quadratic equations for level-\$3\$ abelian surfaces. Abelian varieties (Egloffstein, 1993), 1--18, de Gruyter, Berlin, 1995.

MR1602020 (99d:14046) Gross, Mark ; Popescu, Sorin . Equations of \$(1,d)\$-polarized abelian surfaces. Math. Ann. 310 (1998), no. 2, 333--377.

MR2194379 (2006m:14054) Gunji, Keiichi . Defining equations of the universal abelian surfaces with level three structure. Manuscripta Math. 119 (2006), no. 1, 61--96.

MR0611469 (82h:14028) Sasaki, Ryuji . Some remarks on the equations defining abelian varieties. Math. Z. 177 (1981), no. 1, 49--60.

MR1048533 (91e:14043) Birkenhake, Ch. ; Lange, H. Cubic theta relations. J. Reine Angew. Math. 407 (1990), 167--177.


text:
How to compute five number summary statistics in R with examples

In this tutorial, you will learn about what is five number summary statistics, actual calculation of five number summary and how to find five number summary statistics in R?

What is 5-number summary?

Five number summary, popularly known as Tukey's five number summary, is a set of five descriptive statistics to summarize a continuous univariate data. The five number summary consists of

• minimum value
• lower-hinge value
• median value
• upper-hinge value
• maximum value

of a univariate data.

The lower-hinge is the median of the lower 50 percent data (after sorting) and upper-hinge is the median of the upper 50% data (after sorting).

How to find five-number summary in R?

The Tukey's five number summary for the input data can obtained using fivenum() function available in base package.

The syntax of the fivenum() function is

fivenum(x,na.rm=TRUE)

where,

• x : numeric vector, may include NA's and +/- inf
• na.rm : logical value (default TRUE) to remove NA and NaN

Numerical Problem : Five Number summary using R

Example 1: Actual Calculation of Five Number Summary using R

This example illustrate the how the five number summary is calculated. To understand the actual calculation of five number summary, let us consider built-in data frame PlantGrowth.

# load the data
data("PlantGrowth")
# display data structure
str(PlantGrowth)
'data.frame': 30 obs. of  2 variables:
$weight: num 4.17 5.58 5.18 6.11 4.5 4.61 5.17 4.53 5.33 5.14 ...$ group : Factor w/ 3 levels "ctrl","trt1",..: 1 1 1 1 1 1 1 1 1 1 ...

Calculate Minimum value

Calculate minimum plant weight using min() function.

# minimum weight
Min <- min(PlantGrowth$weight) Min [1] 3.59 Calculate Median value Calculate median plant weight using median() function. # median weight Median <- median(PlantGrowth$weight)
Median
[1] 5.155

Calculate Lower Hinge

Lower hinge is the median of lower 50 percent of the data after sorting the data.

# sort the weight data
weight.ordered <-sort(PlantGrowth$weight) # no. of elements in weight n <-length(PlantGrowth$weight)
# calculate lower hinge
Lower_hinge <-median(weight.ordered[1:round(n/2)])
# display lower hinge
Lower_hinge
[1] 4.53

Calculate Upper Hinge

Upper hinge is the median of upper 50 percent of the data after sorting the data.

# calculate upper hinge
Upper_hinge <-median(weight.ordered[(round(n/2)+1) : n])
Upper_hinge
[1] 5.54

Calculate maximum value

Calculate the maximum value using max() function.

Max <- max(PlantGrowth$weight) Max [1] 6.31 Five number symmary All the above five numbers summary statistics can be combined together using cbind() (Column bind) function and are given names using colnames() function. FiveSumm <-cbind(Min, Lower_hinge,Median, Upper_hinge,Max) colnames(FiveSumm)<- c("Min.","Lower-Hinge","Median","upper-Hinge","Max.") FiveSumm  Min. Lower-Hinge Median upper-Hinge Max. [1,] 3.59 4.53 5.155 5.54 6.31 Example 2: Five number summary using fivenum() function In earlier example, we have seen how the five number summary is calculated without using fivenum() function. Let's see how the five number summary is calculated using fivenum() function in R. FiveNum <-fivenum(PlantGrowth$weight)
FiveNum
[1] 3.590 4.530 5.155 5.540 6.310

The fivenum() function display only the values. You can assign the names to these values using names() function as below:

names(FiveNum)<-c("Min","L-Hinge","Median","U-Hinge","Max")
FiveNum
    Min L-Hinge  Median U-Hinge     Max
3.590   4.530   5.155   5.540   6.310

The summary() function gives six number summary (Min, $1^{st}$ Qu., Median, Mean, $3^{rd}$ Qu. and Max.).

summary(PlantGrowth$weight)  Min. 1st Qu. Median Mean 3rd Qu. Max. 3.590 4.550 5.155 5.073 5.530 6.310  The default quantile function (quantile()) also gives us the minimum,$1^{st}$quartile, median,$3^{rd}$quartile and the maximum value of the data set. quantile(PlantGrowth$weight)
   0%   25%   50%   75%  100%
3.590 4.550 5.155 5.530 6.310

Note that there is difference between the output of fivenum() function, summary() function and simple quantile() function.

The lower and upper hinge using quantile() function can be obtained using the argument type=5 (one of the nine quantile algorithm).

quantile(PlantGrowth\$weight,type=5)
   0%   25%   50%   75%  100%
3.590 4.530 5.155 5.540 6.310

Note that using the type =5 argument in quantile() function, the result of fivenum() and quantile() functions are identical.

Example 3: Five number summary of data with NA, NaN and Inf

Suppose that your data contains NA, NaN or +/- Inf and you need to compute the five number summary.

# create a vector containing NA, Inf and NaN
y<-c(1:10,NA,+Inf,NaN)
y
##  [1]   1   2   3   4   5   6   7   8   9  10  NA Inf NaN

By default, na.rm=TRUE in fivenum() function. It will remove the NA and NaN values and compute the five number summary for the data, while the values +Inf or -Inf will not be removed.

fivenum(y)
[1] 1.0 3.5 6.0 8.5 Inf

Endnote

In this tutorial you learned about what is five number summary and how to compute the five number summary using fivenum() function using R. You also learned the actual method of calculating five number summary.

To learn more about descriptive statistics using R, please refer to the following tutorials:

Hopefully you enjoyed learning this tutorial on how to compute five number summary using R.

VRCBuzz co-founder and passionate about making every day the greatest day of life. Raju is nerd at heart with a background in Statistics. Raju looks after overseeing day to day operations as well as focusing on strategic planning and growth of VRCBuzz products and services. Raju has more than 25 years of experience in Teaching fields. He gain energy by helping people to reach their goal and motivate to align to their passion. Raju holds a Ph.D. degree in Statistics. Raju loves to spend his leisure time on reading and implementing AI and machine learning concepts using statistical models.


text:
# Sequential Equivalence Implies Topological Equivalence

Define two metric spaces $(M,d)$ and $(M,\rho)$ to be equivalent, denoted $d\sim p$, to mean that:

Topological Definition $\forall x\in M: \forall \epsilon>0 \exists \delta_1>0, \delta_2>0: B_{\rho}(x,\delta _1)\subset B_{d}(x,\epsilon)$ and $B_d(x,\delta_2)\subset B_{\rho}(x,\epsilon)$.

This means if a set $U$ is open in $(M,d)$, it's open in $(M,\rho)$ as well, and vice-versa.

Sequential Definition:

$\forall x\in M\;\forall \{x_n\}\subset M, x_n\to x$ in the $d$ metric iff $x_n\to x$ in the $\rho$ metric.

Prove that $d\sim p$ in sequential definition $\implies d\sim p$ in the topological definition.

My professor posed the above question in class as an exercise, and gave us a hint: to try to solve it through a proof by contrapositive. ($\neg q\implies \neg p$). I've negated both statements as follows:

"Attempt":

$\neg q$:

$d\nsim q$ in the topological definition means that $\exists x\in M\exists\epsilon >0\forall\delta_1\forall\delta_2>0 : B_{\rho}(x,\delta_1)\not\subset B_d(x,\epsilon)$ or $B_d(x,\delta_2)\not\subset b_{\rho}(x,\epsilon).$

$\neq p$:

$d\nsim q$ in the sequential definition means that $\exists x\in M\exists \{x_n\}\subset M: x_n\to x$ in $d$ metric but $x_n\not\to x$ in $\rho$ metric or $x_n\to x$ in $\rho$ metric but $x_n\not\to x$ in the $d$ metric.

I'm not sure where to start, so hints would be preferred over complete solutions. Thank you.

If $d \sim \rho$ then $(M,d)$ and $(M,\rho)$ have the same open sets, and this implies quite easily that they have the exact same convergent sequences as well. (A sequence converges to $x$ if, for every open set $O$ containing $x$, a tail of the sequence lies in $O$.)

On the other hand, if $(M,d)$ have the same convergent sequences, they have the same closed sets (a set $A$ in a metric space is closed iff all sequences from $A$ that converge have their limit in $A$, so being closed can be purely defined in terms of sequences converging), and thus the same open sets as well (a set is open iff the complement is closed ).

I don't really see any for a contrapositive.

• Maybe the contrapositive is contained in the proof of „sequentially closed $\implies$ closed“. – user87690 Sep 22 '14 at 16:33
• I gave that proof directly (via closed sets)... – Henno Brandsma Sep 22 '14 at 18:01
• Do you mean a set is open iff the complement is closed? – Sujaan Kunalan Sep 22 '14 at 18:32
• @SujaanKunalan edited thx – Henno Brandsma Sep 22 '14 at 18:34
• I mean, you say „a set $A$ in a metric space is closed iff all sequences from $A$ that converge their limit $A$“, i.e. „closed $\iff$ sequentially closed“ holds for metric spaces. But if you want to actually prove the backward implication, you may use a contrapositive. – user87690 Sep 23 '14 at 8:20

$\neg q$:

$d\nsim q$ in the topological definition means that $\exists x\in M\exists\epsilon >0\forall\delta_1\forall\delta_2>0 : B_{\rho}(x,\delta_1)\not\subset B_d(x,\epsilon)$ or >$B_d(x,\delta_2)\not\subset b_{\rho}(x,\epsilon).$

Hint: without loss of generality, assume $\exists x \in M \exists \epsilon>0 : \forall \delta>0 \; B_\rho(x,\delta) \not\subset B_d(x,\epsilon)$

Now find a sequence $x_n$ such that $x_n\to x$ in $\rho$, but not in $d$.

Hope this helps.


text:
# Tag Info

12

As the polygon is convex, it is simple! Two vertices are consecutive if all other vertices are located on the same side of the line that goes through these two points. This means that the cross product of the vector feom one of the pionts to the other one with the vector from the first point to any other one in the polygon have the same sign (all negative or ...

6

There is quite a bit of work on this important problem. Some of the most insightful work is by Helmut Alt and collaborators. He wrote a survey in 2009: Helmut Alt. "The computational geometry of comparing shapes." Efficient Algorithms. Springer Berlin Heidelberg, 2009. 235-248. (Springer link.)           Image from Helmut Alt ...

5

Given that the polygon is convex, its centroid $C$ is in its interior. Test the gradients of the lines $CV$ for each vertex $V$. This gives a linear time test.

4

An alternative to OmG's answer (which is great) would be to sort your points into an ordered array where you can find any points neighbors by looking at the points on either side. This method would be very good if you need to work with the same polygon for many calculations as most work is done upfront but afterwards the cost of determining if two points are ...

3

The problem you describe is known as the red-blue intersection problem. Here, we have a red set of $n_1$ segments and a blue set of $n_2$ segments and we know that there are only intersections between segments of different colour. Although this special case has been extensively studied, the $O(n\log n + k)$ algorithm, with $n=n_1+n_2$ is still optimal1 when ...

3

Yes, there are more algorithms to do so in $\mathcal O(n)$. The first is dated back to ElGindy and Avis in 1981, Lee 1983 and Joe & Simpson in 1985. The visibility algorithms use stack (the first one three stacks, further only one) and process vertices in order they appear at boundary. The visibility algorithms described in book Art Gallery Theorems and ...

3

Call the center point $(c_x, c_y)$. The function $d(p_x,p_y) = \sqrt{(p_x-c_x)^2+(p_y-c_y)^2}$ computes the distance from the point $(p_x,p_y)$ to the center of the circle. For each edge of the polygon create its line equation from its two endpoints. If the two endpoints are $(a,b)$ and $(c,d)$ then this line is $y = (\frac{d-b}{c-a})\cdot(x-a) + b$. Solve ...

3

You have a 2D convex polygon $G$, and a 3D polyhedron $H$. Let $P_G$ denote the plane that the polygon is contained in. The following should work: Their intersection is a 2D polygon. You can find the edges of the intersection as follows: For each triangle of $H$: If the triangle intersects $G$, output this intersection. This procedure outputs the ...

3

After conducting more research I did find a solution, but first I will examine solutions suggested by posters and considered by myself and review why they didn't work. This problem reduces to finding all chordless cycles in a planar graph. This was one of my first thoughts early on, but this doesn't work when you consider the following: 5-------f----...

2

Run Flood Fill from any point and the farthest points in the both directions are your result. If you find that the distance in one of the directions is zero it means that it was one of them. Exploiting the very same idea, if you try finding pixels with the least number of surrounding pixels and apply limited BFS Flood Fill to find out where it can go - at ...

2

One reasonable approach is to use RANSAC to find a homography that causes many points to be aligned (or approximately aligned). You'd apply this procedure to align the set of vertices of the first polygon with the set of vertices of the second polygon. The homography captures translation, rotation, and scaling, so it allows correcting for all of them. ...

2

In the paper you reference, Theorem 5 is a claim about simple polygons, where Theorem 6 deals with convex polygons, which are a special kind of simple polygons. The 'As we have seen before, ...' refers to this line: 'As we have seen before, each such test can be done in $O(k)$ time.$^8$', where $8$ references another paper. However, even though I do not ...

2

Graham scan for a convex hull works if you have an ordering of points $a_1,a_2,...a_N$ such that you have a sequence $p_1 < p_2 <...< p_k$ where your convex hull is $a_{p_1}, a_{p_2},...,a_{p_k}$ of which it is not possible to have a winding number greater than $1$. In general for any polygon $P$ this might not work, but for a star shaped polygon, ...

2

Suppose $P = \lbrace x: Ax \leq b \rbrace$ is the polyhedra, where $x \in \mathbb{R}^n$. Further assume $P$ is full dimensional, then let $x_0$ be some interior point in P. Let $c \in \mathbb{R}^n$ (and $c \neq 0$) be the objective function you are interested to minimize (say). Then since $x_0 \in int(P)$, there exists a ball $B$ centered at $x_0$ with ...

2

I would use a winding number algorithm. There are a few, but the fastest goes like this:Imagine a line from your point along the positive x-axis. Now, for every edge of your polygon, determine if it crosses this line. if it crosses the line from below to above, then increment the winding number (which is initially zero), if it crosses going from above to ...

2

Below is an example of a polygon with a single hole. The red area is the interior of the polygon, and the white triangle in the center is the hole (which lies outside the polygon). In the figure, I've also drawn a triangulation of this polygon. The dual of this triangulation is a cycle with $6$ vertices, and this is not a tree. However, is this thing I've ...

2

Most spatial indexes should be good, especially if your rectangles are axis aligned. Spatial indexes typically have about $O(log{M})$ insertion time so you could build in index in $O(M * log{M})$. Lookup time is similar, so finding the best/correct rectangle for every point should be around $O(N * log{M})$. For rectangles, the simplest index is probably a ...

2

Your problem can be solved in linear time. This paper describes a method to solve a system of $n$ linear inequalities with at most two variables per inequality and $m$ distinct variables in total in $O(n m^3 \log m)$ time. (I am swapping the meaning of $n$ and $m$ with respect to the paper in order to keep the name $n$ consistent with your question). In ...

2

Form a list of the $4n$ edges making up the $n$ rectangles. Delete every edge that appears twice. The edges that remain describe the outside of the polygon. If you want to list these edges in clockwise or anticlockwise order, that's easy enough to do -- just pick an arbitrary starting vertex and find one of the two edges it is incident on, then find the ...

1

I can list three candidate approaches. I'm not sure how to choose among them -- you might need to experiment among them to see which will work best in your situation. Approach #1: sweepline algorithm This can be solved with a straightforward application of a sweepline algorithm. Sweep a vertical line from left to right, with increasing $x$-values. At any ...

1

It is not too hard. connect the point to the end-point of an edge. If none of these two segments has an intersection with convex-hull, it means you can see that edge completely (as you consider a convex polygon). To find the intersection, you can use a binary search and find that is there any intersection or not.

1

Start from the leftmost point $x_0$ (the one with minimum $x$-coordinate). If there are ties break them in favor of the point with minimum $y$ coordinate. Suppose for simplicity that there are no two points that are collinear with $x_0$ (this case can be handled by suitably breaking ties). Shoot a ray vertically at an angle of $-\frac{\pi}{2}$ radians. ...

1

The quad tree suggestion by D.W. is interesting. I want to expand on it here. The principle of it is to break the area into big (and then progressively smaller) squares and check whether these squares are fully in or fully out of any polygon. Let's call these cases "black" and "white" respectively. If a big square is either black or white you do not have to ...

1

An alternative approach is to use a quad-tree. One approach is to store each polygon in the deepest node that corresponds to a region that wholly contains the polygon. Given a test point, you traverse the quad-tree, and when you visit a node, you do a point-in-polygon test for each polygon associated with that node. This then lets you do a smaller number ...

1

Without any assumptions on the input mesh, you cannot in general get a single b-spline surface that replicates an arbitrary polygon mesh. You would need the mesh to be connected, but you would also need some fairly significant assumptions about the mesh topology. At the very least, you would want the input mesh to be manifold. (It might be possible to ...

1

Here is one approach to identify all rotational symmetries of the graph: Pick any three vertices, $v_1,\dots,v_3$. Loop over all possible combinations of three vertices $w_1,\dots,w_3$. For each such combination, find the unique rotation that maps $v_1 \mapsto w_1,\dots,v_3 \mapsto w_3$, then check whether this is a rotational symmetry of the entire ...

1

First, assume we already have a list $L$ with all segments in $P$ that are at least partially visible from $p$, ordered by the smallest angle $\theta$ such that a segment is visible from $p$ at angle $\theta$. (This can be done with a (angular) sweep line algorithm in $O(n\log n)$) Now, observe that if a line from $p$ to some point on the segment $s_i$ in $... 1 Build a graph, with one vertex per black pixel, and an edge between two pixels if they are adjacent. Compute all-pairs shortest-path distances$d(x,y)$. For each vertex$x$, compute $$f(x) = \max \{d(x,y) : y \in V\}.$$ Find the vertex (pixel)$x$with the maximum score for$f(x)$. This will be one endpoint of the shape. Find the other vertex$y$that ... 1 Compute the topological skeleton of the black pixels. This will form a curved line one pixel wide (i.e., it will be isomorphic to a line). Use the two endpoints of this line as your answer. You can find the endpoints by using depth-first search, or (for a more robust solution) by computing the tangent line at each point$p$and checking for a neighbor ... 1 Your problem is a special case of planar point location. The algorithm/data structure you found by Snarak and Tarjan can answer point location (and thus point in polygon) queries in$O(\log n)$time using$O(n \log n)$preprocessing and$O(n)\$ space. That is optimal. There are two other data structures that achieve this: a data structure by Kirkpatrick and a ...

Only top voted, non community-wiki answers of a minimum length are eligible


text:
NeurIPS 2019
Sun Dec 8th through Sat the 14th, 2019 at Vancouver Convention Center
Paper ID: 6576 Bootstrapping Upper Confidence Bound

### Reviewer 1

1. It is claimed that existing concentration-based confidence bounds are typically data-independent. This is true for the UCB1 algorithm, but there are other more sophisticated algorithms that exploit the full distribution in their confidence bound. For the example, for general distribution that have support in [0,1] the empirical KL-UCB of [Cappé et al., Kullback-Leibler Upper Confidence Bounds for Sequential Resource Allocation, 2013] used empirical likelihood to build confidence intervals, that are not at all of the form \bar y_n + data-independent terms. For Bernoulli bandits, more simple confidence intervals are proposed in the same papers (that extend to sub-Bernoulli, i.e. bounded, distributions). So I think it would be fair that those more sophisticated algorithms are also included in the comparison. Also, the analysis of UCB1 as proposed by [10] has been improved by several authors (using notably self-normalized deviation inequalities instead of union bounds) for sub-Gaussian distribution to show that the index \bar y_{n_k,t} + \sqrt{2\sigma^2log(t)/n_{k,t}} for sigma^2 sub-Gaussian distributions can be used (in place of the \sqrt{2log(t)/(n_{k,t})} originally proposed for 1/4-subGaussian). A fair comparison should include all the improvements from the literature. The experimental setup is also not clearly related to the theoretical guarantees that are obtained: while Theorem 2 hold for any fixed problem instance ("a" stochastic K-armed bandit, frequentist statement), it seems that the regret curves are obtained by averaging several runs on different randomly generated instances (Bayesian evaluation). Maybe I misunderstood something, but if the arms are fixed for good instead of being randomly generated in each run, one could as well provide their value. A Bayesian evaluation is interesting too to access the robustness of the algorithm on different problems, but given the nature of the theoretical results obtain, I think one or two "frequentist" regret curves are mandatory. In the linear bandit part, it seems the dimension d under which the experiments were run is not specified in Section 4.2. 2. The complexity of the algorithm is not discussed in details, it is just written in the introduction that it is "easy to implement". I should be acknowledged that it is significantly more complex that UCB1 for example. Indeed at each time step B bootstrap repetitions are needed to estimated the bootstrapped quantiles, and each of them require to drawn n_k random variables for each arm k (the values of w's). Also, this requires to store the past rewards obtained on all arms, which requires a lot a memory. This constraint is also needed for the empirical KL-UCB mentioned above, which is one more reason to compare the two algorithms that have similar complexity. From Theorem 2, I guess that the w's are Rademacher random variables, but it would be good to specify this in the statement of the algorithm. Bootstrapped UCB has two hyper-parameters, B and delta. Some insight on the parameter delta would be much appreciated. The tuning of the two parameters is never justified. We get that the larger B the better the algorithm and the more complex, but why B=200 specifically? Regarding delta, it is arbitrarily set to delta=0.1 in Section 4.1 and then to delta_t = 1/(1+t) for linear bandits "to be fair". I don't get why this is fair. Regarding the parameter alpha, I would like to mention that it is set to alpha=1/(t+1) in each round in the statement of Algorithm 1 (and I guess, the algorithm was implemented with this choice), however regret guarantees are only obtained by a fixed choice alpha = 1/T^2 where T is the full horizon. This discrepancy is annoying. 3. I checked the proofs of Theorem 2.2 and Theorem 3.2, which are the most important results of the paper. Note that the paper would be interesting even without the habillity to generalize to sub-Weibul distributions (not that actually, all experiments feature sub-Gaussian distributions, so there is not a strong case for this generalization. As such, it should be precised which function \phi is employed in the experiments. If beta=2 I would peferr to employ directly (2log(1/alpha)/n)^{1/2}), but I couldn't figure out what was done. I'm essentially OK with the proof of Theorem 3.2, though I didn't check too carefully the sub-Weibull tricks. I noted two typos in Equation (B.18) : u_1 should be \mu_1 twice. Also the notation \bar y_s is not super-precise as it sometimes refer to s i.i.d. samples from arm 1 or from arm k : I would introduce \bar y_{k,s} to avoid this aliasing. In the proof of Theorem 2.2, I have a hard time to understand where Equation (B.2) comes from, so I think detailed explanations are needed here. By definition I get that $\Pr(\bar y_n - \mu > q_\alpha(y_n - \mu) = \Pr_y(\Pr_w(1/n \sum_{i=1}^n w_i(y_i - \mu) > \bar y_n - \mu ) \leq alpha)$, but the formula in (B.2) seem to have inverted the integration over y and w in a way I don't understand. Also, the notation q_\alpha(z) for any vector z is not really defined, only q_\alpha(y_n - \mu) is defined in the paper: a more general notation should be introduced. The second problem I saw was on top on page 13, where some conditioning on event E is brutally removed: in the first inequality there should be a \bP(\bar y_n - \mu > q_\alpha(y_n - \mu) | E) + P() instead of the same thing without the conditioning. And the distribution of \bar y_n conditioned on the fact that y_n satisfy some condition is not necessarily the same as without the condition.

### Reviewer 2

The paper is clear and well-written. I believe the main result Theorem 2.1 is novel. But I have the following concerns. (1) The results depends on the symmetry of the rewards. This is a huge assumption, which does not hold for many applications, including the Bernoulli bandits and many real-world problems with highly-skewed rewards. I do not take this as a downside of this paper, but this should be explicitly clarified in the abstract and the introduction to avoid overclaims. (2) The function \phi(y_n) is still needed in Theorem 2.2 as an exact concentration bound for \bar{y}_n - \mu. This is only possible in previously studied cases such as bounded rewards or Gaussian rewards. Admittedly this can also be extended to sub-gaussian or sub-Weibull rewards with known Orlicz norm, but the Orlicz norm is arguably never known in practice for potentially unbounded rewards. So from my point of view, the bootstrap UCB improves but does not extend the regime for the regret guarantees. Again I do not think this is a downside and I think the improvement is interesting, but this point should be made explicit at the beginning of the paper to avoid overclaims. (3) When comparing Bootstrap UCB with vanilla UCB, how do you set the alpha for both? Given the parameter \alpha, the confidence level for vanilla UCB is \alpha, while that in your theory (Theorem 2.1) is 2\alpha. For fair comparison, if you take \delta = 0.5, the equation (2.6) should be set as q_{\alpha / 4}(y_n - \bar{y}_n) + 2\log (8 / \alpha) / n. (4) In Theorem 3.2, \alpha_t is set to be 1/T^2 but in implementation it is set to be 1/(t+1). Would it be possible to analyze the latter as well? (5) The authors claim the sub-Weibull variables as "heavy-tailed" (e.g. the second line of Section 3.2). I do not think this is what people call "heavy-tailed". It usually means variables with only finite moments. The random variables with Weibull tail is light-tailed. (6) There are lots of missing references for the multiplier bootstrap. It can be dated back to Rubin (1981), which was called Bayesian bootstrap initially. Later it was studied and developed by Wu (1986), Liu (1988), Mason and Newton (1992), Rao and Zhao (1992), Mammen (1993), Chatterjee (1999), just to name a few. A relatively thorough literature review is important for a high-quality paper. References D. B. Rubin. The bayesian bootstrap. The annals of statistics, pages 130–134, 1981. C.-F. J. Wu. Jackknife, bootstrap and other resampling methods in regression analysis. the Annals of Statistics, 14(4):1261–1295, 1986. R. Y. Liu. Bootstrap procedures under some non-iid models. The Annals of Statistics, 16(4):1696–1708, 1988. Mason, David M., and Michael A. Newton. "A rank statistics approach to the consistency of a general bootstrap." The Annals of Statistics 20.3 (1992): 1611-1624. C. R. Rao and L. Zhao. Approximation to the distribution of M-estimates in linear models by randomly weighted bootstrap. Sankhya: The Indian Journal of Statistics, Series A, pages 323–331, 1992. E. Mammen. Bootstrap and wild bootstrap for high dimensional linear models. The annals of statistics, 21(1):255–285, 1993. S. B. Chatterjee. Generalised bootstrap techniques. PhD thesis, Indian Statistical Institute, Kolkata, 1999.

### Reviewer 3

In this paper, the authors propose a novel point of view on a very well-known algorithm: UCB. Rather than using worst case concentration inequalities, which only exploit the tail information, the authors take advantage of the multiplayer bootstrap to provide a non-parametric data dependent UCB. The multiplayer bootstrap consists in approximating the quantile q_\alpha by reweighting the data with random multipliers independent of the data. Theorem 2.2 provides a significant result by controlling non-asymptotically the bootstrapped quantile. Indeed rather than using a worst case concentration inequality which leads to a data independent UCB, the control of the quantile allows to build a data dependent UCB. Bootstrapped UCB (algorithm 1) uses a Monte Carlo approach to approximate the bootstrapped quantile. The second significant analytical result is a concentration inequality for sub-Weibull Distribution, which is more general than sub-Gaussian distribution. Theorem 3.1 allows extending Bootstrapped UCB (and a lot of bandit algorithms) to sub-Weibull Distribution. Finally Theorem 3.3 states problem dependent and problem independent upper bounds of regret for Bootstrapped UCB. Experimental results show that Bootstrapped UCB outperforms UCB1, while it is more robust against a wrong prior than TS. This is a well-written paper which contains significant results for the bandit community. Nevertheless, I was disappointed by the fact that the control of the approximation of the bootstrapped quantile q^B_\alpha with respect to q_\alpha is not done. Is-it a big deal ? I understand that this control depends only on the parameter B, and hence on the computational cost. However sometimes, we cannot consider that the computational cost is not an issue, for instance for IoT. ______________________________________________________________ The authors answered to my concern. The obtained algorithm is still computationally expensive. However I think that the approach is original and could open research avenue for bandit community. I recommend acceptation.