Design of an artificial language for Human-Computer interaction.

ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA INFORMÁTICA Grado en ingeniería informática Design of an artificial language for Human-Computer interaction. Diseño de un lenguaje artificial para la interacción Hombre-Máquina. Realizador por Jorge García González Tutorizado por Francisco J. Vico Vela Departamento Lenguajes y Ciencias de la Computación UNIVERSIDAD DE MÁLAGA MÁLAGA, Noviembre 2016 Fecha defensa: El Secretario del Tribunal Resumen Este trabajo tiene como objetivo señalar las motivaciones para la búsqueda y creación de un lenguaje artificial de propósito general óptimo con el objetivo práctico a largo plazo de poder realizar una comunicación entre hombre y máquina eficaz y en ausencia de ambigüedades. Siguiendo esa idea, nos planteamos cómo podría estudiarse qué elementos básicos presentes en un lenguaje son realmente necesarios y cuales son simplemente innecesarios o incluso contraproducentes. Dado el objetivo de optimalidad que motiva el trabajo, será necesario intentar plantearse el estudio de los lenguajes de propósito general de manera constructiva (desde la ausencia de los mismos, componiendolos progresivamente). Este trabajo no tiene como objetivo la comprensión del funcionamiento de un idioma (lenguaje natural de propósito general) concreto, por tanto no intentaremos profundizar sobre las complejidades de las capacidades humanas para utilizar lenguajes así como no someteremos los lenguajes resultantes a coincidir con las características de ningún lenguaje natural concreto. Pese a ello, sí que partiremos como objeto de estudio de los tres elementos básicos en la sintaxis de los lenguajes naturales (sujeto, verbo y objeto). Propondremos un problema simple de agrupamiento en el que intervengan varios agentes que dispongan de información parcial que podrá ser compartida entre los susodichos mediante lenguajes no ambiguos de distinta complejidad. Definiremos varios lenguajes con sintaxis, semántica y uso de complejidades crecientes, describiremos tanto el problema como las herramientas para evaluar los resultados contrastando la efectividad de cada lenguaje con el objetivo de tener unos resultados que puedan respaldar empíricamente qué lenguaje resulta mejor para resolver el problema. Palabras claves Lenguajes, lenguajes artificiales, agrupamiento, sistema multiagente. 1 Abstract This project has as objective to note motivations to search and develop an optimal general purpose artificial language with effective and not ambiguous human-machine communication objective in long term. Following this idea, we will ask ourselves how could be studied which languages basic elements are actually necessaries and which ones are unnecessary or even counter-productive. Given the optimality objective that motivates this works, it will be necessary to face general purpose language from a constructive way (from the absence of language, creating them progressively). This work does not aim to face an specific natural language understanding so we will not study human language capacity complexities and we will not subdue our resulting languages to match with any natural language. With that, we will use as study subject three basics elements in natural languages (subject, verb and object). We will propose an enough simple clustering problem performed by agents with partial information that will be shared between them by the use of non ambiguous languages with increasing complex syntax, semantic and use. We will also define some mathematical tools to evaluate results to contrast each language effectiveness to obtain results to empirically support what language is better to face proposed problem. Keywords Languages, artificial languages, clustering, multiagent system. 2 Contents 1 Introduction 4 1.1 Language problem from computer science point of view . . . . . . . . . 4 1.2 What are languages for? . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Natural human language basic structure and animal examples . . . . . 7 1.3.1 Some alternative languages examples . . . . . . . . . . . . . . . 8 1.4 Language emergency in a machine approach . . . . . . . . . . . . . . . 9 2 Proposed clustering problem 11 2.1 Informaldescription ............................. 11 2.2 Formaldescription .............................. 12 2.3 Simulationsapproach ............................ 17 2.3.1 Evaluation............................... 17 2.4 Model designing general approach . . . . . . . . . . . . . . . . . . . . . 19 2.5 Model 1: Without a language . . . . . . . . . . . . . . . . . . . . . . . . 20 2.6 Model 2: With a simple language formed only by numbers . . . . . . . . 22 2.7 Model 3: With language formed by pronouns and numbers . . . . . . . 24 2.8 Model 4: With language formed by pronouns, verbs and numbers . . . . 30 3 Experiments 34 3.1 ExperimentsDetails ............................. 34 3.2 Results .................................... 36 4 Conclusions 38 5 Conclusiones 40 6 References 42 7 Appendix A: Implementation Details 44 3 1 Introduction This work is divided in three main sections. This, first section, serves as introduction to provide context, motivation and approach to the whole work. Second section is dedicated to expose our proposed problem, models to resolve it, mathematical formalizations and evaluation tools. Third section is dedicated to experiments description and results. To end, there are conclusions about the project, references and an appendix with code details. 1.1 Language problem from computer science point of view Natural Language Processing (NLP from now on) is one of the main goals in Artificial Intelligence (AI from now on) because of two main reasons: the first is mainly practical, the communication between humans and machines can change the way we interact with computers and allow a channel of communication much more natural and intuitive for us; the second main reason is a matter of cognitive knowledge, through the study of this problem we can try to understand an issue so complex as the human language mental function. Regarding to the first goal, in the last years we have seen impressive advances. In this direction, statistical NLP is giving goods results, this reformulation from the traditional non-statistical approach is characterized by simpler approximations in front of deep analysis of languages and machine-learning methods based on large and annotated bodies of text (Nadkarni et al., 2011).The best example should be the famous IBM’s Watson (Gliozzo et al., 2013) and its participation in ‘Jeopardy!’ show. We also can see advances in symbolic AI applied to NLP such as the use of George Lakoff’s natural logic to infer from a text in natural language (MacCartney & Manning, 2007), for example. The relation between our usual notion of intelligence, AI and NLP is so old that language is a fundamental part of Turing test. There is no exact definition of intelligence but intuitively is normal to guess that “intelligence”, whatever it may be, must imply the ability of use a language as we, humans, do, because we are “intelligent” and we have that ability. Of course, this is an inference that, in absence of a formal definition of intelligence, has little basis but that absence makes so important NLP as reference point like Chess or Go until they were overtaken. If we observe the usual approach to language analysis and processing, it is often a Top-Down one: it is an attempt that tries to deal with a specific language from its actual complex state or with the language problem in abstract trying to explain all its properties. An important example in this case could be Hans Kamp’s Discourse Representation Theory (Geurts et al., 2007) or Montague Grammar (Janssen, 2011). 4 The problem with this approach is that languages are complex compositions resulted from thousands of years of evolution submitted to culturals, biologicals, historicals and socials factors. For this reason, each natural language could have “burden” in his formation: unnecessary complexity that complicate language analysis and processing. This is a lack to those two main objectives we exposed previously (NLP and understanding language). NLP is a matter that requires a lot of information much of which is not in the language itself. For example, the matter of give meaning to a word (define a concept in the end). How could a machine understand a word like pain if it doesn’t feel it? Yes. We have definitions like “Highly unpleasant physical sensation caused by illness or injury” from Oxford Dictionary but what allow us to understand the word pain is we can feel it and we guess the others beings feel it like we do. It would be comparable with the “Flatland, romance of many dimensions” metaphor. In that book, it is proposed a two dimensional world inhabited by two dimensional entities. If a sphere cross this word, entities could not actually understand the sphere, only a succession of circles, because there is only two spatial dimensions for them. Another comparison would be our understanding of quantum physics. Yes, we have mathematical equations to define it but we have little capacity to imagine it. It is not the world we sense, so it is at least unintuitive and maybe we cannot in fact totally understand it. The last comparison and maybe the best would be to question ourselves about the color of an infrared light band. We simply can not answer. We know infrared frequencies exist but we can not link a colour to them since our eyes cone cells lead only with some light frequencies, we only know colours related to a little spectrum of frequencies and others colours seems simply unimaginables. In this line, can we actually expect a machine to understand all information we associate to words like chair, dog, earth, or liquid? We can make statistical analysis and obtain responses to phrases with that words or even logical definitions and inferences, but maybe we cannot give a machine without other human-like capabilities all information about a word and, without that information, it would be impossible to make a like-human NLP. In the line of language analysis: can we actually expect to understand language ability without a formalized progression in that understanding? As we have complexities hierarchies to analyse problems and algorithms, it would be useful a reference formalized basis to compare natural languages. 1.2 What are languages for? This should be the first question to approach language problem. What is the utility of languages? There is no agreement among expert about how the language ability is 5 2.2 Formal description •A finite one dimensional tape with size ldivided into cells (possibles positions) identified by a natural number (1,2,3, ..., l)so that the first cell is at the right of the last cell, forming a ring of cells. •A set Eof mentities (agents) E=e1, e2, ..., emdefinedas follows  ei= (ρi,t, ni,Ωi,t, σi,t, δi,t, Mi)where ∗ρi,t is eicell position (1 or 2,...or l) at iteration t.ρi,t 6=ρj,t, i 6=j, two entities cannot share cell. ∗niis an identification number. This number can or cannot be the same that entities index (e1could have ni= 2) and are not assigned in order necessarily. ∗Ωi,t = (αi,t, βi,t)is the representation of the world known by ei.αi,t and βi,t are vectors with the world information eihas gathered till iteration t. ∗σi,t = [(φi,t,k, oi,t,k)] is a list of pairs of coming into sentences (φi,t,k) and the side it comes from (oi,t,k) at iteration t. ∗δi,t is the distance between eiand the previous entity in the tape at iteration t. ∗Miis entity’s model of behavior. Mi=Mj∀i, j if all entities share the same model of behavior. •A language (L) whose syntax, lexicon and interpretation is known by all entities. •A cut distance (C) as dissimilarity reference. •Each entity eiat iteration tis able to:  ”observe”: To know the distance between it and entity at its left in ring δi,t.  ”move”: To change its position for the position at its left if that cell is empty. ρi,t+1 ←ρi,t −1⇔ρi,t 6= 1, ρj,t 6=ρi,t −1∀j1≤j≤m ρi,t+1 ←l⇔ρi,t = 1, ρj,t 6=l∀j1≤j≤m  ”say to previous or next entity”: To assign previous or back entity input sentence list a sentence made with Lby ei.  “listen”: To interpret and extract information from σi,t to Ωi. •Each iteration of the problem implies an action turn for each entity. •The final absolute positions of entities have no relevance, only final adjacency of entities matter. •Index number is not known by entities (i.e. e1does not know its index is 1). •Cis known by all entities. 12 •The interpretation from each sentence φi,t,k must defined only by the sentence itself, speaker oi,t,k and receiver previous information Ωi. •Clustering result would be A(E, [ρ1,t, ..., ρm,t]) with tas final iteration and Adefined below. Figure 4: Ring tape example We will define function ∆as distance between two cells b1and b2in ring: ∆(b1, b2) = min(b2−b1, l −b2+b1)b1≤b2 min(b1−b2, l −b1+b2)b2< b1 (1) Given an entities set E, a position vector pand Pas power set, adjacency clustering would be a function A(E, p) = Swhere ∀cz∈S, cz⊆Eand defined as follows: A(E, p) = ∀cz∈P(E)− {∅}, cz∈S iff (2) •An entity with no entities in its sides cells. czis a cluster formed by an only entity. |cz|= 1, ei∈cz,∀ej∈E, i 6=j, ∆(p(i), p(j)) >1 Figure 5: {em−1},{em},{e1},{e2},{e3} ∈ S 13 •There are two entities in czand distance between them is 1. czis a cluster formed by two entities. czis not in a greater cluster cy. ∀eiej∈cz, i 6=j, ∆(p(i), p(j)) = 1,∀cy∈S/cz6=cy:cz*cy Figure 6: {em−1, em},{e1, e2} ∈ S •There are two entities in cz, the distance between them is greater than 1 and cells between them are filled by other entities. czis a cluster with more than 2 consecutive entities.czis not in a greater cluster cy. ∀eiej∈cz, i < j, ∆(p(i), p(j)) >2,∀k/i ≤k≤j:ek∈cz ∀cy∈S/cz6=cy:cz*cy Figure 7: {em−1, em},{e1, e2, e3} ∈ S •There are at least two entities in cz, the distance between them is greater than 1 and cells between them are filled by other entities. czis a cluster with consecutive entities at ring end and ring beginning. czis not in a greater cluster cy. ∀eiej∈cz, i < j, ∆(p(i), p(j)) >2,∀k/i ≤k≤m or 1≤k≤j, ek∈cz ∀cy∈S/cz6=cy:cz*cy Figure 8: {em, e1, e2}/∈S since {em−1, em, e1, e2, e3} ∈ S 14 To simplify, we will establish the next equalities: pi=ρi,1,eioriginal position. p= [p1, ..., pm], original positions vector. di=δi,1, original distance between eiand its previous entity position. d= [di, ..., dm], orginal distances vector. The objective is the performing of a clustering problem by entities from an initial distribution of them in the ring through joining them with only the cut distance as external information and by means of using Lto share the partial information that each eiknows. The complexity of the language should allow a better or a worse result in the task. We will discuss some subjects about the proposed problem: Does the absolute positions really matter? No. As we have defined, the final absolute positions of entities has no relevance, only adjacency has. If we have a ring with mentities with a determined distribution, the only information these entities have and share is about distance between them and their own identification. They only can know its relative position in relation to other entities and final adjacency would be the same if we move all entities a random number of positions left or right because relative positions would remain the same. dand not pis what really defines the initial configuration. From p,dis infered. Is a limitation to allow only movement in one direction? Actually, there is no need to allow a two-direction movement, so it is a matter of simplicity. Suppose a ring with mentities. If eimoves to right in the ring (assuming the cell at its right is empty), its position would be change to ρi,t + 1 (or 1 if ρi,t =l, we will explain the example with an entity is not at extreme cells or extreme index for simplicity) . Applying what we defined previously, what matter is δi,t+1 would have been increased by 1 with respect to δi,t and δi+1,t+1 would have been decreased by 1 with respect to δi+1,t. It would be exactly the same if all entities but eimoves to left so, to move to right e1only has to make all other entities move to left by mean of the language. Of course, it would be required a more complex language to achieve the same with a one-directional movement but in this case, that is an interesting feature in problem since the objective is to test languages. Is actually necessary to allow two-side communication? We allow entities to share information with the entity at its left and its right. It would be simpler to allow only one-side communication but it would imply an important problem: suppose the same problem previously defined but with only one-side communication (i.e: each entity can exclusively “say” sentences to the entity as his right). Information gathering by each entity would be highly limited to one side (opposite to the side he speaks, left in this example) until the information would go over all the ring. So, for example, to know the information from its right, this information should came from left and the entity should be able to recognise it as information from its right. With no information from one side, the ability to perform a clustering task is very limited (absence of comparison) 15 so the entity wouldn’t know if move or not. To have information from two sides would imply a language complex enough to gather information from the whole world and it could limit problem utility to observe differences between languages below that point of complexity. Is actually necessary for entities to know cut distance (C)? Clustering problem can be approached by two main sides: the first is to define the number of clusters we want to obtain (usually referred as classification, k-means algorithm would be the better example) and the second is to define a cut distance to demarcate the maximum similarity between two elements in the same cluster (with hierarchical clustering algorithm as great example). The selection of a cut distance over a number of objective clusters is not random. To classify a set of entities in kclusters there must be at least kentities or the problem has not sense, so the value kimplies more external information about the world than C. Other option would be to use an optimization index to minimize (like Davies-Bouldin Index, for example), this would change an absolute number by an equation to optimize. It would move our problem away from classical clustering approaches like well-studied hierarchical and k-means clustering, so we could use none of them as reference. This would complicate both programming and evaluation with no apparent language analysis improvement so it has been rejected. Is truly important the lexicon? No. As we discussed previously, lexicon is a vital part of a language (without words, it would be no spoken or written language) but it is arbitrary. 16 2.3 Simulations approach Our aim is to show how, by changing L, the resolution of the clustering problem can be improved. This is a bit ambiguous objective since given a clustering problem there is no absolute “best” clustering. Differents algorithms with differents distance functions and differing cut distances would produce differing results. So, our strategy will be to use a reference clustering algorithm to emulate its results. We will define four increasing complexity languages (L), each one of them with an associated entities behaviour model (M). These behaviours will be focused on the utilization of information gained by the use of language. Through this, we will focus outcome improvements on language capacity to observe each language possibilities. Each model will try to create the closest mental image to the original tape and then perform reference clustering algorithm by itself to deduce what other entities must be in its same cluster and use that information to know if move or not. 2.3.1 Evaluation Each cluster cis a set of entities and there are mentities, so we can describe a bijective function between each cluster can a vector vwith mbinary positions with v(i)=1⇔ei∈cand v(i) = 0 ⇔ei/∈c. In example, with m= 5 entities in ring, c={e1, e3, e4},v= [1,0,1,1,0]. Given two clusters c1and c2formed by entities and equivalent to vectors v1and v2 respectively, we’ll use as distance between c1and c2the well known Hamming distance: H(c1, c2) = X v1(i)6=v2(i) 1≡ |c1∪c2|−|c1∩c2|=|c1|+|c2| − 2|c1∩c2| (3) Given two set of clusters S1and S2over the same total entities Ewith |E|=m, distance function Has defined previously and function min as the usual minimum function, we will define the distance between S1and S2as follows: D(S1, S2) = X c1∈S1 min c2∈S2 (H(c1, c2)) + X c2∈S2 min c1∈S1 (H(c2, c1)) (4) Function Dis minimal Hamming distance for each cluster from S1over S2plus vice versa. 17 Extreme cases: 0< D(S1, S2)<(m+ 1)(m−1) (5) I) Sets are entirely different: S1contains an unique cluster with all entities: c1∈S1, c1=E, |S1|= 1 S1contains mclusters, each one with an unique entity: ∀e∈E, {e} ∈ S2,|S2|=m D(S1, S2)=(m−1) + m(m−1) = (m+ 1)(m−1) (6) Since ∀c2∈S2, c2⊆c1,|c2|= 1 ⇒H(c1, c2) = H(c2, c1) = m−1 X c1∈S1 min c2∈S2 (H(c1, c2)) = min c2∈S2 (H(c1, c2)) = m−1 (7) And X c2∈S2 min c1∈S1 (H(c2, c1)) = X c2∈S2 m−1 = m(m−1) (8) II) Sets are the same: S1=S2⇒ ∀c1∈S1, c1∈S2,∀c2∈S2, c2∈S1⇒D(S1, S2)=0 (9) Example: S1={{e1, e2},{e3, e4},{e5, e6}} S2={{e1, e2, e3, e4},{e5, e6}} D(S1, S2) = (2 + 2 + 0) + (2 + 0) = 6 Given proposed clustering problem, original positions vector p, cut distance C, language L, behavior model M, function Dand reference clustering algorithm R. With S1as Rclustering result applied to pand Cand S2as proposed clustering problem result applied with with p,C,Mand L. The evaluation of S2respect to S1would be D(S1, S2)so the lower, the better Land Mcombination. Another option we will use is to evaluate the contrast between possibles clusters set is to suppose a third cluster set S3as the result of adjacency clusters Aapplied to p(the result if Mis simply to do not move). S3would be the initial point and implies an adjacency clustering that could be even better than S2since Mcould break formed from the beginning clusters. This evaluation would be D(S1, S3)−D(S1, S2)and it represents how has Mimproved clustering in relation to original distribution p. 18 As reference algorithm Rto clustering performing by entities and compare results has been chosen classical agglomerative hierarchical clustering algorithm (AHC from now on). In this algorithm, from a m-sized positions vector p, a ring size land a cut distance C, we start with mclusters (each entity is a cluster initially) and construct iteratively greater clusters by joining clusters whose distances are lower than C(Hastie et al. 2008). As similarity function we will use the distance between clusters centroids. It is important to consider that position lis just next to position 1 and the distance between them are 1, as the distance between position l−1and 1 is 3 and so on. Given two centroids c1and c2distance between centroids in a ring is previously defined function ∆. 2.4 Model designing general approach All these algorithms but the first one (this will be explained in his own section) will have an associated language to use and will follow the same general scheme to perform clustering task. Each entity commence with empty mental imagen Ωi,1and its objective is to get the mental image nearest to original vector position pthrough the sharing of distances. To achieve that, they follow the next phases: •Information exchange: when entity eiuses language to obtain and distribute information in order to add information to its own mental image as much as help other entities to do the same. •Information use: entity eiuses gathered information to decide if it should move or not. To perform this task, entity will apply the same clustering algorithm to its mental image of the world that will be used to compare the final result (AHC, as we have explained previously). •Movement: eimoves or not according to previous phase information process. During information exchange phase, eiwill propagate information about last entity at its front it knows to its back and information about last entity at its back it knows to its front. The inflection point change from the first phase to the second is what we call enough information evaluation that is, as sais its own name, an evaluation made by each entity to decide if it has enough information to decide if moves. 19 2.5 Model 1: Without a language The first stage of language to resolve the problem must be the absence of any kind of communication. In this stage, entities will only gather information by observation so the only information each of them are able to gather is the distance between them and the entity at its left (δi). This algorithm is not able to follow the general scheme we previously talk of because entities can not perform the first phase beyond gather the information they directly can “see”. So, entity must work only with the distance between it, the one at its left and cut distance (C). Mental image will be only the last observation and the number of steps it has advanced to know how far it is from its initial position. Ωi,t = ([δi,t], k) Model 1 for each eiat iteration tacts as follows: Figure 9: Model 1 owchart 20 Example: As can be seen, each entity will move only if the entity it can see is in range of C from its original position. Given position vector p= [1,3,4,7,9] with cut distance C= 4 and ring length 10, the system would evolve as follows: Table I: Model 1 evolution example t ρ1,t δ1,t ρ2,t δ2,t ρ3,t δ3,t ρ4,t δ4,t ρ5,t δ5,t 1 1 2 3 2 4 1 7 3 9 2 2 10 2 2 2 4 2 6 2 8 2 3 9 2 1 2 3 2 5 2 7 2 4 9 2 1 2 2 1 5 3 7 2 At third iteration only e4moves since its previous position is at distance 2 and it has only stepped once. At fourth iteration no one should move so it is final iteration. Model relevant details: •No information exchange. •Ensures finalization 21 ally have any information that indicates when they are repeating once and again the same. For that reason. To know if they have enough information to stop gathering and start using it is a complex matter. Using this language, entities are not able to gather information to know absolute references. It could be used an statistical approach and observe patterns repetitions to estimate a confidence threshold. We have prefered to evade an stochastic approach so we will not look for patterns due this not provide absolutely reliable information and it does not focus on language. Is impossible to create a language with given restrictions to allow enough information exchange to avoid this problem? No. It is actually possible to create a language like that, the following is an example: S→D n with nas a natural number. S→I n with nas a natural number. D→fd D with fd as word referring to front entity distance. D→fd with fd as word referring to front entity distance. D→bd D with bd as word referring back entity distance. D→bd with bd as word referring back entity distance. I→fi I with fi as word referring to front entity identification. I→fi with fi as word referring to front entity identification. I→bi I with bi as word referring back entity identification. I→bi with bi as word referring back entity identification. I→mwith mas word referring itself identification. With frontdistance as fd,backdistance as bd,frontidentification as fi,backidentification as bi,me as m, the following pair (φi,t,k, oi,t,k)interpretation by ei: (frontdistance n, back)⇒ri,i+1 =n≡di+1 =nby (v). (frontdistance n, front)⇒ri−1,i−2=n≡di−1=nby (v). (backdistance n, back)⇒ri+1,i+2 =n≡di+2 =nby (v). (backdistance n, front)⇒ri−1,i =n≡di=nby (v). This use has not sense since ei gathers directly di. (frontdistance P n, back)⇒ri+1,j−1=nwith (P n, front)⇒ri−1,j =n. (frontdistance P n, front)⇒ri−1,j−1=nwith (P n, front)⇒ri−1,j =n. (backdistance P n, back)⇒ri+1,j+1 =nwith (P n, back)⇒ri+1,j =n. (backdistance P n, front)⇒ri−1,j+1 =nwith (P n, back)⇒ri+1,j =n. (frontidentification P n, back)⇒ni=nThis use has not much sense since ei knows ni. (frontidentification P n, front)⇒ni−2=n. (backidentification P n, back)⇒ni+2 =n. (backidentification P n, front)⇒ni=nThis use has not much sense since ei knows ni. (frontidentification P n, L)⇒nj−1=nwith (P n, L)⇒nj=n. (backidentification P n, L)⇒nj+1 =nwith (P n, L)⇒nj=n (me n, front)⇒ni−1=n. (me n, back)⇒ni+1 =n. 28 With a language like that, an entity is able to exchange information about distance as well as about identification. By knowing entities identifications, entities can perform a match between what is in front of them and at their back and mount a complete ring image. We will expose in detail how this information can be used in the next stage. In this stage, we will not use this kind of language due to its expansion problem. The “trick” of joining in a lexical element two semantic elements as “who” is related to the information we receive (pronouns) and “what” is that information meaning, is not acceptable if we want to expand a language efficiently. It implies the necessity of a lexical element for each pronoun-meaning combination. For example, if we have xpronouns elements and ypossible meanings for a number n, we would need x∗y lexical elements. This supports language meaning on lexicon much more than on syntax. Although from a theoretical point of view, this would be acceptable, this is not the natural evolve way and it confront one of our objectives: efficiently, since it grows disproportionality in space. In that language there is a lot of redundant information. A sentence would be, for example, like the following: frontidentification frontidentification frontidentification 4. In that sentence is repeated three times 4 has indentification meaning, so there is not only a problem with lexico size, also a redundancy problem. We should note that, frontidentification could seem an easy to remember word since it is a composed word but words are arbitrary signs. We chose composed words to simplify remember its meaning for the example. Model relevant details: •Complete information exchange about distances, no information exchange about identification. •With Cgreater than all di, it starts an infinite exchange information loop and need and extra iteration limit to avoid it. •Once information exchange has finished, it does not ensure finalization since it is teorically possible all entities tries to reach the previous one. •Its erroneos information gathering affects mental image vector and can lead ei to incorrect conclusions. 29 2.8 Model 4: With language formed by pronouns, verbs and numbers Language syntax is like follows: S→A B n with nas a natural number. A→f A with fas a word referring to front (pronoun). A→fwith fas a word referring to front (pronoun). A→b A with bas word referrig to back (pronoun). A→bwith bas a word referring to back (pronoun). A→mwith m as word referring to the entity itself (pronoun). B→dwith das a word referring to distance (verb). B→iwith i as a word referring to identification (verb). The word me will be used as m,identification as iand distance as d. With the following pair (φi,t,k, oi,t,k)interpretation by ei: (front distance n, back)⇒ri,i+1 =n≡di+1 =nby (v). (front distance n, front)⇒ri−1,i−2=n≡di−1=nby (v). (back distance n, back)⇒ri+1,i+2 =n≡di+2 =nby (v). (back distance n, front)⇒ri−1,i =n≡di=nby (v). This use has not much sense since eigathers directly di. (me distance n, back)is not defined. (me distance n, front)is not defined. (front identification n, back)⇒ni=nThis use has not sense since eiknows ni. (front identification n, front)⇒ni−2=n. (back identication n, back)⇒ni+2 =n. (back identification n, front)⇒ni=n. This use has not sense since eigathers directly ni. (me identification n, back)⇒ni−1=n. (me identification n, front)⇒ni+1 =n. (front P n, back)⇒ri+1,j−1=nwith (P n, back)⇒ri+1,j. (front P n, front)⇒ri−1,j−1=nwith (P n, front)⇒ri−1,j. (back P n, back)⇒ri+1,j+1 =nwith (P n, back)⇒ri+1,j. (back P n, front)⇒ri−1,j+1 =nwith (P n, front)⇒ri−1,j. (front P n, L)⇒nj−1=nwith (P n, L)⇒nj=n. (back P n, L)⇒nj+1 =nwith (P n, L)⇒nj=n. 30 Model 4 eimental image at iteration t= 2n+ 1, n ∈Nwith mentities in ring: Ωi,t = (αi,t, βi,t) αi,t =dk+1 nq+1min(k), k ≡i−a−1 (mod m) min(q), q ≡k−1 (mod m)a= 0, ..., min(n, m 2)m≡0 (mod 2) a= 0, ..., min(n, m+1 2)m≡1 (mod 2) βi,t =dk+1 nk+1min(k), k ≡i+a−1 (mod m)a= 1, ..., min(n, m 2)m≡0 (mod 2) a= 1, ..., min(n, m+1 2)m≡1 (mod 2) Note Model 4 mental images are defined only with odds tgreater than 1. It is because of each eialternates the sending of distance and identification information so there are twhere there is no njexchange and it is useless to cross data. Guess a ring defined by the following vector of positions p= [1,5] and ring size l= 9 . With t= 3,d1= 5,d2= 4,n1= 15 and n2= 23, mental images would be like follows: Ω1,3= (5 4 23 15,4 23) Ω2,3= (4 5 15 23,5 15) So each eihave enough information to look for a common njin αi,3and βi,3. That is enough information to deduce there is a ring and implies knowledge about all original distances in vector d. From vector dis trivial to obtain ring size l. When eireach this point, it will process surplus information in Ωi,t (delete columns on αi,t or βi,t with repeated ni,j). With αiand βias distances vectors with no repeated information and aas αilength and bas βilength they would create a deduced positions vector viin a lsize ring like this: vi=−1ui,1(1) + 1 + [ui,1,0, ui,2] ∀k∈1, .., a :ui,1(k) = −1 a−k+1 P j=1 αi(j),∀k∈1, .., b :ui,2(k) = k P j=1 βi(k) So, in previous example, with α1= [5],β1= [],α2= [4],β1= []: v1= 6 + [−5,0] = [1,5] v2= 5 + [−4,0] = [1,6] Note that v1represent the same relative distances in a l= 9 size ring than v2, so, both are correct but subjectives to eioriginal relative position. 31 The algorithm for each eiacts as follows: Figure 12: Model 4 owchart Model 4 will rely on identify a common entity in αi,t and βi,t as explained previously. An example: Guess a ring defined by the following vector of positions p= [1,4] and ring length l= 5,n1= 1 and n2= 2. From e1(position 1) point of view, iis its index so di= 2. From e2(position 4) point of view, jis its index so dj= 3. 32 The evolution of their information step by step would be like follows: Table III: Model 4 evolution example Action e1knows e1says to e2e2knows e2says to e1 They observe and share information. di= 2, ni= 1 (front distance 2,front),(front distance 2,back) dj= 3, nj= 2 (front distance 3,front),(front distance 3,back) They process received information and share identification information. di= 2, ni= 1, di+1 = 3, di−1= 3 (me identification 1,front),(me identification 1,back) dj= 3, nj= 2, dj+1 = 2, dj−1= 2 (me identification 2,front),(me identification 2,back) They process information and cross it. di= 2, ni= 1, di+1 =3= di−1, ni+1 = 2 = ni−1, - dj= 3, nj= 2, dj+1 = 2 = dj−1, nj−1= 2 = nj+1 - Now, each entity has a correct ring mental image and it has been avoided Model 3 Ant Mill problem previously commented. Model relevant details: •Complete information exchange about distances and identifications. •No exchange information infinite loop. •Once information exchange has finished, it does not ensure finalization since is teorically possible all entities tries to reach the previous one. •Each eimental image is subjetive so two differents entities could infer differents clusters. 33 3 Experiments 3.1 Experiments Details We will use Fisher’s iris flower data set to perform our experiments. Specifically vector sepal length (usually first column from data set) rounded (distances must be naturals) as initial distance vector d. d(i) = round(iris(i, 1)), i = 1, ..., 150 l= 150 P i=1 d(i) = 886 Since no model ensures finalization, we have chosen t= 3lwith las ring size as top iteration limit. Model 3 exchange information iteration limit has been defined as T= 1.5l. Since results change with dissimilarity value (cut distance C), we will apply each model from C= 5 to C= 150 with an incrementation of 5. It is important to note that all distances in this vector are lower than 8 since this will affect model 2 performance and it implies model 3 will need given Tfor all but the first test. d(i)<8, i = 1, ..., 150 Project implementation was made with GNU Octave over an Ubuntu 16.04 LTS 64-bits operating system. Computer CPU is intel Core i5-6300HQ, 2.30GHz four cores. As code editor has been used Sublime-Text 2 and as code repository was used Mercurial-Bitbucket combination to milestone saves, Mercurial as code repository manager and Bitbucket as repository cloud manager. It was also used Dropbox as constant cloud backup. Initial implementation strategy was to implement literally all languages and compute each information exchange. It was too slow (thousands of sentences to create, exchange and parse...) so final approach has been to avoid all literal language implementation. With Ωi,t evolution defined for each model and known how final Ωi,t is transformed to be processed as was discussed in corresponding sections, it has been much simplier to create directly transformed vectors working only pure information vectors and matrix. 34 Figure 13: Execution times with C from 5 to 150 Model 1 execution times increase linearly from 0.05 to 1.58 seconds. Model 2 only finishes with three first Cvalues, from that point on, Model 2 times have little variations and are close to 27 seconds. Model 3, as could be expected, is the slowest model. With C= 5, Model 3 does not requires to use top limit exchange information limit Tbut, from that point on, times increase abruptly to increase slowly from C= 45 on. Model 4 begins with the higher time but it reaches stability (close to 44 seconds) from C= 70 on. Model 1, 3 and 4 processes ends without reach top iteration limit in all cases. There are two main code bottle necks: The first bottle neck is to create information vectors for each entity to be processed. Basically, it consists in matrix manipulations and additions so it could be interesting to study if the use of a many-core focus language (like CUDA to use nVidia GPU) could improve performance. The second bottle neck is information processing. Agglomerative hierarchical cluster is applied to vector infered from each Ωi,t for each model but 1. So, in the worst case (Model 3) as with Fisher’s iris data set there are 150 entities (or agents), hierarchical clustering is applied 150 times. Ring size lis equal to 886. Due to model 3 explained Ant Mill problem, and established iteration top limit T= 1.5l, each entity ends with a 1.5∗886 ∗2 = 2658 length associated mental image vector (each iteration entity receives information from left and right). So, with that model, there are 150 vectors with 2658 positions each one to apply hierarchical algorithm. Those 150 35 vectors are very similar (each one is the previous desplaced one position) so there are many calculations repeated. The creation of a hierarchical clustering algorithm to compute clustering to many vectors simultaneous with this conditions could improve speed notably. 3.2 Results Given S1,S2,S3and S4as adjacency clusters set results from Model 1, Model 2, Model 3 and Model 4 respectively, SAHC as cluster set result from reference algorithm Agglomerative Hierarchical Clustering and S0as function Aaplied to initial position vector p. First we will show total distance Dbetween each model cluster set Siand reference cluster set SAHC (the lowest, the better since shows distance to reference). Figure 14: D(Si, SACH ) with C from 5 to 150 Next, we will show how evolves the difference between previously showed values and base value D(S0, SACH )so it will be much more intuitive how good has been each model in improving adjacency clustering result from original position padjacency. This time the higher value the better since it shows the improvement regarding to do nothing. 36 Figure 15: D(S0, SAHC)−D(Si, SAHC) with C from 5 to 150 Model 1 shows a simple behavior based only in observation with no information exchange efectiveness. Model 2 shows how a language with a limited information exchange about a part of the problem based on a syntax that allows raw data with no context is worst than the simplest observation and, as we can see in figure 15, it shows results similars to do nothing for most C. Model 3 shows how a language that allows complete information exchange about a part of problem (it exchange all information about djbut no information about nj) based on a SO (Subject, Object) syntax structure, has obviously better results. As figure 14 shows, outcome clusterings are equals or near to those from reference algorithm. We can not forget this model has needed an extra data to limit information exchange iterations (T) to avoid an infinite loop for any tested Cbut C= 5 and his execution times are the worst as figure 13 shows. Model 4 shows how a language that allows the information exchange about two parts of problem (it allow djand njexchange) based on a SVO (Subject, Verb, Object) syntax structure has restuls similars to model 3. It is important to note that, unlike model 3, model 4 does not requiere a given exchange information iteration limitation. All this supports language with basic Subject, Verb and Object syntax structure utilization to face proposed problem. 37 7 Appendix A: Implementation Details Main code files provided with this project are: [ f i n a l p o s i t i o n s , f i n a l c l u s t e r s e t ] = r ing clus teri ngre duce d ( model , nent i t y , cutdistance , positions , ring len gth , boolshow ) This function is the code to perform proposed clustering as model defines. Function uses four matrix (F,Fid ,B,Bid) as entities mental image vector so each Ωi,t is equivalent to combination of irows from each matrix at iteration t.Fand Bare used to contain front and fack distances and Fid and Bid to contain front and back identifications. finalpositions -> Natural numbers vector. Final entities positions. finalclusterset -> Natural numbers matrix. Cluster set defined by finalpositions as defined in project. Clusters are provided as numbers pairs [a, b]in each row. ais cluster beginning and bcluster final. If b < a, cluster includes from ato nentity and from 1 to b. model -> Natural number from 1 to 4. Model to use M. nentity -> Natural number. Number of entities. Used only if it is not provided an initial positions vector to obtain a vector based in prime numbers. cutdistance -> Natural number. Dissimilarity value, cut distance C. positions -> Not empty natural numbers vector. Originals entities positions to use in problem p. ringlength -> Natural number. Ring size l. boolshow -> Boolean. True to show each iteration evolution. Used mainly for debugging tasks. value = evaluateclusteringwithhammingdistance ( clusterset1 , cl uste rse t 2 , el ementstocluster ) Function to evaluate the distance between two cluster with elementstocluster as number of elements in clustering. Function Dimplementation. Clusters from the sames set must be disjunct. value -> Natural number. clusterset1-> Natural numbers matrix. Clusters are provided as numbers pairs [a, b] in each row. ais cluster beginning and bcluster final. If b < a, cluster includes from a to nentity and from 1 to b. cluserset2-> Natural numbers matrix. Clusters are provided as numbers pairs [a, b]in each row. ais cluster beginning and bcluster final. If b < a, cluster includes from ato nentity and from 1 to b. numberstocluster -> Natural number greater than 0. 44 c l u s t e r s e t = h i e r a r c h i c a l c l u s t e r i n g ( ve c t orpo s i tio n s , cutdistance , ringlength) Function to perform agglomerative hierarchical clustering over a vector keeping in mind it is peformed over a ring with ringlength size. clusterset -> Natural numbers matrix. Clusters are provided as numbers pairs [a, b] in each row. ais cluster beginning and bcluster final. If b < a, cluster includes from a to nentity and from 1 to b. vectorpositions -> natural number vector. Positions vector to perform clustering. cutdistance -> Natural number. Dissimilarity value, cut distance C. elementstocluster -> Natural number. Total number of entities in clusters. ringlength -> Natural number. Ring size. If 0, function will act as if there is no ring so, last position in vectorpositions is not next to first one. move = p ro ces si nfo rmatio n1 ( c l u s t e r s e t , mentalimagepositionvector , e n t i t y p o s i t i o n i n d e x , r i n gl e n g th ) Function to infer if an entity must move or not from a set of clusters, a vector representing entity’s image of the world, its position in that world and ring size. Entity should move if it is not the first in his assigned cluster or if, being the first and having all his cluster partners nearest as is possible, there is no space between its cluster and the next. If ringlength is greater than 1 and there is an only cluster, function should not move if is the entity with greater distance between it and the previously. This avoid an infinite loop when performing clustering. If all entities are in the same cluster, no on is the first, so no one would be motionless. move -> Boolean value. True/1 if entity must move. False/2 if entity must keep its position. clusterset -> Natural numbers matrix. Clusters are provided as numbers pairs [a, b]in each row. ais cluster beginning and bcluster final. If b < a, cluster includes from ato nentity and from 1 to b. mentalimagepositionvector -> Natural numbers vector. It represents how the entity thinks the world is. entitypositionindex -> Natural number greater than 0. It represents entity’s index in mentalimagepositionvector. ringlength -> Natural number. It represesnts how long entity thinks ring is. If 0, it is not kept in mind ring shape so, last position in mentalimagepositionvector is not treated as next to first and vice versa. 45