Tag Archives: coordination

Items of some interest:

Posted on by

These are my recent Pin​board​.in links:

  • [1206.6866] Sto­chas­tic Opti­mal Con­trol in Con­tin­u­ous Space-​​Time Multi-​​Agent Systems

    “Recently, a the­ory for sto­chas­tic opti­mal con­trol in non-​​linear dynam­i­cal sys­tems in con­tin­u­ous space-​​time has been devel­oped (Kap­pen, 2005). We apply this the­ory to col­lab­o­ra­tive multi-​​agent sys­tems. The agents evolve accord­ing to a given non-​​linear dynam­ics with addi­tive Wiener noise. Each agent can con­trol its own dynam­ics. The goal is to min­i­mize the accu­mu­lated joint cost, which con­sists of a state depen­dent term and a term that is qua­dratic in the con­trol. We focus on sys­tems of non-​​interacting agents that have to dis­trib­ute them­selves opti­mally over a num­ber of tar­gets, given a set of end-​​costs for the dif­fer­ent pos­si­ble agent-​​target com­bi­na­tions. We show that opti­mal con­trol is the com­bi­na­to­r­ial sum of inde­pen­dent single-​​agent single-​​target opti­mal con­trols weighted by a fac­tor pro­por­tional to the end-​​costs of the dif­fer­ent com­bi­na­tions. Thus, multi-​​agent con­trol is related to a stan­dard graph­i­cal model infer­ence prob­lem. The addi­tional com­pu­ta­tional cost com­pared to single-​​agent con­trol is expo­nen­tial in the tree-​​width of the graph spec­i­fy­ing the com­bi­na­to­r­ial sum times the num­ber of tar­gets. We illus­trate the result by sim­u­la­tions of sys­tems with up to 42 agents.”

    coor­di­na­tion agent-​​based emergent-​​design nudge-​​targets control-​​theory

  • [1205.6917] Robust self-​​triggered coor­di­na­tion with ternary controllers

    “This paper regards coor­di­na­tion of net­worked sys­tems, which is stud­ied in the frame­work of hybrid dynam­i­cal sys­tems. We design a coor­di­na­tion scheme which com­bines the use of ternary con­trollers with a self-​​triggered com­mu­ni­ca­tion pol­icy. The com­mu­ni­ca­tion pol­icy requires the agents to col­lect, at each sam­pling time, rel­a­tive mea­sure­ments of their neigh­bors’ states: the col­lected infor­ma­tion is then used to update the con­trol and deter­mine the fol­low­ing sam­pling time. We prove that the pro­posed scheme ensures finite-​​time con­ver­gence to a neigh­bor­hood of a con­sen­sus state. We then study the robust­ness of the pro­posed self-​​triggered coor­di­na­tion sys­tem with respect to skews in the agents’ local clocks, to delays, and to lim­ited pre­ci­sion in com­mu­ni­ca­tion. Fur­ther­more, we present two sig­nif­i­cant vari­a­tions of our scheme. First, we design a time-​​varying con­troller which asymp­tot­i­cally dri­ves the sys­tem to con­sen­sus. Sec­ond, we adapt our frame­work to a com­mu­ni­ca­tion model in which an agent does not poll all its neigh­bors simul­ta­ne­ously, but sin­gle neigh­bors instead. This com­mu­ni­ca­tion pol­icy actu­ally leads to a self-​​triggered “gos­sip” coor­di­na­tion system.”

    network-​​theory multi-​​agent-​​systems mechanism-​​design emergent-​​design consensus-​​systems nudge-​​targets algo­rithms

  • [1205.2607] Simulation-​​Based Game The­o­retic Analy­sis of Key­word Auc­tions with Low-​​Dimensional Bid­ding Strategies

    “We per­form a simulation-​​based analy­sis of key­word auc­tions mod­eled as one-​​shot games of incom­plete infor­ma­tion to study a series of mech­a­nism design ques­tions. Our first ques­tion addresses the degree to which incen­tive com­pat­i­bil­ity fails in gen­er­al­ized second-​​price (GSP) auc­tions. Our results sug­gest that sin­cere bid­ding in GSP auc­tions is a strik­ingly poor strat­egy and a poor pre­dic­tor of equi­lib­rium out­comes. We next show that the rank-​​by-​​revenue mech­a­nism is wel­fare opti­mal, cor­rob­o­rat­ing past results. Finally, we ana­lyze profit as a func­tion of auc­tion mech­a­nism under a series of alter­na­tive set­tings. Our con­clu­sions coin­cide with those of Lahaie and Pen­nock [2007] when val­ues and qual­ity scores are strongly pos­i­tively cor­re­lated: in such a case, rank-​​by-​​bid rules are clearly supe­rior. We diverge, how­ever, in show­ing that auc­tions that put lit­tle weight on qual­ity scores almost uni­ver­sally dom­i­nate the pure rank-​​by-​​revenue scheme.”

    game-​​theory agent-​​based sim­u­la­tion eco­nom­ics auc­tion nudge-​​targets

  • Graph­ing the his­tory of phi­los­o­phy « Drunks&Lampposts

    “Each philoso­pher is a node in the net­work and the lines between them (or edges in the ter­mi­nol­ogy of graph the­ory) rep­re­sents lines of influ­ence. The node and text are sized accord­ing to the num­ber of con­nec­tions (both in and out). The algo­rithm that visu­alises the graph also tends to put the bet­ter con­nected nodes in the cen­tre of the dia­gram so we see the most influ­en­tial philoso­phers, in large text, clus­tered in the cen­tre. It all seems about right with the major fig­ures in the west­ern philo­soph­i­cal tra­di­tion tak­ing the cen­tre stage. (I need to also add the direc­tion of influ­ence with a arrow head – some­thing I’ve not got round to yet.) A short­com­ing how­ever is that this eval­u­a­tion only takes into account direct lines of influ­ence. Indi­rect influ­ence via another per­son in the net­work does not enter into it. This prob­a­bly explains why Descartes is smaller than you’d think. It would also be bet­ter if the nodes were sized only by the num­ber of out­ward con­nec­tions although I think over­all the dif­fer­ences would be slight. I’ll get round to that.”

    visu­al­iza­tion philosopher-​​mining

  • [1206.3666] Unsu­per­vised adap­ta­tion of brain machine inter­face decoders

    “The per­for­mance of neural decoders can degrade over time due to non­sta­tion­ar­i­ties in the rela­tion­ship between neu­ronal activ­ity and behav­ior. In this case, brain-​​machine inter­faces (BMI) require adap­ta­tion of their decoders to main­tain high per­for­mance across time. One way to achieve this is by use of peri­od­i­cal cal­i­bra­tion phases, dur­ing which the BMI sys­tem (or an exter­nal human demon­stra­tor) instructs the user to per­form cer­tain move­ments or behav­iors. This approach has two dis­ad­van­tages: (i) cal­i­bra­tion phases inter­rupt the autonomous oper­a­tion of the BMI and (ii) between two cal­i­bra­tion phases the BMI per­for­mance might not be sta­ble but con­tin­u­ously decrease. A bet­ter alter­na­tive would be that the BMI decoder is able to con­tin­u­ously adapt in an unsu­per­vised man­ner dur­ing autonomous BMI oper­a­tion, i.e. with­out know­ing the move­ment inten­tions of the user. In the present arti­cle, we present an effi­cient method for such unsu­per­vised train­ing of BMI sys­tems for con­tin­u­ous move­ment con­trol. The pro­posed method uti­lizes a cost func­tion derived from neu­ronal record­ings, which guides a learn­ing algo­rithm to eval­u­ate the decod­ing para­me­ters. We ver­ify the per­for­mance of our adap­tive method by sim­u­lat­ing a BMI user with an opti­mal feed­back con­trol model and its inter­ac­tion with our adap­tive BMI decoder. The sim­u­la­tion results show that the cost func­tion and the algo­rithm yield fast and pre­cise tra­jec­to­ries towards tar­gets at ran­dom ori­en­ta­tions on a 2-​​dimensional com­puter screen. For ini­tially unknown and non-​​stationary tun­ing para­me­ters, our unsu­per­vised method is still able to gen­er­ate pre­cise tra­jec­to­ries and to keep its per­for­mance sta­ble in the long term. The algo­rithm can option­ally work also with neu­ronal error sig­nals instead or in con­junc­tion with the pro­posed unsu­per­vised adaptation.”

    FOR-​​SCIENCE brain-​​machine-​​interface user-​​interface adaptive-​​control emergent-​​design

  • [1206.3980] Visu­al­iz­ing Stream­ing Text Data with Dynamic Maps

    “The many end­less rivers of text now avail­able present a seri­ous chal­lenge in the task of glean­ing, ana­lyz­ing and dis­cov­er­ing use­ful infor­ma­tion. In this paper, we describe a method­ol­ogy for visu­al­iz­ing text streams in real time. The approach auto­mat­i­cally groups sim­i­lar mes­sages into “coun­tries,” with key­word sum­maries, using seman­tic analy­sis, graph clus­ter­ing and map gen­er­a­tion tech­niques. It han­dles the need for visual sta­bil­ity across time by dynamic graph lay­out and Pro­crustes pro­jec­tion tech­niques, enhanced with a novel sta­ble com­po­nent pack­ing algo­rithm. The result pro­vides a con­tin­u­ous, suc­cinct view of evolv­ing top­ics of inter­est. It can be used in pas­sive mode for overviews and sit­u­a­tional aware­ness, or as an inter­ac­tive data explo­ration tool. To make these ideas con­crete, we describe their appli­ca­tion to an online ser­vice called TwitterScope.”

    visu­al­iza­tion data algo­rithms user-​​experience

  • [1205.3352] Revis­it­ing the effect of exter­nal fields in Axelrod’s model of social dynamics

    “The study of the effects of spa­tially uni­form fields on the steady-​​state prop­er­ties of Axelrod’s model has yielded plenty of con­tro­ver­sial results. Here we re-​​examine the impact of this type of field for a selec­tion of para­me­ters such that the field-​​free steady state of the model is het­ero­ge­neous or mul­ti­cul­tural. Analy­ses of both one and two-​​dimensional ver­sions of Axelrod’s model indi­cate that, con­trary to pre­vi­ous claims in the lit­er­a­ture, the steady state remains het­ero­ge­neous regard­less of the value of the field strength. Turn­ing on the field leads to a dis­con­tin­u­ous decrease on the num­ber of cul­tural domains, which we argue is due to the insta­bil­ity of zero-​​field het­ero­ge­neous absorb­ing con­fig­u­ra­tions. We find, how­ever, that spa­tially nonuni­form fields that imple­ment a con­sen­sus rule among the neigh­bor­hood of the agents enforces homog­e­niza­tion. Although the over­all effects of the fields are essen­tially the same irre­spec­tive of the dimen­sion­al­ity of the model, we argue that the dimen­sion­al­ity has a sig­nif­i­cant impact on the sta­bil­ity of the field-​​free homo­ge­neous steady state.”

    com­plex­ol­ogy agent-​​based exter­nal­i­ties sim­u­la­tion evolutionary-​​economics nudge-​​targets

  • [1206.3421] Lin­ear Latent Vari­able Mod­els: The lava-​​package

    “An R pack­age for spec­i­fy­ing and esti­mat­ing lin­ear latent vari­able mod­els is pre­sented. The phi­los­o­phy of the imple­men­ta­tion is to sep­a­rate the model spec­i­fi­ca­tion from the actual data, which leads to a dynamic and easy way of mod­el­ing com­plex hier­ar­chi­cal struc­tures. Sev­eral advanced fea­tures are imple­mented includ­ing robust stan­dard errors for clus­tered cor­re­lated data, multi­group analy­ses, non-​​linear para­me­ter con­straints, infer­ence with incom­plete data, max­i­mum like­li­hood esti­ma­tion with cen­sored and binary obser­va­tions, and instru­men­tal vari­able esti­ma­tors. In addi­tion an exten­sive sim­u­la­tion inter­face cov­er­ing a broad range of non-​​linear gen­er­al­ized struc­tural equa­tion mod­els is described. The model and soft­ware are demon­strated in data of mea­sure­ments of the sero­tonin trans­porter in the human brain.”

    ontol­ogy sta­tis­tics algo­rithms R-​​language linear-​​models model-​​view-​​controller design-​​patterns

  • [1205.6129] The Miss­ing Mem­ris­tor: Novel Nan­otech­nol­ogy or rather new Case Study for the Phi­los­o­phy and Soci­ol­ogy of Science?

    “In 2008, it was widely announced that the miss­ing mem­ris­tor, a basic two-​​terminal elec­tri­cal cir­cuit ele­ment, had finally been dis­cov­ered. The mem­ris­tor is the fourth and last such cir­cuit ele­ment and thus com­pletes cir­cuit the­ory. Pre­dicted already in 1971, the even­tual dis­cov­ery of some­thing seem­ingly so basic needed almost 40 years. How­ever, this dis­cov­ery is doubted. The pre­dicted mem­ris­tor has no mate­r­ial mem­ory and is based on mag­netic flux, but the dis­cov­ered devices con­sti­tute ana­logue mem­ory stor­age that do not involve mag­net­ism. The per­son who orig­i­nally pro­posed the mem­ris­tor did not reject the dis­cov­ery but instead changed his mind about what a mem­ris­tor is. We briefly intro­duce the his­tory and then care­fully mem­ris­tance and the mem­ris­tor as such. We dis­cuss its sta­tus as a model rather than a device. We dis­cuss the dis­cov­ered devices, their sta­bil­ity, and how sta­bil­ity relates to the con­sis­tency of the the­o­ret­i­cal enti­ties. A thought exper­i­ment assumes a world with­out mag­net­ism. Induc­tors can­not exist there, but mem­ory resis­tors could still be con­structed. On the same grounds as the mem­ris­tor was his­tor­i­cally pre­dicted, an “induc­tor” could then be pre­dicted. Likely, some­body would also ‘dis­cover’ one. A ten­ta­tive soci­o­log­i­cal analy­sis com­pares to the flawed detec­tion of grav­i­ta­tional waves but comes to very dif­fer­ent conclusions.”

    symmetry-​​is-​​the-​​way-​​things-​​ought-​​to-​​be history-​​of-​​science technical-​​assumptions engineering-​​philosophy

  • [1205.2776] Trans­port on cou­pled spa­tial networks

    “Trans­port processes on spa­tial net­works are rep­re­sen­ta­tive of a broad class of real world sys­tems which, rather than being inde­pen­dent, are typ­i­cally inter­de­pen­dent. We pro­pose a mea­sure of util­ity to cap­ture key fea­tures that arise when such sys­tems are cou­pled together. The cou­pling is defined in a way that is not solely topo­log­i­cal, rely­ing on both the dis­tri­b­u­tion of sources and sinks, and the method of route assign­ment. Using a toy model, we explore rel­e­vant cases by sim­u­la­tion. For cer­tain para­me­ter val­ues, a pic­ture emerges of two regimes. The first occurs when the flows go from many sources to a small num­ber of sinks. In this case, net­work util­ity is largest when the cou­pling is at its max­i­mum and the aver­age short­est path is min­i­mized. The sec­ond regime arises when many sources cor­re­spond to many sinks. Here, the opti­mal cou­pling no longer cor­re­sponds to the min­i­mum aver­age short­est path, as the con­ges­tion of traf­fic must also be taken into account. More gen­er­ally, results indi­cate that cou­pled spa­tial sys­tems can give rise to behav­ior that relies sub­tly on the inter­play between the cou­pling and ran­dom­ness in the source-​​sink distribution.”

    nudge-​​targets network-​​theory emergent-​​design epi­demi­ol­ogy sim­u­la­tion

  • [1206.5849] Under­stand­ing the com­plex­ity of the L’evy-walk nature of human mobil­ity with a multi-​​scale cost/​benefit model

    “Prob­a­bil­ity dis­tri­b­u­tions of human dis­place­ments has been fit with expo­nen­tially trun­cated L’evy flights or fat tailed Pareto inverse power law prob­a­bil­ity dis­tri­b­u­tions. Thus, peo­ple usu­ally stay within a given loca­tion (for exam­ple, the city of res­i­dence), but with a non-​​vanishing fre­quency they visit nearby or far loca­tions too. Herein, we show that an impor­tant empir­i­cal dis­tri­b­u­tion of human dis­place­ments (range: from 1 to 1000 km) can be well fit by three con­sec­u­tive Pareto dis­tri­b­u­tions with sim­ple inte­ger expo­nents equal to 1, 2 and ($gtrap­prox$) 3. These three expo­nents cor­re­spond to three dis­place­ment range zones of about 1 km $less­sim Delta r less­sim$ 10 km, 10 km $less­sim Delta r less­sim$ 300 km and 300 km $less­sim Delta r less­sim $ 1000 km, respec­tively. These three zones can be geo­graph­i­cally and phys­i­cally well deter­mined as dis­place­ments within a city, vis­its to nearby cities that may occur within just one-​​day trips, and visit to far loca­tions that may require multi-​​days trips. The incre­men­tal inte­ger val­ues of the three expo­nents can be eas­ily explained with a three-​​scale mobil­ity cost/​benefit model for human dis­place­ments based on sim­ple geo­met­ri­cal con­strains. Essen­tially, peo­ple would divide the space into three major regions (close, medium and far dis­tances) and would assume that the travel ben­e­fits are randomly/​uniformly dis­trib­uted mostly only within spe­cific urban-​​like areas.”

    Levy-​​flights city-​​planning multiscale-​​phenomena self-​​similarity

  • [1206.7011] Ultra­thin Ter­a­hertz Pla­nar Lenses

    “Con­ven­tional opti­cal com­po­nents shape the wave­front of prop­a­gat­ing light by adjust­ing the opti­cal path length, which requires the use of rather thick lenses, espe­cially for the adjust­ment of ter­a­hertz (THz) radi­a­tion due to its long wave­length. Two ultra­thin THz pla­nar lenses were designed and fab­ri­cated based on inter­face phase mod­u­la­tion of antenna res­o­nance. The lens thick­nesses were extremely reduced to 100 nm, which is only 1⁄4000th of the illu­mi­nat­ing light wave­length. The focus­ing and imag­ing func­tions of the lenses were exper­i­men­tally demon­strated. The ultra­thin opti­cal com­po­nents described herein are a sig­nif­i­cant step toward the devel­op­ment of a micro-​​integrated THz system.”

    optics engineering-​​design nudge-​​targets

  • [1206.3789] Tree decom­po­si­tion and para­me­ter­ized algo­rithms for RNA structure-​​sequence align­ment includ­ing ter­tiary inter­ac­tions and pseudoknots

    “We present a gen­eral set­ting for structure-​​sequence com­par­i­son in a large class of RNA struc­tures that uni­fies and gen­er­al­izes a num­ber of recent works on spe­cific fam­i­lies on struc­tures. Our approach is based on tree decom­po­si­tion of struc­tures and gives rises to a gen­eral para­me­ter­ized algo­rithm, where the expo­nen­tial part of the com­plex­ity depends on the fam­ily of struc­tures. For each of the pre­vi­ously stud­ied fam­i­lies, our algo­rithm has the same com­plex­ity as the spe­cific algo­rithm that had been given before.”

    RNA structural-​​biology fold­ing bioin­for­mat­ics algo­rithms nudge-​​targets mod­el­ing

  • [1206.3403] Topo­log­i­cal Mea­sure Locat­ing the Effec­tive Crossover between Seg­re­ga­tion and Inte­gra­tion in a Mod­u­lar Network

    “Com­pu­ta­tional analy­sis of time-​​course data with an under­ly­ing causal struc­ture is needed in a vari­ety of domains, includ­ing neural spike trains, stock price move­ments, and gene expres­sion lev­els. How­ever, it can be chal­leng­ing to deter­mine from just the numer­i­cal time course data alone what is coor­di­nat­ing the vis­i­ble processes, to sep­a­rate the under­ly­ing prima facie causes into gen­uine and spu­ri­ous causes and to do so with a fea­si­ble com­pu­ta­tional com­plex­ity. For this pur­pose, we have been devel­op­ing a novel algo­rithm based on a frame­work that com­bines notions of causal­ity in phi­los­o­phy with algo­rith­mic approaches built on model check­ing and sta­tis­ti­cal tech­niques for mul­ti­ple hypothe­ses test­ing. The causal rela­tion­ships are described in terms of tem­po­ral logic for­mu­lae, refram­ing the infer­ence prob­lem in terms of model check­ing. The logic used, PCTL, allows descrip­tion of both the time between cause and effect and the prob­a­bil­ity of this rela­tion­ship being observed. We show that equipped with these causal for­mu­lae with their asso­ci­ated prob­a­bil­i­ties we may com­pute the aver­age impact a cause makes to its effect and then dis­cover sta­tis­ti­cally sig­nif­i­cant causes through the con­cepts of mul­ti­ple hypoth­e­sis test­ing (treat­ing each causal rela­tion­ship as a hypoth­e­sis), and false dis­cov­ery con­trol. By explor­ing a well-​​chosen fam­ily of poten­tially all sig­nif­i­cant hypothe­ses with rea­son­ably min­i­mal descrip­tion length, it is pos­si­ble to tame the algorithm’s com­pu­ta­tional com­plex­ity while explor­ing the nearly com­plete search-​​space of all prima facie causes. We have tested these ideas in a num­ber of domains and illus­trate them here with two examples.”

    time-​​series sta­tis­tics frame­work dynamical-​​systems to-​​read

  • [1206.5959] The Online Replace­ment Path Problem

    “We study a nat­ural online vari­ant of the replace­ment path prob­lem. The textit{replacement path prob­lem} asks to find for a given graph $G = (V,E)$, two des­ig­nated ver­tices $s,tin V$ and a short­est $s$-$t$ path $P$ in $G$, a textit{replacement path} $P_​e$ for every edge $e$ on the path $P$. The replace­ment path $P_​e$ is sim­ply a short­est $s$-$t$ path in the graph, which avoids the textit{failed} edge $e$. We adapt this prob­lem to deal with the nat­ural sce­nario, that the edge which failed is not known at the time of solu­tion imple­men­ta­tion. Instead, our prob­lem assumes that the iden­tity of the failed edge only becomes avail­able when the rout­ing mech­a­nism tries to cross the edge. This sit­u­a­tion is moti­vated by appli­ca­tions in dis­trib­uted net­works, where infor­ma­tion about recent changes in the net­work is only stored locally, and fault-​​tolerant opti­miza­tion, where an adver­sary tries to delay the dis­cov­ery of the mate­ri­al­ized sce­nario as much as pos­si­ble. Con­se­quently, we define the textit{online replace­ment path prob­lem}, which asks to find a nom­i­nal $s$-$t$ path $Q$ and detours $Q_​e$ for every edge on the path $Q$, such that the worst-​​case arrival time at the des­ti­na­tion is min­i­mized. Our main con­tri­bu­tion is a label set­ting algo­rithm, which solves the prob­lem in undi­rected graphs in time $O(m log n)$ and lin­ear space for all sources and a sin­gle des­ti­na­tion. We also present algo­rithms for exten­sions of the model to any bounded num­ber of failed edges.”

    operations-​​research plan­ning algo­rithms online-​​algorithms nudge-​​targets

  • [1206.6195] Par­rondo games with spa­tial depen­dence, II

    “…Again this sug­gests that the Par­rondo region (mu_​B is non­pos­i­tive and mu_[r,s] is pos­i­tive) has nonzero vol­ume in the limit. …”

    Parrondo-​​games game-​​theory counterintuitive-​​results sim­u­la­tion coop­er­a­tion

  • [1206.4648] Two-​​Manifold Prob­lems with Appli­ca­tions to Non­lin­ear Sys­tem Identification

    “Recently, there has been much inter­est in spec­tral approaches to learn­ing manifolds—so-called ker­nel eigen­map meth­ods. These meth­ods have had some suc­cesses, but their applic­a­bil­ity is lim­ited because they are not robust to noise. To address this lim­i­ta­tion, we look at two-​​manifold prob­lems, in which we simul­ta­ne­ously recon­struct two related man­i­folds, each rep­re­sent­ing a dif­fer­ent view of the same data. By solv­ing these inter­con­nected learn­ing prob­lems together, two-​​manifold algo­rithms are able to suc­ceed where a non-​​integrated approach would fail: each view allows us to sup­press noise in the other, reduc­ing bias. We pro­pose a class of algo­rithms for two-​​manifold prob­lems, based on spec­tral decom­po­si­tion of cross-​​covariance oper­a­tors in Hilbert space, and dis­cuss when two-​​manifold prob­lems are use­ful. Finally, we demon­strate that solv­ing a two-​​manifold prob­lem can aid in learn­ing a non­lin­ear dynam­i­cal sys­tem from lim­ited data.”

    sta­tis­tics inverse-​​problems system-​​identification algo­rithms nudge-​​targets bench­mark­ing

  • [1203.3367] Sto­chas­tic dif­fer­en­tial equa­tions for evo­lu­tion­ary dynam­ics with demo­graphic noise and mutations

    “We present a gen­eral frame­work to describe the evo­lu­tion­ary dynam­ics of an arbi­trary num­ber of types in finite pop­u­la­tions based on sto­chas­tic dif­fer­en­tial equa­tions (SDE). For large, but finite pop­u­la­tions this allows to include demo­graphic noise with­out requir­ing explicit sim­u­la­tions. Instead, the pop­u­la­tion size only rescales the ampli­tude of the noise. More­over, this frame­work admits the inclu­sion of muta­tions between dif­fer­ent types, pro­vided that muta­tion rates, $mu$, are not too small com­pared to the inverse pop­u­la­tion size 1/​N. This ensures that all types are almost always rep­re­sented in the pop­u­la­tion and that the occa­sional extinc­tion of one type does not result in an extended absence of that type. For $mu Nll1$ this lim­its the use of SDE’s, but in this case there are well estab­lished alter­na­tive approx­i­ma­tions based on time scale sep­a­ra­tion. We illus­trate our approach by a Rock-​​Scissors-​​Paper game with muta­tions, where we demon­strate excel­lent agree­ment with sim­u­la­tion based results for suf­fi­ciently large pop­u­la­tions. In the absence of muta­tions the excel­lent agree­ment extends to small pop­u­la­tion sizes.”

    finite-​​size-​​effects population-​​biology noise-​​in-​​design nudge-​​targets

  • [1206.5352] The Sub­word Com­plex­ity of k-​​Automatic Sequences is k-​​Synchronized

    “We show that the sub­word com­plex­ity func­tion p_​x (n), which counts the num­ber of dis­tinct fac­tors of length n of a k-​​automatic sequence x, is k-​​synchronized in the sense of Carpi. As an appli­ca­tion, we gen­er­al­ize recent results of Gold­stein. In con­trast, we show that func­tion which counts the num­ber of unbor­dered fac­tors of length n is not k-​​synchronized.”

    automata strings com­plex­ity nudge-​​targets

  • Con­vex hull algo­rithms — Wikipedia, the free encyclopedia

    “Com­put­ing the con­vex hull means that a non-​​ambiguous and effi­cient rep­re­sen­ta­tion of the required con­vex shape is con­structed. The com­plex­ity of the cor­re­spond­ing algo­rithms is usu­ally esti­mated in terms of n, the num­ber of input points, and h, the num­ber of points on the con­vex hull.”

    computational-​​geometry algo­rithms nudge-​​targets

  • [1205.6363] What Should Devel­op­ers Be Aware Of? An Empir­i­cal Study on the Direc­tives of API Documentation

    “Appli­ca­tion Pro­gram­ming Inter­faces (API) are exposed to devel­op­ers in order to reuse soft­ware libraries. API direc­tives are natural-​​language state­ments in API doc­u­men­ta­tion that make devel­op­ers aware of con­straints and guide­lines related to the usage of an API. This paper presents the design and the results of an empir­i­cal study on the direc­tives of API doc­u­men­ta­tion of object-​​oriented libraries. Its main con­tri­bu­tion is to pro­pose and exten­sively dis­cuss a tax­on­omy of 23 kinds of API directives.”

    digital-​​humanities doc­u­men­ta­tion text-​​mining software-​​development cultural-​​norms

  • Pub­li­ca­tions Avail­able Electronically

    God­fried T. Tou­s­saint, “The Erdos-​​Nagy the­o­rem and its ram­i­fi­ca­tions,” Proc. 11th Cana­dian Con­fer­ence on Com­pu­ta­tional Geom­e­try, Van­cou­ver, Canada, August 16–18 1999, pp. 9–12. Long ver­sion avail­able at: http://​www​.cs​.ubc​.ca/​c​o​n​f​e​r​e​n​c​e​s​/​C​CCG. Also: Tech­ni­cal Report No. SOCS-99.2, School of Com­puter Sci­ence, McGill Uni­ver­sity, June 18, 1999.

    nudge-​​targets geom­e­try genetic-​​programming-​​target low-​​hanging-​​fruit

  • Intro­duc­tion to Lam­ina Emer­gent Mech­a­nisms (LEMS) | Com­pli­ant Mechanisms

    “The fact that LEMs can be fab­ri­cated from pla­nar lay­ers influ­ences both what processes can be used for their man­u­fac­ture and what mate­ri­als may be used in their con­struc­tion. At the micro level, LEMS can be fab­ri­cated using single-​​layer MEMS fab­ri­ca­tion meth­ods and mate­ri­als, which offers sig­nif­i­cant cost and reli­a­bil­ity advan­tages. It also pro­vides oppor­tu­ni­ties for com­plex out-​​of-​​plane motion with only a sin­gle layer. At the macro level, man­u­fac­tur­ing processes used to make sta­tic struc­tures or com­po­nents for assem­bly can be used to cre­ate mech­a­nisms capa­ble of sophis­ti­cated motions and com­plex tasks. Example processes include stamp­ing, fine blank­ing, laser cut­ting, water jet cut­ting, plasma cut­ting, and wire elec­tri­cal dis­charge machin­ing (EDM). Some of these processes, such as stamp­ing, offer sig­nif­i­cant cost advan­tages for high-​​volume pro­duc­tion. Pla­nar fab­ri­ca­tion also allows the use of sheet goods to directly cre­ate mech­a­nisms. The use of low-​​cost, high-​​quality sheet goods has the poten­tial to dra­mat­i­cally reduce cost for high-​​volume pro­duc­tion. It also makes pos­si­ble the next char­ac­ter­is­tic: flat ini­tial state.”

    man­u­fac­tur­ing engineering-​​design fab­ri­ca­tion nudge-​​targets

