A digital organism is a self-replicating computer program that mutates and evolves. Digital organisms are used as a tool to study the dynamics of Darwinian evolution, and to test or verify specific hypotheses or mathematical models of evolution. The study of digital organisms is closely related to the area of artificial life. == History == Digital organisms can be traced back to the game Darwin, developed in 1961 at Bell Labs, in which computer programs had to compete with each other by trying to stop others from executing . A similar implementation that followed this was the game Core War. In Core War, it turned out that one of the winning strategies was to replicate as fast as possible, which deprived the opponent of all computational resources. Programs in the Core War game were also able to mutate themselves and each other by overwriting instructions in the simulated "memory" in which the game took place. This allowed competing programs to embed damaging instructions in each other that caused errors (terminating the process that read it), "enslaved processes" (making an enemy program work for you), or even change strategies mid-game and heal themselves. Steen Rasmussen at Los Alamos National Laboratory took the idea from Core War one step further in his core world system by introducing a genetic algorithm that automatically wrote programs. However, Rasmussen did not observe the evolution of complex and stable programs. It turned out that the programming language in which core world programs were written was very brittle, and more often than not mutations would completely destroy the functionality of a program. The first to solve the issue of program brittleness was Thomas S. Ray with his Tierra system, which was similar to core world. Ray made some key changes to the programming language such that mutations were much less likely to destroy a program. With these modifications, he observed for the first time computer programs that did indeed evolve in a meaningful and complex way. Later, Chris Adami, Titus Brown, and Charles Ofria started developing their Avida system, which was inspired by Tierra but again had some crucial differences. In Tierra, all programs lived in the same address space and could potentially execute or otherwise interfere with each other's code. In Avida, on the other hand, each program lives in its own address space. Because of this modification, experiments with Avida became much cleaner and easier to interpret than those with Tierra. With Avida, digital organism research has begun to be accepted as a valid contribution to evolutionary biology by a growing number of evolutionary biologists. Evolutionary biologist Richard Lenski of Michigan State University has used Avida extensively in his work. Lenski, Adami, and their colleagues have published in journals such as Nature and the Proceedings of the National Academy of Sciences (USA). In 1996, Andy Pargellis created a Tierra-like system called Amoeba that evolved self-replication from a randomly seeded initial condition. More recently REvoSim - a software package based around binary digital organisms - has allowed evolutionary simulations of large populations that can be run for geological timescales.
Quantification (machine learning)
In machine learning, quantification (variously called learning to quantify, or supervised prevalence estimation, or class prior estimation) is the task of using supervised learning in order to train models (quantifiers) that estimate the relative frequencies (also known as prevalence values) of the classes of interest in a sample of unlabelled data items. For instance, in a sample of 100,000 unlabelled tweets known to express opinions about a certain political candidate, a quantifier may be used to estimate the percentage of these tweets which belong to class `Positive' (i.e., which manifest a positive stance towards this candidate), and to do the same for classes `Neutral' and `Negative'. Quantification may also be viewed as the task of training predictors that estimate a (discrete) probability distribution, i.e., that generate a predicted distribution that approximates the unknown true distribution of the items across the classes of interest. Quantification is different from classification, since the goal of classification is to predict the class labels of individual data items, while the goal of quantification it to predict the class prevalence values of sets of data items. Quantification is also different from regression, since in regression the training data items have real-valued labels, while in quantification the training data items have class labels. It has been shown in multiple research works that performing quantification by classifying all unlabelled instances and then counting the instances that have been attributed to each class (the 'classify and count' method) usually leads to suboptimal quantification accuracy. This suboptimality may be seen as a direct consequence of 'Vapnik's principle', which states: If you possess a restricted amount of information for solving some problem, try to solve the problem directly and never solve a more general problem as an intermediate step. It is possible that the available information is sufficient for a direct solution but is insufficient for solving a more general intermediate problem. In our case, the problem to be solved directly is quantification, while the more general intermediate problem is classification. As a result of the suboptimality of the 'classify and count' method, quantification has evolved as a task in its own right, different (in goals, methods, techniques, and evaluation measures) from classification. == Quantification tasks == === Quantification tasks according to the set of classes === The main variants of quantification, according to the characteristics of the set of classes used, are: Binary quantification, corresponding to the case in which there are only n = 2 {\displaystyle n=2} classes and each data item belongs to exactly one of them; Single-label multiclass quantification, corresponding to the case in which there are n > 2 {\displaystyle n>2} classes and each data item belongs to exactly one of them; Multi-label multiclass quantification, corresponding to the case in which there are n ≥ 2 {\displaystyle n\geq 2} classes and each data item can belong to zero, one, or several classes at the same time; Ordinal quantification, corresponding to the single-label multiclass case in which a total order is defined on the set of classes. Regression quantification, a task which stands to 'standard' quantification as regression stands to classification. Strictly speaking, this task is not a quantification task as defined above (since the individual items do not have class labels but are labelled by real values), but has enough commonalities with other quantification tasks to be considered one of them. Most known quantification methods address the binary case or the single-label multiclass case, and only few of them address the multi-label, ordinal, and regression cases. Binary-only methods include the Mixture Model (MM) method, the HDy method, SVM(KLD), and SVM(Q). Methods that can deal with both the binary case and the single-label multiclass case include probabilistic classify and count (PCC), adjusted classify and count (ACC), probabilistic adjusted classify and count (PACC), the Saerens-Latinne-Decaestecker EM-based method (SLD), and KDEy. Methods for multi-label quantification include regression-based quantification (RQ) and label powerset-based quantification (LPQ). Methods for the ordinal case include ordinal versions of the above-mentioned ACC, PACC, and SLD methods, and ordinal versions of the above-mentioned HDy method. Methods for the regression case include Regress and splice and Adjusted regress and sum. === Quantification tasks according to the type of data === Several subtasks of quantification may be identified according to the type of data involved. Example such tasks are: Quantification of networked data. This task consists of performing quantification when the datapoints are members of a relation, i.e., are interlinked. As such, this task is a strict relative of collective classification. Quantification over time. This task consists of performing quantification on sets that become available in a temporal sequence, i.e., as a data stream, and finds application in contexts in which class prevalence values must be monitored over time. == Evaluation measures for quantification == Several evaluation measures can be used for evaluating the error of a quantification method. Since quantification consists of generating a predicted probability distribution that estimates a true probability distribution, these evaluation measures are ones that compare two probability distributions. Most evaluation measures for quantification belong to the class of divergences. Evaluation measures for binary quantification, single-label multiclass quantification, and multi-label quantification, are Absolute Error Squared Error Relative Absolute Error Kullback–Leibler divergence Pearson Divergence Evaluation measures for ordinal quantification are Normalized Match Distance (a particular case of the Earth Mover's Distance) Root Normalized Order-Aware Distance == Applications == Quantification is of special interest in fields such as the social sciences, epidemiology, market research, allocating resources, and ecological modelling, since these fields are inherently concerned with aggregate data. However, quantification is also useful as a building block for solving other downstream tasks, such as improving the accuracy of classifiers on out-of-distribution data, measuring classifier bias and ranker bias, and estimating the accuracy of classifiers on out-of-distribution data. == Resources == LQ 2021: the 1st International Workshop on Learning to Quantify LQ 2022: the 2nd International Workshop on Learning to Quantify LQ 2023: the 3rd International Workshop on Learning to Quantify LQ 2024: the 4th International Workshop on Learning to Quantify LQ 2025: the 5th International Workshop on Learning to Quantify LeQua 2022: the 1st Data Challenge on Learning to Quantify LeQua 2024: the 2nd Data Challenge on Learning to Quantify QuaPy: An open-source Python-based software library for quantification QuantificationLib: A Python library for quantification and prevalence estimation
T-norm fuzzy logics
T-norm fuzzy logics are a family of non-classical logics, informally delimited by having a semantics that takes the real unit interval [0, 1] for the system of truth values and functions called t-norms for permissible interpretations of conjunction. They are mainly used in applied fuzzy logic and fuzzy set theory as a theoretical basis for approximate reasoning. T-norm fuzzy logics belong in broader classes of fuzzy logics and many-valued logics. In order to generate a well-behaved implication, the t-norms are usually required to be left-continuous; logics of left-continuous t-norms further belong in the class of substructural logics, among which they are marked with the validity of the law of prelinearity, (A → B) ∨ (B → A). Both propositional and first-order (or higher-order) t-norm fuzzy logics, as well as their expansions by modal and other operators, are studied. Logics that restrict the t-norm semantics to a subset of the real unit interval (for example, finitely valued Łukasiewicz logics) are usually included in the class as well. Important examples of t-norm fuzzy logics are monoidal t-norm logic (MTL) of all left-continuous t-norms, basic logic (BL) of all continuous t-norms, product fuzzy logic of the product t-norm, or the nilpotent minimum logic of the nilpotent minimum t-norm. Some independently motivated logics belong among t-norm fuzzy logics, too, for example Łukasiewicz logic (which is the logic of the Łukasiewicz t-norm) or Gödel–Dummett logic (which is the logic of the minimum t-norm). == Motivation == As members of the family of fuzzy logics, t-norm fuzzy logics primarily aim at generalizing classical two-valued logic by admitting intermediary truth values between 1 (truth) and 0 (falsity) representing degrees of truth of propositions. The degrees are assumed to be real numbers from the unit interval [0, 1]. In propositional t-norm fuzzy logics, propositional connectives are stipulated to be truth-functional, that is, the truth value of a complex proposition formed by a propositional connective from some constituent propositions is a function (called the truth function of the connective) of the truth values of the constituent propositions. The truth functions operate on the set of truth degrees (in the standard semantics, on the [0, 1] interval); thus the truth function of an n-ary propositional connective c is a function Fc: [0, 1]n → [0, 1]. Truth functions generalize truth tables of propositional connectives known from classical logic to operate on the larger system of truth values. T-norm fuzzy logics impose certain natural constraints on the truth function of conjunction. The truth function ∗ : [ 0 , 1 ] 2 → [ 0 , 1 ] {\displaystyle \colon [0,1]^{2}\to [0,1]} of conjunction is assumed to satisfy the following conditions: Commutativity, that is, x ∗ y = y ∗ x {\displaystyle xy=yx} for all x and y in [0, 1]. This expresses the assumption that the order of fuzzy propositions is immaterial in conjunction, even if intermediary truth degrees are admitted. Associativity, that is, ( x ∗ y ) ∗ z = x ∗ ( y ∗ z ) {\displaystyle (xy)z=x(yz)} for all x, y, and z in [0, 1]. This expresses the assumption that the order of performing conjunction is immaterial, even if intermediary truth degrees are admitted. Monotony, that is, if x ≤ y {\displaystyle x\leq y} then x ∗ z ≤ y ∗ z {\displaystyle xz\leq yz} for all x, y, and z in [0, 1]. This expresses the assumption that increasing the truth degree of a conjunct should not decrease the truth degree of the conjunction. Neutrality of 1, that is, 1 ∗ x = x {\displaystyle 1x=x} for all x in [0, 1]. This assumption corresponds to regarding the truth degree 1 as full truth, conjunction with which does not decrease the truth value of the other conjunct. Together with the previous conditions this condition ensures that also 0 ∗ x = 0 {\displaystyle 0x=0} for all x in [0, 1], which corresponds to regarding the truth degree 0 as full falsity, conjunction with which is always fully false. Continuity of the function ∗ {\displaystyle } (the previous conditions reduce this requirement to the continuity in either argument). Informally this expresses the assumption that microscopic changes of the truth degrees of conjuncts should not result in a macroscopic change of the truth degree of their conjunction. This condition, among other things, ensures a good behavior of (residual) implication derived from conjunction; to ensure the good behavior, however, left-continuity (in either argument) of the function ∗ {\displaystyle } is sufficient. In general t-norm fuzzy logics, therefore, only left-continuity of ∗ {\displaystyle } is required, which expresses the assumption that a microscopic decrease of the truth degree of a conjunct should not macroscopically decrease the truth degree of conjunction. These assumptions make the truth function of conjunction a left-continuous t-norm, which explains the name of the family of fuzzy logics (t-norm based). Particular logics of the family can make further assumptions about the behavior of conjunction (for example, Gödel–Dummett logic requires its idempotence) or other connectives (for example, the logic IMTL (involutive monoidal t-norm logic) requires the involutiveness of negation). All left-continuous t-norms ∗ {\displaystyle } have a unique residuum, that is, a binary function ⇒ {\displaystyle \Rightarrow } such that for all x, y, and z in [0, 1], x ∗ y ≤ z {\displaystyle xy\leq z} if and only if x ≤ y ⇒ z . {\displaystyle x\leq y\Rightarrow z.} The residuum of a left-continuous t-norm can explicitly be defined as ( x ⇒ y ) = sup { z ∣ z ∗ x ≤ y } . {\displaystyle (x\Rightarrow y)=\sup\{z\mid zx\leq y\}.} This ensures that the residuum is the pointwise largest function such that for all x and y, x ∗ ( x ⇒ y ) ≤ y . {\displaystyle x(x\Rightarrow y)\leq y.} The latter can be interpreted as a fuzzy version of the modus ponens rule of inference. The residuum of a left-continuous t-norm thus can be characterized as the weakest function that makes the fuzzy modus ponens valid, which makes it a suitable truth function for implication in fuzzy logic. Left-continuity of the t-norm is the necessary and sufficient condition for this relationship between a t-norm conjunction and its residual implication to hold. Truth functions of further propositional connectives can be defined by means of the t-norm and its residuum, for instance the residual negation ¬ x = ( x ⇒ 0 ) {\displaystyle \neg x=(x\Rightarrow 0)} or bi-residual equivalence x ⇔ y = ( x ⇒ y ) ∗ ( y ⇒ x ) . {\displaystyle x\Leftrightarrow y=(x\Rightarrow y)(y\Rightarrow x).} Truth functions of propositional connectives may also be introduced by additional definitions: the most usual ones are the minimum (which plays a role of another conjunctive connective), the maximum (which plays a role of a disjunctive connective), or the Baaz Delta operator, defined in [0, 1] as Δ x = 1 {\displaystyle \Delta x=1} if x = 1 {\displaystyle x=1} and Δ x = 0 {\displaystyle \Delta x=0} otherwise. In this way, a left-continuous t-norm, its residuum, and the truth functions of additional propositional connectives determine the truth values of complex propositional formulae in [0, 1]. Formulae that always evaluate to 1 are called tautologies with respect to the given left-continuous t-norm ∗ , {\displaystyle ,} or ∗ - {\displaystyle {\mbox{-}}} tautologies. The set of all ∗ - {\displaystyle {\mbox{-}}} tautologies is called the logic of the t-norm ∗ , {\displaystyle ,} as these formulae represent the laws of fuzzy logic (determined by the t-norm) that hold (to degree 1) regardless of the truth degrees of atomic formulae. Some formulae are tautologies with respect to a larger class of left-continuous t-norms; the set of such formulae is called the logic of the class. Important t-norm logics are the logics of particular t-norms or classes of t-norms, for example: Łukasiewicz logic is the logic of the Łukasiewicz t-norm x ∗ y = max ( x + y − 1 , 0 ) {\displaystyle xy=\max(x+y-1,0)} Gödel–Dummett logic is the logic of the minimum t-norm x ∗ y = min ( x , y ) {\displaystyle xy=\min(x,y)} Product fuzzy logic is the logic of the product t-norm x ∗ y = x ⋅ y {\displaystyle xy=x\cdot y} Monoidal t-norm logic MTL is the logic of (the class of) all left-continuous t-norms Basic fuzzy logic BL is the logic of (the class of) all continuous t-norms It turns out that many logics of particular t-norms and classes of t-norms are axiomatizable. The completeness theorem of the axiomatic system with respect to the corresponding t-norm semantics on [0, 1] is then called the standard completeness of the logic. Besides the standard real-valued semantics on [0, 1], the logics are sound and complete with respect to general algebraic semantics, formed by suitable classes of prelinear commutative bounded integral residuated lattices. == History == Some particular t-norm fuzzy logics have been introduced and investigated long before the family was re
Data processing unit
A data processing unit (DPU) is a programmable computer processor that tightly integrates a general-purpose CPU with network interface hardware. They are also occasionally called "IPUs" (infrastructure processing unit) or "SmartNICs". They can be used in place of traditional NICs to relieve the main CPU of complex networking responsibilities and other "infrastructural" duties; although their features vary, they may be used to perform encryption/decryption, serve as a firewall, handle TCP/IP, process HTTP requests, or even function as a hypervisor or storage controller. These devices can be attractive to cloud computing providers whose servers might otherwise spend a significant amount of CPU time on these tasks, cutting into the cycles they can provide to guests. They see use in other kinds of data center environments as well due to their improved power consumption efficiency for routine networking tasks compared to general-purpose CPUs.
Hundred (novel series)
Hundred (ハンドレッド, Handoreddo) is a Japanese light novel series written by Jun Misaki and illustrated by Nekosuke Ōkuma. SB Creative published 16 novels between November 15, 2012, and October 15, 2018, under their GA Bunko imprint. A manga adaptation with art by Sasayuki was serialized in Fujimi Shobo's Monthly Dragon Age magazine. An anime television series adaptation, produced by Production IMS and directed by Tomoki Kobayashi, aired from April to June 2016. == Plot == "Hundreds" are a kind of weapon that get their name from their ability to change into many different forms, and are the only thing that can counter the mysterious life forms called Savage that are attacking Earth. Those who can wield a Hundred are sought out to be made into Slayers, trained individuals who can use them in combat. To become a Slayer, Hayato Kisaragi successfully enrolls in the marine academy city ship Little Garden. However he feels a strange yet familiar sense of incongruity towards Emile Crossford, his roommate who somehow knows him from somewhere. On top of that, shortly after he enters the school, he ends up getting challenged to a duel by the "Queen" and the school's most powerful Slayer, Claire Harvey. == Characters == Hayato Kisaragi (如月 ハヤト, Kisaragi Hayato) Voiced by: Yoshiaki Hasegawa (Japanese); Ricco Fajardo (English) Hayato is the male protagonist of Hundred. Originally from Yamato, Hayato became a Slayer in order to obtain state-of-the-art medical treatment for his sister. His previous encounter with a Savage 10 years ago resulted in him becoming a Variant - one of a very small fraction of people (fewer than 10 in the world, according to Emile) who have survived exposure to the Savages and obtained a greatly increased affinity for Hundreds as a result. He has the highest known compatibility with a Hundred and his Hundred, the Flying Swallow, is a chevalier-type that takes the form of a sword and a shoulder guard. When he first met Emilia he didn't realize that she was really a girl, but upon discovering the truth, he agreed to keep her secret. He is shown to be slightly uncomfortable whenever Emilia was showing him affection and would always blush when around her or other women who show their romantic feelings toward him. Emilia Hermit (エミリア・ハーミット, Emiria Hāmitto) Voiced by: Rumi Ōkubo (Japanese); Mikaela Krantz (English) Emilia is the female protagonist of Hundred. She is a silver-haired girl from the Britannia Empire and Hayato's roommate. She initially poses as a boy under the name Emile Crossfode (エミール・クロスフォード, Emīru Kurosufōdo) with only a few people aware of her secret until she eventually reveals the truth about herself. She and Hayato were survivors from the second Savage attack 10 years earlier, which resulted in her and Hayato becoming Variants. Hayato only has vague recollections of the prior event and it isn't until their encounter with the Savages at Zwei Island that Hayato realizes her true identity. She is a citizen of the Gudenburg Empire by birth and eventually reveals that she is Emilia Gudenburg (エミリア・グーデンブルグ, Emiria Gūdenburugu), the Empire's third princess. Her Hundred is the Arms Shroud that is an innocence type able to change into any form of weapon, something no other Slayer's Hundred can do. Like Hayato, she too is a Variant. Ten years ago she and Hayato where fleeing from the Savages' onslaught when she was attacked by one and almost died. The attack left a potent amount of virus in her gaping wound. Hayato, in an attempt to save her life sucked some of the fluids out, causing him to become a Variant as well. A substantial amount was still left in her system. She is in love with Hayato and is known to be very affectionate towards him and does not care about the rumors circulating about their relationship since everyone assumes them to be gay. Eventually, her status as a princess and girl are revealed to her peers, who were shocked at her heritage and finally understand her feelings to Hayato. Claire Harvey (クレア・ハーヴェイ, Kurea Hāvei) Voiced by: M.A.O (Japanese); Caitlin Glass (English) The highest-ranked Slayer in Little Garden who is from the United States of Liberia, she is called the Queen. The newly-arrived Hayato is forced to duel her to prevent the expulsion of two students who arrived late to the entrance ceremony because they are looking for him at the airport when he arrived. During the duel Hayato accidentally gropes her and she goes all out and defeats him, but the duel is called a draw and the students are allowed to stay. After Hayato saves her from a Savage and, later, accidentally kisses her, she falls in love with him. Her Hundred is a Dragoon Type which utilizes multiple cannons or transforms into a large powerful rifle, in doing so it drains much of her energy. She is also one of the few people who are aware that Emilia is secretly a girl. Karen Kisaragi (如月 カレン, Kisaragi Karen) Voiced by: Kaya Okuno (Japanese); Dawn M. Bennett (English) Hayato's younger sister who is ill. Hayato became a Slayer in order to obtain first-class treatment for her. While staying in the hospital she is often seen playing tarot cards, where she has become sort of a clairvoyant. Unlike her brother, Hayato, she suspected that Emilia was really a girl the moment she met her, until she was later convinced otherwise. She later becomes good friends with popular idol Sakura. Sakura Kirishima (霧島 サクラ, Kirishima Sakura) Voiced by: Mayu Yoshioka (Japanese); Amber Lee Connors (English) She is a popular idol who falls in love with Hayato after seeing him defeat the Trenta Savage at Zwei Island. She originally met Hayato and Karen at a shelter in Gudenberg during the second Savage attack. She remembers Karen but wasn't able to get Hayato's name at the time. After that incident, she lives with her father whom she never meets. When she later falls ill from an unknown illness, her father sells her to the Warslran Research Facility, where subjects like her are injected with vaccines that are developed from the fluids recovered from defeated Savages. She is the only one of the test subjects to have survived and, like Hayato and Emilia, she is also a Variant and a Slayer. Liza Harvey (リザ・ハーヴェイ, Riza Hāvei) Voiced by: Nichika Ōmori (Japanese); Megan Shipman (English) Claire's younger sister. Liddy Steinberg (リディ・スタインバーグ, Ridi Sutainbāgu) Voiced by: Rika Kinugawa (Japanese); Alex Moore (English) Little Garden's student council Vice President who is in charge of enforcement, she is very loyal to Claire and can be very uptight when enforcing the school's rules and regulations. Her Hundred takes the form of a lance and a shield. Erica Candle (エリカ・キャンドル, Erika Kyandoru) Voiced by: Yui Makino (Japanese); Natalie Hoover (English) She is also student council Vice President, however, she is mostly in charge of strategic planning, she has a high admiration for Claire, and it is suggested that she has certain feelings for her. Her Hundred, the Everlasting, is an Arsene type, which takes the form of a massive chained yoyo that she uses for restraining. Unfortunately her Hundred is ineffective against much stronger Savages. She is also one of the few people who became aware of Emilia's secret. Fritz Granz (フリッツ・グランツ, Furittsu Gurantsu) Voiced by: Wataru Hatano (Japanese); Jason Liebrecht (English) Hayato's classmate and Latia's partner. His Hundred takes the form of a sniper rifle. He and Latia were childhood friends, he often pokes fun at her. He is curious about the relationship between Hayato and Emilie and often teases them about their relationship, including sometimes referring to them as a couple on occasion. Latia Saintemilion (レイティア・サンテミリオン, Reitia Santemirion) Voiced by: Yuka Ōtsubo (Japanese); Elizabeth Maxwell (English) She is classmates with Hayato and Emilia, she is also Fritz's partner. Her Hundred is a close quarter melee type. She is Fritz's childhood friend. Charlotte Dimandias (シャーロット・ディマンディウス, Shārotto Dimandiusu) Voiced by: Miyu Matsuki (1st drama CD), Yui Horie (2nd drama CD, anime); Sarah Wiedenheft (English) She is a child prodigy who serves as the Little Garden's only main technical expert and chief researcher on Hundreds. Her authority is equal to that of the student council, that she can go against them or question their decisions. She is best friends with Emilia, and she is one of the characters who knows her secret. Meimei (メイメイ, Meimei) Voiced by: Ayaka Imamura (Japanese); Jill Harris (English) Miharu Kashiwagi (柏木 ミハル, Kashiwagi Miharu) Voiced by: Yuna Yoshino (Japanese); Rachel Glass (English) Miharu is a nurse at the hospital where Karen is staying. She is known for her very sweet demeanor and large breasts. Chris Steinbelt (クリス・シュタインベルト, Kurisu Shutainberuto) Voiced by: Emiri Kato (Japanese); Howard Wang (English) Noa Sheldon (ノア・シェルダン, Noa Sherudan) Voiced by: Yurika Kubo (Japanese); Madeleine Morris (English) Xue-Mei Liu (劉雪梅, Ryū Shuemei) Voiced by: Eri Suzuki (Japanese); Apphia Yu (English) Alphonse Brustad (アルフォ
Simple interactive object extraction
Simple interactive object extraction (SIOX) is an algorithm for extracting foreground objects from color images and videos with very little user interaction. It has been implemented as "foreground selection" tool in the GIMP (since version 2.3.3), as part of the tracer tool in Inkscape (since 0.44pre3), and as function in ImageJ and Fiji (plug-in). Experimental implementations were also reported for Blender and Krita. Although the algorithm was originally designed for videos, virtually all implementations use SIOX primarily for still image segmentation. In fact, it is often said to be the current de facto standard for this task in the open-source world. Initially, a free hand selection tool is used to specify the region of interest. It must contain all foreground objects to extract and as few background as possible. The pixels outside the region of interest form the sure background while the inner region define a superset of the foreground, i.e. the unknown region. A so-called foreground brush is then used to mark representative foreground regions. The algorithm outputs a selection mask. The selection can be refined by either adding further foreground markings or by adding background markings using the background brush. Technically, the algorithm performs the following steps: Create a set of representative colors for sure foreground and sure background, the so-called color signatures. Assign all image points to foreground or background by a weighted nearest neighbor search in the color signatures. Apply some standard image processing operations like erode, dilate, and blur to remove artifacts. Find the connected foreground components that are either large enough or marked by the user. For video segmentation the sure background and sure foreground regions are learned from motion statistics. SIOX also features tools that allow sub-pixel accurate refinement of edges and high texture areas, the so-called "detail refinement brushes". As with all segmentation algorithms, there are always pictures where the algorithm does not yield perfect results. The most critical drawback of SIOX is the color dependence. Although many photos are well-separable by color, the algorithm cannot deal with camouflage. If the foreground and background share many identical shades of similar colors, the algorithm might give a result with parts missing or incorrectly classified foreground. SIOX performs about equally well on different benchmarks compared to graph-based segmentation methods, such as Grabcut. SIOX is, however, more noise robust and can therefore also be used for the segmentation of videos. Graph-based segmentation methods search for a minimum cut and therefore tend to not perform optimally with complex structures. The algorithm has initially been developed at the department of computer science at Freie Universitaet Berlin. The main developer, Gerald Friedland, is now faculty at the EECS department of the University of California at Berkeley and also a Principal Data Scientist at Lawrence Livermore National Lab. He continues to support the development through mentoring, e.g. in the Google Summer of Code.
Anytime algorithm
In computer science, an anytime algorithm is an algorithm that can return a valid solution to a problem even if it is interrupted before it ends. The algorithm is expected to find better and better solutions the longer it keeps running. Most algorithms run to completion: they provide a single answer after performing some fixed amount of computation. In some cases, however, the user may wish to terminate the algorithm prior to completion. The amount of computation required may be substantial, for example, and computational resources might need to be reallocated. Most algorithms either run to completion or they provide no useful solution information. Anytime algorithms, however, are able to return a partial answer, whose quality depends on the amount of computation they were able to perform. The answer generated by anytime algorithms is an approximation of the correct answer. == Names == An anytime algorithm may be also called an "interruptible algorithm". They are different from contract algorithms, which must declare a time in advance; in an anytime algorithm, a process can just announce that it is terminating. == Goals == The goal of anytime algorithms are to give intelligent systems the ability to make results of better quality in return for turn-around time. They are also supposed to be flexible in time and resources. They are important because artificial intelligence or AI algorithms can take a long time to complete results. This algorithm is designed to complete in a shorter amount of time. Also, these are intended to have a better understanding that the system is dependent and restricted to its agents and how they work cooperatively. An example is the Newton–Raphson iteration applied to finding the square root of a number. Another example that uses anytime algorithms is trajectory problems when you're aiming for a target; the object is moving through space while waiting for the algorithm to finish and even an approximate answer can significantly improve its accuracy if given early. What makes anytime algorithms unique is their ability to return many possible outcomes for any given input. An anytime algorithm uses many well defined quality measures to monitor progress in problem solving and distributed computing resources. It keeps searching for the best possible answer with the amount of time that it is given. It may not run until completion and may improve the answer if it is allowed to run longer. This is often used for large decision set problems. This would generally not provide useful information unless it is allowed to finish. While this may sound similar to dynamic programming, the difference is that it is fine-tuned through random adjustments, rather than sequential. Anytime algorithms are designed so that it can be told to stop at any time and would return the best result it has found so far. This is why it is called an interruptible algorithm. Certain anytime algorithms also maintain the last result, so that if they are given more time, they can continue from where they left off to obtain an even better result. == Decision trees == When the decider has to act, there must be some ambiguity. Also, there must be some idea about how to solve this ambiguity. This idea must be translatable to a state to action diagram. == Performance profile == The performance profile estimates the quality of the results based on the input and the amount of time that is allotted to the algorithm. The better the estimate, the sooner the result would be found. Some systems have a larger database that gives the probability that the output is the expected output. One algorithm can have several performance profiles. Most of the time performance profiles are constructed using mathematical statistics using representative cases. For example, in the traveling salesman problem, the performance profile was generated using a user-defined special program to generate the necessary statistics. In this example, the performance profile is the mapping of time to the expected results. This quality can be measured in several ways: certainty: where probability of correctness determines quality accuracy: where error bound determines quality specificity: where the amount of particulars determine quality == Algorithm prerequisites == Initial behavior: While some algorithms start with immediate guesses, others take a more calculated approach and have a start up period before making any guesses. Growth direction: How the quality of the program's "output" or result, varies as a function of the amount of time ("run time") Growth rate: Amount of increase with each step. Does it change constantly, such as in a bubble sort or does it change unpredictably? End condition: The amount of runtime needed