Traversing News with Second Order Swarm Intelligence

David MS Rodrigues Reading the News Through its Structure New Hybrid Connectivity Based Approaches

Figure – Two simplicies a and b connected by the 2-dimensional face, the triangle {1;2;3}. In the analysis of the time-line of The Guardian newspaper (link) the system used feature vectors based on frequency of words and them computed similarity between documents based on those feature vectors. This is a purely statistical approach that requires great computational power and that is difficult for problems that have large feature vectors and many documents. Feature vectors with 100,000 or more items are common and computing similarities between these documents becomes cumbersome. Instead of computing distance (or similarity) matrices between documents from feature vectors, the present approach explores the possibility of inferring the distance between documents from the Q-analysis description. Q-analysis is a very natural notion of connectivity between the simplicies of the structure and in the relation studied, documents are connected to each other through shared sets of tags entered by the journalists. Also in this framework, eccentricity is defined as a measure of the relatedness of one simplex in relation to another [7].

David M.S. Rodrigues and Vitorino Ramos, “Traversing News with Ant Colony Optimisation and Negative Pheromones” [PDF], accepted as preprint for oral presentation at the European Conference on Complex Systems – ECCS‘14 in Lucca, Sept. 22-26, 2014, Italy.

Abstract: The past decade has seen the rapid development of the online newsroom. News published online are the main outlet of news surpassing traditional printed newspapers. This poses challenges to the production and to the consumption of those news. With those many sources of information available it is important to find ways to cluster and organise the documents if one wants to understand this new system. Traditional approaches to the problem of clustering documents usually embed the documents in a suitable similarity space. Previous studies have reported on the impact of the similarity measures used for clustering of textual corpora [1]. These similarity measures usually are calculated for bag of words representations of the documents. This makes the final document-word matrix high dimensional. Feature vectors with more than 10,000 dimensions are common and algorithms have severe problems with the high dimensionality of the data. A novel bio inspired approach to the problem of traversing the news is presented. It finds Hamiltonian cycles over documents published by the newspaper The Guardian. A Second Order Swarm Intelligence algorithm based on Ant Colony Optimisation was developed [2, 3] that uses a negative pheromone to mark unrewarding paths with a “no-entry” signal. This approach follows recent findings of negative pheromone usage in real ants [4].

In this case study the corpus of data is represented as a bipartite relation between documents and keywords entered by the journalists to characterise the news. A new similarity measure between documents is presented based on the Q-analysis description [5, 6, 7] of the simplicial complex formed between documents and keywords. The eccentricity between documents (two simplicies) is then used as a novel measure of similarity between documents. The results prove that the Second Order Swarm Intelligence algorithm performs better in benchmark problems of the travelling salesman problem, with faster convergence and optimal results. The addition of the negative pheromone as a non-entry signal improves the quality of the results. The application of the algorithm to the corpus of news of The Guardian creates a coherent navigation system among the news. This allows the users to navigate the news published during a certain period of time in a semantic sequence instead of a time sequence. This work as broader application as it can be applied to many cases where the data is mapped to bipartite relations (e.g. protein expressions in cells, sentiment analysis, brand awareness in social media, routing problems), as it highlights the connectivity of the underlying complex system.

Keywords: Self-Organization, Stigmergy, Co-Evolution, Swarm Intelligence, Dynamic Optimization, Foraging, Cooperative Learning, Hamiltonian cycles, Text Mining, Textual Corpora, Information Retrieval, Knowledge Discovery, Sentiment Analysis, Q-Analysis, Data Mining, Journalism, The Guardian.

References:

[1] Alexander Strehl, Joydeep Ghosh, and Raymond Mooney. Impact of similarity measures on web-page clustering. In Workshop on Artifcial Intelligence for Web Search (AAAI 2000), pages 58-64, 2000.

[2] David M. S. Rodrigues, Jorge Louçã, and Vitorino Ramos. From standard to second-order Swarm Intelligence phase-space maps. In Stefan Thurner, editor, 8th European Conference on Complex Systems, Vienna, Austria, 9 2011.

[3] Vitorino Ramos, David M. S. Rodrigues, and Jorge Louçã. Second order Swarm Intelligence. In Jeng-Shyang Pan, Marios M. Polycarpou, Michael Wozniak, André C.P.L.F. Carvalho, Hector Quintian, and Emilio Corchado, editors, HAIS’13. 8th International Conference on Hybrid Artificial Intelligence Systems, volume 8073 of Lecture Notes in Computer Science, pages 411-420. Springer Berlin Heidelberg, Salamanca, Spain, 9 2013.

[4] Elva J.H. Robinson, Duncan Jackson, Mike Holcombe, and Francis L.W. Ratnieks. No entry signal in ant foraging (hymenoptera: Formicidae): new insights from an agent-based model. Myrmecological News, 10(120), 2007.

[5] Ronald Harry Atkin. Mathematical Structure in Human Affairs. Heinemann Educational Publishers, 48 Charles Street, London, 1 edition, 1974.

[6] J. H. Johnson. A survey of Q-analysis, part 1: The past and present. In Proceedings of the Seminar on Q-analysis and the Social Sciences, Universty of Leeds, 9 1983.

[7] David M. S. Rodrigues. Identifying news clusters using Q-analysis and modularity. In Albert Diaz-Guilera, Alex Arenas, and Alvaro Corral, editors, Proceedings of the European Conference on Complex Systems 2013, Barcelona, 9 2013.

The Conclusion in scientific papers?

“Here’s a simple test: if somebody reads your conclusions before reading the rest of your paper, will they fully understand them? If the answer is ‘yes’, there’s probably something wrong. A good conclusion says things that become significant after the paper has been read. A good conclusion gives perspective to sights that haven’t yet been seen at the introduction. A conclusion is about the implications of what the reader has learned.”

