Tag Archives: robustness

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:

  • [1112.4323] Between the­ory and prac­tice: guide­lines for an opti­miza­tion scheme with genetic algo­rithms — Part I: single-​​objective con­tin­u­ous global optimization

    The rapid advances in the field of opti­miza­tion meth­ods in many pure and applied sci­ence pose the dif­fi­culty of keep­ing track of the devel­op­ments as well as select­ing an appro­pri­ate tech­nique that best suits the prob­lem in-​​hand. From a prac­ti­tioner point of view is right­ful to wan­der “which opti­miza­tion method is the best for my prob­lem?”. Look­ing at the opti­miza­tion process as a “sys­tem” of inter­con– nected parts, in this paper are col­lected some ideas about how to tackle an opti­miza­tion prob­lem using a class of tools from evo­lu­tion­ary com­pu­ta­tions called Genetic Algo­rithms. Despite the num­ber of opti­miza­tion tech­niques avail­able nowa­days the author of this paper thinks that Genetic Algo­rithms still play a cen­tral role for their ver­sa­til­ity, robust­ness, the­o­ret­i­cal frame­work and sim­plic­ity of use. The paper can be con­sid­ered a “col­lec­tion of tips” (from lit­er­a­ture and per­sonal expe­ri­ence) for the non-​​computer-​​scientist that has to deal with opti­miza­tion prob­lems both in the sci­ence and engi­neer­ing prac­tice. No orig­i­nal meth­ods or algo­rithms are proposed.

    meta-​​optimization pragmatism-​​almost genetic-​​algorithm agile-​​almost project-​​management

  • [1112.6075] A semi­def­i­nite pro­gram­ming approach for solv­ing Mul­ti­ob­jec­tive Lin­ear Programming

    Sev­eral algo­rithms are avail­able in the lit­er­a­ture for find­ing the entire set of Pareto-​​optimal solu­tions in Mul­ti­Ob­jec­tive Lin­ear Pro­gram­ming (MOLP). How­ever, it has not been pro­posed so far an inte­rior point algo­rithm that finds all Pareto-​​optimal solu­tions of MOLP. We present an explicit con­struc­tion, based on a trans­for­ma­tion of any MOLP into a finite sequence of Semi­Def­i­nite Pro­grams (SDP), the solu­tions of which give the entire set of Pareto-​​optimal extreme points solu­tions of MOLP. These SDP prob­lems are solved by inte­rior point meth­ods; thus our approach pro­vides a pseudo-​​polynomial inte­rior point method­ol­ogy to find the set of Pareto-​​optimal solu­tions of MOLP.

    linear-​​programming algo­rithms multiobjective-​​optimization nudge-​​targets operations-​​research

  • [1112.0826] Clus­ter­ing under Per­tur­ba­tion Resilience

    Recently, Bilu and Linial for­mal­ized an implicit assump­tion often made when choos­ing a clus­ter­ing objec­tive: that the opti­mum clus­ter­ing to the objec­tive should be pre­served under small mul­ti­plica­tive per­tur­ba­tions to dis­tances between points. They showed that for max-​​cut clus­ter­ing it is pos­si­ble to cir­cum­vent NP-​​hardness and obtain polynomial-​​time algo­rithms for instances resilient to large (fac­tor $O(sqrt{n})$) per­tur­ba­tions, and sub­se­quently Awasthi et al. con­sid­ered center-​​based objec­tives, giv­ing algo­rithms for instances resilient to O(1) fac­tor per­tur­ba­tions. In this paper, we greatly advance this line of work. For center-​​based objec­tives, we present an algo­rithm that can opti­mally clus­ter instances resilient to $(1 + sqrt{2})$-factor per­tur­ba­tions, solv­ing an open prob­lem of Awasthi et al. For a com­monly used center-​​based objec­tive $k$-median, we addi­tion­ally give algo­rithms for a more relaxed assump­tion in which we allow the opti­mal solu­tion to change in a small $epsilon$ frac­tion of the points after per­tur­ba­tion. We give the first bounds known for this more real­is­tic and more gen­eral set­ting. We also pro­vide pos­i­tive results for min-​​sum clus­ter­ing which is a gen­er­ally much harder objec­tive than $k$-median (and also non-​​center-​​based). Our algo­rithms are based on new link­age cri­te­ria that may be of inde­pen­dent inter­est. Addi­tion­ally, we give sublinear-​​time algo­rithms, show­ing algo­rithms that can return an implicit clus­ter­ing from only access to a small ran­dom sample.

    clus­ter­ing sta­tis­tics nonparametric-​​methods robust­ness resilience algo­rithms nudge-​​targets

  • [1104.3516] An adap­tive hier­ar­chi­cal domain decom­po­si­tion method for par­al­lel con­tact dynam­ics sim­u­la­tions of gran­u­lar materials

    A fully par­al­lel ver­sion of the con­tact dynam­ics (CD) method is pre­sented in this paper. For large enough sys­tems, 100% effi­ciency has been demon­strated for up to 256 proces­sors using a hier­ar­chi­cal domain decom­po­si­tion with dynamic load bal­anc­ing. The iter­a­tive scheme to cal­cu­late the con­tact forces is left domain-​​wise sequen­tial, with data exchange after each iter­a­tion step, which ensures its sta­bil­ity. The num­ber of addi­tional iter­a­tions required for con­ver­gence by the par­tially par­al­lel updates at the domain bound­aries becomes neg­li­gi­ble with increas­ing num­ber of par­ti­cles, which allows for an effec­tive par­al­leliza­tion. Com­pared to the sequen­tial imple­men­ta­tion, we found no influ­ence of the par­al­leliza­tion on sim­u­la­tion results.

    sim­u­la­tion condensed-​​matter granular-​​materials complex-​​systems

Items of some interest…