Items of some interest:

Posted on by

These are my recent Pin​board​.in links:

Items of some interest…

Posted on by

These are my recent Pin​board​.in links:

  • [1110.1462] Dynamic Clus­ter­ing of His­togram Data Based on Adap­tive Squared Wasser­stein Distances

    “…To clus­ter sets of his­togram data, we pro­pose to use Dynamic Clus­ter­ing Algo­rithm, (based on adap­tive squared Wasser­stein dis­tances) that is a k-​​means-​​like algo­rithm for clus­ter­ing a set of indi­vid­u­als into K classes that are apri­ori fixed. The main aim of this research is to pro­vide a tool for clus­ter­ing his­tograms, empha­siz­ing the dif­fer­ent con­tri­bu­tions of the his­togram vari­ables, and their com­po­nents, to the def­i­n­i­tion of the clus­ters. We demon­strate that this can be achieved using adap­tive dis­tances. Two kind of adap­tive dis­tances are con­sid­ered: the first takes into account the vari­abil­ity of each com­po­nent of each descrip­tor for the whole set of indi­vid­u­als; the sec­ond takes into account the vari­abil­ity of each com­po­nent of each descrip­tor in each clus­ter. We fur­nish inter­pre­ta­tive tools of the obtained par­ti­tion based on an exten­sion of the clas­si­cal mea­sures (indexes) to the use of adap­tive dis­tances in the clus­ter­ing cri­te­rion func­tion. Appli­ca­tions on syn­thetic and real-​​world data cor­rob­o­rate the pro­posed procedure.”

    clas­si­fi­ca­tion sta­tis­tics his­tograms met­rics clus­ter­ing

  • [1110.1412] Quan­ti­fy­ing loopy net­work architectures

    “Biol­ogy presents many exam­ples of pla­nar dis­tri­b­u­tion and struc­tural net­works hav­ing dense sets of closed loops. An arche­type of this form of net­work orga­ni­za­tion is the vas­cu­la­ture of dicotyle­do­nous leaves, which show­cases a hierarchically-​​nested archi­tec­ture con­tain­ing closed loops at many dif­fer­ent lev­els. Although a num­ber of meth­ods have been pro­posed to mea­sure aspects of the struc­ture of such net­works, a robust met­ric to quan­tify their hier­ar­chi­cal orga­ni­za­tion is still lack­ing. We present an algo­rith­mic frame­work, the hier­ar­chi­cal loop decom­po­si­tion, that allows map­ping loopy net­works to binary trees, pre­serv­ing in the con­nec­tiv­ity of the trees the archi­tec­ture of the orig­i­nal graph. We apply this frame­work to inves­ti­gate com­puter gen­er­ated graphs, such as arti­fi­cial mod­els and opti­mal dis­tri­b­u­tion net­works, as well as nat­ural graphs extracted from dig­i­tized images of dicotyle­do­nous leaves and vas­cu­la­ture of rat cere­bral neo­cor­tex. We cal­cu­late var­i­ous met­rics based on the Asym­me­try, the cumu­la­tive size dis­tri­b­u­tion and the Strahler bifur­ca­tion ratios of the cor­re­spond­ing trees and dis­cuss the rela­tion­ship of these quan­ti­ties to the archi­tec­tural orga­ni­za­tion of the orig­i­nal graphs. This algo­rith­mic frame­work decou­ples the geo­met­ric infor­ma­tion (exact loca­tion of edges and nodes) from the met­ric topol­ogy (con­nec­tiv­ity and edge weight) and it ulti­mately allows us to per­form a quan­ti­ta­tive sta­tis­ti­cal com­par­i­son between pre­dic­tions of the­o­ret­i­cal mod­els and nat­u­rally occur­ring loopy graphs.”

    com­plex­ol­ogy bio­physics network-​​theory met­rics

  • [1110.1393] High-​​Precision Tun­ing of State for Mem­ris­tive Devices by Adapt­able Variation-​​Tolerant Algorithm

    “Using mem­ris­tive prop­er­ties com­mon for the tita­nium diox­ide thin film devices, we designed a sim­ple write algo­rithm to tune device con­duc­tance at a spe­cific bias point to 1% rel­a­tive accu­racy (which is roughly equiv­a­lent to 7-​​bit pre­ci­sion) within its dynamic range even in the pres­ence of large vari­a­tions in switch­ing behav­ior. The high pre­ci­sion state is non­volatile and the results are likely to be sus­tained for nanoscale mem­ris­tive devices because of the inher­ent fil­a­men­tary nature of the resis­tive switch­ing. The pro­posed func­tion­al­ity of mem­ris­tive devices is espe­cially attrac­tive for ana­log com­put­ing with low pre­ci­sion data. As one rep­re­sen­ta­tive exam­ple we demon­strate hybrid cir­cuitry con­sist­ing of CMOS sum­ming ampli­fier and two mem­ris­tive devices to per­form ana­log mul­ti­ply and accu­mu­late com­pu­ta­tion, which is a typ­i­cal bot­tle­neck oper­a­tion in infor­ma­tion processing.”

    mem­ris­tors engineering-​​design sim­u­la­tion control-​​systems nudge-​​targets

  • [1110.1521] Nodal domains of a non-​​separable prob­lem — the right angled isosce­les triangle

    “Our result may be gen­er­al­ized to other domains where sim­i­lar algo­rithms may apply. Our algo­rithm is based on the fact that the eigen­func­tions are pre­sented as a lin­ear com­bi­na­tion of sim­ple plane waves. It is there­fore tempt­ing to try and gen­er­al­ize it for other drums with sim­i­lar prop­erty. The equi­lat­eral tri­an­gle is an imme­di­ate can­di­date (see [29] and ref­er­ences within). A fur­ther, and quite sur­pris­ing, result is the recur­sive for­mula for the num­ber of nodal loops. To our knowl­edge this is the first known exact for­mula for the nodal count of a non-​​separable pla­nar man­i­fold (for cer­tain eigen­func­tions of tori exact for­mu­las have been given in [22]). The for­mula was found by direct inspec­tion of large tables and has been ver­i­fied for a large bulk of data com­pu­ta­tion­ally. An obvi­ous chal­lenge is to prove this for­mula. In par­tic­u­lar, the recur­sive part of the for­mula resem­bles the famous Euclid algo­rithm for the great­est com­mon divi­sor. A fur­ther inves­ti­ga­tion of the men­tioned for­mula might there­fore expose some new num­ber the­o­ret­i­cal prop­er­ties of the nodal count.”

    physics algo­rithms analytical-​​results open-​​questions geom­e­try acoustics exact-​​form nudge-​​targets

  • [1110.1485] A Face Recog­ni­tion Scheme using Wavelet Based Dom­i­nant Features

    “In this paper, a multi-​​resolution fea­ture extrac­tion algo­rithm for face recog­ni­tion is pro­posed based on two-​​dimensional dis­crete wavelet trans­form (2D-​​DWT), which effi­ciently exploits the local spa­tial vari­a­tions in a face image. For the pur­pose of fea­ture extrac­tion, instead of con­sid­er­ing the entire face image, an entropy-​​based local band selec­tion cri­te­rion is devel­oped, which selects high-​​informative hor­i­zon­tal seg­ments from the face image. In order to cap­ture the local spa­tial vari­a­tions within these high­in­for­ma­tive hor­i­zon­tal bands pre­cisely, the hor­i­zon­tal band is seg­mented into sev­eral small spa­tial mod­ules. Dom­i­nant wavelet coef­fi­cients cor­re­spond­ing to each local region resid­ing inside those hor­i­zon­tal bands are selected as fea­tures. In the selec­tion of the dom­i­nant coef­fi­cients, a thresh­old cri­te­rion is pro­posed, which not only dras­ti­cally reduces the fea­ture dimen­sion but also pro­vides high within-​​class com­pact­ness and high between-​​class sep­a­ra­bil­ity. A prin­ci­pal com­po­nent analy­sis is per­formed to fur­ther reduce the dimen­sion­al­ity of the fea­ture space. Exten­sive exper­i­men­ta­tion is car­ried out upon stan­dard face data­bases and a very high degree of recog­ni­tion accu­racy is achieved by the pro­posed method in com­par­i­son to those obtained by some of the exist­ing methods.”

    face-​​recognition algo­rithms image-​​processing wavelets nudge-​​targets

  • [1110.1553] Hier­ar­chi­cal QR fac­tor­iza­tion algo­rithms for multi-​​core clus­ter systems

    “This paper describes a new QR fac­tor­iza­tion algo­rithm which is espe­cially designed for mas­sively par­al­lel plat­forms com­bin­ing par­al­lel dis­trib­uted multi-​​core nodes. These plat­forms make the present and the fore­see­able future of high-​​performance com­put­ing. Our new QR fac­tor­iza­tion algo­rithm falls in the cat­e­gory of the tile algo­rithms which nat­u­rally enables good data local­ity for the sequen­tial ker­nels exe­cuted by the cores (high sequen­tial per­for­mance), low num­ber of mes­sages in a par­al­lel dis­trib­uted set­ting (small latency term), and fine gran­u­lar­ity (high parallelism).”

    parallel-​​computing operations-​​research fac­tor­iza­tion algo­rithms nudge-​​targets meta-​​algorithms

  • [1110.1560] On the Col­or­ing of Grid Wire­less Sen­sor Net­works: the Vector-​​Based Col­or­ing Method

    “Graph col­or­ing is used in wire­less net­works to opti­mize net­work resources: band­width and energy. Nodes access the medium accord­ing to their color. It is the respon­si­bil­ity of the col­or­ing algo­rithm to ensure that inter­fer­ing nodes do not have the same color. In this research report, we focus on wire­less sen­sor net­works with grid topolo­gies. How does a col­or­ing algo­rithm take advan­tage of the reg­u­lar­ity of grid topol­ogy to pro­vide an opti­mal peri­odic col­or­ing, that is a col­or­ing with the min­i­mum num­ber of col­ors? We pro­pose the Vector-​​Based Col­or­ing Method, denoted VCM, a new method that is able to pro­vide an opti­mal peri­odic col­or­ing for any radio trans­mis­sion range and for any h-​​hop col­or­ing, h>=1. This method con­sists in deter­min­ing at which grid nodes a color can be repro­duced with­out cre­at­ing inter­fer­ences between these nodes while min­i­miz­ing the num­ber of col­ors used. We com­pare the num­ber of col­ors pro­vided by VCM with the num­ber of col­ors obtained by a dis­trib­uted col­or­ing algo­rithm with line and col­umn pri­or­ity assign­ments. We also pro­vide bounds on the num­ber of col­ors of opti­mal gen­eral col­or­ings of the infi­nite grid, and show that peri­odic col­or­ings (and thus VCM) are asymp­tot­i­cally opti­mal. Finally, we dis­cuss the applic­a­bil­ity of this method to a real wire­less network.”

    graph-​​theory algo­rithms operations-​​research nudge-​​targets

  • [1110.1580] A Polylogarithmic-​​Competitive Algo­rithm for the k-​​Server Problem

    “We give the first polylogarithmic-​​competitive ran­dom­ized online algo­rithm for the $k$-server prob­lem on an arbi­trary finite met­ric space. In par­tic­u­lar, our algo­rithm achieves a com­pet­i­tive ratio of O(log^3 n log^2 k log log n) for any met­ric space on n points. Our algo­rithm improves upon the deter­min­is­tic (2k-1)-competitive algo­rithm of Kout­sou­pias and Papadim­itriou [J.ACM’95] when­ever n is sub-​​exponential in k.”

    sched­ul­ing operations-​​research algo­rithms nudge-​​targets

  • [1110.1590] PSA: The Packet Sched­ul­ing Algo­rithm for Wire­less Sen­sor Networks

    “The main cause of wasted energy con­sump­tion in wire­less sen­sor net­works is packet col­li­sion. The packet sched­ul­ing algo­rithm is there­fore intro­duced to solve this prob­lem. Some packet sched­ul­ing algo­rithms can also influ­ence and delay the data trans­mit­ting in the real-​​time wire­less sen­sor net­works. This paper presents the packet sched­ul­ing algo­rithm (PSA) in order to reduce the packet con­ges­tion in MAC layer lead­ing to reduce the over­all of packet col­li­sion in the sys­tem The PSA is com­pared with the sim­ple CSMA/​CA and other approaches using net­work topol­ogy bench­marks in math­e­mat­i­cal method. The per­for­mances of our PSA are bet­ter than the stan­dard (CSMA/​CA). The PSA pro­duces bet­ter through­put than other algo­rithms. On other hand, the aver­age delay of PSA is higher than pre­vi­ous works. How­ever, the PSA uti­lizes the chan­nel bet­ter than all algorithms.”

    sensor-​​networks distributed-​​processing sched­ul­ing rout­ing operations-​​research algo­rithms nudge-​​targets

  • [1110.0725] A Sur­vey of Dis­trib­uted Data Aggre­ga­tion Algorithms

    “Dis­trib­uted data aggre­ga­tion has been an active field of research in the last decade, and a huge diverse amount of tech­niques can be found in the lit­er­a­ture. For this rea­sons, this sur­vey intends to be an impor­tant time sav­ing instru­ment, for those that desire to get a quick and com­pre­hen­sive overview of the state of the art on dis­trib­uted data aggre­ga­tion. More­over, by care­fully high­light­ing the strength and lim­i­ta­tions of the more per­ti­nent approaches, this study can pro­vide a use­ful assis­tance to help read­ers choose which tech­nique to apply in spe­cific set­tings. Cur­rently, there is no ideal gen­eral solu­tion to the dis­trib­uted com­pu­ta­tion of an aggre­ga­tion func­tion, all exist­ing tech­niques have its pit­falls (some more than oth­ers). There­fore, more research in this field will be expected in the next few years. In par­tic­u­lar, due to the added value of com­put­ing com­plex aggre­gates, new algo­rithms might arise to esti­mate the sta­tis­ti­cal dis­tri­b­u­tion of val­ues, as the few exist­ing approaches exhibit some lim­i­ta­tions in terms of accu­racy and resource con­sump­tion. Addi­tional research efforts should be made to improve the sup­port to churn, mes­sage loss, and con­tin­u­ous esti­ma­tion of muta­ble input values.”

    sta­tis­tics reviews distributed-​​processing com­mu­ni­ca­tion coor­di­na­tion nudge-​​targets

  • [0911.3482] Com­plex­ity of Net­works (reprise)

    “Net­work or graph struc­tures are ubiq­ui­tous in the study of com­plex sys­tems. Often, we are inter­ested in com­plex­ity trends of these sys­tem as it evolves under some dynamic. An exam­ple might be look­ing at the com­plex­ity of a food web as species enter an ecosys­tem via migra­tion or spe­ci­a­tion, and leave via extinc­tion. In a pre­vi­ous paper, a com­plex­ity mea­sure of net­works was pro­posed based on the {em com­plex­ity is infor­ma­tion con­tent} par­a­digm. To apply this par­a­digm to any object, one must fix two things: a rep­re­sen­ta­tion lan­guage, in which strings of sym­bols from some alpha­bet describe, or stand for the objects being con­sid­ered; and a means of deter­min­ing when two such descrip­tions refer to the same object. With these two things set, the infor­ma­tion con­tent of an object can be com­puted in prin­ci­ple from the num­ber of equiv­a­lent descrip­tions describ­ing a par­tic­u­lar object. The pre­vi­ously pro­posed rep­re­sen­ta­tion lan­guage had the defi­ciency that the fully con­nected and empty net­works were the most com­plex for a given num­ber of nodes. A vari­a­tion of this mea­sure, called zcom­plex­ity, applied a com­pres­sion algo­rithm to the result­ing bit­string rep­re­sen­ta­tion, to solve this prob­lem. Unfor­tu­nately, zcom­plex­ity proved too com­pu­ta­tion­ally expen­sive to be prac­ti­cal. In this paper, I pro­pose a new rep­re­sen­ta­tion lan­guage that encodes the num­ber of links along with the num­ber of nodes and a rep­re­sen­ta­tion of the lin­klist. This, like zcom­plex­ity, exhibits min­i­mal com­plex­ity for fully con­nected and empty net­works, but is as tractable as the orig­i­nal measure.”

    network-​​theory com­plex­ol­ogy complex-​​systems mea­sure­ment per­form structure-​​function-​​relations discrete-​​mathematics

  • [1108.4279] Detec­tion and emergence

    “Two dif­fer­ent con­cep­tions of emer­gence are rec­on­ciled as two instances of the phe­nom­e­non of detec­tion. In the process of com­par­ing these two con­cep­tions, we find that the notions of com­plex­ity and detec­tion allow us to form a uni­fied def­i­n­i­tion of emer­gence that clearly delin­eates the role of the observer.”

    com­plex­ol­ogy emer­gence pragmatism-it-ain’t but-​​soon

  • [1001.4278] Weight Opti­miza­tion for Dis­trib­uted Aver­age Con­sen­sus Algo­rithm in Sym­met­ric, CCS & KCS Star Networks

    “This paper addresses weight opti­miza­tion prob­lem in dis­trib­uted con­sen­sus aver­ag­ing algo­rithm over net­works with sym­met­ric star topol­ogy. We have deter­mined opti­mal weights and con­ver­gence rate of the net­work in terms of its topo­log­i­cal para­me­ters. In addi­tion, two alter­na­tive topolo­gies with more rapid con­ver­gence rates have been intro­duced. The new topolo­gies are Complete-​​Cored Sym­met­ric (CCS) star and K-​​Cored Sym­met­ric (KCS) star topolo­gies. It has been shown that the opti­mal weights for the edges of cen­tral part in sym­met­ric and CCS star con­fig­u­ra­tions are inde­pen­dent of their branches. By sim­u­la­tion opti­mal­ity of obtained weights under quan­ti­za­tion con­straints have been verified.”

    operations-​​research decision-​​making network-​​theory nudge-​​targets

  • [1109.5389] Water dri­ves pep­tide con­for­ma­tional transitions

    “Tran­si­tions between metastable con­for­ma­tions of a dipep­tide are inves­ti­gated using clas­si­cal mol­e­c­u­lar dynam­ics sim­u­la­tion with explicit water mol­e­cules. The dis­tri­b­u­tion of the sur­round­ing water at dif­fer­ent moments before the tran­si­tions and the dynam­i­cal cor­re­la­tions of water with the peptide’s con­fig­u­ra­tional motions indi­cate that water is the main dri­ving force of the con­for­ma­tional changes.”

    molecular-​​design systems-​​biology sim­u­la­tion intracellular-​​dynamics kinda-​​knew-​​this-​​a-​​long-​​time-​​ago bio­chem­istry

  • [1105.1445] Vehic­u­lar traf­fic flow at an inter­sec­tion with the pos­si­bil­ity of turning

    “We have devel­oped a Nagel-​​Schreckenberg cel­lu­lar automata model for describ­ing of vehic­u­lar traf­fic flow at a sin­gle inter­sec­tion. A set of traf­fic lights oper­at­ing in fixed-​​time scheme con­trols the traf­fic flow. Open bound­ary con­di­tion is applied to the streets each of which con­duct a uni-​​directional flow. Streets are single-​​lane and cars can turn upon reach­ing to the inter­sec­tion with pre­scribed prob­a­bil­i­ties. Exten­sive Monte Carlo sim­u­la­tions are car­ried out to find the model flow char­ac­ter­is­tics. In par­tic­u­lar, we inves­ti­gate the flows depen­dence on the sig­nal­i­sa­tion para­me­ters, turn­ing prob­a­bil­i­ties and input rates. It is shown that for each set of para­me­ters, there exist a plateau region inside which the total out­flow from the inter­sec­tion remains almost con­stant. We also com­pute total wait­ing time of vehi­cles per cycle behind red lights for var­i­ous con­trol parameters.”

    cellular-​​automata com­plex­ol­ogy traffic-​​models agent-​​based sim­u­la­tion nudge-​​substrates

  • [1110.1391] A Com­par­i­son of Dif­fer­ent Machine Translit­er­a­tion Models

    “Machine translit­er­a­tion is a method for auto­mat­i­cally con­vert­ing words in one lan­guage into pho­net­i­cally equiv­a­lent ones in another lan­guage. Machine translit­er­a­tion plays an impor­tant role in nat­ural lan­guage appli­ca­tions such as infor­ma­tion retrieval and machine trans­la­tion, espe­cially for han­dling proper nouns and tech­ni­cal terms. Four machine translit­er­a­tion mod­els — grapheme-​​based translit­er­a­tion model, phoneme-​​based translit­er­a­tion model, hybrid translit­er­a­tion model, and correspondence-​​based translit­er­a­tion model — have been pro­posed by sev­eral researchers. To date, how­ever, there has been lit­tle research on a frame­work in which mul­ti­ple translit­er­a­tion mod­els can oper­ate simul­ta­ne­ously. Fur­ther­more, there has been no com­par­i­son of the four mod­els within the same frame­work and using the same data. We addressed these prob­lems by 1) mod­el­ing the four mod­els within the same frame­work, 2) com­par­ing them under the same con­di­tions, and 3) devel­op­ing a way to improve machine translit­er­a­tion through this com­par­i­son. Our com­par­i­son showed that the hybrid and correspondence-​​based mod­els were the most effec­tive and that the four mod­els can be used in a com­ple­men­tary man­ner to improve machine translit­er­a­tion performance.”

    natural-​​language-​​processing machine-​​learning review nudge-​​targets

  • [1108.5508] A Pat­tern Measure

    “In this paper we pro­pose numer­i­cal mea­sures for eval­u­at­ing the aes­thetic inter­est of sim­ple pat­terns. The pat­terns con­sist of ele­ments (sym­bols, pix­els, etc.) in reg­u­lar square arrays. The mea­sures depend on two char­ac­ter­is­tics of the pat­terns: the num­ber of dif­fer­ent types of ele­ment, and the num­ber of sym­me­tries in their arrange­ment. We define two com­ple­men­tary com­pos­ite mea­sures L and C for the degree of pat­tern in a design, and com­pute them here for 2×2 and 6×6 arrays. The results dis­tin­guish sim­ple from high-​​variation cases. We sus­pect that the mea­sure L cor­re­sponds to the degree that human beings intu­itively feel a design to be “inter­est­ing”, so this model would aid in quan­ti­fy­ing the visual con­nec­tion of two– dimen­sional designs with view­ers. The other com­pos­ite mea­sure C based on these numer­i­cal prop­er­ties char­ac­ter­izes the extent of ran­dom­ness of an array. Com­bin­ing sym­bol vari­ety with sym­me­try cal­cu­la­tions allows us to employ hier­ar­chi­cal scal­ing to count the rel­a­tive impact of dif­fer­ent lev­els of scale. By iden­ti­fy­ing sub­struc­tures we can dis­tin­guish between orga­nized pat­terns and dis­or­ga­nized com­plex­ity. The mea­sures described here are related to ver­bal descrip­tors derived from work by psy­chol­o­gists on responses to visual environments.”

    cog­ni­tion aes­thet­ics experimental-​​psychology nudge-​​targets learning-​​by-​​watching

  • [1106.5264] Acquir­ing Cor­rect Knowl­edge for Nat­ural Lan­guage Generation

    “Nat­ural lan­guage gen­er­a­tion (NLG) sys­tems are com­puter soft­ware sys­tems that pro­duce texts in Eng­lish and other human lan­guages, often from non-​​linguistic input data. NLG sys­tems, like most AI sys­tems, need sub­stan­tial amounts of knowl­edge. How­ever, our expe­ri­ence in two NLG projects sug­gests that it is dif­fi­cult to acquire cor­rect knowl­edge for NLG sys­tems; indeed, every knowl­edge acqui­si­tion (KA) tech­nique we tried had sig­nif­i­cant prob­lems. In gen­eral terms, these prob­lems were due to the com­plex­ity, nov­elty, and poorly under­stood nature of the tasks our sys­tems attempted, and were wors­ened by the fact that peo­ple write so dif­fer­ently. This meant in par­tic­u­lar that corpus-​​based KA approaches suf­fered because it was impos­si­ble to assem­ble a siz­able cor­pus of high-​​quality con­sis­tent man­u­ally writ­ten texts in our domains; and struc­tured expert-​​oriented KA tech­niques suf­fered because experts dis­agreed and because we could not get enough infor­ma­tion about spe­cial and unusual cases to build robust sys­tems. We believe that such prob­lems are likely to affect many other NLG sys­tems as well. In the long term, we hope that new KA tech­niques may emerge to help NLG sys­tem builders. In the shorter term, we believe that under­stand­ing how indi­vid­ual KA tech­niques can fail, and using a mix­ture of dif­fer­ent KA tech­niques with dif­fer­ent strengths and weak­nesses, can help devel­op­ers acquire NLG knowl­edge that is mostly correct.”

    natural-​​language-​​processing artificial-​​intelligence interesting-​​problems high-​​hanging-​​fruit machine-​​learning nudge-​​targets

  • [1105.2423] Cytoskele­ton and Cell Motility

    “The present arti­cle is an invited con­tri­bu­tion to the Ency­clo­pe­dia of Com­plex­ity and Sys­tem Sci­ence, Robert A. Mey­ers Ed., Springer New York (2009). It is a review of the bio­phys­i­cal mech­a­nisms that underly cell motility.…”

    bio­physics biol­ogy review i-​​used-​​to-​​do-​​this-​​stuff lovely

  • [1110.0671] Width Dis­tri­b­u­tions for Con­vex Reg­u­lar Polyhedra

    “The mean width is a mea­sure on three-​​dimensional con­vex bod­ies that enjoys equal sta­tus with vol­ume and sur­face area [Rota]. As the phrase sug­gests, it is the mean of a prob­a­bil­ity den­sity f. We ver­ify for­mu­las for mean widths of the reg­u­lar tetra­he­dron and the cube. Higher-​​order moments of f_​tetra and f_​cube have not been exam­ined until now. Assume that each poly­he­dron has edges of unit length. We deduce that the mean square width of the reg­u­lar tetra­he­dron is 1/3+(3+sqrt(3))/(3*pi) and the mean square width of the cube is 1+4/pi.”

    geom­e­try mathematical-​​recreations nudge-​​targets

  • [cs/​0305036] Using Dynamic Sim­u­la­tion in the Devel­op­ment of Con­struc­tion Machinery

    “As in the car indus­try for quite some time, dynamic sim­u­la­tion of com­plete vehi­cles is being prac­ticed more and more in the devel­op­ment of off-​​road machin­ery. How­ever, spe­cific ques­tions arise due not only to com­pany struc­ture and size, but espe­cially to the type of prod­uct. Tightly cou­pled, non-​​linear sub­sys­tems of dif­fer­ent domains make pre­dic­tion and opti­mi­sa­tion of the com­plete system’s dynamic behav­iour a chal­lenge. Fur­ther­more, the demand for ver­sa­tile machines leads to some­times con­tra­dic­tory tar­get require­ments and can turn the design process into a hunt for the least painful com­pro­mise. This can be avoided by pro­found sys­tem knowl­edge, assisted by simulation-​​driven prod­uct devel­op­ment. This paper gives an overview of joint research into this issue by Volvo Wheel Load­ers and Linkop­ing Uni­ver­sity on that mat­ter, lists the results of a related lit­er­a­ture review and intro­duces the term “oper­ate­abil­ity”. Rather than giv­ing detailed answers, the prob­lem space for ongo­ing and future research is exam­ined and pos­si­ble solu­tions are sketched.”

    engineering-​​design design-​​automation mod­el­ing dynamical-​​systems man­u­fac­tur­ing nudge-​​targets

Items of some interest…

Posted on by

These are my recent Pin​board​.in links:

  • [1101.4003] Dyna-​​H: a heuris­tic plan­ning rein­force­ment learn­ing algo­rithm applied to role-​​playing-​​game strat­egy deci­sion systems

    “In a Role-​​Playing Game, find­ing opti­mal tra­jec­to­ries is one of the most impor­tant tasks. In fact, the strat­egy deci­sion sys­tem becomes a key com­po­nent of a game engine. Deter­min­ing the way in which deci­sions are taken (online, batch or sim­u­lated) and the con­sumed resources in deci­sion mak­ing (e.g. exe­cu­tion time, mem­ory) will influ­ence, in mayor degree, the game per­for­mance. When clas­si­cal search algo­rithms such as A* can be used, they are the very first option. Nev­er­the­less, such meth­ods rely on pre­cise and com­plete mod­els of the search space, and there are many inter­est­ing sce­nar­ios where their appli­ca­tion is not pos­si­ble. Then, model free meth­ods for sequen­tial deci­sion mak­ing under uncer­tainty are the best choice. In this paper, we pro­pose a heuris­tic plan­ning strat­egy to incor­po­rate the abil­ity of heuristic-​​search in path-​​finding into a Dyna agent. The pro­posed Dyna-​​H algo­rithm, as A* does, selects branches more likely to pro­duce out­comes than other branches. Besides, it has the advan­tages of being a model-​​free online rein­force­ment learn­ing algo­rithm. The pro­posal was eval­u­ated against the one-​​step Q-​​Learning and Dyna-​​Q algo­rithms obtain­ing excel­lent exper­i­men­tal results: Dyna-​​H sig­nif­i­cantly over­comes both meth­ods in all exper­i­ments. We sug­gest also, a func­tional anal­ogy between the pro­posed sam­pling from worst tra­jec­to­ries heuris­tic and the role of dreams (e.g. night­mares) in human behavior.”

    plan­ning machine-​​learning nudge-​​targets easy-​​pickins

  • [0908.3565] Dis­trib­uted Loca­tion Opti­miza­tion for Sen­sors with Lim­ited Range Het­ero­ge­neous Capa­bil­i­ties using Gen­er­al­ized Voronoi Partition

    “In this paper a gen­er­al­iza­tion of the Voronoi par­ti­tion is used for solv­ing a het­ero­ge­neous dis­trib­uted loca­tional opti­miza­tion prob­lem for autonomous agents, such as AGVs, UAVs, etc. The prob­lem addressed is of opti­mal deploy­ment of agents equipped with sen­sors, hav­ing het­ero­ge­neous capa­bil­i­ties, and lim­ited range, to max­i­mize sen­sor cov­er­age. An objec­tive func­tion for opti­mal deploy­ment of agents is for­mu­lated, and its crit­i­cal points are deter­mined. The opti­mal deploy­ment is shown to be the gen­er­al­ized cen­troidal Voronoi con­fig­u­ra­tion in which the agents are located at the cen­troids of the cor­re­spond­ing gen­er­al­ized Voronoi cells. For­mal results on sta­bil­ity, con­ver­gence, and on spa­tial dis­tri­b­u­tion of the pro­posed con­trol laws respon­si­ble for agent motion, under some con­straints on the agents’ speeds and limit on sen­sor range are pro­vided. The the­o­ret­i­cal results are sup­ported with illus­tra­tive simulation”

    agent-​​based coor­di­na­tion sensor-​​networks nudge-​​targets emergent-​​design

  • [1106.6058] Sta­bil­ity of strate­gies in payoff-​​driven evo­lu­tion­ary games on networks

    “We con­sider a net­work of cou­pled agents play­ing the Prisoner’s Dilemma game, in which play­ers are allowed to pick a strat­egy in the inter­val [0,1], with 0 cor­re­spond­ing to defec­tion, 1 to coop­er­a­tion, and inter­me­di­ate val­ues rep­re­sent­ing mixed strate­gies in which each player may act as a coop­er­a­tor or a defec­tor over a large num­ber of inter­ac­tions with a cer­tain prob­a­bil­ity. Our model is payoff-​​driven, i.e., we assume that the level of accu­mu­lated pay­off at each node is a rel­e­vant para­me­ter in the selec­tion of strate­gies. Also, we con­sider that each player chooses his/​her strat­egy in a con­text of lim­ited infor­ma­tion. We present a deter­min­is­tic non­lin­ear model for the evo­lu­tion of strate­gies. We show that the final strate­gies depend on the net­work struc­ture and on the choice of the para­me­ters of the game. We find that polar­ized strate­gies (pure cooperator/​defector states) typ­i­cally emerge when (i) the net­work con­nec­tions are sparse, (ii) the net­work degree dis­tri­b­u­tion is het­ero­ge­neous, (iii) the net­work is assor­ta­tive, and sur­pris­ingly, (iv) the ben­e­fit of coop­er­a­tion is high.”

    prisoners’-dilemma agent-​​based network-​​theory artificial-​​life com­plex­ol­ogy nudge-​​targets

  • [1106.0296] The Emer­gence of Lead­er­ship in Social Networks

    “We study a net­worked ver­sion of the minor­ity game in which agents can choose to fol­low the choices made by a neigh­bour­ing agent in a social net­work. We show that for a wide vari­ety of net­works a lead­er­ship struc­ture always emerges, with most agents fol­low­ing the choice made by a few agents. We find a suit­able para­me­ter­i­sa­tion which high­lights the uni­ver­sal aspects of the behav­iour and which also indi­cates where results depend on the type of social network.”

    minority-​​game social-​​networks soci­ol­ogy agent-​​based network-​​theory

  • [1106.1816] Mon­i­tor­ing Teams by Over­hear­ing: A Multi-​​Agent Plan-​​Recognition Approach

    “Recent years are see­ing an increas­ing need for on-​​line mon­i­tor­ing of teams of coop­er­at­ing agents, e.g., for visu­al­iza­tion, or per­for­mance track­ing. How­ever, in mon­i­tor­ing deployed teams, we often can­not rely on the agents to always com­mu­ni­cate their state to the mon­i­tor­ing sys­tem. This paper presents a non-​​intrusive approach to mon­i­tor­ing by ‘over­hear­ing’, where the mon­i­tored team’s state is inferred (via plan-​​recognition) from team-​​members’ rou­tine com­mu­ni­ca­tions, exchanged as part of their coor­di­nated task exe­cu­tion, and observed (over­heard) by the mon­i­tor­ing sys­tem. Key chal­lenges in this approach include the demand­ing run-​​time require­ments of mon­i­tor­ing, the scarce­ness of obser­va­tions (increas­ing mon­i­tor­ing uncer­tainty), and the need to scale-​​up mon­i­tor­ing to address poten­tially large teams. To address these, we present a set of com­ple­men­tary novel tech­niques, exploit­ing knowl­edge of the social struc­tures and pro­ce­dures in the mon­i­tored team: (i) an effi­cient prob­a­bilis­tic plan-​​recognition algo­rithm, well-​​suited for pro­cess­ing com­mu­ni­ca­tions as obser­va­tions; (ii) an approach to exploit­ing knowl­edge of the team’s social behav­ior to pre­dict future obser­va­tions dur­ing exe­cu­tion (reduc­ing mon­i­tor­ing uncer­tainty); and (iii) mon­i­tor­ing algo­rithms that trade expres­siv­ity for scal­a­bil­ity, rep­re­sent­ing only cer­tain use­ful mon­i­tor­ing hypothe­ses, but allow­ing for any num­ber of agents and their dif­fer­ent activ­i­ties to be rep­re­sented in a sin­gle coher­ent entity. We present an empir­i­cal eval­u­a­tion of these tech­niques, in com­bi­na­tion and apart, in mon­i­tor­ing a deployed team of agents, run­ning on machines phys­i­cally dis­trib­uted across the coun­try, and engaged in com­plex, dynamic task exe­cu­tion. We also com­pare the per­for­mance of these tech­niques to human expert and novice mon­i­tors, and show that the tech­niques pre­sented are capa­ble of mon­i­tor­ing at human-​​expert lev­els, despite the dif­fi­culty of the task.”

    emergent-​​design agent-​​based swarms coor­di­na­tion nudge

  • [1011.2861] A Com­pre­hen­sive Work­flow for General-​​Purpose Neural Mod­el­ing with Highly Con­fig­urable Neu­ro­mor­phic Hard­ware Systems

    “In this paper we present a method­olog­i­cal frame­work that meets novel require­ments emerg­ing from upcom­ing types of accel­er­ated and highly con­fig­urable neu­ro­mor­phic hard­ware sys­tems. We describe in detail a device with 45 mil­lion pro­gram­ma­ble and dynamic synapses that is cur­rently under devel­op­ment, and we sketch the con­cep­tual chal­lenges that arise from tak­ing this plat­form into oper­a­tion. More specif­i­cally, we aim at the estab­lish­ment of this neu­ro­mor­phic sys­tem as a flex­i­ble and neu­ro­sci­en­tif­i­cally valu­able mod­el­ing tool that can be used by non-​​hardware-​​experts. We con­sider var­i­ous func­tional aspects to be cru­cial for this pur­pose, and we intro­duce a con­sis­tent work­flow with detailed descrip­tions of all involved mod­ules that imple­ment the sug­gested steps: The inte­gra­tion of the hard­ware inter­face into the simulator-​​independent model descrip­tion lan­guage PyNN; a fully auto­mated trans­la­tion between the PyNN domain and appro­pri­ate hard­ware con­fig­u­ra­tions; an exe­cutable spec­i­fi­ca­tion of the future neu­ro­mor­phic sys­tem that can be seam­lessly inte­grated into this biology-​​to-​​hardware map­ping process as a test bench for all soft­ware lay­ers and pos­si­ble hard­ware design mod­i­fi­ca­tions; an eval­u­a­tion scheme that deploys mod­els from a ded­i­cated bench­mark library, com­pares the results gen­er­ated by vir­tual or pro­to­type hard­ware devices with ref­er­ence soft­ware sim­u­la­tions and ana­lyzes the dif­fer­ences. The inte­gra­tion of these com­po­nents into one hardware-​​software work­flow pro­vides an ecosys­tem for ongo­ing prepar­a­tive stud­ies that sup­port the hard­ware design process and rep­re­sents the basis for the matu­rity of the model-​​to-​​hardware map­ping soft­ware. The func­tion­al­ity and flex­i­bil­ity of the lat­ter is proven with a vari­ety of exper­i­men­tal results.”

    neural-​​networks biologically-​​inspired elec­tron­ics emergent-​​design nudge-​​targets

