Items of some interest…

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…

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…

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

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

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

    clas­si­fi­ca­tion sta­tis­tics his­tograms met­rics clus­ter­ing
  • [1110.1412] Quan­ti­fy­ing loopy net­work architectures

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

    com­plex­ol­ogy bio­physics network-​​theory met­rics
  • [1110.1393] High-​​Precision Tun­ing of State for Mem­ris­tive Devices by Adapt­able Variation-​​Tolerant Algorithm

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

    mem­ris­tors engineering-​​design sim­u­la­tion control-​​systems nudge-​​targets
  • [1110.1521] Nodal domains of a non-​​separable prob­lem — the right angled isosce­les triangle

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

    physics algo­rithms analytical-​​results open-​​questions geom­e­try acoustics exact-​​form nudge-​​targets
  • [1110.1485] A Face Recog­ni­tion Scheme using Wavelet Based Dom­i­nant Features

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

    face-​​recognition algo­rithms image-​​processing wavelets nudge-​​targets
  • [1110.1553] Hier­ar­chi­cal QR fac­tor­iza­tion algo­rithms for multi-​​core clus­ter systems

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

    parallel-​​computing operations-​​research fac­tor­iza­tion algo­rithms nudge-​​targets meta-​​algorithms
  • [1110.1560] On the Col­or­ing of Grid Wire­less Sen­sor Net­works: the Vector-​​Based Col­or­ing Method

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

    graph-​​theory algo­rithms operations-​​research nudge-​​targets
  • [1110.1580] A Polylogarithmic-​​Competitive Algo­rithm for the k-​​Server Problem

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

    sched­ul­ing operations-​​research algo­rithms nudge-​​targets
  • [1110.1590] PSA: The Packet Sched­ul­ing Algo­rithm for Wire­less Sen­sor Networks

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

    sensor-​​networks distributed-​​processing sched­ul­ing rout­ing operations-​​research algo­rithms nudge-​​targets
  • [1110.0725] A Sur­vey of Dis­trib­uted Data Aggre­ga­tion Algorithms

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

    sta­tis­tics reviews distributed-​​processing com­mu­ni­ca­tion coor­di­na­tion nudge-​​targets
  • [0911.3482] Com­plex­ity of Net­works (reprise)

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

    network-​​theory com­plex­ol­ogy complex-​​systems mea­sure­ment per­form structure-​​function-​​relations discrete-​​mathematics
  • [1108.4279] Detec­tion and emergence

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

    com­plex­ol­ogy emer­gence pragmatism-it-ain’t but-​​soon
  • [1001.4278] Weight Opti­miza­tion for Dis­trib­uted Aver­age Con­sen­sus Algo­rithm in Sym­met­ric, CCS & KCS Star Networks

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

    operations-​​research decision-​​making network-​​theory nudge-​​targets
  • [1109.5389] Water dri­ves pep­tide con­for­ma­tional transitions

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

    molecular-​​design systems-​​biology sim­u­la­tion intracellular-​​dynamics kinda-​​knew-​​this-​​a-​​long-​​time-​​ago bio­chem­istry
  • [1105.1445] Vehic­u­lar traf­fic flow at an inter­sec­tion with the pos­si­bil­ity of turning

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

    cellular-​​automata com­plex­ol­ogy traffic-​​models agent-​​based sim­u­la­tion nudge-​​substrates
  • [1110.1391] A Com­par­i­son of Dif­fer­ent Machine Translit­er­a­tion Models

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

    natural-​​language-​​processing machine-​​learning review nudge-​​targets
  • [1108.5508] A Pat­tern Measure

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

    cog­ni­tion aes­thet­ics experimental-​​psychology nudge-​​targets learning-​​by-​​watching
  • [1106.5264] Acquir­ing Cor­rect Knowl­edge for Nat­ural Lan­guage Generation

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

    natural-​​language-​​processing artificial-​​intelligence interesting-​​problems high-​​hanging-​​fruit machine-​​learning nudge-​​targets
  • [1105.2423] Cytoskele­ton and Cell Motility

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

    bio­physics biol­ogy review i-​​used-​​to-​​do-​​this-​​stuff lovely
  • [1110.0671] Width Dis­tri­b­u­tions for Con­vex Reg­u­lar Polyhedra

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

    geom­e­try mathematical-​​recreations nudge-​​targets
  • [cs/​0305036] Using Dynamic Sim­u­la­tion in the Devel­op­ment of Con­struc­tion Machinery

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

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