Posted on by

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

  • [1110.0585] Dis­crim­i­nately Decreas­ing Dis­crim­inabil­ity with Learned Image Filters

    “In machine learn­ing and com­puter vision, input images are often fil­tered to increase data dis­crim­inabil­ity. In some sit­u­a­tions, how­ever, one may wish to pur­posely decrease dis­crim­inabil­ity of one clas­si­fi­ca­tion task (a “dis­trac­tor” task), while simul­ta­ne­ously pre­serv­ing infor­ma­tion rel­e­vant to another (the task-​​of-​​interest): For exam­ple, it may be impor­tant to mask the iden­tity of per­sons con­tained in face images before sub­mit­ting them to a crowd­sourc­ing site (e.g., Mechan­i­cal Turk) when label­ing them for cer­tain facial attrib­utes. Another exam­ple is inter-​​dataset gen­er­al­iza­tion: when train­ing on a dataset with a par­tic­u­lar covari­ance struc­ture among mul­ti­ple attrib­utes, it may be use­ful to sup­press one attribute while pre­serv­ing another so that a trained clas­si­fier does not learn spu­ri­ous cor­re­la­tions between attrib­utes. In this paper we present an algo­rithm that finds opti­mal fil­ters to give high dis­crim­inabil­ity to one task while simul­ta­ne­ously giv­ing low dis­crim­inabil­ity to a dis­trac­tor task. We present results show­ing the effec­tive­ness of the pro­posed tech­nique on both sim­u­lated data and nat­ural face images.”

    machine-​​learning data-​​preparation fil­ter­ing algo­rithms nudge-​​targets

  • [1110.5183] Dif­fu­sion of Infor­ma­tion in Robot Swarms

    “This work is devoted to com­mu­ni­ca­tion approaches, which spread infor­ma­tion in robot swarms. These mech­a­nisms are use­ful for large-​​scale sys­tems and also for such cases when a lim­ited com­mu­ni­ca­tion equip­ment does not allow rout­ing of infor­ma­tion pack­ages. We focus on two approaches such as vir­tual fields and epi­demic algo­rithms, dis­cuss sev­eral aspects of hard­ware imple­men­ta­tion and demon­strate exper­i­ments per­formed with micro­ro­bots “Jasmine”.”

    agent-​​based swarms com­mu­ni­ca­tion complex-​​systems epi­demi­ol­ogy dynamical-​​systems exper­i­ment

  • [1109.5229] Dis­trib­uted Algo­rithms for Opti­mal Power Flow Problem

    “Opti­mal power flow (OPF) is an impor­tant prob­lem for power gen­er­a­tion and it is in gen­eral non-​​convex. With the employ­ment of renew­able energy, it will be desir­able if OPF can be solved very effi­ciently so its solu­tion can be used in real time. With some spe­cial net­work struc­ture, e.g. trees, the prob­lem has been shown to have a zero dual­ity gap and the con­vex dual prob­lem yields the opti­mal solu­tion. In this paper, we pro­pose a pri­mal and a dual algo­rithm to coor­di­nate the smaller sub­prob­lems decom­posed from the con­vex­i­fied OPF. We can arrange the sub­prob­lems to be solved sequen­tially and cumu­la­tively in a cen­tral node or solved in par­al­lel in dis­trib­uted nodes. We test the algo­rithms on IEEE radial dis­tri­b­u­tion test feed­ers, some ran­dom tree-​​structured net­works, and the IEEE trans­mis­sion sys­tem bench­marks. Sim­u­la­tion results show that the com­pu­ta­tion time can be improved dra­mat­i­cally with our algo­rithms over the cen­tral­ized approach of solv­ing the prob­lem with­out decom­po­si­tion, espe­cially in tree-​​structured prob­lems. The com­pu­ta­tion time grows lin­early with the prob­lem size with the cumu­la­tive approach while the dis­trib­uted one can have size-​​independent com­pu­ta­tion time.”

    operations-​​research algo­rithms network-​​theory infra­struc­ture com­po­si­tion nudge-​​targets

  • Coupon collector’s prob­lem — Wikipedia, the free encyclopedia

    “In prob­a­bil­ity the­ory, the coupon collector’s prob­lem describes the “col­lect all coupons and win” con­tests. It asks the fol­low­ing ques­tion: Sup­pose that there are n coupons, from which coupons are being col­lected with replace­ment. What is the prob­a­bil­ity that more than t sam­ple tri­als are needed to col­lect all n coupons? An alter­na­tive state­ment is: Given n coupons, how many coupons do you expect you need to draw with replace­ment before hav­ing drawn each coupon at least once. The math­e­mat­i­cal analy­sis of the prob­lem reveals that the expected num­ber of tri­als needed grows as Θ(nlog(n)). For exam­ple, when n = 50 it takes about 225 tri­als to col­lect all 50 coupons.”

    probability-​​theory slic-​​representation nudge-​​targets

  • [1107.2379] Data Sta­bil­ity in Clus­ter­ing: A Closer Look

    “This paper con­sid­ers the model intro­duced by Bilu and Linial (2010), who study prob­lems for which the opti­mal clus­ter­ing does not change when the dis­tances are per­turbed by mul­ti­plica­tive fac­tors. They show that even when a prob­lem is NP-​​hard, it is some­times pos­si­ble to obtain polynomial-​​time algo­rithms for instances resilient to large per­tur­ba­tions, e.g. on the order of $O(sqrt{n})$ for max-​​cut clus­ter­ing. Awasthi et al. (2010) extend this line of work by con­sid­er­ing center-​​based objec­tives, and Bal­can and Liang (2011) con­sider the $k$-median and min-​​sum objec­tives, giv­ing effi­cient algo­rithms for instances resilient to cer­tain con­stant mul­ti­plica­tive per­tur­ba­tions. Here, we are moti­vated by the ques­tion of to what extent these assump­tions can be relaxed while allow­ing for effi­cient algo­rithms. We show there is lit­tle room to improve these results by giv­ing NP-​​hardness lower bounds for both the $k$-median and min-​​sum objec­tives. On the other hand, we show that mul­ti­plica­tive resilience para­me­ters, even only on the order of $Theta(1)$, can be so strong as to make the clus­ter­ing prob­lem triv­ial, and we exploit these assump­tions to present a sim­ple one pass stream­ing algo­rithm for the $k$-median objec­tive. We also con­sider a model of addi­tive per­tur­ba­tions and give a cor­re­spon­dence between addi­tive and mul­ti­plica­tive notions of sta­bil­ity. Our results pro­vide a close exam­i­na­tion of the con­se­quences of assum­ing, even con­stant, sta­bil­ity in data.”

    clus­ter­ing sta­tis­tics algo­rithms robust­ness nudge-​​targets

  • [1109.5641] Energy-​​Aware Load Bal­anc­ing in Con­tent Deliv­ery Networks

    “Internet-​​scale dis­trib­uted sys­tems such as con­tent deliv­ery net­works (CDNs) oper­ate hun­dreds of thou­sands of servers deployed in thou­sands of data cen­ter loca­tions around the globe. Since the energy costs of oper­at­ing such a large IT infra­struc­ture are a sig­nif­i­cant frac­tion of the total oper­at­ing costs, we argue for redesign­ing CDNs to incor­po­rate energy opti­miza­tions as a first-​​order prin­ci­ple. We pro­pose tech­niques to turn off CDN servers dur­ing peri­ods of low load while seek­ing to bal­ance three key design goals: max­i­mize energy reduc­tion, min­i­mize the impact on client-​​perceived ser­vice avail­abil­ity (SLAs), and limit the fre­quency of on-​​off server tran­si­tions to reduce wear-​​and-​​tear and its impact on hard­ware reli­a­bil­ity. We pro­pose an opti­mal offline algo­rithm and an online algo­rithm to extract energy sav­ings both at the level of local load bal­anc­ing within a data cen­ter and global load bal­anc­ing across data cen­ters. We eval­u­ate our algo­rithms using real pro­duc­tion work­load traces from a large com­mer­cial CDN. Our results show that it is pos­si­ble to reduce the energy con­sump­tion of a CDN by more than 55% while ensur­ing a high level of avail­abil­ity that meets cus­tomer SLA require­ments and incur­ring an aver­age of one on-​​off tran­si­tion per server per day. Fur­ther, we show that keep­ing even 10% of the servers as hot spares helps absorb load spikes due to global flash crowds with lit­tle impact on avail­abil­ity SLAs. Finally, we show that redis­trib­ut­ing load across prox­i­mal data cen­ters can enhance ser­vice avail­abil­ity sig­nif­i­cantly, but has only a mod­est impact on energy savings.”

    algo­rithms load-​​balancing infra­struc­ture nudge-​​targets operations-​​research

  • [1110.0264] Face Recog­ni­tion using Opti­mal Rep­re­sen­ta­tion Ensemble

    “Recently, the face rec­og­niz­ers based on lin­ear rep­re­sen­ta­tions have been shown to deliver state-​​of-​​the-​​art per­for­mance. In real-​​world appli­ca­tions, how­ever, face images usu­ally suf­fer from expres­sions, dis­guises and ran­dom occlu­sions. The prob­lem­atic facial parts under­mine the valid­ity of the linear-​​subspace assump­tion and thus the recog­ni­tion per­for­mance dete­ri­o­rates sig­nif­i­cantly. In this work, we address the prob­lem in a learning-​​inference-​​mixed fash­ion. By observ­ing that the linear-​​subspace assump­tion is more reli­able on cer­tain face patches rather than on the holis­tic face, some Bayesian Patch Rep­re­sen­ta­tions (BPRs) are ran­domly gen­er­ated and inter­preted accord­ing to the Bayes’ the­ory. We then train an ensem­ble model over the patch-​​representations by min­i­miz­ing the empir­i­cal risk w.r.t the “leave-​​one-​​out mar­gins”. The obtained model is termed Opti­mal Rep­re­sen­ta­tion Ensem­ble (ORE), since it guar­an­tees the opti­mal­ity from the per­spec­tive of Empir­i­cal Risk Min­i­miza­tion. To han­dle the unknown pat­terns in test faces, a robust ver­sion of BPR is pro­posed by tak­ing the non-​​face cat­e­gory into con­sid­er­a­tion. Equipped with the Robust-​​BPRs, the infer­ence abil­ity of ORE is increased dra­mat­i­cally and sev­eral record-​​breaking accu­ra­cies (99.9% on Yale-​​B and 99.5% on AR) and desir­able effi­cien­cies (below 20 ms per face in Mat­lab) are achieved. It also over­whelms other mod­u­lar heuris­tics on the faces with ran­dom occlu­sions, extreme expres­sions and dis­guises. Fur­ther­more, to accom­mo­date immense BPRs sets, a boosting-​​like algo­rithm is also derived. The boosted model, a.k.a Boosted-​​ORE, obtains sim­i­lar per­for­mance to its pro­to­type. Besides the empir­i­cal supe­ri­or­i­ties, two desir­able fea­tures of the pro­posed meth­ods, namely, the training-​​determined model-​​selection and the data-​​weight-​​free boost­ing pro­ce­dure, are also the­o­ret­i­cally verified.”

    image-​​analysis face-​​recognition algo­rithms nudge-​​targets

  • [1110.0957] Dic­tio­nary Learn­ing for Deblur­ring and Dig­i­tal Zoom

    “This paper pro­poses a novel approach to image deblur­ring and dig­i­tal zoom­ing using sparse local mod­els of image appear­ance. These mod­els, where small image patches are rep­re­sented as lin­ear com­bi­na­tions of a few ele­ments drawn from some large set (dic­tio­nary) of can­di­dates, have proven well adapted to sev­eral image restora­tion tasks. A key to their suc­cess has been to learn dic­tio­nar­ies adapted to the recon­struc­tion of small image patches. In con­trast, recent works have pro­posed instead to learn dic­tio­nar­ies which are not only adapted to data recon­struc­tion, but also tuned for a spe­cific task. We intro­duce here such an approach to deblur­ring and dig­i­tal zoom, using pairs of blurry/​sharp (or low-​​/​high-​​resolution) images for train­ing, as well as an effec­tive sto­chas­tic gra­di­ent algo­rithm for solv­ing the cor­re­spond­ing opti­miza­tion task. Although this learn­ing prob­lem is not con­vex, once the dic­tio­nar­ies have been learned, the sharp/​high-​​resolution image can be recov­ered via con­vex opti­miza­tion at test time. Exper­i­ments with syn­thetic and real data demon­strate the effec­tive­ness of the pro­posed approach, lead­ing to state-​​of-​​the-​​art per­for­mance for non-​​blind image deblur­ring and dig­i­tal zoom.”

    image-​​processing image-​​analysis algo­rithms nudge-​​targets hyper­res­o­lu­tion

  • [1110.0477] Dis­trib­uted Evo­lu­tion­ary Graph Partitioning

    “We present a novel dis­trib­uted evo­lu­tion­ary algo­rithm, KaFF­PaE, to solve the Graph Par­ti­tion­ing Prob­lem, which makes use of KaFFPa (Karl­sruhe Fast Flow Par­ti­tioner). The use of our mul­ti­level graph par­ti­tioner KaFFPa pro­vides new effec­tive crossover and muta­tion oper­a­tors. By com­bin­ing these with a scal­able com­mu­ni­ca­tion pro­to­col we obtain a sys­tem that is able to improve the best known par­ti­tion­ing results for many inputs in a very short amount of time. For exam­ple, in Walshaw’s well known bench­mark tables we are able to improve or recom­pute 76% of entries for the tables with 1%, 3% and 5% imbalance.”

    algo­rithms graph-​​theory evolutionary-​​algorithms nudge-​​targets

  • [1104.1605] Effi­cient Top-​​K Retrieval in Online Social Tag­ging Networks

    “We con­sider in this paper top-​​k query answer­ing in social tag­ging sys­tems, also known as folk­sonomies. This prob­lem requires a sig­nif­i­cant depar­ture from exist­ing, socially agnos­tic tech­niques. In a network-​​aware con­text, one can (and should) exploit the social links, which can indi­cate how users relate to the seeker and how much weight their tag­ging actions should have in the result build-​​up. We pro­pose an algo­rithm that has the poten­tial to scale to cur­rent appli­ca­tions. While the prob­lem has already been con­sid­ered in pre­vi­ous lit­er­a­ture, this was done either under strong sim­pli­fy­ing assump­tions or under choices that can­not scale to even moderate-​​size real world appli­ca­tions. We first con­sider a key aspect of the prob­lem, which is access­ing the clos­est or most rel­e­vant users for a given seeker. We describe how this can be done on the fly (with­out any pre-​​computations) for sev­eral pos­si­ble choices — arguably the most nat­ural ones — of prox­im­ity com­pu­ta­tion in a user net­work. Based on this, our top-​​k algo­rithm is sound and com­plete, while address­ing the scal­a­bil­ity issues of the exist­ing ones. Impor­tantly, our tech­nique is instance opti­mal in the case when the search relies exclu­sively on the social weight of tag­ging actions. To fur­ther reduce response times, we then con­sider direc­tions for effi­ciency by approx­i­ma­tion. Exten­sive exper­i­ments on real world data show that our tech­niques can dras­ti­cally improve the response time, with­out sac­ri­fic­ing precision.”

    folk­son­omy tag­ging network-​​theory search-​​algorithms nudge-​​targets data-​​access

