Tag Archives: complexology

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:

  • Cin­derella Doc­u­men­ta­tion : The­o­ret­i­cal Background

    “At first sight it is not clear whether this require­ment is sat­is­fi­able in gen­eral. Turn on your favorite sys­tem for doing inter­ac­tive geom­e­try or para­met­ric CAD and make the fol­low­ing exper­i­ment: Draw a hor­i­zon­tal line and con­struct two cir­cles of equal radius whose cen­ters are con­strained to slide along the line. Move the cir­cles to a posi­tion in which they inter­sect, and con­struct the upper point of inter­sec­tion of the two cir­cles. Now move one cir­cle so that its cen­ter passes through the cen­ter of the other cir­cle. Most prob­a­bly you will see that the point of inter­sec­tion sud­denly jumps from the upper inter­sec­tion to the lower one. This is what has hap­pened in all the sys­tems we have tried so far. Such behav­ior runs counter to our require­ment of con­ti­nu­ity: You make a small move, and a depen­dent point sud­denly jumps.”

    sim­u­la­tion geom­e­try algo­rithms rep­re­sen­ta­tion nudge-​​targets

  • Reli­gion and the City | New​geog​ra​phy​.com

    “He talks about items rang­ing from mul­ti­cul­tural sen­si­tiv­i­ties to tak­ing the arts seri­ous to “being famous for help­ing the poor.” The lat­ter was an item that jumped out at me because, as I’ve noted before, too many urban­ist argu­ments are basi­cally argu­ments for what I call “Star­bucks urban­ism.” If called on this, peo­ple will say, “But of course tran­sit will ben­e­fit the poor too.” But that’s not how it’s sold. Urban­ists ought to be famous for the way they design, imple­ment, and talk about their poli­cies as instru­ments for help­ing the poor and facil­i­tat­ing upward eco­nomic and social mobil­ity. There’s a lot of other good stuff in the video that’s rel­e­vant to urban­ism. For those who pre­fer read­ing, Keller also wrote a paper called “Our New Global Cul­ture: Min­istry in Cities, which says of itself: “This paper sur­veys the rise of global cities, the cul­ture and dom­i­nant world­views within these cities, and a frame­work for min­is­ter­ing in them.”?

    city-​​planning orga­ni­za­tion mar­ket­ing Workan­tile Coscience out­reach diver­sity man­age­ment

  • Study Hacks » Blog Archive » What You Know Mat­ters More Than What You Do

    “Accord­ing to my col­leagues, this star researcher tends to begin with tech­niques, not prob­lems. He first mas­ters a tech­nique that seems promis­ing (and when I say “mas­ter,” I mean it — he really goes deep in build­ing his under­stand­ing). He then uses this new tech­nique to seek out prob­lems that were once hard but now yield eas­ily. He’s rest­less in this quest, often mas­ter­ing sev­eral new tech­niques each year.”

    heuris­tics work­life inno­va­tion pro­duc­tiv­ity problem-​​seeing problem-​​solving

  • Jour­natic worker takes ‘This Amer­i­can Life’ inside out­sourced jour­nal­ism | Poynter.

    “If you’ve never heard of Jour­natic, that’s kind of the idea. The com­pany, which was founded in 2006, has a web­site that doesn’t appear on at least the first five pages of Google search results. Job open­ings, often posted on Craigslist or Jour​nal​is​mJobs​.com, once men­tioned the company’s name, but no longer. Jour­natic cur­rently works with “dozens” of media com­pa­nies, Tim­pone said, though he declined to name them. He’s spo­ken before of the real estate sec­tion Jour­natic pro­duces for the San Fran­cisco Chron­i­cle. He said more are sign­ing up all the time.”

    disintermediation-​​in-​​action jour­nal­ism work­life out­sourc­ing exposé

  • A Step-​​by-​​Step Guide to Tribal Lead­er­ship: Part 1: The Five Stages of Tribal Cul­ture « emer­gent by design

    “Tribal Lead­ers are the peo­ple who focus their efforts on upgrad­ing the tribal cul­ture. (upgrad­ing the words we use to describe our real­ity and the behav­iors we prac­tice that shape the direc­tion of our lives) They set the stan­dard of per­for­mance in their indus­tries, from pro­duc­tiv­ity and prof­itabil­ity to employee reten­tion, and attract tal­ent. Most of all, they help bring groups to unity by rec­og­niz­ing their ‘trib­al­ness’ – get­ting peo­ple to talk about the things they really care about, com­ing together around these com­mon causes, and form­ing mis­sions to make some­thing great hap­pen, and to live in great­ness. The goal of Tribal Lead­er­ship is to learn how to get peo­ple ‘unstuck’ – from unhelp­ful lan­guage and behav­iors, so we can level up and tran­si­tion into higher-​​performance, less stress­ful, and more fun states of Being.”

    i-​​hate-​​the-​​word-​​tribes col­lab­o­ra­tion lead­er­ship cultural-​​dynamics advice

  • [1206.6532] Esti­mat­ing Nui­sance Para­me­ters in Inverse Problems

    “Many inverse prob­lems include nui­sance para­me­ters which, while not of direct inter­est, are required to recover pri­mary para­me­ters. Struc­ture present in these prob­lems allows effi­cient opti­miza­tion strate­gies — a well known exam­ple is vari­able pro­jec­tion, where non­lin­ear least squares prob­lems which are lin­ear in some para­me­ters can be very effi­ciently opti­mized. In this paper, we extend the idea of pro­ject­ing out a sub­set over the vari­ables to a broad class of max­i­mum like­li­hood (ML) and max­i­mum a pos­te­ri­ori like­li­hood (MAP) prob­lems with nui­sance para­me­ters, such as vari­ance or degrees of free­dom. As a result, we are able to incor­po­rate nui­sance para­me­ter esti­ma­tion into large-​​scale con­strained and uncon­strained inverse prob­lem for­mu­la­tions. We apply the approach to a vari­ety of prob­lems, includ­ing esti­ma­tion of unknown vari­ance para­me­ters in the Gauss­ian model, degree of free­dom (d.o.f.) para­me­ter esti­ma­tion in the con­text of robust inverse prob­lems, auto­matic cal­i­bra­tion, and opti­mal exper­i­men­tal design. Using numer­i­cal exam­ples, we demon­strate improve­ment in recov­ery of pri­mary para­me­ters for sev­eral large– scale inverse prob­lems. The pro­posed approach is com­pat­i­ble with a wide vari­ety of algo­rithms and for­mu­la­tions, and its imple­men­ta­tion requires only minor mod­i­fi­ca­tions to exist­ing algorithms.”

    reinventing-​​the-​​wheel feature-​​extraction opti­miza­tion modeling-​​is-​​not-​​mathematics nudge-​​targets

  • [1206.4608] A Hybrid Algo­rithm for Con­vex Semi­def­i­nite Optimization

    “We present a hybrid algo­rithm for opti­miz­ing a con­vex, smooth func­tion over the cone of pos­i­tive semi­def­i­nite matri­ces. Our algo­rithm con­verges to the global opti­mal solu­tion and can be used to solve gen­eral large-​​scale semi­def­i­nite pro­grams and hence can be read­ily applied to a vari­ety of machine learn­ing prob­lems. We show exper­i­men­tal results on three machine learn­ing prob­lems (matrix com­ple­tion, met­ric learn­ing, and sparse PCA) . Our approach out­per­forms state-​​of-​​the-​​art algorithms.”

    algo­rithms opti­miza­tion computational-​​complexity spe­cial­iza­tion nudge-​​targets

  • [1206.6690] Gen­er­a­tion and Prop­er­ties of Snarks

    “For many of the unsolved prob­lems con­cern­ing cycles and match­ings in graphs it is known that it is suf­fi­cient to prove them for emph{snarks}, the class of non­triv­ial 3-​​regular graphs which can­not be 3-​​edge coloured. In the first part of this paper we present a new algo­rithm for gen­er­at­ing all non-​​isomorphic snarks of a given order. Our imple­men­ta­tion of the new algo­rithm is 14 times faster than pre­vi­ous pro­grams for gen­er­at­ing snarks, and 29 times faster for gen­er­at­ing weak snarks. Using this pro­gram we have gen­er­ated all non-​​isomorphic snarks on $nleq 36$ ver­tices. Pre­vi­ously lists up to $n=28$ ver­tices have been pub­lished. In the sec­ond part of the paper we ana­lyze the sets of gen­er­ated snarks with respect to a num­ber of prop­er­ties and con­jec­tures. We find that some of the strongest ver­sions of the cycle dou­ble cover con­jec­ture hold for all snarks of these orders, as does Jaeger’s Petersen colour­ing con­jec­ture, which in turn implies that Fulkerson’s con­jec­ture has no small coun­terex­am­ples. In con­trast to these pos­i­tive results we also find coun­terex­am­ples to eight pre­vi­ously pub­lished con­jec­tures con­cern­ing cycle cov­er­ings and the gen­eral cycle struc­ture of cubic graphs.”

    graph-​​theory com­bi­na­torics algo­rithms nudge-​​targets

  • [1206.6238] Entrain­abil­ity enhance­ment by period mis­match in biloop genetic oscillators

    “Effects of the period mis­match on entrain­ment prop­er­ties in two cou­pled genetic oscil­la­tors are stud­ied. The entrain­ment is cal­cu­lated with a phase reduc­tion approach and a Flo­quet mul­ti­plier analy­sis, and their depen­den­cies on cou­pling strength and the period ratio are inves­ti­gated in two genetic oscil­la­tor mod­els (smooth and relax­ation oscil­la­tors). We find that the exis­tence of the period mis­match induces an enhance­ment of entrain­ment in both smooth and relax­ation oscil­la­tors. By cal­cu­lat­ing Flo­quet mul­ti­pli­ers, we show that the enhance­ment mech­a­nism is based on the cou­pled oscil­la­tors which are in the vicin­ity of bifur­ca­tion on limit cycle.”

    biological-​​engineering emergent-​​design reaction-​​networks oscil­la­tors control-​​theory

  • [1206.4672] Effi­cient Active Algo­rithms for Hier­ar­chi­cal Clustering

    “Advances in sens­ing tech­nolo­gies and the growth of the inter­net have resulted in an explo­sion in the size of mod­ern datasets, while stor­age and pro­cess­ing power con­tinue to lag behind. This moti­vates the need for algo­rithms that are effi­cient, both in terms of the num­ber of mea­sure­ments needed and run­ning time. To com­bat the chal­lenges asso­ci­ated with large datasets, we pro­pose a gen­eral frame­work for active hier­ar­chi­cal clus­ter­ing that repeat­edly runs an off-​​the-​​shelf clus­ter­ing algo­rithm on small sub­sets of the data and comes with guar­an­tees on per­for­mance, mea­sure­ment com­plex­ity and run­time com­plex­ity. We instan­ti­ate this frame­work with a sim­ple spec­tral clus­ter­ing algo­rithm and pro­vide con­crete results on its per­for­mance, show­ing that, under some assump­tions, this algo­rithm recov­ers all clus­ters of size ?(log n) using O(n log^2 n) sim­i­lar­i­ties and runs in O(n log^3 n) time for a dataset of n objects. Through exten­sive exper­i­men­ta­tion we also demon­strate that this frame­work is prac­ti­cally alluring.”

    clus­ter­ing algo­rithms nudge-​​targets practically-​​alluring

  • Most Bla­tant Pro-​​ACTA Cam­paign So Far Is A Copy­right Monop­oly Vio­la­tion — Falkvinge on Infopolicy

    “This episode shows clearer than ever that the copy­right and patent monop­o­lies are not intended to be pro­tec­tive of inno­va­tion or pro­tec­tive of the econ­omy. They’re obvi­ously too com­plex even for their strongest sup­port­ers and lob­by­ists to under­stand and adhere to. Rather, they are intended as legal clubs to be used by the now-​​rich incum­bents against resource-​​strapped upstarts. The copy­right and patent monop­o­lies are only pro­tec­tive of the past, pro­tec­tive against the present and future of inno­va­tion, cre­ativ­ity, and economy.”

    copy­right intellectual-​​property cor­po­ratism public-​​policy

  • [1112.5218] Pat­terns of neu­tral diver­sity under gen­eral mod­els of selec­tive sweeps

    “Two major sources of sto­chas­tic­ity in the dynam­ics of neu­tral alle­les result from resam­pling of finite pop­u­la­tions (genetic drift) and the ran­dom genetic back­ground of nearby selected alle­les on which the neu­tral alle­les are found (linked selec­tion). There is now good evi­dence that linked selec­tion plays an impor­tant role in shap­ing poly­mor­phism lev­els in a num­ber of species. One of the best inves­ti­gated mod­els of linked selec­tion is the recur­rent full sweep model, in which newly arisen selected alle­les fix rapidly. How­ever, the bulk of selected alle­les that sweep into the pop­u­la­tion may not be des­tined for rapid fix­a­tion. Here we develop a gen­eral model of recur­rent selec­tive sweeps in a coa­les­cent frame­work, one that gen­er­al­izes the recur­rent full sweep model to the case where selected alle­les do not sweep to fix­a­tion. We show that in a large pop­u­la­tion, only the ini­tial rapid increase of a selected allele affects the geneal­ogy at par­tially linked sites, which under fairly gen­eral assump­tions are unaf­fected by the sub­se­quent fate of the selected allele. We also apply the the­ory to a sim­ple model to inves­ti­gate the impact of recur­rent par­tial sweeps on lev­els of neu­tral diver­sity, and find that for a given reduc­tion in diver­sity, the impact of recur­rent par­tial sweeps on the fre­quency spec­trum at neu­tral sites is deter­mined pri­mar­ily by the fre­quen­cies achieved by the selected alle­les. Con­se­quently, recur­rent sweeps of selected alle­les to low fre­quen­cies can have a pro­found effect on lev­els of diver­sity but can leave the fre­quency spec­trum rel­a­tively unper­turbed. In fact, the lim­it­ing coa­les­cent model under a high rate of sweeps to low fre­quency is iden­ti­cal to the stan­dard neu­tral model. The gen­eral model of selec­tive sweeps we describe goes some way towards pro­vid­ing a more flex­i­ble frame­work to describe genomic pat­terns of diver­sity than is cur­rently available.”

    neutral-​​networks evolutionary-​​dynamics fitness-​​landscapes diver­sity theoretical-​​biology

  • [1206.3520] Recov­er­ing the tree-​​like trend of evo­lu­tion despite exten­sive lat­eral genetic trans­fer: A prob­a­bilis­tic analysis

    “In the pres­ence of high­ways, deal­ing with more gen­eral net­work set­tings would be desir­able. Also our def­i­n­i­tion of high­ways as con­nect­ing two edges is some­what restric­tive. In gen­eral, one is also inter­ested in pref­er­en­tial genetic trans­fers between clades.”

    algo­rithms lateral-​​gene-​​transfer cladis­tics phy­lo­ge­net­ics inverse-​​problems ontol­ogy modeling-​​is-​​not-​​mathematics nudge-​​targets

  • [1206.3279] The Phy­lo­ge­netic Indian Buf­fet Process: A Non-​​Exchangeable Non­para­met­ric Prior for Latent Features

    “Non­para­met­ric Bayesian mod­els are often based on the assump­tion that the objects being mod­eled are exchange­able. While appro­pri­ate in some appli­ca­tions (e.g., bag-​​of-​​words mod­els for doc­u­ments), exchange­abil­ity is some­times assumed sim­ply for com­pu­ta­tional rea­sons; non-​​exchangeable mod­els might be a bet­ter choice for appli­ca­tions based on sub­ject mat­ter. Draw­ing on ideas from graph­i­cal mod­els and phy­lo­ge­net­ics, we describe a non-​​exchangeable prior for a class of non­para­met­ric latent fea­ture mod­els that is nearly as effi­cient com­pu­ta­tion­ally as its exchange­able coun­ter­part. Our model is applic­a­ble to the gen­eral set­ting in which the depen­den­cies between objects can be expressed using a tree, where edge lengths indi­cate the strength of rela­tion­ships. We demon­strate an appli­ca­tion to mod­el­ing prob­a­bilis­tic choice.”

    sta­tis­tics algo­rithms ontol­ogy col­li­ga­tion feature-​​extraction philosophy-​​of-​​science nudge-​​targets

  • “The Eurozone’s Strat­egy is a Dis­as­ter” « naked capitalism

    “Why should Ger­man and other tax­pay­ers, mostly from the north, pay for the oth­ers, mostly from the south? Because their gov­ern­ments are respon­si­ble for the dis­as­trous sit­u­a­tion we are in.”

    financial-​​crisis public-​​policy eco­nom­ics cultural-​​dynamics fair-​​weather-​​bosses

  • [1206.6504] An Abstract Approach to Strat­i­fi­ca­tion in Lin­ear Logic

    “We study the notion of strat­i­fi­ca­tion, as used in sub­sys­tems of lin­ear logic with low com­plex­ity bounds on the cut-​​elimination pro­ce­dure (the so-​​called light log­ics), from an abstract point of view, intro­duc­ing a log­i­cal sys­tem in which strat­i­fi­ca­tion is han­dled by a sep­a­rate modal­ity. This modal­ity, which is a gen­er­al­iza­tion of the para­graph modal­ity of Girard’s light lin­ear logic, arises from a gen­eral cat­e­gor­i­cal con­struc­tion applic­a­ble to all mod­els of lin­ear logic. We thus learn that strat­i­fi­ca­tion may be for­mu­lated inde­pen­dently of expo­nen­tial modal­i­ties; when it is forced to be con­nected to expo­nen­tial modal­i­ties, it yields inter­est­ing com­plex­ity prop­er­ties. In par­tic­u­lar, from our analy­sis stem three alter­na­tive refor­mu­la­tions of Bail­lot and Mazza’s lin­ear logic by lev­els: one geo­met­ric, one inter­ac­tive, and one semantic.”

    linear-​​logic logic-​​programming for­mal­iza­tion nudge-​​targets rep­re­sen­ta­tion

  • [1205.0802] Win-​​stay-​​lose-​​learn pro­motes coop­er­a­tion in the spa­tial prisoner’s dilemma game

    “Hold­ing on to one’s strat­egy is nat­ural and com­mon if the later war­rants suc­cess and sat­is­fac­tion. This goes against wide­spread sim­u­la­tion prac­tices of evo­lu­tion­ary games, where play­ers fre­quently con­sider chang­ing their strat­egy even though their pay­offs may be mar­gin­ally dif­fer­ent than those of the other play­ers. Inspired by this obser­va­tion, we intro­duce an aspiration-​​based win-​​stay-​​lose-​​learn strat­egy updat­ing rule into the spa­tial prisoner’s dilemma game. The rule is sim­ple and intu­itive, fore­see­ing strat­egy changes only by dis­sat­is­fied play­ers, who then attempt to adopt the strat­egy of one of their near­est neigh­bors, while the strate­gies of sat­is­fied play­ers are not sub­ject to change. We find that the pro­posed win-​​stay-​​lose-​​learn rule pro­motes the evo­lu­tion of coop­er­a­tion, and it does so very robustly and inde­pen­dently of the ini­tial con­di­tions. In fact, we show that even a minute ini­tial frac­tion of coop­er­a­tors may be suf­fi­cient to even­tu­ally secure a highly coop­er­a­tive final state. In addi­tion to exten­sive sim­u­la­tion results that sup­port our con­clu­sions, we also present results obtained by means of the pair approx­i­ma­tion of the stud­ied game. Our find­ings con­tinue the suc­cess story of related win-​​stay strat­egy updat­ing rules, and by doing so reveal new ways of resolv­ing the prisoner’s dilemma.”

    game-​​theory agent-​​based com­plex­ol­ogy

  • The Rude Pundit

    “And there’s every­thing you need to know about the Repub­li­can Party. “Shit hap­pened, but so what? Peo­ple were vic­tim­ized, but why should we care? That was nearly forty years ago.” The demen­tia in refus­ing to look back­ward, refus­ing to make up for the mis­takes of the past, whether it’s the Bush tax cuts or the lies that got us into war or the lies that got us into this finan­cial cri­sis, makes us damned to repeat. ”

    sum­mary pol­i­tics Repub­li­cans