Items of some interest…

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

  • [1106.1804] A Crit­i­cal Assess­ment of Bench­mark Com­par­i­son in Planning

    “Recent trends in plan­ning research have led to empir­i­cal com­par­i­son becom­ing com­mon­place. The field has started to set­tle into a method­ol­ogy for such com­par­isons, which for obvi­ous prac­ti­cal rea­sons requires run­ning a sub­set of plan­ners on a sub­set of prob­lems. In this paper, we char­ac­ter­ize the method­ol­ogy and exam­ine eight implicit assump­tions about the prob­lems, plan­ners and met­rics used in many of these com­par­isons. The prob­lem assump­tions are: PR1) the per­for­mance of a gen­eral pur­pose plan­ner should not be penalized/​biased if exe­cuted on a sam­pling of prob­lems and domains, PR2) minor syn­tac­tic dif­fer­ences in rep­re­sen­ta­tion do not affect per­for­mance, and PR3) prob­lems should be solv­able by STRIPS capa­ble plan­ners unless they require ADL. The plan­ner assump­tions are: PL1) the lat­est ver­sion of a plan­ner is the best one to use, PL2) default para­me­ter set­tings approx­i­mate good per­for­mance, and PL3) time cut-​​offs do not unduly bias out­come. The met­rics assump­tions are: M1) per­for­mance degrades sim­i­larly for each plan­ner when run on degraded run­time envi­ron­ments (e.g., machine plat­form) and M2) the num­ber of plan steps dis­tin­guishes per­for­mance. We find that most of these assump­tions are not sup­ported empir­i­cally; in par­tic­u­lar, that plan­ners are affected dif­fer­ently by these assump­tions. We con­clude with a call to the com­mu­nity to devote research resources to improv­ing the state of the prac­tice and espe­cially to enhanc­ing the avail­able bench­mark problems.”

    plan­ning bench­mark­ing algo­rithms horse-​​races engineering-​​design operations-​​research nudge-​​targets
  • [1108.4361] The rela­tion­ship between acquain­tance­ship and coau­thor­ship in sci­en­tific col­lab­o­ra­tion networks

    “This arti­cle exam­ines the rela­tion­ship between acquain­tance­ship and coau­thor­ship pat­terns in a multi-​​disciplinary, multi-​​institutional, geo­graph­i­cally dis­trib­uted research cen­ter. Two social net­works are con­structed and com­pared: a net­work of coau­thor­ship, rep­re­sent­ing how researchers write arti­cles with one another, and a net­work of acquain­tance­ship, rep­re­sent­ing how those researchers know each other on a per­sonal level, based on their responses to an online sur­vey. Sta­tis­ti­cal analy­ses of the topol­ogy and com­mu­nity struc­ture of these net­works point to the impor­tance of small-​​scale, local, per­sonal net­works pred­i­cated upon acquain­tance­ship for accom­plish­ing col­lab­o­ra­tive work in sci­en­tific communities.”

    academic-​​culture network-​​theory cita­tion social-​​networks
  • [1108.4223] The set-​​theoretic multiverse

    “The mul­ti­verse view in set the­ory, intro­duced and argued for in this arti­cle, is the view that there are many dis­tinct con­cepts of set, each instan­ti­ated in a cor­re­spond­ing set-​​theoretic uni­verse. The uni­verse view, in con­trast, asserts that there is an absolute back­ground set con­cept, with a cor­re­spond­ing absolute set-​​theoretic uni­verse in which every set-​​theoretic ques­tion has a def­i­nite answer. The mul­ti­verse posi­tion, I argue, explains our expe­ri­ence with the enor­mous diver­sity of set-​​theoretic pos­si­bil­i­ties, a phe­nom­e­non that chal­lenges the uni­verse view. In par­tic­u­lar, I argue that the con­tin­uum hypoth­e­sis is set­tled on the mul­ti­verse view by our exten­sive knowl­edge about how it behaves in the mul­ti­verse, and as a result it can no longer be set­tled in the man­ner for­merly hoped for.”

    math­e­mat­ics mathematical-​​criticism looking-​​forward-​​to-​​understanding-​​this-​​someday pragmatism-it-ain’t
  • [1102.1934] The struc­ture of the Arts & Human­i­ties Cita­tion Index: A map­ping on the basis of aggre­gated cita­tions among 1,157 journals

    “Using the Arts & Human­i­ties Cita­tion Index (A&HCI) 2008, we apply map­ping tech­niques pre­vi­ously devel­oped for map­ping jour­nal struc­tures in the Sci­ence and Social Sci­ence Cita­tion Indices. Cita­tion rela­tions among the 110,718 records were aggre­gated at the level of 1,157 jour­nals spe­cific to the A&HCI, and the jour­nal struc­tures are ques­tioned on whether a cog­ni­tive struc­ture can be recon­structed and visu­al­ized. Both cosine-​​normalization (bot­tom up) and fac­tor analy­sis (top down) sug­gest a divi­sion into approx­i­mately twelve sub­sets. The rela­tions among these sub­sets are explored using var­i­ous visu­al­iza­tion tech­niques. How­ever, we were not able to retrieve this struc­ture using the ISI Sub­ject Cat­e­gories, includ­ing the 25 cat­e­gories which are spe­cific to the A&HCI. We dis­cuss options for val­i­da­tion such as against the cat­e­gories of the Human­i­ties Indi­ca­tors of the Amer­i­can Acad­emy of Arts and Sci­ences, the panel struc­ture of the Euro­pean Ref­er­ence Index for the Human­i­ties (ERIH), and com­pare our results with the cur­ricu­lum orga­ni­za­tion of the Human­i­ties Sec­tion of the Col­lege of Let­ters and Sci­ences of UCLA as an exam­ple of insti­tu­tional organization.”

    network-​​theory citation-​​networks human­i­ties academic-​​culture quantitative-​​humanities
  • [1108.4220] A Dynam­i­cal Sys­tems Approach for Sta­tic Eval­u­a­tion in Go

    “In the paper argu­ments are given why the con­cept of sta­tic eval­u­a­tion has the poten­tial to be a use­ful exten­sion to Monte Carlo tree search. A new con­cept of mod­el­ing sta­tic eval­u­a­tion through a dynam­i­cal sys­tem is intro­duced and strengths and weak­nesses are dis­cussed. The gen­eral suit­abil­ity of this approach is demonstrated.”

    representation-​​theory plan­ning monte-​​carlo-​​models nudge algo­rithms
  • [1105.5449] AntNet: Dis­trib­uted Stig­mer­getic Con­trol for Com­mu­ni­ca­tions Networks

    “…We com­pare our algo­rithm with six state-​​of-​​the-​​art rout­ing algo­rithms com­ing from the telecom­mu­ni­ca­tions and machine learn­ing fields. The algo­rithms’ per­for­mance is eval­u­ated over a set of real­is­tic test­beds. We run many exper­i­ments over real and arti­fi­cial IP data­gram net­works with increas­ing num­ber of nodes and under sev­eral par­a­dig­matic spa­tial and tem­po­ral traf­fic dis­tri­b­u­tions. Results are very encour­ag­ing. AntNet showed supe­rior per­for­mance under all the exper­i­men­tal con­di­tions with respect to its com­peti­tors. We ana­lyze the main char­ac­ter­is­tics of the algo­rithm and try to explain the rea­sons for its superiority.”

    ant-​​colony-​​optimization network-​​theory net­works con­trol algo­rithms nudge-​​targets rout­ing
  • Bozo Sapi­ens: Sacco and Vanzetti: Evidence

    “Wigmore’s tech­nique, like prob­a­bil­ity itself, is both wide-​​ranging and tediously painstak­ing; his book was pop­u­lar only among insom­niac judges. But now that com­put­ers can take on the numer­i­cal drudgery, it is prov­ing its worth in just such tan­gled cases as Sacco’s and Vanzetti’s. The legal schol­ars Joseph Kadane and David Schum have applied a sophis­ti­cated exten­sion of Wigmore’s method to the vast body of evi­dence from the case. Theirs is a remark­able achieve­ment; their charts retain all the orig­i­nal com­plex­i­ties: the facts with­held or per­verted, the hearsay, the lies told and dis­avowed on both sides, the charged polit­i­cal atmos­phere of eighty years ago. They never dis­count a fact, no mat­ter how far-​​fetched; they  sim­ply give it its due weight in their dynamic struc­ture. Their con­clu­sion?  Unjust though it is to sum­ma­rize a book in a sen­tence, the bal­ance of prob­a­bil­ity seems to favor the view expressed long ago by one of the defen­dants’ close com­pan­ions: “every­one in the Boston anar­chis­tic cir­cle knew that Sacco was guilty and that Vanzetti was inno­cent as far as the actual par­tic­i­pa­tion in the killing.” So, there it is: whichever side our polit­i­cal instincts favor, we are des­tined to be half wrong. Vanzetti’s last words were: “I wish to for­give some peo­ple for what they are now doing to me.”  If we were all will­ing to make the extra effort to work out the prob­a­bil­i­ties, per­haps we might not need for­give­ness so often.”

    probability-​​theory legal-​​studies computational-​​methods his­tory
  • Get­ting first sale wrong

    “I hate to imag­ine it, but this deci­sion raises some fright­en­ing pos­si­bil­i­ties and requires greater vig­i­lance on the part of librar­i­ans.  At the very least, libraries must demand infor­ma­tion from pub­lish­ers about where every item has been man­u­fac­tured. Obtain­ing such infor­ma­tion is no longer an option, since our legal uses of the things we buy now depends on know­ing this, and the place where the pub­lisher is located or where the sale took place is sim­ply not suf­fi­cient.  But what I really fear is that pub­lish­ers will begin to man­u­fac­ture more of their works over­seas and then try to demand a higher price – one that includes “pub­lic lend­ing rights” – from libraries. If libraries are in a dif­fi­cult posi­tion, stu­dents may be even worse off under the Sec­ond Circuit’s rul­ing.  Again, pub­lish­ers now have an incen­tive to man­u­fac­ture their text­books abroad and sell them to U.S. stu­dents.  Such stu­dents would no longer have the right to re-​​sell their text­books or to pur­chase used texts.  The defen­dant in the case, Supap Kirt­saeng, had made a lucra­tive busi­ness out of reselling text­books pur­chased in Asia.  He was per­haps an unsym­pa­thetic party, but what he was doing was not dif­fer­ent in kind from the resale of texts that is com­mon on all col­lege cam­puses.  This activ­ity makes higher edu­ca­tion a lit­tle more pos­si­ble for many.  Now pub­lish­ers have an easy way for to close down this sec­ondary mar­ket for text­books, about which they have com­plained for years.  In the process, the cost of edu­ca­tion for col­lege stu­dents would be pushed up even further.”

    copy­right insan­ity intellectual-​​property academic-​​culture librar­i­ans
  • [1106.6037] Black Hole Search with Finite Automata Scat­tered in a Syn­chro­nous Torus

    “We con­sider the prob­lem of locat­ing a black hole in syn­chro­nous anony­mous net­works using finite state agents. A black hole is a harm­ful node in the net­work that destroys any agent vis­it­ing that node with­out leav­ing any trace. The objec­tive is to locate the black hole with­out destroy­ing too many agents. This is dif­fi­cult to achieve when the agents are ini­tially scat­tered in the net­work and are unaware of the loca­tion of each other. Pre­vi­ous stud­ies for black hole search used more pow­er­ful mod­els where the agents had non-​​constant mem­ory, were labelled with dis­tinct iden­ti­fiers and could either write mes­sages on the nodes of the net­work or mark the edges of the net­work. In con­trast, we solve the prob­lem using a small team of finite-​​state agents each car­ry­ing a con­stant num­ber of iden­ti­cal tokens that could be placed on the nodes of the net­work. Thus, all resources used in our algo­rithms are inde­pen­dent of the net­work size. We restrict our atten­tion to ori­ented torus net­works and first show that no finite team of finite state agents can solve the prob­lem in such net­works, when the tokens are not mov­able. In case the agents are equipped with mov­able tokens, we deter­mine lower bounds on the num­ber of agents and tokens required for solv­ing the prob­lem in torus net­works of arbi­trary size. Fur­ther, we present a deter­min­is­tic solu­tion to the black hole search prob­lem for ori­ented torus net­works, using the min­i­mum num­ber of agents and tokens.”

    algo­rithms agent-​​based multi-​​agent-​​systems network-​​theory nudge-​​targets
  • [1106.1821] Col­lec­tive Intel­li­gence, Data Rout­ing and Braess’ Paradox

    “We con­sider the prob­lem of design­ing the the util­ity func­tions of the utility-​​maximizing agents in a multi-​​agent sys­tem so that they work syn­er­gis­ti­cally to max­i­mize a global util­ity. The par­tic­u­lar prob­lem domain we explore is the con­trol of net­work rout­ing by plac­ing agents on all the routers in the net­work. Con­ven­tional approaches to this task have the agents all use the Ideal Short­est Path rout­ing Algo­rithm (ISPA). We demon­strate that in many cases, due to the side-​​effects of one agent’s actions on another agent’s per­for­mance, hav­ing agents use ISPA’s is sub­op­ti­mal as far as global aggre­gate cost is con­cerned, even when they are only used to route infin­i­tes­i­mally small amounts of traf­fic. The util­ity func­tions of the indi­vid­ual agents are not “aligned” with the global util­ity, intu­itively speak­ing. As a par­tic­u­lar exam­ple of this we present an instance of Braess’ para­dox in which adding new links to a net­work whose agents all use the ISPA results in a decrease in over­all through­put. We also demon­strate that load-​​balancing, in which the agents’ deci­sions are col­lec­tively made to opti­mize the global cost incurred by all traf­fic cur­rently being routed, is sub­op­ti­mal as far as global cost aver­aged across time is con­cerned. This is also due to ‘side-​​effects’, in this case of cur­rent rout­ing deci­sion on future traf­fic. The math­e­mat­ics of Col­lec­tive Intel­li­gence (COIN) is con­cerned pre­cisely with the issue of avoid­ing such dele­te­ri­ous side-​​effects in multi-​​agent sys­tems, both over time and space. We present key con­cepts from that math­e­mat­ics and use them to derive an algo­rithm whose ideal ver­sion should have bet­ter per­for­mance than that of hav­ing all agents use the ISPA, even in the infin­i­tes­i­mal limit. We present exper­i­ments ver­i­fy­ing this, and also show­ing that a machine-​​learning-​​based ver­sion of this COIN algo­rithm in which costs are only impre­cisely esti­mated via empir­i­cal means (a ver­sion poten­tially applic­a­ble in the real world) also out­per­forms the ISPA, despite hav­ing access to less infor­ma­tion than does the ISPA. In par­tic­u­lar, this COIN algo­rithm almost always avoids Braess’ paradox.”

    collective-​​intelligence search-​​algorithms figure-​​ground-​​error plan­ning nudge
  • [1108.0404] Exploit­ing Agent and Type Inde­pen­dence in Col­lab­o­ra­tive Graph­i­cal Bayesian Games

    “Effi­cient col­lab­o­ra­tive deci­sion mak­ing is an impor­tant chal­lenge for mul­ti­a­gent sys­tems. Find­ing opti­mal joint actions is espe­cially chal­leng­ing when each agent has only imper­fect infor­ma­tion about the state of its envi­ron­ment. Such prob­lems can be mod­eled as col­lab­o­ra­tive Bayesian games in which each agent receives pri­vate infor­ma­tion in the form of its type. How­ever, rep­re­sent­ing and solv­ing such games requires space and com­pu­ta­tion time expo­nen­tial in the num­ber of agents. This arti­cle intro­duces col­lab­o­ra­tive graph­i­cal Bayesian games (CGBGs), which facil­i­tate more effi­cient col­lab­o­ra­tive deci­sion mak­ing by decom­pos­ing the global pay­off func­tion as the sum of local pay­off func­tions that depend on only a few agents. We pro­pose a frame­work for the effi­cient solu­tion of CGBGs based on the insight that they posses two dif­fer­ent types of inde­pen­dence, which we call agent inde­pen­dence and type inde­pen­dence. In par­tic­u­lar, we present a fac­tor graph rep­re­sen­ta­tion that cap­tures both forms of inde­pen­dence and thus enables effi­cient solu­tions. In addi­tion, we show how this rep­re­sen­ta­tion can pro­vide lever­age in sequen­tial tasks by using it to con­struct a novel method for decen­tral­ized par­tially observ­able Markov deci­sion processes. Exper­i­men­tal results in both ran­dom and bench­mark tasks demon­strate the improved scal­a­bil­ity of our meth­ods com­pared to sev­eral exist­ing alternatives.”

    col­lab­o­ra­tion agent-​​based complex-​​systems emergent-​​design nudge-​​targets
  • [1102.2837] Effi­cient Pro­mo­tion Strate­gies in Hier­ar­chi­cal Organizations

    “The Peter prin­ci­ple has been recently inves­ti­gated by means of an agent-​​based sim­u­la­tion and its valid­ity has been numer­i­cally cor­rob­o­rated. It has been con­firmed that, within cer­tain con­di­tions, it can really influ­ence in a neg­a­tive way the effi­ciency of a pyra­mi­dal orga­ni­za­tion adopt­ing mer­i­to­cratic pro­mo­tions. It was also found that, in order to bypass these effects, alter­na­tive pro­mo­tion strate­gies should be adopted, as for exam­ple a ran­dom selec­tion choice. In this paper, within the same line of research, we study pro­mo­tion strate­gies in a more real­is­tic hier­ar­chi­cal and mod­u­lar orga­ni­za­tion and we show the robust­ness of our pre­vi­ous results, extend­ing their valid­ity to a more gen­eral con­text. We dis­cuss also why the adop­tion of these strate­gies could be use­ful for real organizations.”

    organizational-​​behavior com­plex­ol­ogy complexological-​​amusements agent-​​based com­pe­tence

Items of some interest…

These are my Pin​board​.in links for May 14th from 15:11 to 15:18: