Archive for the ‘Evoluntionary’ Category

Intuition, deliberation, and the evolution of cooperation [hackathons for example?]

Monday, January 11th, 2016

Intuition, deliberation, and the evolution of cooperation by Adam Bear and David G. Rand.

Significance:

The role of intuition versus deliberation in human cooperation has received widespread attention from experimentalists across the behavioral sciences in recent years. Yet a formal theoretical framework for addressing this question has been absent. Here, we introduce an evolutionary game-theoretic model of dual-process agents playing prisoner’s dilemma games. We find that, across many types of environments, evolution only ever favors agents who (i) always intuitively defect, or (ii) are intuitively predisposed to cooperate but who, when deliberating, switch to defection if it is in their self-interest to do so. Our model offers a clear explanation for why we should expect deliberation to promote selfishness rather than cooperation and unifies apparently contradictory empirical results regarding intuition and cooperation.

Abstract:

Humans often cooperate with strangers, despite the costs involved. A long tradition of theoretical modeling has sought ultimate evolutionary explanations for this seemingly altruistic behavior. More recently, an entirely separate body of experimental work has begun to investigate cooperation’s proximate cognitive underpinnings using a dual-process framework: Is deliberative self-control necessary to reign in selfish impulses, or does self-interested deliberation restrain an intuitive desire to cooperate? Integrating these ultimate and proximate approaches, we introduce dual-process cognition into a formal game-theoretic model of the evolution of cooperation. Agents play prisoner’s dilemma games, some of which are one-shot and others of which involve reciprocity. They can either respond by using a generalized intuition, which is not sensitive to whether the game is one-shot or reciprocal, or pay a (stochastically varying) cost to deliberate and tailor their strategy to the type of game they are facing. We find that, depending on the level of reciprocity and assortment, selection favors one of two strategies: intuitive defectors who never deliberate, or dual-process agents who intuitively cooperate but sometimes use deliberation to defect in one-shot games. Critically, selection never favors agents who use deliberation to override selfish impulses: Deliberation only serves to undermine cooperation with strangers. Thus, by introducing a formal theoretical framework for exploring cooperation through a dual-process lens, we provide a clear answer regarding the role of deliberation in cooperation based on evolutionary modeling, help to organize a growing body of sometimes-conflicting empirical results, and shed light on the nature of human cognition and social decision making.

Guidance for the formation of new communities, i.e., between strangers?

Critically, selection never favors agents who use deliberation to override selfish impulses: Deliberation only serves to undermine cooperation with strangers.

How would you motivate the non-deliberative formation of an online community for creating a topic map?

It just occurred to me, is the non-deliberative principle in play at hackathons? Where there are strangers but not sufficient time or circumstances to deliberate on your contribution and return on that contribution?

Hackathons, the ones I have read about, tend to be physical, summer camp type events. Is physical presence and support a key?

If you were going to do a topic map hackathon, physical or online, what would be its focus?

I first saw this in a tweet by Steve Strogatz.

AI vs. Taxpayer (so far, taxpayer wins)

Saturday, October 10th, 2015

Computer Scientists Wield Artificial Intelligence to Battle Tax Evasion by Lynnley Browning.

From the post:

When federal authorities want to ferret out abusive tax shelters, they send an army of forensic accountants, auditors and lawyers to burrow into suspicious tax returns.

Analyzing mountains of filings and tracing money flows through far-flung subsidiaries is notoriously difficult; even if the Internal Revenue Service manages to unravel a major scheme, it typically does so only years after its emergence, by which point a fresh dodge has often already replaced it.

But what if that needle-in-a-haystack quest could be done routinely, and quickly, by a computer? Could the federal tax laws — 74,608 pages of legal gray areas and welters of credits, deductions and exemptions — be accurately rendered in an algorithm?

“We see the tax code as a calculator,” said Jacob Rosen, a researcher at the Massachusetts Institute of Technology who focuses on the abstract representation of financial transactions and artificial intelligence techniques. “There are lots of extraordinarily smart people who take individual parts of the tax code and recombine them in complex transactions to construct something not intended by the law.”

A recent paper by Mr. Rosen and four other computer scientists — two others from M.I.T. and two at the Mitre Corporation, a nonprofit technology research and development organization — demonstrated how an algorithm could detect a certain type of known tax shelter used by partnerships.