Items of some interest:

Posted on by

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

  • Tar­get Expres­sion Exam­ples — Eureqa Formulize

    ‘The “Tar­get Expres­sion” in the field at the top of the Set Tar­get tab tells For­mulize what type of model to search for. By default, the tar­get expres­sion is an equa­tion where y (or, if there’s no y, what­ever vari­able is in col­umn A) is mod­eled as a func­tion of all other vari­ables. To edit the tar­get expres­sion, click on it, then make the desired alter­ations. Use the spe­cial func­tion f(…) to spec­ify the part of the equa­tion that For­mulize will attempt to fill in; For­mulize will search for the for­mula f(…) using the vari­ables you put inside the parentheses.’

    for­mulize eureqa genetic-​​programming symbolic-​​regression mod­el­ing doc­u­men­ta­tion

  • A New Solu­tion to the Puz­zle of Sim­plic­ity — PhilSci-​​Archive

    “Explain­ing the con­nec­tion, if any, between sim­plic­ity and truth is among the deep­est prob­lems fac­ing the phi­los­o­phy of sci­ence, sta­tis­tics, and machine learn­ing. Say that an effi­cient truth-​​finding method min­i­mizes worst-​​case costs en route to con­verg­ing to the true answer to a the­ory choice prob­lem. Let the costs con­sid­ered include the num­ber of times a false answer is selected, the num­ber of times opin­ion is reversed, and the times at which the rever­sals occur. It is demon­strated that (1)always choos­ing the sim­plest the­ory com­pat­i­ble with expe­ri­ence and (2) hang­ing onto it while it remains sim­plest is both nec­es­sary and suf­fi­cient for efficiency.”

    via:cshalizi occam’s-razor sim­plic­ity model-​​discovery expla­na­tion philosophy-​​of-​​science

  • [1206.4599] A Uni­fied Robust Clas­si­fi­ca­tion Model

    “A wide vari­ety of machine learn­ing algo­rithms such as sup­port vec­tor machine (SVM), min­i­max prob­a­bil­ity machine (MPM), and Fisher dis­crim­i­nant analy­sis (FDA), exist for binary clas­si­fi­ca­tion. The pur­pose of this paper is to pro­vide a uni­fied clas­si­fi­ca­tion model that includes the above mod­els through a robust opti­miza­tion approach. This uni­fied model has sev­eral ben­e­fits. One is that the exten­sions and improve­ments intended for SVM become applic­a­ble to MPM and FDA, and vice versa. Another ben­e­fit is to pro­vide the­o­ret­i­cal results to above learn­ing meth­ods at once by deal­ing with the uni­fied model. We give a sta­tis­ti­cal inter­pre­ta­tion of the uni­fied clas­si­fi­ca­tion model and pro­pose a non-​​convex opti­miza­tion algo­rithm that can be applied to non-​​convex vari­ants of exist­ing learn­ing methods.”

    clas­si­fi­ca­tion algo­rithms lumpers-​​and-​​spliters-​​sittin-​​in-​​a-​​tree

  • CUDA Down­loads | NVIDIA Devel­oper Zone

    This release of the CUDA Toolkit  enables devel­op­ment using GPUs using the Kepler archi­tec­ture, such as the GeForce GTX680. Fea­ture and func­tion­al­ity builds on the foun­da­tion of the CUDA 4.1 release which intro­duced: A new  LLVM-​​based CUDA com­piler 1000+ new image pro­cess­ing func­tions Redesigned Visual Pro­filer with auto­mated per­for­mance analy­sis and inte­grated expert guidance

    CUDA GPU pro­gram­ming library MacOS

  • [1206.2057] Fin­ish­ing Flows Quickly with Pre­emp­tive Scheduling

    “Today’s data cen­ters face extreme chal­lenges in pro­vid­ing low latency. How­ever, fair shar­ing, a prin­ci­ple com­monly adopted in cur­rent con­ges­tion con­trol pro­to­cols, is far from opti­mal for sat­is­fy­ing latency require­ments. We pro­pose Pre­emp­tive Dis­trib­uted Quick (PDQ) flow sched­ul­ing, a pro­to­col designed to com­plete flows quickly and meet flow dead­lines. PDQ enables flow pre­emp­tion to approx­i­mate a range of sched­ul­ing dis­ci­plines. For exam­ple, PDQ can emu­late a short­est job first algo­rithm to give pri­or­ity to the short flows by paus­ing the con­tend­ing flows. PDQ bor­rows ideas from cen­tral­ized sched­ul­ing dis­ci­plines and imple­ments them in a fully dis­trib­uted man­ner, mak­ing it scal­able to today’s data cen­ters. Fur­ther, we develop a mul­ti­path ver­sion of PDQ to exploit path diver­sity. Through exten­sive packet-​​level and flow-​​level sim­u­la­tion, we demon­strate that PDQ sig­nif­i­cantly out­per­forms TCP, RCP and D3 in data cen­ter envi­ron­ments. We fur­ther show that PDQ is sta­ble, resilient to packet loss, and pre­serves nearly all its per­for­mance gains even given inac­cu­rate flow information.”

    queuing-​​models engineering-​​design algo­rithms performance-​​measure nudge-​​targets

  • [1206.2216] Com­plex Sys­tems Sci­ence: Dreams of Uni­ver­sal­ity, Real­ity of Interdisciplinarity

    “Using a large data­base (~ 215 000 records) of rel­e­vant arti­cles, we empir­i­cally study the “com­plex sys­tems” field and its claims to find uni­ver­sal prin­ci­ples apply­ing to sys­tems in gen­eral. The study of ref­er­ences shared by the papers allows us to obtain a global point of view on the struc­ture of this highly inter­dis­ci­pli­nary field. We show that its over­all coher­ence does not arise from a uni­ver­sal the­ory but instead from com­pu­ta­tional tech­niques and fruit­ful adap­ta­tions of the idea of self-​​organization to spe­cific sys­tems. We also find that com­mu­ni­ca­tion between dif­fer­ent dis­ci­plines goes through spe­cific “trad­ing zones”, ie sub-​​communities that cre­ate an inter­face around spe­cific tools (a DNA microchip) or con­cepts (a network).”

    via:cshalizi com­plex­ol­ogy pro­fes­sion­al­iza­tion network-​​theory disappointed-​​by-​​lack-​​of-​​Abbott-​​ref citation-​​networks

Items of some interest:

Posted on by

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

  • [0912.1523] Deco­her­ence in Search Algorithms

    “Recently sev­eral quan­tum search algo­rithms based on quan­tum walks were pro­posed. Those algo­rithms dif­fer from Grover’s algo­rithm in many aspects. The goal is to find a marked ver­tex in a graph faster than clas­si­cal algo­rithms. Since the imple­men­ta­tion of those new algo­rithms in quan­tum com­put­ers or in other quan­tum devices is error-​​prone, it is impor­tant to ana­lyze their robust­ness under deco­her­ence. In this work we ana­lyze the impact of deco­her­ence on quan­tum search algo­rithms imple­mented on two-​​dimensional grids and on hypercubes.”

    quan­tums search-​​algorithms robust­ness nudge-​​targets

  • The Man­i­fest Des­tiny of Arti­fi­cial Intel­li­gence » Amer­i­can Scientist

    “Arti­fi­cial intel­li­gence began with an ambi­tious research agenda: To endow machines with some of the traits we value most highly in ourselves—the fac­ulty of rea­son, skill in solv­ing prob­lems, cre­ativ­ity, the capac­ity to learn from expe­ri­ence. Early results were promis­ing. Com­put­ers were pro­grammed to play check­ers and chess, to prove the­o­rems in geom­e­try, to solve anal­ogy puz­zles from IQ tests, to rec­og­nize let­ters of the alpha­bet. Mar­vin Min­sky, one of the pio­neers, declared in 1961: “We are on the thresh­old of an era that will be strongly influ­enced, and quite pos­si­bly dom­i­nated, by intel­li­gent problem-​​solving machines.””

    artificial-​​intelligence nudge-​​book cultural-​​assumptions degenerate-​​research-​​programmes

  • About « Digress​.it

    “Digress​.it is a Word­Press plu­gin that offers paragraph-​​level com­ment­ing in the mar­gins of a text. Digress​.it is geared toward in-​​depth dis­cus­sions of longer doc­u­ments: arti­cle, essay or even book-​​length.

    Blogs aren’t bad for hav­ing con­ver­sa­tions, but com­ments tend to get unwieldy, and can feel detached when the orig­i­nal post is long. To solve this, Digress​.it lets you run blog-​​style com­ment threads — digres­sions, if you will — off of indi­vid­ual para­graphs. To do this effi­ciently, we’ve re-​​imagined the con­ven­tional post-​​discussion hier­ar­chy of blogs, mov­ing the com­ment area from beneath the post to beside it (float­ing to the right) — hear­ken­ing back to the age-​​old prac­tice of scrib­bling in page mar­gins. We see great pos­si­bil­i­ties for edu­ca­tors, lit­er­ary groups, polit­i­cal or civic activists, legal schol­ars, and pretty much any­one who wants to do a com­mu­nal read­ing and encour­age discussion.”

    blog­ging social-​​media con­ver­sa­tion pub­lish­ing word­press

  • [1205.3676] Con­sen­sus of Multi-​​Agent Net­works in the Pres­ence of Adver­saries Using Only Local Information

    “This paper addresses the prob­lem of resilient con­sen­sus in the pres­ence of mis­be­hav­ing nodes. Although it is typ­i­cal to assume knowl­edge of at least some non­lo­cal infor­ma­tion when study­ing secure and fault-​​tolerant con­sen­sus algo­rithms, this assump­tion is not suit­able for large-​​scale dynamic net­works. To rem­edy this, we empha­size the use of local strate­gies to deal with resilience to secu­rity breaches. We study a con­sen­sus pro­to­col that uses only local infor­ma­tion and we con­sider worst-​​case secu­rity breaches, where the com­pro­mised nodes have full knowl­edge of the net­work and the inten­tions of the other nodes. We pro­vide nec­es­sary and suf­fi­cient con­di­tions for the nor­mal nodes to reach con­sen­sus despite the influ­ence of the mali­cious nodes under dif­fer­ent threat assump­tions. These con­di­tions are stated in terms of a novel graph-​​theoretic prop­erty referred to as net­work robustness.”

    agent-​​based game-​​theory network-​​theory social-​​dynamics nudge-​​targets algo­rithms

  • [1205.2604] The Infi­nite Latent Events Model

    “We present the Infi­nite Latent Events Model, a non­para­met­ric hier­ar­chi­cal Bayesian dis­tri­b­u­tion over infi­nite dimen­sional Dynamic Bayesian Net­works with binary state rep­re­sen­ta­tions and noisy-​​OR-​​like tran­si­tions. The dis­tri­b­u­tion can be used to learn struc­ture in dis­crete time­series data by simul­ta­ne­ously infer­ring a set of latent events, which events fired at each timestep, and how those events are causally linked. We illus­trate the model on a sound fac­tor­iza­tion task, a net­work topol­ogy iden­ti­fi­ca­tion task, and a video game task.”

    seems-​​familiar-​​somehow

  • Space­Funcs­Doc — OpenOpt

    “The fol­low­ing geom­e­try objects are imple­mented for now in Space­Funcs mod­ule:
    Point, Line, Line­Seg­ment, Cir­cle, Plane, Tri­an­gle, Poly­gon, Sphere, Poly­tope, Poly­he­dron, Tetra­he­dron. Some more are intended to be done in next Space­Funcs release.”

    geom­e­try nudge-​​targets numerical-​​methods libraries

  • GitHub does dot­files — dot​files​.github​.com

    “Why would I want my dot­files on GitHub?”

    system-​​administration Unix GitHub hints tuto­r­ial

  • [1205.4591] ForeCA: Fore­castable Com­po­nent Analysis

    “Blind source sep­a­ra­tion (BSS) tech­niques are often applied to mul­ti­vari­ate time series with the goal to obtain bet­ter fore­casts. But BSS and the need for bet­ter fore­casts are often treated sep­a­rately, in the sense that find­ing an opti­mally trans­formed (sub-)space has noth­ing to do with the aim to pre­dict well. Here I intro­duce Fore­castable Com­po­nent Analy­sis (ForeCA), a new BSS tech­nique for tem­po­rally depen­dent sig­nals that uses fore­casta­bil­ity as the explicit objec­tive in find­ing an opti­mal trans­for­ma­tion. It sep­a­rates the sig­nal into the fore­castable, $mathbf{F}$, and the orthog­o­nal white noise space, $mathbf{F}^{bot}$. Sim­u­la­tions and appli­ca­tions to finan­cial data show that ForeCA suc­cess­fully finds sig­nals that can be used to fore­cast. ForeCA there­fore auto­mat­i­cally dis­cov­ers infor­ma­tive struc­ture in mul­ti­vari­ate sig­nals. The R pack­age (this http URL) will be pub­licly avail­able on CRAN upon pub­li­ca­tion of the manuscript.”

    sta­tis­tics algo­rithms component-​​analysis pre­dic­tion

  • [1201.5597] The mate-​​in-​​n prob­lem of infi­nite chess is decidable

    “…The proof pro­ceeds by show­ing that the mate-​​in-​​n prob­lem is express­ible in what we call the first-​​order struc­ture of chess, which we prove (in the rel­e­vant frag­ment) is an auto­matic struc­ture, whose the­ory is there­fore decid­able. Indeed, it is defin­able in Pres­burger arith­metic. Unfor­tu­nately, this res­o­lu­tion of the mate-​​in-​​n prob­lem does not appear to set­tle the decid­abil­ity of the more gen­eral winning-​​position prob­lem, the prob­lem of deter­min­ing whether a des­ig­nated player has a win­ning strat­egy from a given posi­tion, since a posi­tion may admit a win­ning strat­egy with­out any bound on the num­ber of moves required. This issue is con­nected with trans­fi­nite game val­ues in infi­nite chess, and the exact value of the omega one of chess is not known.”

    mathematical-​​recreations game-​​theory proof­ing games unde­cid­abil­ity

  • [1203.5351] Activ­ity dri­ven mod­el­ing of dynamic networks

    “Net­work mod­el­ing plays a crit­i­cal role in iden­ti­fy­ing sta­tis­ti­cal reg­u­lar­i­ties and struc­tural prin­ci­ples com­mon to many sys­tems. The large major­ity of recent mod­el­ing approaches are con­nec­tiv­ity dri­ven. The struc­tural pat­terns of the net­work are at the basis of the mech­a­nisms rul­ing the net­work for­ma­tion. Con­nec­tiv­ity dri­ven mod­els nec­es­sar­ily pro­vide a time-​​aggregated rep­re­sen­ta­tion that may fail to describe the instan­ta­neous and fluc­tu­at­ing dynam­ics of many net­works. We address this chal­lenge by defin­ing the activ­ity poten­tial, a time invari­ant func­tion char­ac­ter­iz­ing the agents’ inter­ac­tions and con­struct­ing an activ­ity dri­ven model capa­ble of encod­ing the instan­ta­neous time descrip­tion of the net­work dynam­ics. The model pro­vides an expla­na­tion of struc­tural fea­tures such as the pres­ence of hubs, which sim­ply orig­i­nate from the het­ero­ge­neous activ­ity of agents. Within this frame­work, highly dynam­i­cal net­works can be described ana­lyt­i­cally, allow­ing a quan­ti­ta­tive dis­cus­sion of the biases induced by the time-​​aggregated rep­re­sen­ta­tions in the analy­sis of dynam­i­cal processes.”

    network-​​theory infer­ence sta­tis­tics com­plex­ol­ogy

Items of some interest:

Posted on by

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

  • Pub­lish­ing Has Per­ished: Long Live the Per­sonal Cloud | Cloud­line | Wired​.com

    “Even that arrange­ment wouldn’t be ideal, though. When a pub­lisher aban­dons an arti­cle of mine, it also aban­dons links to it from any page that referred to the arti­cle. In the sci­en­tific and aca­d­e­mic realms, dig­i­tal object iden­ti­fiers (DOIs) are used to mint name­spaces that can tran­scend the life­times (or atten­tion spans) of indi­vid­ual pub­lish­ers. That tech­nol­ogy hasn’t yet trick­led down to the rest of us, but I’d love to have my per­sonal cloud imple­ment such a scheme and be the resolver of last resort for my pub­lished work.”

    via:vielmetti pub­lish­ing archives extended-​​mind mem­ory make-​​it-​​so

  • [1206.1355] A Cov­er­age The­ory of Bista­tic Radar Net­works: Worst-​​Case Intru­sion Path and Opti­mal Deployment

    “In this paper, we study opti­mal radar deploy­ment for intru­sion detec­tion, with focus on net­work cov­er­age. In con­trast to the disk-​​based sens­ing model in a tra­di­tional sen­sor net­work, the detec­tion range of a bista­tic radar depends on the loca­tions of both the radar trans­mit­ter and radar receiver, and is char­ac­ter­ized by Cassini ovals. Fur­ther­more, in a net­work with mul­ti­ple radar trans­mit­ters and receivers, since any pair of trans­mit­ter and receiver can poten­tially form a bista­tic radar, the detec­tion ranges of dif­fer­ent bista­tic radars are cou­pled and the cor­re­spond­ing net­work cov­er­age is inti­mately related to the loca­tions of all trans­mit­ters and receivers, mak­ing the opti­mal deploy­ment design highly non-​​trivial. Clearly, the detectabil­ity of an intruder depends on the high­est SNR received by all pos­si­ble bista­tic radars. We focus on the worst-​​case intru­sion detectabil­ity, i.e., the min­i­mum pos­si­ble detectabil­ity along all pos­si­ble intru­sion paths. Although it is plau­si­ble to deploy radars on a short­est line seg­ment across the field, it is not always opti­mal in gen­eral, which we illus­trate via counter-​​examples. We then present a suf­fi­cient con­di­tion on the field geom­e­try for the opti­mal­ity of short­est line deploy­ment to hold. Fur­ther, we quan­tify the local struc­ture of detectabil­ity cor­re­spond­ing to a given deploy­ment order and spac­ings of radar trans­mit­ters and receivers, build­ing on which we char­ac­ter­ize the opti­mal deploy­ment to max­i­mize the worst-​​case intru­sion detectabil­ity. Our results show that the opti­mal deploy­ment loca­tions exhibit a bal­anced struc­ture. We also develop a polynomial-​​time approx­i­ma­tion algo­rithm for char­ac­ter­iz­ing the worse-​​case intru­sion path for any given loca­tions of radars under ran­dom deployment.”

    opti­miza­tion sim­u­la­tion nudge-​​targets coevo­lu­tion minimax-​​problems

  • [1206.0323] Fair­ness and Sta­bil­ity Analy­sis of Con­ges­tion Con­trol Schemes in Vehic­u­lar Ad-​​hoc Networks

    “Coop­er­a­tive vehi­cle safety (CVS) sys­tems oper­ate based on broad­cast of vehi­cle posi­tion and safety infor­ma­tion to neigh­bor­ing cars. The com­mu­ni­ca­tion medium of CVS is a vehic­u­lar ad-​​hoc net­work. One of the main chal­lenges in large scale deploy­ment of CVS sys­tems is the issue of scal­a­bil­ity. To address the scal­a­bil­ity prob­lem, sev­eral con­ges­tion con­trol meth­ods have been pro­posed and are cur­rently under field study. These algo­rithms adapt trans­mis­sion rate and power based on net­work mea­sures such as chan­nel busy ratio. We exam­ine two such algo­rithms and study their dynamic behav­ior in time and space to eval­u­ate sta­bil­ity (in time) and fair­ness (in space) prop­er­ties of these algo­rithms. We present sta­bil­ity con­di­tions and eval­u­ate sta­bil­ity and fair­ness of the algo­rithms through sim­u­la­tion exper­i­ments. Results show that there is a trade-​​off between fast con­ver­gence, tem­po­ral sta­bil­ity and spa­tial fair­ness. The proper ranges of para­me­ters for achiev­ing sta­bil­ity are pre­sented for the dis­cussed algo­rithms. Sta­bil­ity is ver­i­fied for all typ­i­cal road den­sity cases. Fair­ness is shown to be nat­u­rally achieved for some algo­rithms, while under the same con­di­tions other algo­rithms may suf­fer from unfair­ness issues. A method for resolv­ing unfair­ness is intro­duced and eval­u­ated through simulations.”

    robot­ics com­plex­ol­ogy emergent-​​design traffic-​​models collective-​​behavior performance-​​measure nudge-​​targets sim­u­la­tion

  • [1205.6147] A curvature-​​driven effec­tive attrac­tion in mul­ti­com­po­nent membranes

    “We study closed liq­uid mem­branes that seg­re­gate into three phases due to dif­fer­ences in the chem­i­cal and phys­i­cal prop­er­ties of its com­po­nents. The shape and in-​​plane mem­brane arrange­ment of the phases are cou­pled through phase-​​specific bend­ing ener­gies and line ten­sions. We use sim­u­lated anneal­ing Monte Carlo sim­u­la­tions to find low-​​energy struc­tures, allow­ing both phase arrange­ment and mem­brane shape to relax. The three-​​phase sys­tem is the sim­plest one in which there are mul­ti­ple inter­face pairs, allow­ing us to ana­lyze inter­fa­cial pref­er­ences and pair­wise dis­tinct line ten­sions. We observe the system’s pref­er­ence for inter­face pairs that max­i­mize dif­fer­ences in spon­ta­neous cur­va­ture. From a pat­tern selec­tion per­spec­tive, this acts as an effec­tive attrac­tion between phases of most dis­parate spon­ta­neous cur­va­ture. We show that this effec­tive attrac­tion is robust enough to per­sist even when the inter­face between these phases is the most penal­ized by line ten­sion. This effect is dri­ven by geom­e­try and not by any explicit component-​​component interaction.”

    sim­u­la­tion membrane-​​physics clas­si­fi­ca­tion phase-​​diagrams nudge-​​targets

  • [1205.2170] Col­lab­o­ra­tive Search on the Plane with­out Communication

    “We use dis­trib­uted com­put­ing tools to pro­vide a new per­spec­tive on the behav­ior of coop­er­a­tive bio­log­i­cal ensem­bles. We intro­duce the Ants Nearby Trea­sure Search (ANTS) prob­lem, a gen­er­al­iza­tion of the clas­si­cal cow-​​path prob­lem, which is rel­e­vant for col­lec­tive for­ag­ing in ani­mal groups. In the ANTS prob­lem, k iden­ti­cal (prob­a­bilis­tic) agents, ini­tially placed at some cen­tral loca­tion, col­lec­tively search for a trea­sure in the two-​​dimensional plane. The trea­sure is placed at a tar­get loca­tion by an adver­sary and the goal is to find it as fast as pos­si­ble as a func­tion of both k and D, where D is the dis­tance between the cen­tral loca­tion and the target.…”

    low-​​hanging-​​fruit nudge-​​targets agent-​​based autonomous-​​agents

  • [1206.1571] Steady-​​state fluc­tu­a­tions of a genetic feed­back loop: an exact solution

    “…For the case where the degra­da­tion rate of bound and free pro­tein is the same, our solu­tion is at vari­ance with a pre­vi­ous claim of an exact solu­tion (Hornos et al, Phys. Rev. E {bf 72}, 051907 (2005) and sub­se­quent stud­ies). We show explic­itly that this is due to an unphys­i­cal for­mu­la­tion of the under­ly­ing mas­ter equa­tion in those studies.”

    unphys­i­cal bio­chem­istry mod­els analytical-​​models-​​of-​​messy-​​old-​​life

  • [1202.0937] Com­pres­sive binary search

    Some­thing inter­est­ing but very dif­fi­cult in here about rep­re­sen­ta­tion the­ory for meta­heuris­tics, and prac­ti­cal (con­tex­tual) land­scape recon­fig­u­ra­tion. “In this paper we con­sider the prob­lem of locat­ing a nonzero entry in a high-​​dimensional vec­tor from pos­si­bly adap­tive lin­ear mea­sure­ments. We con­sider a recur­sive bisec­tion method which we dub the com­pres­sive binary search and show that it improves on what any non­adap­tive method can achieve. We also estab­lish a non-​​asymptotic lower bound that applies to all meth­ods, regard­less of their com­pu­ta­tional com­plex­ity. Com­bined, these results show that the com­pres­sive binary search is within a dou­ble log­a­rith­mic fac­tor of the opti­mal performance.”

    needle-​​in-​​a-​​haystack algo­rithms computational-​​complexity

  • [1107.0500] Fac­tor­iza­tion of Matri­ces of Quaternions

    “We review known fac­tor­iza­tion results in quater­nion matri­ces. Specif­i­cally, we derive the Jor­dan canon­i­cal form, polar decom­po­si­tion, sin­gu­lar value decom­po­si­tion, the QR fac­tor­iza­tion. We prove there is a Schur fac­tor­iza­tion for com­mut­ing matri­ces, and from this derive the spec­tral the­o­rem. We do not con­sider algo­rithms, but do point to some of the numer­i­cal lit­er­a­ture. Rather than work directly with matri­ces of quater­nions, we work with com­plex matri­ces with a spe­cific sym­me­try based on the dual oper­a­tion. We dis­cuss related results regard­ing com­plex matri­ces that are self-​​dual or sym­met­ric, but per­haps not Hermitian.”

    quan­tums algo­rithms matri­ces open-​​questions nudge-​​targets amus­ing

  • [1204.0163] Coor­di­na­tion and Emer­gence in the Cel­lu­lar Auto­mated Fash­ion Game

    “Fash­ion plays such a cru­cial rule in the evo­lu­tion of cul­ture and soci­ety that it is regarded as a sec­ond nature to the human being. Also, its impact on econ­omy is quite non­triv­ial. On what is fash­ion­able, inter­est­ingly, there are two view­points that are both extremely wide­spread but almost oppo­site: con­formists think that what is pop­u­lar is fash­ion­able, while rebels believe that being dif­fer­ent is the essence. Fash­ion color is fash­ion­able in the first sense, and Lady Gaga in the sec­ond. We inves­ti­gate a model where the pop­u­la­tion con­sists of the afore-​​mentioned two groups of peo­ple that are located on a spa­tial struc­ture. The­o­ret­i­cally, this model is equiv­a­lent to the match­ing pen­nies game on the cor­re­spond­ing net­work, and has its own inter­est to game the­ory: it is a hybrid model of pure com­pe­ti­tion and pure coop­er­a­tion. This is true because when a con­formist meets a rebel, they play the zero sum match­ing pen­nies game, which is pure com­pe­ti­tion. When two con­formists (rebels) meet, they play the (anti-​​) coor­di­na­tion game, which is pure coop­er­a­tion. Sim­u­la­tion shows that in most cases peo­ple can reach an extra­or­di­nar­ily high degree of coop­er­a­tion, through self­ish, myopic, naive, and local inter­ac­tions. Phase tran­si­tion, as well as emer­gence of many inter­est­ing pat­terns, is also observed.”

    cellular-​​automata agent-​​based social-​​dynamics com­plex­ol­ogy

  • [1205.3111] Sta­bil­ity of Boolean Mul­ti­plex Networks

    “We extend the for­mal­ism of Ran­dom Boolean Net­works with canal­iz­ing rules to mul­ti­level com­plex net­works. The for­mal­ism allows to model genetic net­works in which each gene might take part in more than one sig­nal­ing path­way. We use a semi-​​annealed approach to study the sta­bil­ity of this class of mod­els when cou­pled in a mul­ti­plex net­work and show that the ana­lyt­i­cal results are in good agree­ment with numer­i­cal sim­u­la­tions. Our main find­ing is that the mul­ti­plex struc­ture pro­vides a mech­a­nism for the sta­bi­liza­tion of the sys­tem and of chaotic regimes of indi­vid­ual lay­ers. Our results help under­stand­ing why some genetic net­works that are the­o­ret­i­cally expected to oper­ate in the chaotic regime can actu­ally dis­play dynam­i­cal stability.”

    boolean-​​networks com­plex­ol­ogy kauff­ma­nia inter­est­ing

  • [1109.1488] Are Opin­ions Based on Sci­ence: Mod­el­ling Social Response to Sci­en­tific Facts

    Oh how I laughed and laughed. “As sci­en­tists we like to think that mod­ern soci­eties and their mem­bers base their views, opin­ions and behav­iour on sci­en­tific facts.…”

    sci­ence! cultural-​​assumptions agent-​​based sim­u­la­tion social-​​networks

  • [1206.0594] Sim­ple and Deter­min­is­tic Matrix Sketching

    I hadn’t heard of matrix sketch­ing before; war­rants a look someday.

    algo­rithms operations-​​research data-​​cleaning summarization-​​algorithms nudge-​​targets

  • [1205.0537] A greedy-​​navigator approach to nav­i­ga­ble city plans

    “We use a set of four the­o­ret­i­cal nav­i­ga­bil­ity indices for street maps to inves­ti­gate the shape of the result­ing street net­works, if they are grown by opti­miz­ing these indices. The indices com­pare the per­for­mance of sim­u­lated nav­i­ga­tors (hav­ing a par­tial infor­ma­tion about the sur­round­ings, like humans in many real sit­u­a­tions) to the per­for­mance of opti­mally nav­i­gat­ing indi­vid­u­als. We show that our sim­ple greedy short­cut con­struc­tion strat­egy gen­er­ates the emerg­ing struc­tures that are dif­fer­ent from real road net­work, but not incon­ceiv­able. The result­ing city plans, for all nav­i­ga­tion indices, share com­mon qual­i­ta­tive prop­er­ties such as the ten­dency for tri­an­gu­lar blocks to appear, while the more quan­ti­ta­tive fea­tures, such as degree dis­tri­b­u­tions and clus­ter­ing, are char­ac­ter­is­ti­cally dif­fer­ent depend­ing on the type of met­rics and rout­ing strate­gies. We show that it is the type of met­rics used which deter­mines the over­all shapes char­ac­ter­ized by struc­tural het­ero­gene­ity, but the rout­ing schemes con­tribute to more sub­tle details of local­ity, which is more empha­sized in case of unre­stricted con­nec­tions when the edge cross­ing is allowed.”

    city-​​planning emer­gence emergent-​​design agent-​​based nudge-​​targets

  • [1105.0703] Adap­tive Cut Gen­er­a­tion Algo­rithm for Improved Lin­ear Pro­gram­ming Decod­ing of Binary Lin­ear Codes

    “…Then, we pro­pose a new and effec­tive algo­rithm to gen­er­ate par­ity inequal­i­ties derived from cer­tain addi­tional redun­dant par­ity check (RPC) con­straints that can elim­i­nate pseudocode­words pro­duced by the LP decoder, often sig­nif­i­cantly improv­ing the decoder error-​​rate per­for­mance. The cut-​​generating algo­rithm is based upon a spe­cific trans­for­ma­tion of an ini­tial parity-​​check matrix of the lin­ear block code. We also design two vari­a­tions of the pro­posed decoder to make it more effi­cient when it is com­bined with the new cut-​​generating algo­rithm. Sim­u­la­tion results for sev­eral low-​​density parity-​​check (LDPC) codes demon­strate that the pro­posed decod­ing algo­rithms sig­nif­i­cantly nar­row the per­for­mance gap between LP decod­ing and ML decoding.”

    linear-​​programming information-​​theory algo­rithms nudge-​​targets searching-​​under-​​the-​​streetlight

  • [1203.4802] A Reference-​​Free Algo­rithm for Com­pu­ta­tional Nor­mal­iza­tion of Shot­gun Sequenc­ing Data

    “Deep shot­gun sequenc­ing and analy­sis of genomes, tran­scrip­tomes, ampli­fied single-​​cell genomes, and metagenomes has enabled inves­ti­ga­tion of a wide range of organ­isms and ecosys­tems. How­ever, sam­pling vari­a­tion in short-​​read data sets and high sequenc­ing error rates of mod­ern sequencers present many new com­pu­ta­tional chal­lenges in data inter­pre­ta­tion. These chal­lenges have led to the devel­op­ment of new classes of map­ping tools and {em de novo} assem­blers. These algo­rithms are chal­lenged by the con­tin­ued improve­ment in sequenc­ing through­put. We here describe dig­i­tal nor­mal­iza­tion, a single-​​pass com­pu­ta­tional algo­rithm that sys­tem­atizes cov­er­age in shot­gun sequenc­ing data sets, thereby decreas­ing sam­pling vari­a­tion, dis­card­ing redun­dant data, and remov­ing the major­ity of errors. Dig­i­tal nor­mal­iza­tion sub­stan­tially reduces the size of shot­gun data sets and decreases the mem­ory and time require­ments for {em de novo} sequence assem­bly, all with­out sig­nif­i­cantly impact­ing con­tent of the gen­er­ated con­tigs. We apply dig­i­tal nor­mal­iza­tion to the assem­bly of micro­bial genomic data, ampli­fied single-​​cell genomic data, and tran­scrip­tomic data. Our imple­men­ta­tion is freely avail­able for use and modification.”

    genomics bioin­for­mat­ics algo­rithms sta­tis­tics data-​​cleaning

  • [0908.2741] B-​​Rank: A top N Rec­om­men­da­tion Algorithm

    “In this paper B-​​Rank, an effi­cient rank­ing algo­rithm for rec­om­mender sys­tems, is pro­posed. B-​​Rank is based on a ran­dom walk model on hyper­graphs. Depend­ing on the setup, B-​​Rank out­per­forms other state of the art algo­rithms in terms of pre­ci­sion, recall (19% — 50%), and inter list diver­sity (20% — 60%). B-​​Rank cap­tures well the dif­fer­ence between pop­u­lar and niche objects. The pro­posed algo­rithm pro­duces very promis­ing results for sparse and dense vot­ing matri­ces. Fur­ther­more, a rec­om­men­da­tion list update algo­rithm is introduced,to cope with new votes. This tech­nique sig­nif­i­cantly reduces com­pu­ta­tional com­plex­ity. The imple­men­ta­tion of the algo­rithm is sim­ple, since B-​​Rank needs no para­me­ter tuning.”

    algo­rithms peer-​​production bench­mark­ing amus­ing

  • [1205.2777] Mod­el­ling slowly chang­ing dynamic gene-​​regulatory networks

    “Dynamic gene-​​regulatory net­works are com­plex since the num­ber of poten­tial com­po­nents involved in the sys­tem is very large. Esti­mat­ing dynamic net­works is an impor­tant task because they com­pro­mise valu­able infor­ma­tion about inter­ac­tions among genes. Graph­i­cal mod­els are a pow­er­ful class of mod­els to esti­mate con­di­tional inde­pen­dence among ran­dom vari­ables, e.g. inter­ac­tions in dynamic sys­tems. Indeed, these inter­ac­tions tend to vary over time. How­ever, the lit­er­a­ture has been focused on sta­tic net­works, which can only reveal over­all struc­tures. Time-​​course exper­i­ments are per­formed in order to tease out sig­nif­i­cant changes in net­works. It is typ­i­cally rea­son­able to assume that changes in genomic net­works are few because sys­tems in biol­ogy tend to be sta­ble. We intro­duce a new model for esti­mat­ing slowly changes in dynamic gene-​​regulatory net­works which is suit­able for a high-​​dimensional dataset, e.g. time-​​course genomic data. Our method is based on i) the penal­ized like­li­hood with $ell_1$-norm, ii) the penal­ized dif­fer­ences between con­di­tional inde­pen­dence ele­ments across time points and iii) the heuris­tic search strat­egy to find opti­mal smooth­ing para­me­ters. We imple­ment a set of lin­ear con­straints nec­es­sary to esti­mate sparse graphs and penal­ized chang­ing in dynamic net­works. These con­straints are not in the lin­ear form. For this rea­son, we intro­duce slack vari­ables to re-​​write our prob­lem into a stan­dard con­vex opti­miza­tion prob­lem sub­ject to equal­ity lin­ear con­straints. We show that GL$_Delta$ per­forms well in a sim­u­la­tion study. Finally, we apply the pro­posed model to a time-​​course genetic dataset T-​​cell.”

    gene-​​regulatory-​​networks mod­el­ing systems-​​biology operations-​​research linear-​​programming nudge-​​targets

  • [1205.3532] New Algo­rithms on Rooted Triplet Consistency

    “An evo­lu­tion­ary tree (phy­lo­ge­netic tree) is a binary, rooted, unordered tree that mod­els the evo­lu­tion­ary his­tory of cur­rently liv­ing species in which leaves are labeled by species. In this paper, we inves­ti­gate the prob­lem of find­ing the max­i­mum con­sen­sus evo­lu­tion­ary tree from a set of given rooted triplets. A rooted triplet is a phy­lo­ge­netic tree on three leaves and shows the evo­lu­tion­ary rela­tion­ship of the cor­re­spond­ing three species. The men­tioned prob­lem is known to be APX-​​hard. We present two new heuris­tic algo­rithms. For a given set of m triplets on n species, the Fast­Tree algo­rithm runs in O(mn^2) which is faster than any other pre­vi­ously known algo­rithms, although, the out­come is less sat­is­fac­tory. The BPMTR algo­rithm runs in O(mn^3) and in aver­age per­forms bet­ter than any other pre­vi­ously known approx­i­ma­tion algo­rithms for this problem.”

    cladis­tics algo­rithms open-​​questions nudge-​​targets

  • [1205.3720] A k-​​shell decom­po­si­tion method for weighted networks

    “One major lim­i­ta­tion of most cen­tral­ity mea­sures, includ­ing the k-​​core decom­po­si­tion method, is their design to work on unweighted graphs. How­ever, in prac­tice, real net­works are weighted, and their weights describe impor­tant and well defined prop­er­ties of the under­ly­ing sys­tems. In order to over­come this lim­i­ta­tion two main approaches were fol­lowed, but, both hav­ing draw­backs of their own. Under the first approach one would com­pletely neglect the weights and per­form the analy­sis on the unweighted net­work, but then one chooses to neglect an impor­tant prop­erty of the net­work. The sec­ond approach would be to con­sider only links with weights above some — (usu­ally) arbi­trary cho­sen — thresh­old value. How­ever, this approach has a draw­back since it has to deal with the selec­tion of a proper cut-​​off value, and as we will dis­cuss later, this could have sig­nif­i­cant impact on the results. Addi­tion­ally, by neglect­ing links bel­low a thresh­old, the net­work becomes sparser with some nodes get­ting dis­con­nected and not con­sid­ered by the applied method afterwards.”

    network-​​theory social-​​networks algo­rithms graph-​​theory

  • [1109.2341] Guar­an­teed suc­cess­ful strate­gies for a square achieve­ment game on an n by n grid

    “At some places (see the ref­er­ences) Mar­tin Erick­son describes a cer­tain game: “Two play­ers alter­nately write O’s (first player) and X’s (sec­ond player) in the unoc­cu­pied cells of an n x n grid. The first player (if any) to occupy four cells at the ver­tices of a square with hor­i­zon­tal and ver­ti­cal sides is the win­ner.” Then he asks “What is the out­come of the game given opti­mal play?” or “What is the small­est n such that the first player has a win­ning strategy?” ”

    nudge-​​targets game-​​theory mathematical-​​recreations

  • [1206.0217] Effi­cient tech­niques for min­ing spa­tial databases

    “Clus­ter­ing is one of the major tasks in data min­ing. In the last few years, Clus­ter­ing of spa­tial data has received a lot of research atten­tion. Spa­tial data­bases are com­po­nents of many advanced infor­ma­tion sys­tems like geo­graphic infor­ma­tion sys­tems VLSI design sys­tems. In this the­sis, we intro­duce sev­eral effi­cient algo­rithms for clus­ter­ing spa­tial data. First, we present a grid-​​based clus­ter­ing algo­rithm that has sev­eral advan­tages and com­pa­ra­ble per­for­mance to the well known effi­cient clus­ter­ing algo­rithm. The algo­rithm has sev­eral advan­tages. The algo­rithm does not require many input para­me­ters. It requires only three para­me­ters, the num­ber of the points in the data space, the num­ber of the cells in the grid and a per­cent­age. The num­ber of the cells in the grid reflects the accu­racy that should be achieved by the algo­rithm. The algo­rithm is capa­ble of dis­cov­er­ing clus­ters of arbi­trary shapes. The com­pu­ta­tional com­plex­ity of the algo­rithm is com­pa­ra­ble to the com­plex­ity of the most effi­cient clus­ter­ing algo­rithm. The algo­rithm has been imple­mented and tested against dif­fer­ent ranges of data­base sizes. The per­for­mance results show that the run­ning time of the algo­rithm is supe­rior to the most well known algo­rithms (CLARANS [23]). The results show also that the per­for­mance of the algo­rithm do not degrade as the num­ber of the data points increases.”

    GIS sta­tis­tics clus­ter­ing context-​​sensitive-​​data nudge-​​targets data-​​mining

  • [1205.5407] FASTSUBS: An Effi­cient Admis­si­ble Algo­rithm for Find­ing the Most Likely Lex­i­cal Sub­sti­tutes Using a Sta­tis­ti­cal Lan­guage Model

    “Lex­i­cal sub­sti­tutes have found use in the con­text of word sense dis­am­bigua­tion, unsu­per­vised part-​​of-​​speech induc­tion, para­phras­ing, machine trans­la­tion, and text sim­pli­fi­ca­tion. Using a sta­tis­ti­cal lan­guage model to find the most likely sub­sti­tutes in a given con­text is a suc­cess­ful approach, but the cost of a naive algo­rithm is pro­por­tional to the vocab­u­lary size. This paper presents the Fast­subs algo­rithm which can effi­ciently and cor­rectly iden­tify the most likely lex­i­cal sub­sti­tutes for a given con­text based on a sta­tis­ti­cal lan­guage model with­out going through most of the vocab­u­lary. The effi­ciency of Fast­subs makes large scale exper­i­ments based on lex­i­cal sub­sti­tutes fea­si­ble. For exam­ple, it is pos­si­ble to com­pute the top 10 sub­sti­tutes for each one of the 1,173,766 tokens in Penn Tree­bank in about 6 hours on a typ­i­cal work­sta­tion. The same task would take about 6 days with the naive algo­rithm. An imple­men­ta­tion of the algo­rithm and a dataset with the top 100 sub­sti­tutes of each token in the WSJ sec­tion of the Penn Tree­bank are avail­able from the author’s web­site at this http URL”

    lin­guis­tics data-​​cleaning algo­rithms nudge-​​targets clas­si­fi­ca­tion

  • [1204.1002] Fast Multi-​​Scale Detec­tion of Rel­e­vant Communities

    “Nowa­days, net­works are almost ubiq­ui­tous. In the past decade, com­mu­nity detec­tion received an increas­ing inter­est as a way to uncover the struc­ture of net­works by group­ing nodes into com­mu­ni­ties more densely con­nected inter­nally than exter­nally. Yet most of the effec­tive meth­ods avail­able do not con­sider the poten­tial lev­els of organ­i­sa­tion, or scales, a net­work may encom­pass and are there­fore lim­ited. In this paper we present a method com­pat­i­ble with global and local cri­te­ria that enables fast multi-​​scale com­mu­nity detec­tion. The method is derived in two algo­rithms, one for each type of cri­te­rion, and imple­mented with 6 known cri­te­ria. Uncov­er­ing com­mu­ni­ties at var­i­ous scales is a com­pu­ta­tion­ally expen­sive task. There­fore this work puts a strong empha­sis on the reduc­tion of com­pu­ta­tional com­plex­ity. Some heuris­tics are intro­duced for speed-​​up pur­poses. Exper­i­ments demon­strate the effi­ciency and accu­racy of our method with respect to each algo­rithm and cri­te­rion by test­ing them against large gen­er­ated multi-​​scale net­works. This study also offers a com­par­i­son between cri­te­ria and between the global and local approaches.”

    social-​​networks network-​​theory algo­rithms community-​​detection

  • [1105.2204] A Bayesian Model of NMR Spec­tra for the Decon­vo­lu­tion and Quan­tifi­ca­tion of Metabo­lites in Com­plex Bio­log­i­cal Mixtures

    Now this one is cool.

    sta­tis­tics inverse-​​problems bio­chem­istry signal-​​processing algo­rithms machine-​​learning nudge-​​targets inference-of-things-that-aren’t-toys

  • Growthol­ogy: Civic Startup Accelerator

    “…What exactly are we talk­ing about when we say ‘using data’? Steven John­son wrote an inter­est­ing piece in Wired two years ago using New York City 311 call data. Those city subway/​train/​bus route apps on your smart­phone? Pos­si­ble thanks to city gov­ern­ments open­ing up their data. The recently released Kauff­man Foun­da­tion health care report con­tains plenty of dis­cus­sion and ideas for both the pub­lic and pri­vate sector.”

    social-​​entrepreneurship public-​​policy star­tups business-​​development-​​sortof shadow-​​economies open-​​science

  • [1205.4422] 3D-​​Algorithms of Com­posed Pur­suit Navigation

    “The prob­lem of pur­su­ing a mov­ing tar­get is always one of the main top­ics in nav­i­ga­tion. In the lit­er­a­tures, there are two well-​​known algo­rithms called Pure Pur­suit and Pure Ren­dezvous nav­i­ga­tion in the 3-​​dimensional space $mathbb{R}^3$. In this paper, these two meth­ods are com­bined to intro­duce a novel fam­ily of pur­su­ing algo­rithms called Com­posed Pur­suit Nav­i­ga­tion. The Kine­matic and geo­met­ric prop­er­ties of this nav­i­ga­tion is stud­ied. The tra­jec­to­ries of this new fam­ily of algo­rithms ben­e­fit the advan­tages of two known meth­ods and its promi­nence is demon­strated in two real exam­ples. More­over, it is shown that the met­ric related to the algo­rithms are given by Mat­sumoto metrics.”

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

  • [1205.5975] A Domain-​​Specific Com­piler for Lin­ear Alge­bra Operations

    “We present a pro­to­typ­i­cal lin­ear alge­bra com­piler that auto­mat­i­cally exploits domain-​​specific knowl­edge to gen­er­ate high-​​performance algo­rithms. The input to the com­piler is a tar­get equa­tion together with knowl­edge of both the struc­ture of the prob­lem and the prop­er­ties of the operands. The out­put is a vari­ety of high-​​performance algo­rithms, and the cor­re­spond­ing source code, to solve the tar­get equa­tion. Our approach con­sists in the decom­po­si­tion of the input equa­tion into a sequence of library-​​supported ker­nels. Since in gen­eral such a decom­po­si­tion is not unique, our com­piler returns not one but a num­ber of algo­rithms. The poten­tial of the com­piler is shown by means of its appli­ca­tion to a chal­leng­ing equa­tion aris­ing within the genome-​​wide asso­ci­a­tion study. As a result, the com­piler pro­duces mul­ti­ple “best” algo­rithms that out­per­form the best exist­ing libraries.”

    domain-​​specific-​​language linear-​​algebra software-​​engineering com­piler nudge-​​targets

  • [1206.1098] The inter­play of intrin­sic and extrin­sic bounded noises in genetic networks

    “After being con­sid­ered as a nui­sance to be fil­tered out, it became recently clear that bio­chem­i­cal noise plays a com­plex role, often fully func­tional, for a genetic net­work. The influ­ence of intrin­sic and extrin­sic noises on genetic net­works has inten­sively been inves­ti­gated in last ten years, though con­tri­bu­tions on the co-​​presence of both are sparse. Extrin­sic noise is usu­ally mod­eled as an unbounded white or col­ored gauss­ian sto­chas­tic process, even though real­is­tic sto­chas­tic per­tur­ba­tions are clearly bounded. In this paper we con­sider Gillespie-​​like sto­chas­tic mod­els of non­lin­ear net­works, i.e. the intrin­sic noise, where the model jump rates are affected by col­ored bounded extrin­sic noises syn­the­sized by a suit­able bio­chem­i­cal state-​​dependent Langevin sys­tem. These sys­tems are described by a mas­ter equa­tion, and a sim­u­la­tion algo­rithm to ana­lyze them is derived. This new mod­el­ing par­a­digm should enlarge the class of sys­tems amenable at mod­el­ing. We inves­ti­gated the influ­ence of both ampli­tude and auto­cor­re­la­tion time of a extrin­sic Sine-​​Wiener noise on: $(i)$ the Michaelis-​​Menten approx­i­ma­tion of noisy enzy­matic reac­tions, which we show to be applic­a­ble also in co-​​presence of both intrin­sic and extrin­sic noise, $(ii)$ a model of enzy­matic futile cycle and $(iii)$ a genetic tog­gle switch. In $(ii)$ and $(iii)$ we show that the pres­ence of a bounded extrin­sic noise induces qual­i­ta­tive mod­i­fi­ca­tions in the prob­a­bil­ity den­si­ties of the involved chem­i­cals, where new modes emerge, thus sug­gest­ing the pos­si­bile func­tional role of bounded noises.”

    bio­chem­istry structural-​​biology reaction-​​networks biological-​​engineering noise its-​​complicated-​​inside-​​a-​​cell sim­u­la­tion nudge-​​targets

  • [1205.3058] A Tight Lower Bound on the Con­trol­la­bil­ity of Net­works with Mul­ti­ple Leaders

    “In this paper we study the con­trol­la­bil­ity of net­worked sys­tems with sta­tic net­work topolo­gies using tools from alge­braic graph the­ory. Each agent in the net­work acts in a decen­tral­ized fash­ion by updat­ing its state in accor­dance with a nearest-​​neighbor aver­ag­ing rule, known as the con­sen­sus dynam­ics. In order to con­trol the sys­tem, exter­nal con­trol inputs are injected into the so called leader nodes, and the influ­ence is prop­a­gated through­out the net­work. Our main result is a tight topo­log­i­cal lower bound on the rank of the con­trol­la­bil­ity matrix for such sys­tems with arbi­trary net­work topolo­gies and pos­si­bly mul­ti­ple leaders.”

    network-​​theory algo­rithms emergent-​​design nudge-​​targets

  • [1205.3180] Community-​​Quality-​​Based Player Rank­ing in Col­lab­o­ra­tive Games with no Explicit Objectives

    “How­ever, when the game has no clear objec­tives, no met– ric exists to mea­sure player con­tri­bu­tion qual­ity. Indeed, each player may have a dif­fer­ent per­sonal moti­va­tion to achieve dif– fer­ent self-​​imposed goals [4], and player actions can be con– sidered fair or dis­rup­tive towards the com­mu­nity depend­ing on whether they respect or dam­age other player con­tri­bu­tions. In these cases, there is a very abstract and sub­jec­tive shared implicit objec­tive that could be described as build­ing a fair and not dis­rup­tive player com­mu­nity. It should be noted that fair play­ers ben­e­fit from their behav­ior, as it is more likely that other play­ers act fair towards them. Fur­ther­more, a com– munity of dis­rup­tive play­ers seems to repel fair play­ers and the com­mu­nity qual­ity has an intu­itive ten­dency to grad­u­ally drop off. Con­trar­ily, a com­mu­nity of fair play­ers lures new fair play­ers, which lead, in turn, to an increase of the commu– nity quality.”

    social-​​dynamics game-​​theory col­lab­o­ra­tion performance-​​measure teams ranking-​​schemes agile-​​management to-​​explore

  • [1205.3648] 6-​​Body Cen­tral Con­fig­u­ra­tions Formed by Two Isosce­les Triangles

    “In this paper,we show the exis­tence of a class of 6-​​body cen­tral con­fig­u­ra­tions with two isosce­les tri­an­gles; which are con­gru­ent to each other and keep some distance.We also study the nec­es­sary con­di­tions about masses for the bod­ies which can form a cen­tral configuration.”

    N-​​body-​​problems sim­u­la­tion mathematical-​​recreations nudge-​​targets special-​​cases inverse-​​problems-​​done-​​backwards

  • [1206.1074] Memetic Arti­fi­cial Bee Colony Algo­rithm for Large-​​Scale Global Optimization

    Peo­ple who mis­un­der­stand the dif­fer­ence between a “pro­gram”, a “design pat­tern” and an “algo­rithm”, I’m think­ing. That said, an inter­est­ing camel’s nose for get­ting more con­tex­tual nar­ra­tive and less ridicu­lous over­gen­er­al­iza­tion (even acci­den­tally) in an engi­neer­ing paper.…

    algo­rithms pro­gram­ming subjective-​​objective-​​decontextualization-​​bias rather-​​interesting

  • [1205.2200] A Greedy Dou­ble Swap Heuris­tic for Nurse Scheduling

    “One of the key chal­lenges of nurse sched­ul­ing prob­lem (NSP) is the num­ber of con­straints placed on prepar­ing the timetable, both from the reg­u­la­tory require­ments as well as the patients’ demand for the appro­pri­ate nurs­ing care spe­cial­ists. In addi­tion, the pref­er­ences of the nurs­ing staffs related to their work sched­ules add another dimen­sion of com­plex­ity. Most solu­tions pro­posed for solv­ing nurse sched­ul­ing involve the use of math­e­mat­i­cal pro­gram­ming and gen­er­ally con­sid­ers only the hard con­straints. How­ever, the psy­cho­log­i­cal needs of the nurses are ignored and this resulted in sub­se­quent inter­ven­tions by the nurs­ing staffs to rem­edy any defi­ciency and often results in last minute changes to the sched­ule. In this paper, we present a staff pref­er­ence opti­miza­tion frame­work which is solved with a greedy dou­ble swap heuris­tic. The heuris­tic yields good per­for­mance in speed at solv­ing the prob­lem. The heuris­tic is sim­ple and we will demon­strate its per­for­mance by imple­ment­ing it on open source spread­sheet software.”

    sched­ul­ing operations-​​research heuris­tics performance-​​measure nudge-​​targets

  • What is Max? « Cycling 74

    “Max gives you the parts to cre­ate unique sounds, stun­ning visu­als, and engag­ing inter­ac­tive media. These parts are called ‘objects’ – visual boxes that con­tain tiny pro­grams to do some­thing spe­cific. Each object does some­thing dif­fer­ent. Some make noises, some make video effects, oth­ers just do sim­ple cal­cu­la­tions or make deci­sions. In Max you add objects to a visual can­vas and con­nect them together with patch­cords. You can use as many as you like. By com­bin­ing objects, you cre­ate inter­ac­tive and unique soft­ware with­out ever writ­ing any code (you can do that too if you really want to). Just connect.”

    visual-​​programming genetic-​​programming-​​target generative-​​art soft­ware lan­guages

  • [1205.3397] 1.85 Approx­i­ma­tion for Min-​​Power Strong Connectivity

    “Given a directed sim­ple graph G=(V,E) and a nonnegative-​​valued cost func­tion the power of a ver­tex u in a directed span­ning sub­graph H is given by the max­i­mum cost of an arcs of H exit­ing u. The power of H is the sum of the power of its ver­tices. Power Assign­ment seeks to min­i­mize the power of H while H sat­is­fies some con­nec­tiv­ity con­straint. In this paper, we assume E is bidi­rected (for every directed edge e in E, the oppo­site edge exists and has the same cost), while H is required to be strongly con­nected. This is the orig­i­nal power assign­ment prob­lem intro­duced by Chen and Huang in 1989, who proved that bidi­rected min­i­mum span­ning tree has approx­i­ma­tion ratio at most 2 (this is tight). In Approx 2010, we intro­duced a Greedy approx­i­ma­tion algo­rithm and claimed a ratio of 1.992. Here we improve the analy­sis to 1.85.”

    algo­rithms computational-​​complexity operations-​​research nudge-​​targets

  • [1206.1106] No More Pesky Learn­ing Rates

    “The per­for­mance of sto­chas­tic gra­di­ent descent (SGD) depends crit­i­cally on how learn­ing rates are tuned and decreased over time. We pro­pose a method to auto­mat­i­cally adjust mul­ti­ple learn­ing rates so as to min­i­mize the expected error at any one time. The method relies on local gra­di­ent vari­a­tions across sam­ples. Using a num­ber of con­vex and non-​​convex learn­ing tasks, we show that the result­ing algo­rithm matches the per­for­mance of the best set­tings obtained through sys­tem­atic search, and effec­tively removes the need for learn­ing rate tuning.”

    opti­miza­tion algo­rithms gradient-​​descent adaptive-​​control silos-​​in-​​action

  • Prac­tic­ing Ruby

    “Get­ting bet­ter at soft­ware devel­op­ment can be hard work. There is an end­less sea of learn­ing mate­ri­als out there, but just fig­ur­ing out what top­ics you should focus on could take up all of your time if you let it. Don’t fall into that trap, instead, let me do the leg­work for you! As a sub­scriber to Prac­tic­ing Ruby, you’ll get access to well-​​polished weekly brain dumps about top­ics that will help you become a bet­ter Ruby devel­oper. You’ll also be able to join a ded­i­cated group of Prac­tic­ing Ruby­ists in lively con­ver­sa­tions about the eclec­tic mix of top­ics I’m writ­ing about.”

    Ruby pro­gram­ming tuto­r­ial sub­scrip­tions to-​​read

  • [1206.1103] Peri­odiz­ing qua­sicrys­tals: Anom­alous dif­fu­sion in qua­si­peri­odic systems

    “We intro­duce a con­struc­tion to embed a qua­si­peri­odic lat­tice of obsta­cles into a sin­gle unit cell of a higher-​​dimensional space, with peri­odic bound­ary con­di­tions. This con­struc­tion trans­par­ently shows the exis­tence of chan­nels in these systems,in which par­ti­cles may travel with­out col­lid­ing, up to a crit­i­cal obsta­cle radius. It pro­vides a sim­ple and effi­cient algo­rithm for numer­i­cal sim­u­la­tion of dynam­ics in qua­si­peri­odic struc­tures, as well as giv­ing a nat­ural notion of uni­form dis­tri­b­u­tion (mea­sure) and aver­ages. As an appli­ca­tion, we sim­u­late dif­fu­sion in a two-​​dimensional qua­sicrys­tal, find­ing three dif­fer­ent regimes, in par­tic­u­lar atyp­i­cal weak super-​​diffusion in the pres­ence of chan­nels, and sub-​​diffusion when obsta­cles overlap.”

    qua­sicrys­tals tiling algo­rithms topol­ogy sim­u­la­tion computational-​​geometry

  • [1205.3193] A Com­par­a­tive Study of Col­lab­o­ra­tive Fil­ter­ing Algorithms

    “Col­lab­o­ra­tive fil­ter­ing is a rapidly advanc­ing research area. Every year sev­eral new tech­niques are pro­posed and yet it is not clear which of the tech­niques work best and under what con­di­tions. In this paper we con­duct a study com­par­ing sev­eral col­lab­o­ra­tive fil­ter­ing tech­niques — both clas­sic and recent state-​​of-​​the-​​art — in a vari­ety of exper­i­men­tal con­texts. Specif­i­cally, we report con­clu­sions con­trol­ling for num­ber of items, num­ber of users, spar­sity level, per­for­mance cri­te­ria, and com­pu­ta­tional com­plex­ity. Our con­clu­sions iden­tify what algo­rithms work well and in what con­di­tions, and con­tribute to both indus­trial deploy­ment col­lab­o­ra­tive fil­ter­ing algo­rithms and to the research community.”

    overview collaborative-​​filtering performance-​​space pre­dic­tion algo­rithms swarms

  • Ben Linus and the Magic Box — YouTube

    Genetic Pro­gram­ming explained. [accord­ing to most folks]

    genetic-​​programming Lost self-​​definition you-​​keep-​​using-​​that-​​word

  • [1204.6170] A dis­trib­uted resource allo­ca­tion algo­rithm for many processes

    “Resource allo­ca­tion is the prob­lem that a process may enter a crit­i­cal sec­tion CS of its code only when its resource require­ments are not in con­flict with those of other processes in their crit­i­cal sec­tions. For each exe­cu­tion of CS, these require­ments are given anew. In the resource require­ments, lev­els can be dis­tin­guished, such as e.g. read access or write access. We allow infi­nitely many processes that com­mu­ni­cate by reli­able asyn­chro­nous mes­sages and have finite mem­ory. A sim­ple starvation-​​free solu­tion is pre­sented. Processes only wait for one another when they have con­flict­ing resource require­ments. The cor­rect­ness of the solu­tion is argued with invari­ants and tem­po­ral logic. It has been ver­i­fied with the proof assis­tant PVS.”

    distributed-​​processing con­cur­rency nudge-​​targets algo­rithms mod­el­ing

  • [1205.5911] A Hough Trans­form Approach to Solv­ing Lin­ear Min-​​Max Problems

    “Sev­eral ways to accel­er­ate the solu­tion of 2D/​3D lin­ear min-​​max prob­lems in $n$ con­straints are dis­cussed. We also present an algo­rithm for solv­ing such prob­lems in the 2D case, which is supe­rior to CGAL’s lin­ear pro­gram­ming solver, both in per­for­mance and in stability.”

    algo­rithms computational-​​geometry nudge-​​targets convex-​​hulls linear-​​programming

  • [1205.2664] A Bayesian Sam­pling Approach to Explo­ration in Rein­force­ment Learning

    “We present a mod­u­lar approach to rein­force­ment learn­ing that uses a Bayesian rep­re­sen­ta­tion of the uncer­tainty over mod­els. The approach, BOSS (Best of Sam­pled Set), dri­ves explo­ration by sam­pling mul­ti­ple mod­els from the pos­te­rior and select­ing actions opti­misti­cally. It extends pre­vi­ous work by pro­vid­ing a rule for decid­ing when to resam­ple and how to com­bine the mod­els. We show that our algo­rithm achieves nearop­ti­mal reward with high prob­a­bil­ity with a sam­ple com­plex­ity that is low rel­a­tive to the speed at which the pos­te­rior dis­tri­b­u­tion con­verges dur­ing learn­ing. We demon­strate that BOSS per­forms quite favor­ably com­pared to state-​​of-​​the-​​art reinforcement-​​learning approaches and illus­trate its flex­i­bil­ity by pair­ing it with a non-​​parametric model that gen­er­al­izes across states.”

    exploration-​​and-​​exploitation algo­rithms machine-​​learning reinforcement-​​learning integrate-​​method-​​into-​​GP

  • Stowe Boyd

    “The new media folks des­per­ately want to write for some hypo­thet­i­cal audi­ence, one they can find the cen­ter of. They are like bor­der col­lies, wired to herd sheep and fran­tic if they can’t find any.”

    disintermediation-​​in-​​action jour­nal­ism public-​​policy poll­sters cultural-​​assumptions

  • [1205.2282] A Dis­cus­sion on Par­al­leliza­tion Schemes for Sto­chas­tic Vec­tor Quan­ti­za­tion Algorithms

    “This paper stud­ies par­al­leliza­tion schemes for sto­chas­tic Vec­tor Quan­ti­za­tion algo­rithms in order to obtain time speed-​​ups using dis­trib­uted resources. We show that the most intu­itive par­al­leliza­tion scheme does not lead to bet­ter per­for­mances than the sequen­tial algo­rithm. Another dis­trib­uted scheme is there­fore intro­duced which obtains the expected speed-​​ups. Then, it is improved to fit imple­men­ta­tion on dis­trib­uted archi­tec­tures where com­mu­ni­ca­tions are slow and inter-​​machines syn­chro­niza­tion too costly. The schemes are tested with sim­u­lated dis­trib­uted archi­tec­tures and, for the last one, with Microsoft Win­dows Azure plat­form obtain­ing speed-​​ups up to 32 Vir­tual Machines.”

    algo­rithms distributed-​​processing par­al­leliza­tion nudge-​​targets

  • Crypto break­through shows Flame was designed by world-​​class sci­en­tists | Ars Technica

    “More inter­est­ingly, the results have shown that not our pub­lished chosen-​​prefix col­li­sion attack was used, but an entirely new and unknown vari­ant,” Stevens wrote in a state­ment dis­trib­uted on Thurs­day. “This has led to our con­clu­sion that the design of Flame is partly based on world-​​class crypt­analy­sis. Fur­ther research will be con­ducted to recon­struct the entire chosen-​​prefix col­li­sion attack devised for Flame.“ The analy­sis rein­forces the­o­ries that researchers from Kasper­sky Lab, CrySyS Lab, and Syman­tec pub­lished almost two weeks ago. Namely, Flame could only have been devel­oped with the back­ing of a wealthy nation-​​state. Stevens’ and de Weger’s con­clu­sion means that, in addi­tion to a team of engi­neers who devel­oped a global mal­ware plat­form that escaped detec­tion for at least two years, Flame also required world-​​class cryp­tog­ra­phers who have bro­ken new ground in their field. “It’s not a garden-​​variety col­li­sion attack, or just an imple­men­ta­tion of pre­vi­ous MD5 col­li­sions papers—which would be dif­fi­cult enough,” Matthew Green, a pro­fes­sor spe­cial­iz­ing in cryp­tog­ra­phy in the com­puter sci­ence depart­ment at Johns Hop­kins Uni­ver­sity, told Ars. “There were math­e­mati­cians doing new sci­ence to make Flame work.”

    cryp­tog­ra­phy MD5-​​woops algo­rithms nudge-​​targets

  • On Out­reach: something’s got to give | Neu­rotic Physiology

    “A change in the way acad­e­mia views out­reach is going to take a while, and it may take even longer for sci­ence com­mu­ni­ca­tion to become a really respected “alter­na­tive” career. In the mean­time, many sci­en­tists DO do out­reach. They go into schools, they give talks at bars, they talk to their friends and fam­ily. Some of them send me and other sci­ence blog­gers arti­cles (THANK YOU!! And you know, never hes­i­tate to send me an arti­cle!) to cover, or speak out proudly in sup­port of their work. There IS sci­ence out­reach out there, and a lot of it is GREAT.”

    sci­ence! academic-​​culture disintermediation-​​targets-​​who-​​have-​​noticed

  • [1206.0785] The Quan­tum Frontier

    “Many open prob­lems remain. Some are of a fun­da­men­tal nature. What does nature allow us to com­pute effi­ciently? What does nature allow us to make secure? Oth­ers are of a more prac­ti­cal nature. How will we build scal­able quan­tum com­put­ers? For what prob­lems are there effec­tive quan­tum algo­rithms? How broad an impact will quan­tum infor­ma­tion pro­cess­ing have? At the very least, quan­tum com­pu­ta­tion, and quan­tum infor­ma­tion pro­cess­ing more gen­er­ally, has changed for­ever how human­ity thinks about and works with physics, com­pu­ta­tion, and information.”

    quan­tums quantum-​​computing overview

  • [1205.6867] Min­i­miz­ing the aver­age dis­tance to a clos­est leaf in a phy­lo­ge­netic tree

    “In this paper we described a sim­ple new cri­te­rion, min­i­miz­ing the Aver­age Dis– tance to the Clos­est Leaf (ADCL), for find­ing a sub­set of sequences that either rep­re­sent the diver­sity of the sequences in a sam­ple, or are close on aver­age to a set of query sequences. In doing so, abun­dance infor­ma­tion is taken into account and attempt to strike a bal­ance between opti­mal­ity and cen­tral­ity in the tree. In par­tic­u­lar, this cri­te­rion is the only way in which we are aware to pick sequences that are phy­lo­ge­net­i­cally close on aver­age to a set of query sequences. We have also inves­ti­gated means of min­i­miz­ing the ADCL, includ­ing a heuris­tic that per­forms well in prac­tice and an exact dynamic pro­gram. ADCL min­i­miza­tion appears to avoid pick­ing chimeric sequences in simulation.”

    algo­rithms phy­lo­ge­net­ics cladis­tics performance-​​measure nudge-​​targets bioin­for­mat­ics

  • fish’s fish shell

    “How do I run a com­mand from his­tory? Type some part of the com­mand, and then hit the up or down arrow keys to nav­i­gate through his­tory matches.”

    want unix shell

  • [1206.0823] Orthog­o­nal Match­ing Pur­suit with Noisy and Miss­ing Data: Low and High Dimen­sional Results

    “Many mod­els for sparse regres­sion typ­i­cally assume that the covari­ates are known com­pletely, and with­out noise. Par­tic­u­larly in high-​​dimensional appli­ca­tions, this is often not the case. This paper devel­ops effi­cient OMP-​​like algo­rithms to deal with pre­cisely this set­ting. Our algo­rithms are as effi­cient as OMP, and improve on the best-​​known results for miss­ing and noisy data in regres­sion, both in the high-​​dimensional set­ting where we seek to recover a sparse vec­tor from only a few mea­sure­ments, and in the clas­si­cal low-​​dimensional set­ting where we recover an unstruc­tured regres­sor. In the high-​​dimensional set­ting, our support-​​recovery algo­rithm requires no knowl­edge of even the sta­tis­tics of the noise. Along the way, we also obtain improved per­for­mance guar­an­tees for OMP for the stan­dard sparse regres­sion prob­lem with Gauss­ian noise.”

    sta­tis­tics algo­rithms nudge-​​targets performance-​​measure cultural-​​assumptions-​​of-​​statistics

  • [1204.5213] Solv­ing Weighted Vot­ing Game Design Prob­lems Opti­mally: Rep­re­sen­ta­tions, Syn­the­sis, and Enumeration

    “We study the inverse power index prob­lem for weighted vot­ing games: the prob­lem of find­ing a weighted vot­ing game in which the power of the play­ers is as close as pos­si­ble to a cer­tain tar­get dis­tri­b­u­tion. Our goal is to find algo­rithms that solve this prob­lem exactly. Thereto, we study var­i­ous sub­classes of sim­ple games, and their asso­ci­ated rep­re­sen­ta­tion meth­ods. We sur­vey algo­rithms and impos­si­bil­ity results for the syn­the­sis prob­lem, i.e., con­vert­ing a rep­re­sen­ta­tion of a sim­ple game into another rep­re­sen­ta­tion. We con­tribute to the syn­the­sis prob­lem by show­ing that it is impos­si­ble to com­pute in poly­no­mial time the list of ceil­ing coali­tions (also known as shift-​​maximal los­ing coali­tions) of a game from its list of roof coali­tions (also known as shift-​​minimal win­ning coali­tions), and vice versa. ”

    inverse-​​problems algo­rithms game-​​theory vot­ing nudge-​​targets

  • [1206.0937] Detect­ing Acti­va­tions over Graphs using Span­ning Tree Wavelet Bases

    “This paper focuses on the prob­lem of detect­ing acti­va­tions over a graph when obser­va­tions are cor­rupted by noise. The prob­lem of detect­ing graph-​​structured acti­va­tions is rel­e­vant to many appli­ca­tions includ­ing iden­ti­fy­ing con­ges­tion in router and road net­works, elic­it­ing pref­er­ences in social net­works, and detect­ing viruses in human and com­puter net­works. Fur­ther­more, these appli­ca­tions require that the method is scal­able to large graphs. Luck­ily, com­puter sci­ence boasts a plethora of effi­cient graph based algo­rithms that we can adapt to the detec­tion framework.”

    sta­tis­tics network-​​theory algo­rithms pattern-​​discovery inverse-​​problems nudge-​​targets

  • [1206.1270] Fac­tor­ing non­neg­a­tive matri­ces with lin­ear programs

    “This paper describes a new approach for com­put­ing non­neg­a­tive matrix fac­tor­iza­tions (NMFs) with lin­ear pro­gram­ming. The key idea is a data-​​driven model for the fac­tor­iza­tion, in which the most salient fea­tures in the data are used to express the remain­ing fea­tures. More pre­cisely, given a data matrix X, the algo­rithm iden­ti­fies a matrix C that sat­is­fies X is approx­i­mately equal to CX and some lin­ear con­straints. The matrix C selects fea­tures, which are then used to com­pute a low-​​rank NMF of X. A the­o­ret­i­cal analy­sis demon­strates that this approach has the same type of guar­an­tees as the recent NMF algo­rithm of Arora et al. (2012). In con­trast with this ear­lier work, the pro­posed method (1) has bet­ter noise tol­er­ance, (2) extends to more gen­eral noise mod­els, and (3) leads to effi­cient, scal­able algo­rithms. Exper­i­ments with syn­thetic and real datasets pro­vide evi­dence that the new approach is also supe­rior in prac­tice. An opti­mized C++ imple­men­ta­tion of the new algo­rithm can fac­tor a multi-​​Gigabyte matrix in a mat­ter of minutes.”

    via:cshalizi algo­rithms linear-​​programming nudge-​​targets

  • [1206.1032] Fre­quent Pat­terns min­ing in time-​​sensitive Data Stream

    “Min­ing fre­quent item­sets through sta­tic Data­bases has been exten­sively stud­ied and used and is always con­sid­ered a highly chal­leng­ing task. For this rea­son it is inter­est­ing to extend it to data streams field. In the stream­ing case, the fre­quent pat­terns’ min­ing has much more infor­ma­tion to track and much greater com­plex­ity to man­age. Infre­quent items can become fre­quent later on and hence can­not be ignored. The out­put struc­ture needs to be dynam­i­cally incre­mented to reflect the evo­lu­tion of item­set fre­quen­cies over time. In this paper, we study this prob­lem and specif­i­cally the method­ol­ogy of min­ing time-​​sensitive data streams. We tried to improve an exist­ing algo­rithm by increas­ing the tem­po­ral accu­racy and dis­card­ing the out-​​of-​​date data by adding a new con­cept called the “Shak­ing Point”. We pre­sented as well some exper­i­ments illus­trat­ing the time and space required.”

    pattern-​​discovery time-​​series data-​​mining algo­rithms trad­ing nudge-​​targets

  • [1206.0580] O(1) Delta Com­po­nent Com­pu­ta­tion Tech­nique for the Qua­dratic Assign­ment Problem

    “The paper describes a novel tech­nique that allows to reduce by half the num­ber of delta val­ues that were required to be com­puted with com­plex­ity O(N) in most of the heuris­tics for the qua­dratic assign­ment prob­lem. Using the cor­re­la­tion between the old and new delta val­ues, obtained in this work, a new for­mula of com­plex­ity O(1) is pro­posed. Found result leads up to 25% per­for­mance increase in such well-​​known algo­rithms as Robust Tabu Search and oth­ers based on it.”

    algo­rithms com­bi­na­torics operations-​​research quadratic-​​assignment nudge-​​targets

  • [1206.1268] Para­me­ter Esti­ma­tion Through Ignorance

    “Dynam­i­cal mod­el­ling lies at the heart of our under­stand­ing of phys­i­cal sys­tems. Its role in sci­ence is deeper than mere oper­a­tional fore­cast­ing, in that it allows us to eval­u­ate the ade­quacy of the math­e­mat­i­cal struc­ture of our mod­els. Despite the impor­tance of model para­me­ters, there is no gen­eral method of para­me­ter esti­ma­tion out­side lin­ear sys­tems. A new rel­a­tively sim­ple method of para­me­ter esti­ma­tion for non­lin­ear sys­tems is pre­sented, based on vari­a­tions in the accu­racy of prob­a­bil­ity fore­casts. It is illus­trated on the Logis­tic Map, the Henon Map and the 12-​​D Lorenz96 flow, and its abil­ity to out­per­form lin­ear least squares in these sys­tems is explored at var­i­ous noise lev­els and sam­pling rates. As expected, it is more effec­tive when the fore­cast error dis­tri­b­u­tions are non-​​Gaussian. The new method selects para­me­ter val­ues by min­i­miz­ing a proper, local skill score for con­tin­u­ous prob­a­bil­ity fore­casts as a func­tion of the para­me­ter val­ues. This new approach is eas­ier to imple­ment in prac­tice than alter­na­tive non­lin­ear meth­ods based on the geom­e­try of attrac­tors or the abil­ity of the model to shadow the obser­va­tions. New direct mea­sures of inad­e­quacy in the model, the “Implied Igno­rance” and the infor­ma­tion deficit are introduced.”

    sta­tis­tics symbolic-​​regression parameter-​​estimation algo­rithms nudge-​​targets

  • 10 Time­frames | Con­tents Magazine

    “…And lis­ten, trust me, even if you do not feel that way at the end of these years, even if you are feel­ing burned out and done with the vagaries of social user design inter­ac­tion uni­ver­sal community-​​driven agile infor­ma­tion expe­ri­ence, even if you are ready to close your lap­top screen for­ever, you are beloved on the earth. You are skilled and tal­ented and young and bright and accred­ited. The world wishes it were you.”

    advice speech

  • [1206.0629] DEMON: a Local-​​First Dis­cov­ery Method for Over­lap­ping Communities

    “Com­mu­nity dis­cov­ery in com­plex net­works is an inter­est­ing prob­lem with a num­ber of appli­ca­tions, espe­cially in the knowl­edge extrac­tion task in social and infor­ma­tion net­works. How­ever, many large net­works often lack a par­tic­u­lar com­mu­nity orga­ni­za­tion at a global level. In these cases, tra­di­tional graph par­ti­tion­ing algo­rithms fail to let the latent knowl­edge embed­ded in mod­u­lar struc­ture emerge, because they impose a top-​​down global view of a net­work. We pro­pose here a sim­ple local-​​first approach to com­mu­nity dis­cov­ery, able to unveil the mod­u­lar orga­ni­za­tion of real com­plex net­works. This is achieved by demo­c­ra­t­i­cally let­ting each node vote for the com­mu­ni­ties it sees sur­round­ing it in its lim­ited view of the global sys­tem, i.e. its ego neigh­bor­hood, using a label prop­a­ga­tion algo­rithm; finally, the local com­mu­ni­ties are merged into a global col­lec­tion. We tested this intu­ition against the state-​​of-​​the-​​art over­lap­ping and non-​​overlapping com­mu­nity dis­cov­ery meth­ods, and found that our new method clearly out­per­forms the oth­ers in the qual­ity of the obtained com­mu­ni­ties, eval­u­ated by using the extracted com­mu­ni­ties to pre­dict the meta­data about the nodes of sev­eral real world net­works. We also show how our method is deter­min­is­tic, fully incre­men­tal, and has a lim­ited time com­plex­ity, so that it can be used on web-​​scale real networks.”

    network-​​theory algo­rithms community-​​discovery sta­tis­tics expla­na­tion referral-​​networks

  • [1206.0430] Con­ges­tion Games on Weighted Directed Graphs, with Appli­ca­tions to Spec­trum Sharing

    “With the advance of com­plex large-​​scale net­works, it is becom­ing increas­ingly impor­tant to under­stand how self­ish and spa­tially dis­trib­uted indi­vid­u­als will share net­work resources with­out cen­tral­ized coor­di­na­tions. In this paper, we intro­duce the graph­i­cal con­ges­tion game with weighted edges (GCGWE) as a gen­eral the­o­ret­i­cal model to study this prob­lem. In GCGWE, we view the play­ers as ver­tices in a weighted graph. The amount of neg­a­tive impact (e.g. con­ges­tion) caused by two close-​​by play­ers to each other is deter­mined by the weight of the edge link­ing them. The GCGWE uni­fies and sig­nif­i­cantly gen­er­al­izes sev­eral sim­pler mod­els con­sid­ered in the pre­vi­ous lit­er­a­ture, and is well suited for mod­el­ing a wide range of net­work­ing sce­nar­ios. One good exam­ple is to use the GCGWE to model spec­trum shar­ing in wire­less net­works, where we can prop­erly define the edge weights and pay­off func­tions to cap­ture the rather com­pli­cated inter­fer­ence rela­tion­ship between wire­less nodes. By iden­ti­fy­ing which GCG­WEs pos­sess pure Nash equi­lib­ria and the very desir­able finite improve­ment prop­erty, we gain insight into when spa­tially dis­trib­uted wire­less nodes will be able to self-​​organize into a mutu­ally accept­able resource allo­ca­tion. We also con­sider the effi­ciency of the pure Nash equi­lib­ria, and the com­pu­ta­tional com­plex­ity of find­ing them.”

    network-​​theory algo­rithms agent-​​based nudge-​​targets com­plex­ol­ogy

  • [1206.0855] A Mixed Observ­abil­ity Markov Deci­sion Process Model for Musi­cal Pitch

    “Par­tially observ­able Markov deci­sion processes have been widely used to pro­vide mod­els for real-​​world deci­sion mak­ing prob­lems. In this paper, we will pro­vide a method in which a slightly dif­fer­ent ver­sion of them called Mixed observ­abil­ity Markov deci­sion process, MOMDP, is going to join with our prob­lem. Basi­cally, we aim at offer­ing a behav­ioural model for inter­ac­tion of intel­li­gent agents with musi­cal pitch envi­ron­ment and we will show that how MOMDP can shed some light on build­ing up a deci­sion mak­ing model for musi­cal pitch conveniently.”

    music machine-​​learning generative-​​art pattern-​​discovery nudge-​​targets

  • [1206.0766] Why Opti­mal States Recruit Fewer Reac­tions in Meta­bolic Networks

    “The meta­bolic net­work of a liv­ing cell involves sev­eral hun­dreds or thou­sands of inter­con­nected bio­chem­i­cal reac­tions. Pre­vi­ous research has shown that under real­is­tic con­di­tions only a frac­tion of these reac­tions is con­cur­rently active in any given cell. This is par­tially deter­mined by nutri­ent avail­abil­ity, but is also strongly depen­dent on the meta­bolic func­tion and net­work struc­ture. Here, we estab­lish rig­or­ous bounds show­ing that the frac­tion of active reac­tions is smaller (rather than larger) in meta­bolic net­works evolved or engi­neered to opti­mize a spe­cific meta­bolic task, and we show that this is largely deter­mined by the pres­ence of ther­mo­dy­nam­i­cally irre­versible reac­tions in the net­work. We also show that the inac­ti­va­tion of a cer­tain num­ber of reac­tions deter­mined by irre­versibil­ity can gen­er­ate a cas­cade of sec­ondary reac­tion inac­ti­va­tions that prop­a­gates through the net­work. The math­e­mat­i­cal results are com­ple­mented with numer­i­cal sim­u­la­tions of the meta­bolic net­works of the bac­terium Escherichia coli and of human cells, which show, coun­ter­in­tu­itively, that even the max­i­miza­tion of the total reac­tion flux in the net­work leads to a reduced num­ber of active reactions.”

    network-​​theory biological-​​engineering metabolic-​​networks systems-​​biology engineering-​​design structural-​​biology

  • It Evolved Into Birds: Ten Science-​​Fictional Thinkers On the Past and Future of Cyber­punk | Motherboard

    “But the ideas orig­i­nally behind that trope — now that’s the cool part. My friends who work in aero­space tell me the old guys who built the indus­try all grew up read­ing Hein­lein and Clarke, and went into aero­space to turn those crazy things they read as kids into prac­ti­cal real­i­ties as adults. Well, I work in super­com­put­ing, and I can assure you that this indus­try is full of young geniuses who grew up read­ing Gib­son, Vinge, and Rucker — and yes, me — and they went into this field to do the same thing. We don’t quite live in the world that cyber­punk fic­tion pre­dicted. But we live in the world that the kids who grew up read­ing cyber­punk fic­tion built, and that is a very cool thing indeed.”

    cyber­punk fic­tion genre ret­ro­spec­tive science-​​fiction cultural-​​norms