Items of some interest…

Posted on by

These are my recent Pin​board​.in links:

  • [1106.4577] Inter­ac­tive Exe­cu­tion Mon­i­tor­ing of Agent Teams

    “There is an increas­ing need for auto­mated sup­port for humans mon­i­tor­ing the activ­ity of dis­trib­uted teams of coop­er­at­ing agents, both human and machine. We char­ac­ter­ize the domain-​​independent chal­lenges posed by this prob­lem, and describe how prop­er­ties of domains influ­ence the chal­lenges and their solu­tions. We will con­cen­trate on dynamic, data-​​rich domains where humans are ulti­mately respon­si­ble for team behav­ior. Thus, the auto­mated aid should inter­ac­tively sup­port effec­tive and timely deci­sion mak­ing by the human. We present a domain-​​independent cat­e­go­riza­tion of the types of alerts a plan-​​based mon­i­tor­ing sys­tem might issue to a user, where each type gen­er­ally requires dif­fer­ent mon­i­tor­ing tech­niques. We describe a mon­i­tor­ing frame­work for inte­grat­ing many domain-​​specific and task-​​specific mon­i­tor­ing tech­niques and then using the con­cept of value of an alert to avoid oper­a­tor over­load. We use this frame­work to describe an exe­cu­tion mon­i­tor­ing approach we have used to imple­ment Exe­cu­tion Assis­tants (EAs) in two dif­fer­ent dynamic, data-​​rich, real-​​world domains to assist a human in mon­i­tor­ing team behav­ior. One domain (Army small unit oper­a­tions) has hun­dreds of mobile, geo­graph­i­cally dis­trib­uted agents, a com­bi­na­tion of humans, robots, and vehi­cles. The other domain (teams of unmanned ground and air vehi­cles) has a hand­ful of coop­er­at­ing robots. Both domains involve unpre­dictable adver­saries in the vicin­ity. Our approach cus­tomizes mon­i­tor­ing behav­ior for each spe­cific task, plan, and sit­u­a­tion, as well as for user pref­er­ences. Our EAs alert the human con­troller when reported events threaten plan exe­cu­tion or phys­i­cally threaten team mem­bers. Alerts were gen­er­ated in a timely man­ner with­out inun­dat­ing the user with too many alerts (less than 10 per­cent of alerts are unwanted, as judged by domain experts).”

    emergent-​​design multi-​​agent-​​systems engineering-​​design con­trol coor­di­na­tion nudge-​​targets

  • [1107.1322] Text Clas­si­fi­ca­tion: A Sequen­tial Read­ing Approach

    “We pro­pose to model the text clas­si­fi­ca­tion process as a sequen­tial deci­sion process. In this process, an agent learns to clas­sify doc­u­ments into top­ics while read­ing the doc­u­ment sen­tences sequen­tially and learns to stop as soon as enough infor­ma­tion was read for decid­ing. The pro­posed algo­rithm is based on a mod­eli­sa­tion of Text Clas­si­fi­ca­tion as a Markov Deci­sion Process and learns by using Rein­force­ment Learn­ing. Exper­i­ments on four dif­fer­ent clas­si­cal mono-​​label cor­pora show that the pro­posed approach per­forms com­pa­ra­bly to clas­si­cal SVM approaches for large train­ing sets, and bet­ter for small train­ing sets. In addi­tion, the model auto­mat­i­cally adapts its read­ing process to the quan­tity of train­ing infor­ma­tion provided.”

    text-​​classification natural-​​language-​​processing machine-​​learning nudge-​​targets

  • [1011.0362] Opti­miza­tion of arti­fi­cial flock­ings by means of anisotropy measurements

    “An effec­tive pro­ce­dure to deter­mine the opti­mal para­me­ters appear­ing in arti­fi­cial flock­ings is pro­posed in terms of opti­miza­tion prob­lems. We numer­i­cally exam­ine genetic algo­rithms (GAs) to deter­mine the opti­mal set of para­me­ters such as the weights for three essen­tial inter­ac­tions in BOIDS by Reynolds (1987) under ‘zero-​​collision’ and ‘no-​​breaking-​​up’ con­straints. As a fit­ness func­tion (the energy func­tion) to be max­i­mized by the GA, we choose the so-​​called the $gamma$-value of anisotropy which can be observed empir­i­cally in typ­i­cal flocks of star­ling. We con­firm that the GA suc­cess­fully finds the solu­tion hav­ing a large $gamma$-value leading-​​up to a strong anisotropy. The numer­i­cal expe­ri­ence shows that the pro­ce­dure might enable us to make more real­is­tic and effi­cient arti­fi­cial flock­ing of star­ling even in our per­sonal com­put­ers. We also eval­u­ate two dis­tinct types of inter­ac­tions in agents, namely, met­ric and topo­log­i­cal def­i­n­i­tions of inter­ac­tions. We con­firmed that the topo­log­i­cal def­i­n­i­tion can explain the empir­i­cal evi­dence much bet­ter than the met­ric def­i­n­i­tion does.”

    artificial-​​life network-​​theory sim­u­la­tion boids opti­miza­tion nudge-​​targets

  • [1106.5316] Online Cake Cut­ting (pub­lished version)

    “We pro­pose an online form of the cake cut­ting prob­lem. This mod­els sit­u­a­tions where agents arrive and depart dur­ing the process of divid­ing a resource. We show that well known fair divi­sion pro­ce­dures like cut-​​and-​​choose and the Dubins-​​Spanier mov­ing knife pro­ce­dure can be adapted to apply to such online prob­lems. We pro­pose some fair­ness prop­er­ties that online cake cut­ting pro­ce­dures can pos­sess like online forms of pro­por­tion­al­ity and envy-​​freeness. We also con­sider the impact of col­lu­sion between agents. Finally, we study the­o­ret­i­cally and empir­i­cally the com­pet­i­tive ratio of these online cake cut­ting pro­ce­dures. Based on its resis­tance to col­lu­sion, and its good per­for­mance in prac­tice, our results favour the online ver­sion of the cut-​​and-​​choose pro­ce­dure over the online ver­sion of the mov­ing knife procedure.”

    game-​​theory economic-​​crisis decision-​​making fair­ness nudge-​​targets