I had to chuckle when I read:

“There are lots of extraordinarily smart people who take individual parts of the tax code and recombine them in complex transactions to construct something not intended by the law.”

It would be more accurate to say: “…something not intended by the tax policy wonks at the IRS.”

Or at Justice Sutherland said in Gregory v. Helvering (1934):

The legal right of a taxpayer to decrease the amount of what otherwise would be his taxes, or altogether to avoid them, by means which the law permits, cannot be doubted.

Gregory v. Helvering isn’t much comfort because Sutherland also found against the taxpayer in that case on a “not intended by the law” basis.

Still, if you read the paper you will realize taxpayers are still well ahead vis-a-vis any AI:

Drawbacks are that currently SCOTE has a very simplified view of transactions, audit points and law.

Should we revisit the Turing test?

Perhaps a series of tax code tests, 1040A, 1040 long form, corporate reorganization, each one more complex than the one before.

Pitch the latest AIs against tax professionals?

How Could Language Have Evolved?

Monday, September 1st, 2014

How Could Language Have Evolved? by Johan J. Bolhuis, Ian Tattersall, Noam Chomsky, Robert C. Berwick.

Abstract:

The evolution of the faculty of language largely remains an enigma. In this essay, we ask why. Language’s evolutionary analysis is complicated because it has no equivalent in any nonhuman species. There is also no consensus regarding the essential nature of the language “phenotype.” According to the “Strong Minimalist Thesis,” the key distinguishing feature of language (and what evolutionary theory must explain) is hierarchical syntactic structure. The faculty of language is likely to have emerged quite recently in evolutionary terms, some 70,000–100,000 years ago, and does not seem to have undergone modification since then, though individual languages do of course change over time, operating within this basic framework. The recent emergence of language and its stability are both consistent with the Strong Minimalist Thesis, which has at its core a single repeatable operation that takes exactly two syntactic elements a and b and assembles them to form the set {a, b}.

Interesting that Chomsky and his co-authors have seized upon “hierarchical syntactic structure” as “the key distinguishing feature of language.”

Remember text as an Ordered Hierarchy of Content Objects (OHCO), which has made the rounds in markup circles since 1993. It’s staying power was quite surprising since examples are hard to find outside of markup text encodings. Your average text prior to markup can be mapped to OHCO only with difficulty in most cases.

Syntactic structures are attributed to languages so be mindful that any “hierarchical syntactic structure” is entirely of human origin separate and apart from language.

‘A Perfect and Beautiful Machine’:…

Tuesday, June 24th, 2014

‘A Perfect and Beautiful Machine’: What Darwin’s Theory of Evolution Reveals About Artificial Intelligence by Daniel C. Dennett.

From the post:


All things in the universe, from the most exalted (“man”) to the most humble (the ant, the pebble, the raindrop) were creations of a still more exalted thing, God, an omnipotent and omniscient intelligent creator — who bore a striking resemblance to the second-most exalted thing. Call this the trickle-down theory of creation. Darwin replaced it with the bubble-up theory of creation. One of Darwin’s nineteenth-century critics, Robert Beverly MacKenzie, put it vividly:

In the theory with which we have to deal, Absolute Ignorance is the artificer; so that we may enunciate as the fundamental principle of the whole system, that, in order to make a perfect and beautiful machine, it is not requisite to know how to make it. This proposition will be found, on careful examination, to express, in condensed form, the essential purport of the Theory, and to express in a few words all Mr. Darwin’s meaning; who, by a strange inversion of reasoning, seems to think Absolute Ignorance fully qualified to take the place of Absolute Wisdom in all the achievements of creative skill.

It was, indeed, a strange inversion of reasoning. To this day many people cannot get their heads around the unsettling idea that a purposeless, mindless process can crank away through the eons, generating ever more subtle, efficient, and complex organisms without having the slightest whiff of understanding of what it is doing.

Turing’s idea was a similar — in fact remarkably similar — strange inversion of reasoning. The Pre-Turing world was one in which computers were people, who had to understand mathematics in order to do their jobs. Turing realized that this was just not necessary: you could take the tasks they performed and squeeze out the last tiny smidgens of understanding, leaving nothing but brute, mechanical actions. In order to be a perfect and beautiful computing machine, it is not requisite to know what arithmetic is.