via Elements of style : Article : Nature Physics.

Finally can we get past that idiotic nonsense of using it just to repeat the abstract, repeat the introduction, repeat everything in the paper, and repeat again and again, … though in fancy words? Thank you!

Quantos Hertz são suficientes para detectar o voo MH370?

Li hoje no The Guardian que um sinal das caixas negras do avião da Malásia MH370, desaparecido há quase 1 mês, pode finalmente ter sido detectado.

O mais curioso desta notícia é que o jornalista refere que as caixas negras emitem um sinal com uma frequência de 37.5kHz por segundo.

Perceberam? 37.5kHz por segundo? Um erro típico de jornalista que não faz a mínima ideia do que frequência quer dizer e muito menos tem uma noção do que a unidade Hertz significa (será que pelo menos percebe o k antes do Hz? ou que Hertz vem do nome do físico alemão Heinrich Hertz?).

Este tipo de erro é crasso, mas é infelizmente é também comum. Hoje em dias os professores não estão nas escolas para fazer os alunos pensar, mas antes e apenas para produzirem soldadinhos de chumbo com cabeças ocas. E em grandes quantidades para aumentar os índices de produtividade. Depois dá nisto.

Complicated or complex – knowing the difference is important

Complicated or complex – knowing the difference is importantBirds flocking provide a good example of a complex adaptive systemBirds flocking provide a good example of a complex adaptive systemUnderstanding the difference between complex and complicated systems is becoming important for many aspects of management and policy. With complicated problems or issues one can define the problem and strategically develop actions, time-frames and milestones along a path to success. In contrast, cause and effect are difficult to predict in complex adaptive systems. This post aims to provide more detail around these concepts as an introduction. It complements the LfS Managing complex adaptive systems page, which provides annotated links to a number of key on-line resources in this area.

via Complicated or complex – knowing the difference is important | sparksforchange.

Onde estás Alan Turing?

Alan Turing

O Jardim do Campo Grande passou o ano de 2013 divido em dois. Um jardim mais perto de Entrecampos aberto ao público, e o jardim que fica em frente à Faculdade de Ciências… fechado para obras. Abriu agora (infelizmente para o presidente da Câmara não ficou pronto a tempo das eleições) e com uma curiosidade interessante:

O percurso que ladeia o jardim do lado da FCUL elogia os grande matemáticos dos tempos modernos desde 1537 com Pedro Nunes até aos tempos recentes. A CML mandou instalar uma placas no chão em jeito de cronologia de eventos e a verdade é que não se fica indiferente, quer-se sempre seguir até à próxima para ver quem está lá, e o que comemora.

A verdade é que percorri hoje este caminho 4 vezes em menos de 45 minutos para me deliciar com os pormenores biográficos (entre outros prazeres que o coração agradece) dos matemáticos que ajudaram a construir a sociedade moderna. Euler, Bayes, Newton, Libeniz, Gauss, Hilbert, Poincaré… estão todos lá… e mais alguns que a memória não me ajuda.

MAS

Mas a verdade é que apesar de tudo isto estar muito bonito… a cronologia é omissa em alguns monstros do século XX. E honestamente são tão importantes que não percebo como podem faltar.

Vamos andando e em 1933 apanhamos com Kolmogorov e saltamos para 1950 e apanhamos com Von Newmann. Volto atrás, vou até mais à frente e pasmo. Faço uma pirueta e pergunto-me:

SERÁ QUE SE ESQUECERAM?

Onde está Alan Turing? O génio da criptanálise que ajudou a derrotar a Alemanha? O Homem que dá o nome ao teste de Turing! O homem que escreveu papers tão fundamentais?

DEVE SER ENGANO, DEIXA LÁ VER DE QUEM MAIS SE ESQUECERAM, pensei eu incrédulo.

A verdade é que logo a seguir falta outro monstro do século XX. Claude Shannon que é só apelidado de pai da teoria da informação.

E pronto por esta altura já tinha uns 6Km nas pernas e um bocado enjoado com o que NÃO VI, voltei para casa e escrevi esta cartita

Senhor presidente da Câmara de Lisboa,

O senhor gosta de comer bem, e aquilo que fez no jardim do campo grande é um belo bacalhau no forno com batatinhas a murro. Só que, tal como está, esqueceu-se de colocar o bacalhau e ficou apenas com as batatas.

Se por acaso não tiver uns trocos para meter lá umas placas a lembrar os feitos destes dois senhores, pelo menos contrate um Banksy qualquer para resolver o problema.

Cumprimentos

Um Lisboeta que até gosta de correr no seu nosso novo jardim.

De regresso de Salamanca

Cycling in Salamanca

Estive em Salamanca uma noite para apresentar o meu trabalho recente com o Vitorino Ramos. A verdade é que não conhecia Salamanca e fique completamente agradado com a experiência.

By the River Tormes in Salamanca

A cidade é calma, com uma população de 150 mil habitantes, e a diferença para Lisboa nota-se. No entanto não é tão pequena que uma pessoa se sinta isolado. Para além disso depois das siesta os Espanhois enchem as ruas e fazem a festa. No momento estão a decorrer as feiras de Salamanca e as noites são completamente animadas com as ‘casetas’ espalhadas pelas ruas a servir tapas, pintos e cañas como se não houvesse amanhã.

Casa Lis in Salamanca

Ainda tive oportunidade de passear um pouco antes da minha apresentação e fui dar um salto à Casa Lis, que funciona como museu de arte noveau e art deco. Uma maravilha que sem ter a riqueza de outros museus, não podia deixar escapar.

Salamanca é sem dúvida uma cidade a (re)visitar com mais tempo, mas enquanto o tempo não chega… há que me preparar para a viagem a Barcelona (outra paixão antiga).