Tag Archives: classification

Items of some interest…

Posted on by

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • [1108.4279] Detec­tion and emergence

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • [1108.5508] A Pat­tern Measure

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

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

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

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

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

  • [1105.2423] Cytoskele­ton and Cell Motility

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

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

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

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

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

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

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

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

Items of some interest…

Posted on by

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

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

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

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

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

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

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

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

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

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

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

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

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

  • [1109.0573] Phase Retrieval via Matrix Completion

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • Old​Fonts​.com | About Us

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

    typog­ra­phy fonts hand­writ­ing

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Items of some interest…

Posted on by

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

  • [1106.1796] Accel­er­at­ing Rein­force­ment Learn­ing by Com­pos­ing Solu­tions of Auto­mat­i­cally Iden­ti­fied Subtasks

    “This paper dis­cusses a sys­tem that accel­er­ates rein­force­ment learn­ing by using trans­fer from related tasks. With­out such trans­fer, even if two tasks are very sim­i­lar at some abstract level, an exten­sive re-​​learning effort is required. The sys­tem achieves much of its power by trans­fer­ring parts of pre­vi­ously learned solu­tions rather than a sin­gle com­plete solu­tion. The sys­tem exploits strong fea­tures in the multi-​​dimensional func­tion pro­duced by rein­force­ment learn­ing in solv­ing a par­tic­u­lar task. These fea­tures are sta­ble and easy to rec­og­nize early in the learn­ing process. They gen­er­ate a par­ti­tion­ing of the state space and thus the func­tion. The par­ti­tion is rep­re­sented as a graph. This is used to index and com­pose func­tions stored in a case base to form a close approx­i­ma­tion to the solu­tion of the new task. Exper­i­ments demon­strate that func­tion com­po­si­tion often pro­duces more than an order of mag­ni­tude increase in learn­ing rate com­pared to a basic rein­force­ment learn­ing algorithm.”

    algo­rithms learn­ing problem-​​solving decom­po­si­tion spec­i­fi­ca­tion nudge-​​targets

  • [1105.5447] Adap­tive Par­al­lel Iter­a­tive Deep­en­ing Search

    “Many of the arti­fi­cial intel­li­gence tech­niques devel­oped to date rely on heuris­tic search through large spaces. Unfor­tu­nately, the size of these spaces and the cor­re­spond­ing com­pu­ta­tional effort reduce the applic­a­bil­ity of oth­er­wise novel and effec­tive algo­rithms. A num­ber of par­al­lel and dis­trib­uted approaches to search have con­sid­er­ably improved the per­for­mance of the search process. Our goal is to develop an archi­tec­ture that auto­mat­i­cally selects par­al­lel search strate­gies for opti­mal per­for­mance on a vari­ety of search prob­lems. In this paper we describe one such archi­tec­ture real­ized in the Eureka sys­tem, which com­bines the ben­e­fits of many dif­fer­ent approaches to par­al­lel heuris­tic search. Through empir­i­cal and the­o­ret­i­cal analy­ses we observe that fea­tures of the prob­lem space directly affect the choice of opti­mal par­al­lel search strat­egy. We then employ machine learn­ing tech­niques to select the opti­mal par­al­lel search strat­egy for a given prob­lem space. When a new search task is input to the sys­tem, Eureka uses fea­tures describ­ing the search space and the cho­sen archi­tec­ture to auto­mat­i­cally select the appro­pri­ate search strat­egy. Eureka has been tested on a MIMD par­al­lel proces­sor, a dis­trib­uted net­work of work­sta­tions, and a sin­gle work­sta­tion using mul­ti­thread­ing. Results gen­er­ated from fif­teen puz­zle prob­lems, robot arm motion prob­lems, arti­fi­cial search spaces, and plan­ning prob­lems indi­cate that Eureka out­per­forms any of the tested strate­gies used exclu­sively for all prob­lem instances and is able to greatly reduce the search time for these applications.”

    algo­rithms search-​​algorithms opti­miza­tion artificial-​​intelligence par­al­lelism performance-​​measure nudge-​​targets

  • [1106.4064] Algo­rith­mic Pro­gram­ming Lan­guage Identification

    “Moti­vated by the amount of code that goes uniden­ti­fied on the web, we intro­duce a prac­ti­cal method for algo­rith­mi­cally iden­ti­fy­ing the pro­gram­ming lan­guage of source code. Our work is based on super­vised learn­ing and intel­li­gent sta­tis­ti­cal fea­tures. We also explored, but aban­doned, a gram­mat­i­cal approach. In test­ing, our imple­men­ta­tion greatly out­per­forms that of an exist­ing tool that relies on a Bayesian classifier.”

    algo­rithms pro­gram­ming clas­si­fi­ca­tion lan­guages archives cute nudge-​​targets

  • [1108.4972] Algo­rithms for the Prob­lems of Length-​​Constrained Heav­i­est Segments

    “We present algo­rithms for length-​​constrained max­i­mum sum seg­ment and max­i­mum den­sity seg­ment prob­lems, in par­tic­u­lar, and the prob­lem of find­ing length-​​constrained heav­i­est seg­ments, in gen­eral, for a sequence of real num­bers. Given a sequence of n real num­bers and two real para­me­ters L and U (L <= U), the max­i­mum sum seg­ment prob­lem is to find a con­sec­u­tive sub­se­quence, called a seg­ment, of length at least L and at most U such that the sum of the num­bers in the sub­se­quence is max­i­mum. The max­i­mum den­sity seg­ment prob­lem is to find a seg­ment of length at least L and at most U such that the den­sity of the num­bers in the sub­se­quence is the max­i­mum. For the first prob­lem with non-​​uniform width there is an algo­rithm with time and space com­plex­i­ties in O(n). We present an algo­rithm with time com­plex­ity in O(n) and space com­plex­ity in O(U). For the sec­ond prob­lem with non-​​uniform width there is a com­bi­na­to­r­ial solu­tion with time com­plex­ity in O(n) and space com­plex­ity in O(U). We present a sim­ple geo­met­ric algo­rithm with the same time and space com­plex­i­ties. We extend our algo­rithms to respec­tively solve the length-​​constrained k max­i­mum sum seg­ments prob­lem in O(n+k) time and O(max{U, k}) space, and the length-​​constrained $k$ max­i­mum den­sity seg­ments prob­lem in O(n min{k, U-​​L}) time and O(U+k) space. We present exten­sions of our algo­rithms to find all the length-​​constrained seg­ments hav­ing user spec­i­fied sum and den­sity in O(n+m) and O(nlog (U-L)+m) times respec­tively, where m is the num­ber of out­put. Pre­vi­ously, there was no known algo­rithm with non-​​trivial result for these prob­lems. We indi­cate the exten­sions of our algo­rithms to higher dimen­sions. All the algo­rithms can be extended in a straight for­ward way to solve the prob­lems with non-​​uniform width and non-​​uniform weight.”

    algo­rithms operations-​​research search-​​algorithms opti­miza­tion nudge-​​targets

  • [1109.4920] Beyond pix­els and regions: A non local patch means (NLPM) method for content-​​level restora­tion, enhance­ment, and recon­struc­tion of degraded doc­u­ment images

    “A patch-​​based non-​​local restora­tion and recon­struc­tion method for pre­pro­cess­ing degraded doc­u­ment images is intro­duced. The method col­lects rel­a­tive data from the whole input image, while the image data are first rep­re­sented by a content-​​level descrip­tor based on patches. This patch-​​equivalent rep­re­sen­ta­tion of the input image is then cor­rected based on sim­i­lar patches iden­ti­fied using a mod­i­fied genetic algo­rithm (GA) result­ing in a low com­pu­ta­tional load. The cor­rected patch-​​equivalent is then con­verted to the out­put restored image. The fact that the method uses the patches at the con­tent level allows it to incor­po­rate high-​​level restora­tion in an objec­tive and self-​​sufficient way. The method has been applied to sev­eral degraded doc­u­ment images, includ­ing the DIBCO’09 con­test dataset with promis­ing results.”

    dig­i­ti­za­tion algo­rithms OCR archives machine-​​learning nudge-​​targets

  • [1105.6205] Cloud-​​based Evo­lu­tion­ary Algo­rithms: An algo­rith­mic study

    “After a proof of con­cept using Drop­box™, a free stor­age and syn­chro­niza­tion ser­vice, showed that an evo­lu­tion­ary algo­rithm using sev­eral dis­sim­i­lar com­put­ers con­nected via WiFi or Eth­er­net had a good scal­ing behav­ior in terms of eval­u­a­tions per sec­ond, it remains to be proved whether that effect also trans­lates to the algo­rith­mic per­for­mance of the algo­rithm. In this paper we will check sev­eral dif­fer­ent, and dif­fi­cult, prob­lems, and see what effects the auto­matic load-​​balancing and asyn­chrony have on the speed of res­o­lu­tion of problems.”

    drop­box genetic-​​algorithm distributed-​​processing tips-​​and-​​tricks

Items of some interest…

Posted on by

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

  • [1107.0674] “Mem­ory foam” approach to unsu­per­vised learning

    “We pro­pose an alter­na­tive approach to con­struct an arti­fi­cial learn­ing sys­tem, which nat­u­rally learns in an unsu­per­vised man­ner. Its math­e­mat­i­cal pro­to­type is a dynam­i­cal sys­tem, which auto­mat­i­cally shapes its vec­tor field in response to the input sig­nal. The vec­tor field con­verges to a gra­di­ent of a multi-​​dimensional prob­a­bil­ity den­sity dis­tri­b­u­tion of the input process, taken with neg­a­tive sign. The most prob­a­ble pat­terns are rep­re­sented by the sta­ble fixed points, whose basins of attrac­tion are formed auto­mat­i­cally. The per­for­mance of this sys­tem is illus­trated with musi­cal signals.”

    machine-​​learning clas­si­fi­ca­tion learning-​​from-​​data algo­rithms nudge-​​targets

  • [1107.0550] 3D Ter­res­trial LiDAR data clas­si­fi­ca­tion of com­plex nat­ural scenes using a multi-​​scale dimen­sion­al­ity cri­te­rion: appli­ca­tions in geomorphology

    “3D point clouds of nat­ural envi­ron­ments rel­e­vant to geo­mor­phol­ogy prob­lems (rivers, cliffs…) often require to clas­sify the data into ele­men­tary rel­e­vant classes. A typ­i­cal exam­ple is the sep­a­ra­tion of ripar­ian veg­e­ta­tion from soil in flu­vial envi­ron­ments, the dis­tinc­tion between fresh sur­faces and rock­fall in cliff envi­ron­ments, or more gen­er­ally the clas­si­fi­ca­tion of sur­faces accord­ing to their mor­phol­ogy (rip­ples, grain size…). Nat­ural sur­faces are very het­ero­ge­neous and their dis­tinc­tive prop­er­ties are sel­dom defined at a unique scale. We have thus defined a multi-​​scale mea­sure of the point cloud dimen­sion­al­ity around each point. The dimen­sion­al­ity char­ac­ter­izes the local 3D orga­ni­za­tion of the point cloud and varies from being 1D (points set along a line) to really tak­ing all 3D vol­ume, at each scale. We present the tech­nique and illus­trate its effi­ciency in sep­a­rat­ing ripar­ian veg­e­ta­tion from ground and clas­si­fy­ing a moun­tain stream in veg­e­ta­tion, rock, gravel and water sur­face. The supe­ri­or­ity of the multi-​​scale analy­sis in enhanc­ing class sep­a­ra­bil­ity and spa­tial res­o­lu­tion of the clas­si­fi­ca­tion is also demon­strated. Large scenes can be clas­si­fied on a com­mod­ity lap­top in a rea­son­able time. The tech­nique is robust to miss­ing data and espe­cially shadow zones. The clas­si­fi­ca­tion is fast and accu­rate and can account for some degree of intra-​​class mor­pho­log­i­cal vari­abil­ity such as dif­fer­ent veg­e­ta­tion types. A prob­a­bilis­tic con­fi­dence in the clas­si­fi­ca­tion result is given at each point allow­ing the user to remove the points for which the clas­si­fi­ca­tion is uncer­tain. The process can be both fully auto­mated but also fully cus­tomized by the user includ­ing a graph­i­cal def­i­n­i­tion of the clas­si­fiers if so desired. Although devel­oped for fully 3D data, the method can be read­ily applied to 2.5D air­borne LiDAR data.”

    image-​​analysis image-​​segmentation learning-​​from-​​data clas­si­fi­ca­tion nudge-​​targets

  • [1105.6001] A Call to Arms: Revis­it­ing Data­base Design

    “Good data­base design is cru­cial to obtain a sound, con­sis­tent data­base, and — in turn — good data­base design method­olo­gies are the best way to achieve the right design. These method­olo­gies are taught to most Com­puter Sci­ence under­grad­u­ates, as part of any Intro­duc­tion to Data­base class. They can be con­sid­ered part of the “canon”, and indeed, the over­all approach to data­base design has been unchanged for years. More­over, none of the major data­base research assess­ments iden­tify data­base design as a strate­gic research direc­tion. Should we con­clude that data­base design is a solved prob­lem? Our the­sis is that data­base design remains a crit­i­cal unsolved prob­lem. Hence, it should be the sub­ject of more research. Our start­ing point is the obser­va­tion that tra­di­tional data­base design is not used in prac­tice — and if it were used it would result in designs that are not well adapted to cur­rent envi­ron­ments. In short, data­base design has failed to keep up with the times. In this paper, we put forth argu­ments to sup­port our view­point, ana­lyze the root causes of this sit­u­a­tion and sug­gest some avenues of research.”

    data­base ontol­ogy software-​​development computer-​​science design-​​patterns