What Darwin and Turing had both discovered, in their different ways, was the existence of competence without comprehension. This inverted the deeply plausible assumption that comprehension is in fact the source of all advanced competence. Why, after all, do we insist on sending our children to school, and why do we frown on the old-fashioned methods of rote learning? We expect our children’s growing competence to flow from their growing comprehension. The motto of modern education might be: “Comprehend in order to be competent.” For us members of H. sapiens, this is almost always the right way to look at, and strive for, competence. I suspect that this much-loved principle of education is one of the primary motivators of skepticism about both evolution and its cousin in Turing’s world, artificial intelligence. The very idea that mindless mechanicity can generate human-level — or divine level! — competence strikes many as philistine, repugnant, an insult to our minds, and the mind of God.
….

“…competence without comprehension….” I rather like that!

Is that what we are observing in crowd-sourcing?

The essay is well worth your time and consideration.

Measuring the Evolution of Ontology Complexity:…

Tuesday, October 15th, 2013

Measuring the Evolution of Ontology Complexity: The Gene Ontology Case Study by Olivier Dameron, Charles Bettembourg, Nolwenn Le Meur. (Dameron O, Bettembourg C, Le Meur N (2013) Measuring the Evolution of Ontology Complexity: The Gene Ontology Case Study. PLoS ONE 8(10): e75993. doi:10.1371/journal.pone.0075993)

Abstract:

Ontologies support automatic sharing, combination and analysis of life sciences data. They undergo regular curation and enrichment. We studied the impact of an ontology evolution on its structural complexity. As a case study we used the sixty monthly releases between January 2008 and December 2012 of the Gene Ontology and its three independent branches, i.e. biological processes (BP), cellular components (CC) and molecular functions (MF). For each case, we measured complexity by computing metrics related to the size, the nodes connectivity and the hierarchical structure.

The number of classes and relations increased monotonously for each branch, with different growth rates. BP and CC had similar connectivity, superior to that of MF. Connectivity increased monotonously for BP, decreased for CC and remained stable for MF, with a marked increase for the three branches in November and December 2012. Hierarchy-related measures showed that CC and MF had similar proportions of leaves, average depths and average heights. BP had a lower proportion of leaves, and a higher average depth and average height. For BP and MF, the late 2012 increase of connectivity resulted in an increase of the average depth and average height and a decrease of the proportion of leaves, indicating that a major enrichment effort of the intermediate-level hierarchy occurred.

The variation of the number of classes and relations in an ontology does not provide enough information about the evolution of its complexity. However, connectivity and hierarchy-related metrics revealed different patterns of values as well as of evolution for the three branches of the Gene Ontology. CC was similar to BP in terms of connectivity, and similar to MF in terms of hierarchy. Overall, BP complexity increased, CC was refined with the addition of leaves providing a finer level of annotations but decreasing slightly its complexity, and MF complexity remained stable.

Prospective ontology authors and ontology authors need to read this paper carefully.

Over a period of only four years, the ontologies studied in this paper evolved.

Which is a good thing, because the understandings that underpinned the original ontologies changed over those four years.

The lesson here being that for all of their apparent fixity, a useful ontology is no more fixed than authors who create and maintain it and the users who use it.

At any point in time an ontology may be “fixed” for some purpose or in some view, but that is a snapshot in time, not an eternal view.

As ontologies evolve, so must the mappings that bind them with and to other ontologies.

A blind mapping, simple juxtaposition of terms from ontologies is one form of mapping. A form that makes maintenance a difficult and chancy affair.

If on the other hand, each term had properties that supported the recorded mapping, any maintainer could follow enunciated rules for maintenance of that mapping.

Blind mapping: Pay the cost of mapping every time ontology mappings become out of synchronization enough to pinch (or lead to disaster).

Sustainable mapping: Pay the full cost of mapping once and then maintain the mapping.

What’s your comfort level with risk?

  • Discovery of a “smoking gun” memo on tests of consumer products.
  • Inappropriate access to spending or financial records.
  • Preservation of inappropriate emails.
  • etc.

What are you not able to find with an unmaintained ontology?

…Conceptual Model For Evolving Graphs

Wednesday, September 11th, 2013

An Analytics-Aware Conceptual Model For Evolving Graphs by Amine Ghrab, Sabri Skhiri, Salim Jouili, and Esteban Zimanyi.

Abstract:

Graphs are ubiquitous data structures commonly used to represent highly connected data. Many real-world applications, such as social and biological networks, are modeled as graphs. To answer the surge for graph data management, many graph database solutions were developed. These databases are commonly classified as NoSQL graph databases, and they provide better support for graph data management than their relational counterparts. However, each of these databases implement their own operational graph data model, which differ among the products. Further, there is no commonly agreed conceptual model for graph databases.

In this paper, we introduce a novel conceptual model for graph databases. The aim of our model is to provide analysts with a set of simple, well-defined, and adaptable conceptual components to perform rich analysis tasks. These components take into account the evolving aspect of the graph. Our model is analytics-oriented, flexible and incremental, enabling analysis over evolving graph data. The proposed model provides a typing mechanism for the underlying graph, and formally defines the minimal set of data structures and operators needed to analyze the graph.

The authors concede that much work remains to be done, both theoretical and practical on their proposal.

With the rise of distributed computing, every “fact” depends upon a calculated moment of now. What was a “fact” five minutes ago may not longer be considered as a “fact” but as an “error.”

Who is responsible for changes in “facts,” warranties for “facts,” who gives and gets notices about changes in “facts,” all remain to be determined.

Models for evolving graphs may assist in untangling the rights, obligations and relationships that are nearly upon us with distributed computing.

DEAP: Distributed Evolutionary Algorithms in Python

Monday, April 9th, 2012

DEAP: Distributed Evolutionary Algorithms in Python

From the website:

DEAP is intended to be an easy to use distributed evolutionary algorithm library in the Python language. Its two main components are modular and can be used separately. The first module is a Distributed Task Manager (DTM), which is intended to run on cluster of computers. The second part is the Evolutionary Algorithms in Python (EAP) framework.

Components

DTM

DTM is a distributed task manager that is able to spread workload over a buch of computers using a TCP or a MPI connection.

DTM include the following features:

  • Easy to use parallelization paradigms
  • Offers a similar interface to the Python's multiprocessing module
  • Basic load balancing algorithm
  • Works over mpi4py
  • Support for TCP communication manager

EAP

EAP is the evolutionary core of DEAP, it provides data structures, methods and tools to design any kind of evolutionary algorithm. It works in perfect harmony with DTM, allowing easy parallelization of any demanding evolutionary task.

EAP includes the following features:

  • Genetic algorithm using any imaginable representation
    • List, Array, Set, Dictionary, Tree, Numpy Array (tip revision), etc.
  • Genetic programing using prefix trees
    • Loosely typed, Strongly typed
    • Automatically defined functions
  • Evolution strategies (including CMA-ES)
  • Multi-objective optimisation (NSGA-II, SPEA-II)
  • Co-evolution of multiple populations
  • Parallelization of the evaluations (and more)
  • Hall of Fame of the best individuals that lived in the population
  • Checkpoints that take snapshots of a system regularly
  • Benchmarks module containing most common test functions
  • Genealogy of an evolution (that is compatible with NetworkX)
  • Examples of alternative algorithms : Particle Swarm Optimization, Differential Evolution

If you are interested in evolutionary approaches to data mining, not a bad place to start.

META’2012 International Conference on Metaheuristics and Nature Inspired Computing

Saturday, November 5th, 2011

META’2012 International Conference on Metaheuristics and Nature Inspired Computing

Dates:

  • Paper submission: May 15, 2012
  • Session/Tutorial submission: May 15, 2012
  • Paper notification: July 15, 2012
  • Session/Tutorial notification: June 15, 2012
  • Conference: October 27-31, 2012

From the website:

The 4th International Conference on Metaheuristics and Nature Inspired Computing, META’2012, will held in Port El-Kantaoiui (Sousse, Tunisia).

The Conference will be an exchange space thanks to the sessions of the research works presentations and also will integrate tutorials and a vocational training of metaheuristics and nature inspired computing.

The scope of the META’2012 conference includes, but is not limited to:

  • Local search, tabu search, simulated annealing, VNS, ILS, …
  • Evolutionary algorithms, swarm optimization, scatter search, …
  • Emergent nature inspired algorithms: quantum computing, artificial immune systems, bee colony, DNA computing, …
  • Parallel algorithms and hybrid methods with metaheuristics, machine learning, game theory, mathematical programming, constraint programming, co-evolutionary, …
  • Application to: logistics and transportation, telecommunications, scheduling, data mining, engineering design, bioinformatics, …
  • Theory of metaheuristics, landscape analysis, convergence, problem difficulty, very large neighbourhoods, …
  • Application to multi-objective optimization
  • Application in dynamic optimization, problems with uncertainty,bi-level optimization, …

The “proceedings” for Meta ’10 can be seen at: Meta ’10 papers. It would be more accurate to say “extended abstracts” because, for example,

Luis Filipe de Mello Santos, Daniel Madeira, Esteban Clua, Simone Martins and Alexandre Plastino. A parallel GRASP resolution for a GPU architecture

runs all of two (2) pages. As is about the average length of the other twenty (20) papers that I checked.

I like concise writing but two pages to describe a parallel GRASP setup on a GPU architecture? Just an enticement (there is an ugly word I could use) to get you to read the ISI journal with the article.

Conference and its content look very interesting. Can’t say I care for the marketing technique for the journals in question. Not objecting to the marketing of the journals, but don’t say proceedings when what is meant is ads for the journals.

Modeling Network Evolution Using Graph Motifs

Sunday, May 8th, 2011

Modeling Network Evolution Using Graph Motifs by Drew Conway.

Abstract:

Network structures are extremely important to the study of political science. Much of the data in its subfields are naturally represented as networks. This includes trade, diplomatic and conflict relationships. The social structure of several organization is also of interest to many researchers, such as the affiliations of legislators or the relationships among terrorist. A key aspect of studying social networks is understanding the evolutionary dynamics and the mechanism by which these structures grow and change over time. While current methods are well suited to describe static features of networks, they are less capable of specifying models of change and simulating network evolution. In the following paper I present a new method for modeling network growth and evolution. This method relies on graph motifs to generate simulated network data with particular structural characteristic. This technique departs notably from current methods both in form and function. Rather than a closed-form model, or stochastic implementation from a single class of graphs, the proposed “graph motif model” provides a framework for building flexible and complex models of network evolution. The paper proceeds as follows: first a brief review of the current literature on network modeling is provided to place the graph motif model in context. Next, the graph motif model is introduced, and a simple example is provided. As a proof of concept, three classic random graph models are recovered using the graph motif modeling method: the Erdos-Renyi binomial random graph, the Watts-Strogatz “small world” model, and the Barabasi-Albert preferential attachment model. In the final section I discuss the results of these simulations and subsequent advantage and disadvantages presented by using this technique to model social networks.

Now there’s an interesting idea.

Modeling the evolution of topic maps.

I wonder if the more interesting evolution would reflect the authoring of the topic map or the subject matter of the topic map?

I suppose that would depend upon the author and/or the subject of the map.


Update:

Graph Motif Modeling software now available as distributed Python package

Graph Motif Model Documentation

evo*2011

Thursday, March 10th, 2011

evo*2011

From the website:

evo* comprises the premier co-located conferences in the field of Evolutionary Computing: eurogp, evocop, evobio and evoapplications.

Featuring the latest in theoretical and applied research, evo* topics include recent genetic programming challenges, evolutionary and other meta-heuristic approaches for combinatorial optimization, evolutionary algorithms, machine learning and data mining techniques in the biosciences, in numerical optimization, in music and art domains, in image analysis and signal processing, in hardware optimization and in a wide range of applications to scientific, industrial, financial and other real-world problems.

Conference is 27-29 April 2011 in Torino, Italy.

Even if you are not in the neighborhood, the paper abstracts make an interesting read!

As Time Goes by: Discovering Eras in Evolving Social Networks

Friday, November 12th, 2010

As Time Goes by: Discovering Eras in Evolving Social Networks Authors(s): Michele Berlingerio, Michele Coscia, Fosca Giannotti, Anna Monreale, Dino Pedreschi

Abstract:

Within the large body of research in complex network analysis, an important topic is the temporal evolution of networks. Existing approaches aim at analyzing the evolution on the global and the local scale, extracting properties of either the entire network or local patterns. In this paper, we focus instead on detecting clusters of temporal snapshots of a network, to be interpreted as eras of evolution. To this aim, we introduce a novel hierarchical clustering methodology, based on a dissimilarity measure (derived from the Jaccard coefficient) between two temporal snapshots of the network. We devise a framework to discover and browse the eras, either in top-down or a bottom-up fashion, supporting the exploration of the evolution at any level of temporal resolution. We show how our approach applies to real networks, by detecting eras in an evolving co-authorship graph extracted from a bibliographic dataset; we illustrate how the discovered temporal clustering highlights the crucial moments when the network had profound changes in its structure. Our approach is finally boosted by introducing a meaningful labeling of the obtained clusters, such as the characterizing topics of each discovered era, thus adding a semantic dimension to our analysis.

Deeply interesting work.

Questions:

  1. Is is a fair assumption that terms used by one scholar will be used the same way by scholars that cite them? (discussion)
  2. If you think #1 is true, then does entity resolution, etc., however you want to talk about recognition of subjects, apply from the first scholar outwards? If so, how far? (discussion)
  3. If you think #1 is false, why? (discussion)
  4. How would you go about designing a project to identify usages of terms in a body of literature? Such that you could detect changes in usage? What questions would you have to ask? (3-5 pages, citations)

PS: Another way to think about this area is: Do terms have social lives? Is that a useful way to talk about them?

A Survey of Genetics-based Machine Learning

Thursday, October 21st, 2010

A Survey of Genetics-based Machine Learning Author: Tim Kovacs

Abstract:

This is a survey of the field of Genetics-based Machine Learning (GBML): the application of evolutionary algorithms to machine learning. We assume readers are familiar with evolutionary algorithms and their application to optimisation problems, but not necessarily with machine learning. We briefly outline the scope of machine learning, introduce the more specific area of supervised learning, contrast it with optimisation and present arguments for and against GBML. Next we introduce a framework for GBML which includes ways of classifying GBML algorithms and a discussion of the interaction between learning and evolution. We then review the following areas with emphasis on their evolutionary aspects: GBML for sub-problems of learning, genetic programming, evolving ensembles, evolving neural networks, learning classifier systems, and genetic fuzzy systems.

The author’s preprint has 322 references. Plus there are slides, bibliographies in BibTeX.

If you are interesting in augmented topic map authoring using GBML, this would be a good starting place.

Questions:

  1. Pick 3 subject areas. What arguments would you make in favor of GBML for augmenting authoring of a topic map for those subject areas?
  2. Same subject areas, but what arguments would you make against the use of GBML for augmenting authoring of a topic map for those subject areas?
  3. Design an experiment to test one of your arguments for and against GBML. (project, use of the literature encouraged)
  4. Convert the BibTeX formatted bibliographies into a topic map. (project)

Evolutionary Clustering and Analysis of Heterogeneous Information Networks

Saturday, October 9th, 2010

Evolutionary Clustering and Analysis of Heterogeneous Information Networks Authors: Manish Gupta; Charu Aggarwal; Jiawei Han; Yizhou Sun Keywords: ENetClus, evolutionary clustering, typed-clustering, DBLP, bibliographic networks

Abstract:

In this paper, we study the problem of evolutionary clustering of multi-typed objects in a heterogeneous bibliographic network. The traditional methods of homogeneous clustering methods do not result in a good typed-clustering. The design of heterogeneous methods for clustering can help us better understand the evolution of each of the types apart from the evolution of the network as a whole. In fact, the problem of clustering and evolution diagnosis are closely related because of the ability of the clustering process to summarize the network and provide insights into the changes in the objects over time. We present such a tightly integrated method for clustering and evolution diagnosis of heterogeneous bibliographic information networks. We present an algorithm, ENetClus, which performs such an agglomerative evolutionary clustering which is able to show variations in the clusters over time with a temporal smoothness approach. Previous work on clustering networks is either based on homogeneous graphs with evolution, or it does not account for evolution in the process of clustering heterogeneous networks. This paper provides the first framework for evolution-sensitive clustering and diagnosis of heterogeneous information networks. The ENetClus algorithm generates consistent typed-clusterings across time, which can be used for further evolution diagnosis and insights. The framework of the algorithm is specifically designed in order to facilitate insights about the evolution process. We use this technique in order to provide novel insights about bibliographic information networks.

Exploring heterogeneous information networks is a first step towards discovery/recognition of new subjects. What other novel insights will emerge from work on heterogeneous information networks only future research can answer.