Items of some interest:

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

  • [1006.5366] “Not only defended but also applied”: The per­ceived absur­dity of Bayesian inference

    “The mis­sion­ary zeal of many Bayesians of old has been matched, in the other direc­tion, by a view among some the­o­reti­cians that Bayesian meth­ods are absurd-​​not merely mis­guided but obvi­ously wrong in prin­ci­ple. We con­sider sev­eral exam­ples, begin­ning with Feller’s clas­sic text on prob­a­bil­ity the­ory and con­tin­u­ing with more recent cases such as the per­ceived Bayesian nature of the so-​​called dooms­day argu­ment. We ana­lyze in this note the intel­lec­tual back­ground behind var­i­ous mis­con­cep­tions about Bayesian sta­tis­tics, with­out aim­ing at a com­plete his­tor­i­cal cov­er­age of the rea­sons for this dismissal.”

    social-​​dynamics sta­tis­tics martial-​​arts-​​schools
  • [1206.3268] Fea­ture Selec­tion via Block-​​Regularized Regression

    “In this paper, we con­sid­ered the prob­lem of find­ing a sub­set of covari­ates in a high-​​dimensional space that affect the out­put vari­able when there is a block struc– ture in the covari­ates. In the con­text of asso­ci­a­tion map­ping, we pro­posed a regression-​​based model with a Markov chain prior that encodes the infor­ma­tion in the cor­re­la­tion struc­ture such as dis­tance and re– com­bi­na­tion rate between adja­cent SNP mark­ers. We demon­strated on the sim­u­lated and mouse data that our pro­posed algo­rithm can be used to iden­tify groups of SNP mark­ers as a rel­e­vant block of causal SNPs. The idea of rep­re­sent­ing the cor­re­la­tion struc­ture as a Markov chain in a vari­able selec­tion method to learn grouped rel­e­vant vari­ables can be gen­er­al­ized to use a graph­i­cal model as a prior in a vari­able selec­tion prob– lem to rep­re­sent an arbi­trary cor­re­la­tion struc­ture in vari­ables in a high-​​dimensional space. Another inter– est­ing exten­sion of the model is to model a struc­ture in out­put vari­ables as well when mea­sure­ments of mul– tiple out­put vari­ables are available.”

    sta­tis­tics bioin­for­mat­ics algo­rithms data-​​mining feature-​​extraction
  • Fil­ipe Kiss : A bet­ter git log

    “So, are you tired of this old and bored git log screen?”

    yes software-​​development git tricks-​​n-​​tips bash
  • Neu­roskep­tic: Brains are Dif­fer­ent on Macs

    “The paper goes into lots more detail, but the les­son for researchers is extremely sim­ple: don’t cross the streams of data-​​analysis. Set up your analy­sis stream and then use it on all of your data. Same hard­ware, same soft­ware, same set­tings. Imag­ine you’re doing a study com­par­ing brain struc­ture in two groups. Halfway through ana­lyz­ing your data, you upgrade your MacOS. All of the brains you ana­lyze after that will be, say, 5% “big­ger”. That’ll cer­tainly make your data much nois­ier, and if you hap­pen to ana­lyze most of Group A before Group B, it’ll give you a false pos­i­tive find­ing. Some­times you just can’t avoid changes in hard­ware or soft­ware — IT techs have a habit of upgrad­ing things with­out ask­ing — but in these cases, you should run the same data under the old and the new regime to see if it’s mak­ing a dif­fer­ence. Finally, it would be wrong to blame FreeSurfer for this. I’d be sur­prised if they were any worse than the other soft­ware pack­ages. Mix­ing and match­ing ver­sions is some­thing that the FreeSurfer devel­op­ers specif­i­cally warn against. This paper shows why.”

    data-​​analysis repro­ducibil­ity technical-​​assumptions anomalies-​​are-​​where-​​you-​​find-​​them
  • Plug: What is infer­en­tial­ism? « Odontomachus’s Blog

    “I’ve been crit­i­cal of objects and the idea of ref­er­ence for a while now. To me sen­tences and propo­si­tions, by virtue of their role as “moves” in social inter­ac­tions, are likely to have pri­or­ity in a prop­erly objec­tive account of mean­ing. Many puta­tive objects (e.g. cor­po­ra­tions or muta­ble dig­i­tal doc­u­ments) bor­der on being fic­tional, gain­ing their object­hood only through what we say about them; and many refer­ring phrases seem to refer to dif­fer­ent things, depend­ing on what is being pred­i­cated. I think this opin­ion would make me what Pere­grin calls a “strong infer­en­tial­ist”. Even­tu­ally I hope that think­ing clearly about seman­tics ought to (among other things) help bring calm to the cur­rent mass hys­te­ria which is the Seman­tic Web and Linked Data, and help steer all of that energy expen­di­ture to improve its consequence.”

    prag­ma­tism indirect-​​links phi­los­o­phy talking-​​about-​​thinking-​​and-​​the-​​reverse
  • [1206.3552] A Clas­si­fi­ca­tion for Com­mu­nity Dis­cov­ery Meth­ods in Com­plex Networks

    “In the last few years many real-​​world net­works have been found to show a so-​​called com­mu­nity struc­ture orga­ni­za­tion. Much effort has been devoted in the lit­er­a­ture to develop meth­ods and algo­rithms that can effi­ciently high­light this hid­den struc­ture of the net­work, tra­di­tion­ally by par­ti­tion­ing the graph. Since net­work rep­re­sen­ta­tion can be very com­plex and can con­tain dif­fer­ent vari­ants in the tra­di­tional graph model, each algo­rithm in the lit­er­a­ture focuses on some of these prop­er­ties and estab­lishes, explic­itly or implic­itly, its own def­i­n­i­tion of com­mu­nity. Accord­ing to this def­i­n­i­tion it then extracts the com­mu­ni­ties that are able to reflect only some of the fea­tures of real com­mu­ni­ties. The aim of this sur­vey is to pro­vide a man­ual for the com­mu­nity dis­cov­ery prob­lem. Given a meta def­i­n­i­tion of what a com­mu­nity in a social net­work is, our aim is to orga­nize the main cat­e­gories of com­mu­nity dis­cov­ery based on their own def­i­n­i­tion of com­mu­nity. Given a desired def­i­n­i­tion of com­mu­nity and the fea­tures of a prob­lem (size of net­work, direc­tion of edges, mul­ti­di­men­sion­al­ity, and so on) this review paper is designed to pro­vide a set of approaches that researchers could focus on.”

    via:cshalizi graph-​​theory com­mu­nity clas­si­fi­ca­tion algo­rithms nudge
  • [1205.0792] Exact Wavelets on the Ball

    “We develop an exact wavelet trans­form on the three-​​dimensional ball (i.e. on the solid sphere), which we name the fla­glet trans­form. For this pur­pose we first con­struct an exact har­monic trans­form on the radial line using damped Laguerre poly­no­mi­als and develop a cor­re­spond­ing quad­ra­ture rule. Com­bined with the spher­i­cal har­monic trans­form, this approach leads to a sam­pling the­o­rem on the ball and a novel three-​​dimensional decom­po­si­tion which we call the Fourier-​​Laguerre trans­form. We relate this new trans­form to the well-​​known Fourier-​​Bessel decom­po­si­tion and show that band-​​limitness in the Fourier-​​Laguerre basis is a suf­fi­cient con­di­tion to com­pute the Fourier-​​Bessel decom­po­si­tion exactly. We then con­struct the fla­glet trans­form on the ball through a har­monic tiling, which is exact thanks to the exact­ness of the Fourier-​​Laguerre trans­form (from which the name fla­glets is coined). The cor­re­spond­ing wavelet ker­nels have com­pact local­i­sa­tion prop­er­ties in real and har­monic space and their angu­lar aper­ture is invari­ant under radial trans­la­tion. We intro­duce a mul­tires­o­lu­tion algo­rithm to per­form the fla­glet trans­form rapidly, while cap­tur­ing all infor­ma­tion at each wavelet scale in the min­i­mal num­ber of sam­ples on the ball. Our imple­men­ta­tion of these new tools achieves float­ing point pre­ci­sion and is made pub­licly avail­able. We per­form numer­i­cal exper­i­ments demon­strat­ing the speed and accu­racy of these libraries and illus­trate their capa­bil­i­ties on a sim­ple denois­ing example.”

    wavelets geom­e­try representation-​​theory signal-​​processing answer-​​languages
  • [1205.3077] Efficiency-​​Revenue Trade-​​offs in Auctions

    “When agents with inde­pen­dent pri­ors bid for a sin­gle item, Myerson’s opti­mal auc­tion max­i­mizes expected rev­enue, whereas Vickrey’s second-​​price auc­tion opti­mizes social wel­fare. We address the nat­ural ques­tion of trade-​​offs between the two cri­te­ria, that is, auc­tions that opti­mize, say, rev­enue under the con­straint that the wel­fare is above a given level. If one allows for ran­dom­ized mech­a­nisms, it is easy to see that there are polynomial-​​time mech­a­nisms that achieve any point in the trade-​​off (the Pareto curve) between rev­enue and wel­fare. We inves­ti­gate whether one can achieve the same guar­an­tees using deter­min­is­tic mech­a­nisms. We pro­vide a neg­a­tive answer to this ques­tion by show­ing that this is a (weakly) NP-​​hard prob­lem. On the pos­i­tive side, we pro­vide polynomial-​​time deter­min­is­tic mech­a­nisms that approx­i­mate with arbi­trary pre­ci­sion any point of the trade-​​off between these two fun­da­men­tal objec­tives for the case of two bid­ders, even when the val­u­a­tions are cor­re­lated arbi­trar­ily. The major prob­lem left open by our work is whether there is such an algo­rithm for three or more bid­ders with inde­pen­dent val­u­a­tion distributions.”

    algo­rithms Pareto-​​front performance-​​measure multiobjective-​​optimization
  • Sym­bol­set

    “Sym­bol­sets are seman­tic sym­bol fonts. They work in mod­ern browsers and any­where Open­Type fea­tures are supported.”

    typog­ra­phy uni­code
  • [1204.6653] Elim­i­na­tion of Glass Arti­facts and Object Segmentation

    “Many images nowa­days are cap­tured from behind the glasses and may have cer­tain stains dis­crep­ancy because of glass and must be processed to make dif­fer­en­ti­a­tion between the glass and objects behind it. This research paper pro­poses an algo­rithm to remove the dam­aged or cor­rupted part of the image and make it con­sis­tent with other part of the image and to seg­ment objects behind the glass. The dam­aged part is removed using total vari­a­tion inpaint­ing method and seg­men­ta­tion is done using kmeans clus­ter­ing, anisotropic dif­fu­sion and water­shed trans­for­ma­tion. The final out­put is obtained by inter­po­la­tion. This algo­rithm can be use­ful to appli­ca­tions in which some part of the images are cor­rupted due to data trans­mis­sion or needs to seg­ment objects from an image for fur­ther processing.”

    image-​​segmentation image-​​processing nudge-​​targets algo­rithms
  • The whole of the law — Things from your life

    “But it’ll be your deci­sion, not iner­tia or fate. The ongo­ing cadence of ask­ing these ques­tions (and, maybe, the con­tent of any answers you come up with) will con­vene an open space for you to live in. A world where what­ever you do is right.”

    this
  • The Pirate Uni­ver­sity | Pirate university

    “The Pirate Uni­ver­sity is an on-​​line bul­letin board on which stu­dents post requests for aca­d­e­mic pub­li­ca­tions. You can com­pare it to an aca­d­e­mic wish list. Oth­ers, who know where to find these pub­li­ca­tions, reply and if pos­si­ble, pro­vide links to the resources searched. The Pirate Uni­ver­sity is not pro­vid­ing, stor­ing or shar­ing copy­righted mate­r­ial. An impor­tant ques­tion is if the upload­ing of arti­cles, pub­li­ca­tions is legal. If you are the copy­right holder of the arti­cle requested, there should be no prob­lem. Also in cer­tain cases, if you or your insti­tute have acquired the rights of the pub­li­ca­tion, or if it is free of rights, there shouldn’t be a prob­lem. It is prob­a­bly best to con­sult with your librar­ian to see which kind of pub­li­ca­tion is okay to share on the Internet.”

    academic-​​culture pub­lish­ing col­lab­o­ra­tion crowd­sourc­ing librar­i­ans open-​​access schol­ar­ship
  • [1206.3793] A dis­trib­uted classification/​estimation algo­rithm for sen­sor networks

    “…We pro­pose a novel coop­er­a­tive iter­a­tive algo­rithm which copes with the com­mu­ni­ca­tion con­straints imposed by the net­work and shows remark­able per­for­mance. Our main result is a rig­or­ous proof of the con­ver­gence of the algo­rithm and a char­ac­ter­i­za­tion of the limit behav­ior. We also show that, in the limit when the num­ber of sen­sors goes to infin­ity, the com­mon unknown para­me­ter is esti­mated with arbi­trary small error, while the clas­si­fi­ca­tion error con­verges to that of the opti­mal cen­tral­ized max­i­mum like­li­hood esti­ma­tor. We also show numer­i­cal results that val­i­date the the­o­ret­i­cal analy­sis and sup­port their pos­si­ble gen­er­al­iza­tion. We com­pare our strat­egy with the Expectation-​​Maximization algo­rithm and we dis­cuss trade-​​offs in terms of robust­ness, speed of con­ver­gence and imple­men­ta­tion simplicity.”

    distributed-​​processing collective-​​behavior sensor-​​networks algo­rithms nudge-​​targets
  • [1204.6391] Extend­ing par­tial rep­re­sen­ta­tions of func­tion graphs and per­mu­ta­tion graphs

    “Func­tion graphs are graphs rep­re­sentable by inter­sec­tions of con­tin­u­ous real-​​valued func­tions on the inter­val [0,1] and are known to be exactly the com­ple­ments of com­pa­ra­bil­ity graphs. As such they are rec­og­niz­able in poly­no­mial time. Func­tion graphs gen­er­al­ize per­mu­ta­tion graphs, which arise when all func­tions con­sid­ered are lin­ear. We focus on the prob­lem of extend­ing par­tial rep­re­sen­ta­tions, which gen­er­al­izes the recog­ni­tion prob­lem. We observe that for per­mu­ta­tion graphs an easy exten­sion of Golumbic’s com­pa­ra­bil­ity graph recog­ni­tion algo­rithm can be exploited. This approach fails for func­tion graphs. Nev­er­the­less, we present a polynomial-​​time algo­rithm for extend­ing a par­tial rep­re­sen­ta­tion of a graph by func­tions defined on the entire inter­val [0,1] pro­vided for some of the ver­tices. On the other hand, we show that if a par­tial rep­re­sen­ta­tion con­sists of func­tions defined on subin­ter­vals of [0,1], then the prob­lem of extend­ing this rep­re­sen­ta­tion to func­tions on the entire inter­val [0,1] becomes NP-​​complete.”

    graph-​​theory math-i-didn’t-know representation-​​theory ontol­ogy inter­est­ing
  • [1206.3294] Flex­i­ble Pri­ors for Exemplar-​​based Clustering

    “Exemplar-​​based clus­ter­ing meth­ods have been shown to pro­duce state-​​of-​​the-​​art results on a num­ber of syn­thetic and real-​​world clus­ter­ing prob­lems. They are appeal­ing because they offer com­pu­ta­tional ben­e­fits over latent-​​mean mod­els and can han­dle arbi­trary pair­wise sim­i­lar­ity mea­sures between data points. How­ever, when try­ing to recover under­ly­ing struc­ture in clus­ter­ing prob­lems, tai­lored sim­i­lar­ity mea­sures are often not enough; we also desire con­trol over the dis­tri­b­u­tion of clus­ter sizes. Pri­ors such as Dirich­let process pri­ors allow the num­ber of clus­ters to be unspec­i­fied while express­ing pri­ors over data par­ti­tions. To our knowl­edge, they have not been applied to exemplar-​​based mod­els. We show how to incor­po­rate pri­ors, includ­ing Dirich­let process pri­ors, into the recently intro­duced affin­ity prop­a­ga­tion algo­rithm. We develop an effi­cient max­prod­uct belief prop­a­ga­tion algo­rithm for our new model and demon­strate exper­i­men­tally how the expanded range of clus­ter­ing pri­ors allows us to bet­ter recover true clus­ter­ings in sit­u­a­tions where we have some infor­ma­tion about the gen­er­at­ing process.”

    clus­ter­ing algo­rithms
  • Mag­a­zine — The Case Against Cre­den­tial­ism — The Atlantic

    ’”ALL OF OUR WORK HAS GIVEN ME A VERY STRONG view,” Richard Boy­atzis told me one after­noon. The con­sult­ing firm Boy­atzis heads, McBer and Com­pany, was founded by David McClel­land in 1963. Its spe­cialty has been ana­lyz­ing what peo­ple actu­ally do in busi­ness jobs—not what their job descrip­tions say, but how they spend their time and which skills seem most impor­tant to their suc­cess. “I’ve come to see that when­ever a group insti­tutes a cre­den­tial­ing process, whether by licens­ing or insist­ing on advanced degrees, the espoused rhetoric is to enforce the stan­dards of pro­fes­sion­al­ism. This is true whether it’s among accoun­tants or plumbers or physi­cians. But the observed con­se­quences always seem to be these two: the exclu­sion of cer­tain groups, whether by inten­tion or not, and the estab­lish­ment of mediocre per­for­mance standards.“‘

    pro­fes­sion­al­iza­tion cre­den­tial­ing Andrew-​​Abbott-​​smiles-​​in-​​Chicago author­ity exper­tise cultural-​​assumptions disintermediation-​​targets
  • [1205.2483] Edge-​​clique graphs of cock­tail par­ties have unbounded rankwidth

    “In an attempt to find a polynomial-​​time algo­rithm for the edge-​​clique cover prob­lem on cographs we tried to prove that the edge-​​clique graphs of cographs have bounded rankwidth. How­ever, this is not the case. In this note we show that the edge-​​clique graphs of cock­tail party graphs have unbounded rank width.”

    open-​​questions nudge-​​targets graph-​​theory algo­rithms
  • [1206.3235] Iden­ti­fy­ing rea­son­ing pat­terns in games

    “We present an algo­rithm that iden­ti­fies the rea­son­ing pat­terns of agents in a game, by iter­a­tively exam­in­ing the graph struc­ture of its Multi-​​Agent Influ­ence Dia­gram (MAID) rep­re­sen­ta­tion. If the deci­sion of an agent par­tic­i­pates in no rea­son­ing pat­terns, then we can effec­tively ignore that deci­sion for the pur­pose of cal­cu­lat­ing a Nash equi­lib­rium for the game. In some cases, this can lead to expo­nen­tial time sav­ings in the process of equi­lib­rium cal­cu­la­tion. More­over, our algo­rithm can be used to enu­mer­ate the rea­son­ing pat­terns in a game, which can be use­ful for con­struct­ing more effec­tive com­put­er­ized agents inter­act­ing with humans.”

    game-​​theory infer­ence strat­egy nudge-​​targets learning-​​by-​​watching

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:

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

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

    plan­ning machine-​​learning nudge-​​targets easy-​​pickins
  • [0908.3565] Dis­trib­uted Loca­tion Opti­miza­tion for Sen­sors with Lim­ited Range Het­ero­ge­neous Capa­bil­i­ties using Gen­er­al­ized Voronoi Partition

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

    agent-​​based coor­di­na­tion sensor-​​networks nudge-​​targets emergent-​​design
  • [1106.6058] Sta­bil­ity of strate­gies in payoff-​​driven evo­lu­tion­ary games on networks

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

    prisoners’-dilemma agent-​​based network-​​theory artificial-​​life com­plex­ol­ogy nudge-​​targets
  • [1106.0296] The Emer­gence of Lead­er­ship in Social Networks

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

    minority-​​game social-​​networks soci­ol­ogy agent-​​based network-​​theory
  • [1106.1816] Mon­i­tor­ing Teams by Over­hear­ing: A Multi-​​Agent Plan-​​Recognition Approach

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

    emergent-​​design agent-​​based swarms coor­di­na­tion nudge
  • [1011.2861] A Com­pre­hen­sive Work­flow for General-​​Purpose Neural Mod­el­ing with Highly Con­fig­urable Neu­ro­mor­phic Hard­ware Systems

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

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