Items of some interest…

Posted on by

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

  • [1105.4335] Phys­i­cal approaches to the dynam­ics of genetic cir­cuits: A tutorial

    “Cel­lu­lar behav­ior is gov­erned by gene reg­u­la­tory processes that are intrin­si­cally dynamic and non­lin­ear, and are sub­ject to non-​​negligible amounts of ran­dom fluc­tu­a­tions. Such con­di­tions are ubiq­ui­tous in phys­i­cal sys­tems, where they have been stud­ied for decades using the tools of sta­tis­ti­cal and non­lin­ear physics. The goal of this review is to show how approaches tra­di­tion­ally used in physics can help in reach­ing a systems-​​level under­stand­ing of liv­ing cells. To that end, we present an overview of the dynam­i­cal phe­nom­ena exhib­ited by genetic cir­cuits and their func­tional sig­nif­i­cance. We also describe the the­o­ret­i­cal and exper­i­men­tal approaches that are being used to unravel the rela­tion­ship between cir­cuit struc­ture and func­tion in dynam­i­cal cel­lu­lar processes under the influ­ence of noise, both at the single-​​cell level and in cel­lu­lar pop­u­la­tions, where inter­cel­lu­lar cou­pling plays an impor­tant role.”

    systems-​​biology biological-​​engineering genetic-​​regulatory-​​networks emergent-​​design bio­chem­istry overview

  • [1106.0371] A Novel Image Seg­men­ta­tion Enhance­ment Tech­nique based on Active Con­tour and Topo­log­i­cal Alignments

    “Topo­log­i­cal align­ments and snakes are used in image pro­cess­ing, par­tic­u­larly in locat­ing object bound­aries. Both of them have their own advan­tages and lim­i­ta­tions. To improve the over­all image bound­ary detec­tion sys­tem, we focused on devel­op­ing a novel algo­rithm for image pro­cess­ing. The algo­rithm we pro­pose to develop will based on the active con­tour method in con­junc­tion with topo­log­i­cal align­ments method to enhance the image detec­tion approach. The algo­rithm presents novel tech­nique to incor­po­rate the advan­tages of both Topo­log­i­cal Align­ments and snakes. Where the ini­tial seg­men­ta­tion by Topo­log­i­cal Align­ments is firstly trans­formed into the input of the snake model and begins its evolve­ment to the inter­ested object bound­ary. The results show that the algo­rithm can deal with low con­trast images and shape cells, demon­strate the seg­men­ta­tion accu­racy under weak image bound­aries, which respon­si­ble for lack­ing accu­racy in image detect­ing tech­niques. We have achieved bet­ter seg­men­ta­tion and bound­ary detect­ing for the image, also the abil­ity of the sys­tem to improve the low con­trast and deal with over and under segmentation.”

    image-​​segmentation algo­rithms nudge-​​targets

  • [1106.2508] A Prac­ti­cal Imple­men­ta­tion of the Bernoulli Factory

    “…While sev­eral prac­ti­cal uses of the method have been pro­posed in Monte Carlo appli­ca­tions, these require an imple­men­ta­tion frame­work that is flex­i­ble, gen­eral and effi­cient. We present such a frame­work for func­tions that are either strictly lin­ear, con­cave, or con­vex on the unit inter­val using a series of enve­lope func­tions defined through a cas­cade, and show that this method not only greatly reduces the num­ber of input bits needed in prac­tice com­pared to other cur­rently pro­posed solu­tions for more spe­cific prob­lems, but can eas­ily be cou­pled to more asymp­tot­i­cally effi­cient meth­ods to allow for the­o­ret­i­cally strong results.”

    algo­rithms numerical-​​methods Monte-​​Carlo-​​simulation probability-​​theory nudge-​​targets

  • [1105.1729] Evo­lu­tion­ary search for novel super­hard materials

    “We have devel­oped a method for pre­dic­tion of the hard­est crys­tal struc­tures in a given chem­i­cal sys­tem. It is based on the evo­lu­tion­ary algo­rithm USPEX and electronegativity-​​based hard­ness model that we have aug­mented with bond-​​valence model and graph the­ory. These exten­sions enable cor­rect descrip­tion of the hard­ness of lay­ered, mol­e­c­u­lar and low-​​symmetry crys­tal struc­tures. Apply­ing this method to C and TiO2, we have (i) obtained a num­ber of low-​​energy car­bon struc­tures with hard­ness slightly lower than dia­mond and (ii) proved that TiO2 in any of its pos­si­ble poly­morphs can­not be the hard­est oxide, its hard­ness being below 17 GPa.”

    materials-​​science genetic-​​algorithm condensed-​​matter sim­u­la­tion nudge-​​targets

  • [1109.0573] Phase Retrieval via Matrix Completion

    “This paper con­sid­ers the fun­da­men­tal prob­lem of recov­er­ing a gen­eral sig­nal, an image for exam­ple, from the mag­ni­tude of its Fourier trans­form. This prob­lem, also known as phase retrieval, arises in many appli­ca­tions and has chal­lenged engi­neers, physi­cists, and math­e­mati­cians for decades. Its ori­gin comes from the fact that detec­tors can often times only record the squared mod­u­lus of the Fres­nel or Fraun­hofer dif­frac­tion pat­tern of the radi­a­tion that is scat­tered from an object. In such set­tings, one can­not mea­sure the phase of the opti­cal wave reach­ing the detec­tor and, there­fore, much infor­ma­tion about the scat­tered object or the opti­cal field is lost since, as is well known, the phase encodes a lot of the struc­tural con­tent of the image we wish to form.”

    image-​​processing inverse-​​problems signal-​​processing system-​​identification frequency-​​space algo­rithms nudge-​​targets numerical-​​methods

  • [1109.0807] Har­monic Analy­sis of Boolean Net­works: Deter­mi­na­tive Power and Perturbations

    “Con­sider a large Boolean net­work with a feed for­ward struc­ture. Given a prob­a­bil­ity dis­tri­b­u­tion for the inputs, can one find-​​possibly small-​​collections of input nodes that deter­mine the states of most other nodes in the network?…”

    Boolean-​​networks Kauff­ma­nia com­plex­ol­ogy discrete-​​mathematics mathematical-​​recreations nudge-​​targets

  • [0801.0830] Evo­lu­tion of cen­tral pat­tern gen­er­a­tors for the con­trol of a five-​​link bipedal walk­ing mechanism

    “With the aim of pro­duc­ing a sta­ble human-​​like bipedal gait, a five-​​link pla­nar walk­ing mech­a­nism is cou­pled with a cen­tral pat­tern gen­er­a­tor (CPG) neural net­work, con­sist­ing of units based on Matsuoka’s half-​​center oscil­la­tor model with a firm basis in neu­ro­phys­i­ol­ogy. As a min­i­mal­is­tic approach to bipedal walk­ing, this type of walk­ing mech­a­nism con­tains only four actu­a­tors, and is lack­ing feet and ankles. The mech­a­nism is sim­u­lated with accu­rate physics, allow­ing real­is­tic fit­ness eval­u­a­tions for the cre­ation of CPG con­trollers through evo­lu­tion­ary com­pu­ta­tion. The oscil­la­tory para­me­ters, inter­nal con­nec­tiv­ity struc­ture, and exter­nal feed­back path­ways of the net­works are deter­mined through genetic algo­rithms (GA) opti­miza­tion. The evolved CPG net­works are trans­ferred to a hard­ware imple­men­ta­tion of the mech­a­nism, to test their per­for­mance under real-​​world dynam­ics. Results con­firm that the bio­log­i­cally inspired CPG model is very well suited for con­trol­ling legged loco­mo­tion, since a diverse man­i­fes­ta­tion of CPG net­works (with and with­out exter­nal feed­back) have been observed to suc­ceed dur­ing the course of GA eval­u­a­tions. Obser­va­tions also imply that while the CPG mech­a­nism is inher­ently able to sus­tain a sta­ble gait, the uti­liza­tion of feed­back path­ways makes the gait more human-​​like and is needed to pro­vide a means to adapt to irreg­u­lar­i­ties in the environment.”

    robot­ics engineering-​​design genetic-​​algorithm neural-​​networks cyber­net­ics nudge-​​targets

  • [1109.3351] Phys­i­cal lim­its on coop­er­a­tive protein-​​DNA bind­ing and the kinet­ics of com­bi­na­to­r­ial tran­scrip­tion regulation

    “Much of the com­plex­ity observed in gene reg­u­la­tion orig­i­nates from coop­er­a­tive protein-​​DNA bind­ing. While stud­ies of the tar­get search of pro­teins for their spe­cific bind­ing sites on the DNA have revealed design prin­ci­ples for the quan­ti­ta­tive char­ac­ter­is­tics of protein-​​DNA inter­ac­tions, no such prin­ci­ples are known for the coop­er­a­tive inter­ac­tions between DNA-​​binding pro­teins. We con­sider a sim­ple the­o­ret­i­cal model for two inter­act­ing tran­scrip­tion fac­tor (TF) species, search­ing for and bind­ing to two adja­cent tar­get sites hid­den in the genomic back­ground. We study the kinetic com­pe­ti­tion of a dimer search path­way and a monomer search path­way, as well as the steady-​​state reg­u­la­tion func­tion medi­ated by the two TFs over a broad range of TF-​​TF inter­ac­tion strengths. Using a tran­scrip­tional AND-​​logic as exem­plary func­tional con­text, we iden­tify the func­tion­ally desir­able regime for the inter­ac­tion. We find that both weak and very strong TF-​​TF inter­ac­tions are favor­able, albeit with dif­fer­ent char­ac­ter­is­tics. How­ever, there is also an unfa­vor­able regime of inter­me­di­ate inter­ac­tions where the genetic response is pro­hib­i­tively slow.”

    biological-​​engineering genetic-​​regularory-​​networks systems-​​biology emergent-​​design nudge-​​targets

  • [1109.6874] #h00t: Cen­sor­ship Resis­tant Microblogging

    “Microblog­ging ser­vices such as Twit­ter are an increas­ingly impor­tant way to com­mu­ni­cate, both for indi­vid­u­als and for groups through the use of hash­tags that denote top­ics of con­ver­sa­tion. How­ever, groups can be eas­ily blocked from com­mu­ni­cat­ing through block­ing of posts with the given hash­tags. We pro­pose #h00t, a sys­tem for cen­sor­ship resis­tant microblog­ging. #h00t presents an inter­face that is much like Twit­ter, except that hash­tags are replaced with very short hashes (e.g., 24 bits) of the group iden­ti­fier. Nat­u­rally, with such short hashes, hash­tags from dif­fer­ent groups may col­lide and #h00t users will actu­ally seek to cre­ate col­li­sions. By encrypt­ing all posts with keys derived from the group iden­ti­fiers, #h00t client soft­ware can fil­ter out other groups’ posts while mak­ing such fil­ter­ing dif­fi­cult for the adver­sary. In essence, by lever­ag­ing col­li­sions, groups can tun­nel their posts in other groups’ posts. A cen­sor could not block a given group with­out also block­ing the other groups with col­lid­ing hash­tags. We eval­u­ate the fea­si­bil­ity of #h00t through traces col­lected from Twit­ter, show­ing that a sin­gle mod­ern com­puter has enough com­pu­ta­tional through­put to encrypt every tweet sent through Twit­ter in real time. We also use these traces to ana­lyze the band­width and anonymity trade­offs that would come with dif­fer­ent vari­a­tions on how group iden­ti­fiers are encoded and hash­tags are selected to pur­pose­fully col­lide with one another.”

    social-​​media steganog­ra­phy robust­ness activism cute

  • [1107.0414] A ran­dom walk on image patches

    “In this paper we address the prob­lem of under­stand­ing the suc­cess of algo­rithms that orga­nize patches accord­ing to graph-​​based met­rics. Algo­rithms that ana­lyze patches extracted from images or time series have led to state-​​of-​​the art tech­niques for clas­si­fi­ca­tion, denois­ing, and the study of non­lin­ear dynam­ics. The main con­tri­bu­tion of this work is to pro­vide a the­o­ret­i­cal expla­na­tion for the above exper­i­men­tal obser­va­tions. Our approach relies on a detailed analy­sis of the com­mute time met­ric on pro­to­typ­i­cal graph mod­els that epit­o­mize the geom­e­try observed in gen­eral patch graphs.…”

    image-​​segmentation image-​​analysis algo­rithms com­bi­na­torics nudge-​​targets

  • [1107.0385] An algo­rithm for autonomously plot­ting solu­tion sets in the pres­ence of turn­ing points

    “Plot­ting solu­tion sets for par­tic­u­lar equa­tions may be com­pli­cated by the exis­tence of turn­ing points. Here we describe an algo­rithm which not only over­comes such prob­lem­atic points, but does so in the most gen­eral of set­tings. Appli­ca­tions of the algo­rithm are high­lighted through two exam­ples: the first pro­vides ver­i­fi­ca­tion, while the sec­ond demon­strates a non-​​trivial appli­ca­tion. The lat­ter is fol­lowed by a thor­ough run-​​time analy­sis. While both exam­ples deal with bivari­ate equa­tions, it is dis­cussed how the algo­rithm may be gen­er­al­ized for space curves in $R^{3}$.”

    visu­al­iza­tion math­e­mat­ics graph­ics approx­i­ma­tion algo­rithms nudge-​​targets

  • [1105.1033] Adap­tively Learn­ing the Crowd Kernel

    “We intro­duce an algo­rithm that, given n objects, learns a sim­i­lar­ity matrix over all n^2 pairs, from crowd­sourced data alone. The algo­rithm sam­ples responses to adap­tively cho­sen triplet-​​based relative-​​similarity queries. Each query has the form “is object ‘a’ more sim­i­lar to ‘b’ or to ‘c’?” and is cho­sen to be max­i­mally infor­ma­tive given the pre­ced­ing responses. The out­put is an embed­ding of the objects into Euclid­ean space (like MDS); we refer to this as the “crowd ker­nel.” SVMs reveal that the crowd ker­nel cap­tures promi­nent and sub­tle fea­tures across a num­ber of domains, such as “is striped” among neck­ties and “vowel vs. con­so­nant” among letters.”

    clas­si­fi­ca­tion ontology-​​discovery crowd­sourc­ing feature-​​extraction algo­rithms nudge-​​targets performance-​​space-​​analysis

  • [1109.1030] An Algo­rithm for Detect­ing Intrin­si­cally Knot­ted Graphs

    “We describe an algo­rithm that rec­og­nizes some (per­haps all) intrin­si­cally knot­ted (IK) graphs, and can help find knot­less embed­dings for graphs that are not IK. The algo­rithm, imple­mented as a Math­e­mat­ica pro­gram, has already been used by Gold­berg, Mattman, and Naimi [6] to greatly expand the list of known minor min­i­mal IK graphs, and to find knot­less embed­dings for some graphs that had pre­vi­ously resisted attempts to clas­sify them as IK or non-​​IK.”

    com­bi­na­torics topol­ogy algo­rithms nudge-​​targets

  • [1109.5635] Approx­i­mat­ing Edit Dis­tance in Near-​​Linear Time

    “We show how to com­pute the edit dis­tance between two strings of length n up to a fac­tor of 2^{~O(sqrt(log n))} in n^(1+o(1)) time. This is the first sub-​​polynomial approx­i­ma­tion algo­rithm for this prob­lem that runs in near-​​linear time, improv­ing on the state-​​of-​​the-​​art n^(1/3+o(1)) approx­i­ma­tion. Pre­vi­ously, approx­i­ma­tion of 2^{~O(sqrt(log n))} was known only for embed­ding edit dis­tance into l_​1, and it is not known if that embed­ding can be com­puted in less than qua­dratic time.”

    algo­rithms string-​​editing Levenshtein-​​distance rewriting-​​systems bioin­for­mat­ics nudge-​​targets

  • [1107.1866] Priority-​​based task reas­sign­ments in hier­ar­chi­cal 2D mesh-​​connected sys­tems using tableaux

    “Task reas­sign­ments in 2D mesh-​​connected sys­tems (2D-​​MSs) have been researched and sim­u­lated for sev­eral decades. We pro­pose a hier­ar­chi­cal 2D mesh-​​connected sys­tem (2D-​​HMS) in order to exploit the reg­u­lar nature of a 2D-​​MS. In our approach priority-​​based task assign­ments and reas­sign­ments in a 2D-​​HMS are rep­re­sented by tableaux and their algo­rithms. We pro­vide exam­ples of priority-​​based task reas­sign­ments in a 2D-​​HMS in which task relo­ca­tions are sim­ply reduced to a jeu de taquin slide.”

    sched­ul­ing operations-​​research algo­rithms grid-​​computing opti­miza­tion nudge-​​targets

  • [1101.4744] Clus­ter­ing func­tional data using wavelets

    “We present two meth­ods for detect­ing pat­terns and clus­ters in high dimen­sional time-​​dependent func­tional data. Our meth­ods are based on wavelet-​​based sim­i­lar­ity mea­sures, since wavelets are well suited for iden­ti­fy­ing highly dis­crim­i­nant local time and scale fea­tures. The mul­tires­o­lu­tion aspect of the wavelet trans­form pro­vides a time-​​scale decom­po­si­tion of the sig­nals allow­ing to visu­al­ize and to clus­ter the func­tional data into homo­ge­neous groups. For each input func­tion, through its empir­i­cal orthog­o­nal wavelet trans­form the first method uses the dis­tri­b­u­tion of energy across scales gen­er­ate a handy num­ber of fea­tures that can be suf­fi­cient to still make the sig­nals well dis­tin­guish­able. Our new sim­i­lar­ity mea­sure com­bined with an effi­cient fea­ture selec­tion tech­nique in the wavelet domain is then used within more or less clas­si­cal clus­ter­ing algo­rithms to effec­tively dif­fer­en­ti­ate among high dimen­sional pop­u­la­tions. The sec­ond method uses dis­sim­i­lar­ity mea­sures between the whole time-​​scale rep­re­sen­ta­tions and are based on wavelet-​​coherence tools. The clus­ter­ing is then per­formed using a k-​​centroid algo­rithm start­ing from these dis­sim­i­lar­i­ties. Prac­ti­cal per­for­mance of these meth­ods that jointly designs both the fea­ture selec­tion in the wavelet domain and the clas­si­fi­ca­tion dis­tance is demon­strated through sim­u­la­tions as well as daily pro­files of the French elec­tric­ity power demand.”

    clas­si­fi­ca­tion time-​​series feature-​​extraction machine-​​learning multiobjective-​​optimization ontology-​​discovery wavelets nudge-​​targets

  • [1105.3726] Con­trol­ling Com­plex Net­works with Com­pen­satory Perturbations

    “The response of com­plex net­works to per­tur­ba­tions is of utmost impor­tance in areas as diverse as ecosys­tem man­age­ment, emer­gency response, and cell repro­gram­ming. A fun­da­men­tal prop­erty of net­works is that the per­tur­ba­tion of one node can affect other nodes, in a process that may cause the entire or sub­stan­tial part of the sys­tem to change behav­ior and pos­si­bly col­lapse. Recent research in meta­bolic and food-​​web net­works has demon­strated the con­cept that net­work dam­age caused by exter­nal per­tur­ba­tions can often be mit­i­gated or reversed by the appli­ca­tion of com­pen­satory per­tur­ba­tions. Com­pen­satory per­tur­ba­tions are con­strained to be phys­i­cally admis­si­ble and amenable to imple­men­ta­tion on the net­work. How­ever, the sys­tem­atic iden­ti­fi­ca­tion of com­pen­satory per­tur­ba­tions that con­form to these con­straints remains an open prob­lem. Here, we present a method to con­struct com­pen­satory per­tur­ba­tions that can con­trol the fate of gen­eral net­works under such con­straints. Our approach accounts for the full non­lin­ear behav­ior of real com­plex net­works and can bring the sys­tem to a desir­able tar­get state even when this state is not directly acces­si­ble. Appli­ca­tions to genetic net­works show that com­pen­satory per­tur­ba­tions are effec­tive even when lim­ited to a small frac­tion of all nodes in the net­work and that they are far more effec­tive when lim­ited to the highest-​​degree nodes. The approach is con­cep­tu­ally sim­ple and com­pu­ta­tion­ally effi­cient, mak­ing it suit­able for the res­cue, con­trol, and repro­gram­ming of large com­plex net­works in var­i­ous domains.”

    emergent-​​design com­plex­ol­ogy con­trol biological-​​engineering nudge-​​targets

  • [1109.1275] A For­mal Ver­i­fi­ca­tion Approach to the Design of Syn­thetic Gene Networks

    “The design of genetic net­works with spe­cific func­tions is one of the major goals of syn­thetic biol­ogy. How­ever, con­struct­ing bio­log­i­cal devices that work “as required” remains chal­leng­ing, while the cost of uncov­er­ing flawed designs exper­i­men­tally is large. To address this issue, we pro­pose a fully auto­mated frame­work that allows the cor­rect­ness of syn­thetic gene net­works to be for­mally ver­i­fied in sil­ico from rich, high level func­tional spec­i­fi­ca­tions. Given a device, we auto­mat­i­cally con­struct a math­e­mat­i­cal model from exper­i­men­tal data char­ac­ter­iz­ing the parts it is com­posed of. The spe­cific model struc­ture guar­an­tees that all exper­i­men­tal obser­va­tions are cap­tured and allows us to con­struct finite abstrac­tions through poly­he­dral oper­a­tions. The cor­rect­ness of the model with respect to tem­po­ral logic spec­i­fi­ca­tions can then be ver­i­fied auto­mat­i­cally using meth­ods inspired by model check­ing. Over­all, our pro­ce­dure is con­ser­v­a­tive but it can fil­ter through a large num­ber of poten­tial device designs and select few that sat­isfy the spec­i­fi­ca­tion to be imple­mented and tested fur­ther exper­i­men­tally. Illus­tra­tive exam­ples of the appli­ca­tion of our meth­ods to the design of sim­ple syn­thetic gene net­works are included.”

    genetic-​​regulatory-​​networks bioin­for­mat­ics biological-​​engineering design-​​automation emergent-​​design acceptance-​​testing performance-​​measure nudge

  • [1108.1150] Epis­ta­sis can lead to frag­mented neu­tral spaces and con­tin­gency in evolution

    “Under neu­tral rec­i­p­ro­cal sign epis­ta­sis, two genetic changes are jointly neu­tral, even though their indi­vid­ual effects are dele­te­ri­ous. By using the widely stud­ied map­ping from an RNA sequence to sec­ondary struc­ture, we inves­ti­gate the effect of this kind of epis­ta­sis on neu­tral spaces cor­re­spond­ing to net­works of geno­types that fold to the same sec­ondary struc­ture. Neu­tral net­works for RNA struc­tures with n bonds are typ­i­cally frag­mented into at least 2n dif­fer­ent neu­tral com­po­nents that can­not be con­nected by sin­gle point muta­tions. By exhaus­tive enu­mer­a­tion of all RNA sec­ondary struc­tures of sequences of length 15 we show that most net­works are not dom­i­nated by one neu­tral com­po­nent, but are rather bro­ken up into mul­ti­ple large com­po­nents. Although they gen­er­ate the same phe­no­type, com­po­nents of a sin­gle neu­tral net­work are het­ero­ge­neous, show­ing wide vari­a­tions in their robust­ness and their evolv­abil­ity. Both prop­er­ties are cor­re­lated with com­po­nent size, rather than with the size of their under­ly­ing neu­tral net­work. In par­tic­u­lar, sets of acces­si­ble phe­no­types can vary quite strongly between com­po­nents. Thus, the poten­tial for future inno­va­tion is con­tin­gent on which neu­tral com­po­nent a pop­u­la­tion occu­pies. We fur­ther argue that neu­tral rec­i­p­ro­cal sign epis­ta­sis may have sim­i­lar con­se­quences for neu­tral evo­lu­tion of other bio­log­i­cal sys­tems as well.”

    com­bi­na­torics RNA neutral-​​networks com­plex­ol­ogy bioin­for­mat­ics polymer-​​models mathematical-​​recreations nudge-​​targets

  • Old​Fonts​.com | About Us

    “Will­son founded 3IP in 1989 to self-​​publish a book of pre­ten­tious nature essays. Soon after, he found him­self tin­ker­ing with type design, and 3IP has since become known for its library of authentic-​​looking hand­writ­ing fonts—many of them mod­eled after his­tor­i­cal penmanship—and antique text simulations.”

    typog­ra­phy fonts hand­writ­ing

  • Col­lec­tive Wis­dom — Crooked Timber

    “More broadly, a sim­ple dic­tum such as ‘lis­ten to the experts’ isn’t going to work, pre­cisely because our most pow­er­ful meth­ods of gen­er­at­ing new knowl­edge (viz. the sci­ences) are not so much based on lis­ten­ing to indi­vid­ual experts, as on includ­ing these experts (and many oth­ers) in broader social sys­tems which expose them con­tin­u­ally to the ideas of oth­ers and vice-​​versa. Design­ing (or – per­haps bet­ter– nur­tur­ing) such sys­tems is hard to think about and hard to do – but it has to be the way forward.”

    via:arsyed wisdom-​​of-​​crowds com­plex­ol­ogy inno­va­tion cultural-​​assumptions cre­den­tial­ing problem-​​solving what-​​is-​​true-​​is-​​what-​​gets-​​said

  • [1109.1146] A Dis­trib­uted Mincut/​Maxflow Algo­rithm Com­bin­ing Path Aug­men­ta­tion and Push-​​Relabel

    “We develop a novel dis­trib­uted algo­rithm for the min­i­mum cut prob­lem. We pri­mar­ily aim at solv­ing large sparse prob­lems. Assum­ing ver­tices of the graph are par­ti­tioned into sev­eral regions, the algo­rithm per­forms path aug­men­ta­tions inside the regions and updates of the push-​​relabel style between the regions. The inter­ac­tion between regions is con­sid­ered expen­sive (regions are loaded into the mem­ory one-​​by-​​one or located on sep­a­rate machines in a net­work). The algo­rithm works in sweeps — passes over all regions. Let $B$ be the set of ver­tices inci­dent to inter-​​region edges of the graph. We present a sequen­tial and par­al­lel ver­sions of the algo­rithm which ter­mi­nate in at most $2|B|^2+1$ sweeps. The com­pet­ing algo­rithm by Delong and Boykov uses push-​​relabel updates inside regions. In the case of a fixed par­ti­tion we prove that this algo­rithm has a tight $O(n^2)$ bound on the num­ber of sweeps, where $n$ is the num­ber of ver­tices. We tested sequen­tial ver­sions of the algo­rithms on instances of maxflow prob­lems in com­puter vision. Exper­i­men­tally, the num­ber of sweeps required by the new algo­rithm is much lower than for the Delong and Boykov’s vari­ant. Large prob­lems (up to $108$ ver­tices and $6cdot 108$ edges) are solved using under 1GB of mem­ory in about 10 sweeps.”

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

  • [1105.4953] A fast near­est neigh­bor search algo­rithm based on vec­tor quantization

    “In this arti­cle, we pro­pose a new fast near­est neigh­bor search algo­rithm, based on vec­tor quan­ti­za­tion. Like many other branch and bound search algo­rithms [1,10], a pre­pro­cess­ing recur­sively par­ti­tions the data set into dis­jointed sub­sets until the num­ber of points in each part is small enough. In doing so, a search-​​tree data struc­ture is built. This pre­lim­i­nary recur­sive data-​​set par­ti­tion is based on the vec­tor quan­ti­za­tion of the empir­i­cal dis­tri­b­u­tion of the ini­tial data-​​set. Unlike pre­vi­ously cited meth­ods, this kind of par­ti­tions does not a pri­ori allow to elim­i­nate sev­eral brother nodes in the search tree with a sin­gle test. To over­come this dif­fi­culty, we pro­pose an algo­rithm to reduce the num­ber of tested brother nodes to a min­i­mal list that we call “friend Voronoi cells”. The com­plete descrip­tion of the method requires a deeper insight into the prop­er­ties of Delau­nay tri­an­gu­la­tions and Voronoi diagrams”

    algo­rithms search-​​algorithms data-​​analysis nudge-​​targets

  • [1108.0986] A prox­i­mal point algo­rithm for sequen­tial fea­ture extrac­tion applications

    “We pro­pose a prox­i­mal point algo­rithm to solve LAROS prob­lem, that is the prob­lem of find­ing a “large approx­i­mately rank-​​one sub­ma­trix”. This LAROS prob­lem is used to sequen­tially extract fea­tures in data. We also develop a new stop­ping cri­te­rion for the prox­i­mal point algo­rithm, which is based on the dual­ity con­di­tions of eps-​​optimal solu­tions of the LAROS prob­lem, with a the­o­ret­i­cal guar­an­tee. We test our algo­rithm with two image data­bases and show that we can use the LAROS prob­lem to extract appro­pri­ate com­mon fea­tures from these images.”

    algo­rithms image-​​segmentation feature-​​extraction nudge-​​targets

  • [1011.2348] Ergodic Con­trol and Poly­he­dral approaches to PageR­ank Optimization

    “We study a gen­eral class of PageR­ank opti­miza­tion prob­lems which con­sist in find­ing an opti­mal out­link strat­egy for a web site sub­ject to design con­straints. We con­sider both a con­tin­u­ous prob­lem, in which one can choose the inten­sity of a link, and a dis­crete one, in which in each page, there are oblig­a­tory links, fac­ul­ta­tive links and for­bid­den links. We show that the con­tin­u­ous prob­lem, as well as its dis­crete vari­ant when there are no con­straints cou­pling dif­fer­ent pages, can both be mod­eled by con­strained Markov deci­sion processes with ergodic reward, in which the web­mas­ter deter­mines the tran­si­tion prob­a­bil­i­ties of web­surfers. Although the num­ber of actions turns out to be expo­nen­tial, we show that an asso­ci­ated poly­tope of tran­si­tion mea­sures has a con­cise rep­re­sen­ta­tion, from which we deduce that the con­tin­u­ous prob­lem is solv­able in poly­no­mial time, and that the same is true for the dis­crete prob­lem when there are no cou­pling con­straints. We also pro­vide effi­cient algo­rithms, adapted to very large net­works. Then, we inves­ti­gate the qual­i­ta­tive fea­tures of opti­mal out­link strate­gies, and iden­tify in par­tic­u­lar assump­tions under which there exists a “mas­ter” page to which all con­trolled pages should point. We report numer­i­cal results on frag­ments of the real web graph.”

    opti­miza­tion PageR­ank operations-​​research algo­rithms nudge-​​targets

Items of some interest…

Posted on by

These are my Pin​board​.in links for May 15th from 08:31 to 12:15: