Qlone is a 3D scanning app based on photogrammetry for creation of 3D models on mobile devices. The resultant 3D models can be exported for external use. Qlone was featured at the Apple Worldwide Developers Conference in 2021. It was also featured on BBC Click. == Qlone features == === 3D scanning === 3D scanning with Qlone requires the use of an included mat design. The user prints the mat onto a sheet of paper, then places the object to be scanned in the centre of the mat. An augmented reality dome within the Qlone app guides the user through the subsequent scanning process. The iOS version of Qlone allows scanning without the mat. === 3D editing === Qlone's editing features allow users to adjust 3D scanned models using texture mapping, polygon mesh size simplification, digital sculpting, cleaning and smoothing, and artistic effects. === File export === Qlone exports directly to multiple 3D platforms including SketchFab, i.materialise, Lens Studio for Snapchat, Shapeways and CGTrader. Models can also be exported in different 3D formats for use in other 3D tools – OBJ, STL, FBX, USDZ, GLB (Binary gLTF), PLY, and X3D. == Use in Science, Education and Academia == Due to its inexpensive, simple and accessible nature for creating 3D models, Qlone was used in many academically educational and scientific research projects. The European Space Agency used Qlone to scan rocks in a Tele-Robotic rock collection experiment. Neurosurgeons from the University of Southern California and surgeons from Tulane University School of Medicine used Qlone to create 3D models of cadaveric specimens and anatomical models with the aim of increasing access to such components for enhancing anatomy training and allowing realistic surgical simulations for neurosurgeons and practitioners worldwide. Archaeologists from Texas A&M University used Qlone to create 3D replicas of artifacts and models and students from Vancouver iTech Preparatory Middle School used Qlone to create 3D scans of more than 100 artifacts from Fort Vancouver National Historic Site.
Zeuthen strategy
The Zeuthen strategy in cognitive science is a negotiation strategy used by some artificial agents. Its purpose is to measure the willingness to risk conflict. An agent will be more willing to risk conflict if it does not have much to lose in case that the negotiation fails. In contrast, an agent is less willing to risk conflict when it has more to lose. The value of a deal is expressed in its utility. An agent has much to lose when the difference between the utility of its current proposal and the conflict deal is high. When both agents use the monotonic concession protocol, the Zeuthen strategy leads them to agree upon a deal in the negotiation set. This set consists of all conflict free deals, which are individually rational and Pareto optimal, and the conflict deal, which maximizes the Nash product. The strategy was introduced in 1930 by the Danish economist Frederik Zeuthen. == Three key questions == The Zeuthen strategy answers three open questions that arise when using the monotonic concession protocol, namely: Which deal should be proposed at first? On any given round, who should concede? In case of a concession, how much should the agent concede? The answer to the first question is that any agent should start with its most preferred deal, because that deal has the highest utility for that agent. The second answer is that the agent with the smallest value of Risk(i,t) concedes, because the agent with the lowest utility for the conflict deal profits most from avoiding conflict. To the third question, the Zeuthen strategy suggests that the conceding agent should concede just enough raise its value of Risk(i,t) just above that of the other agent. This prevents the conceding agent to have to concede again in the next round. == Risk == Risk ( i , t ) = { 1 U i ( δ ( i , t ) ) = 0 U i ( δ ( i , t ) ) − U i ( δ ( j , t ) ) U i ( δ ( i , t ) ) otherwise {\displaystyle {\text{Risk}}(i,t)={\begin{cases}1&U_{i}(\delta (i,t))=0\\{\frac {U_{i}(\delta (i,t))-U_{i}(\delta (j,t))}{U_{i}(\delta (i,t))}}&{\text{otherwise}}\end{cases}}} Risk(i,t) is a measurement of agent i's willingness to risk conflict. The risk function formalizes the notion that an agent's willingness to risk conflict is the ratio of the utility that agent would lose by accepting the other agent's proposal to the utility that agent would lose by causing a conflict. Agent i is said to be using a rational negotiation strategy if at any step t + 1 that agent i sticks to his last proposal, Risk(i,t) > Risk(j,t). == Sufficient concession == If agent i makes a sufficient concession in the next step, then, assuming that agent j is using a rational negotiation strategy, if agent j does not concede in the next step, he must do so in the step after that. The set of all sufficient concessions of agent i at step t is denoted SC(i, t). == Minimal sufficient concession == δ ′ = arg max δ ∈ S C ( A , t ) { U A ( δ ) } {\displaystyle \delta '=\arg \max _{\delta \in {SC(A,t)}}\{U_{A}(\delta )\}} is the minimal sufficient concession of agent A in step t. Agent A begins the negotiation by proposing δ ( A , 0 ) = arg max δ ∈ N S U A ( δ ) {\displaystyle \delta (A,0)=\arg \max _{\delta \in {NS}}U_{A}(\delta )} and will make the minimal sufficient concession in step t + 1 if and only if Risk(A,t) ≤ Risk(B,t). Theorem If both agents are using Zeuthen strategies, then they will agree on δ = arg max δ ′ ∈ N S { π ( δ ′ ) } , {\displaystyle \delta =\arg \max _{\delta '\in {NS}}\{\pi (\delta ')\},} that is, the deal which maximizes the Nash product. Proof Let δA = δ(A,t). Let δB = δ(B,t). According to the Zeuthen strategy, agent A will concede at step t {\displaystyle t} if and only if R i s k ( A , t ) ≤ R i s k ( B , t ) . {\displaystyle Risk(A,t)\leq Risk(B,t).} That is, if and only if U A ( δ A ) − U A ( δ B ) U A ( δ A ) ≤ U B ( δ B ) − U B ( δ A ) U B ( δ B ) {\displaystyle {\frac {U_{A}(\delta _{A})-U_{A}(\delta _{B})}{U_{A}(\delta _{A})}}\leq {\frac {U_{B}(\delta _{B})-U_{B}(\delta _{A})}{U_{B}(\delta _{B})}}} U B ( δ B ) ( U A ( δ A ) − U A ( δ B ) ) ≤ U A ( δ A ) ( U B ( δ B ) − U B ( δ A ) ) {\displaystyle U_{B}(\delta _{B})(U_{A}(\delta _{A})-U_{A}(\delta _{B}))\leq U_{A}(\delta _{A})(U_{B}(\delta _{B})-U_{B}(\delta _{A}))} U A ( δ A ) U B ( δ B ) − U A ( δ B ) U B ( δ B ) ≤ U A ( δ A ) U B ( δ B ) − U A ( δ A ) U B ( δ A ) {\displaystyle U_{A}(\delta _{A})U_{B}(\delta _{B})-U_{A}(\delta _{B})U_{B}(\delta _{B})\leq U_{A}(\delta _{A})U_{B}(\delta _{B})-U_{A}(\delta _{A})U_{B}(\delta _{A})} − U A ( δ B ) U B ( δ B ) ≤ − U A ( δ A ) U B ( δ A ) {\displaystyle -U_{A}(\delta _{B})U_{B}(\delta _{B})\leq -U_{A}(\delta _{A})U_{B}(\delta _{A})} U A ( δ A ) U B ( δ A ) ≤ U A ( δ B ) U B ( δ B ) {\displaystyle U_{A}(\delta _{A})U_{B}(\delta _{A})\leq U_{A}(\delta _{B})U_{B}(\delta _{B})} π ( δ A ) ≤ π ( δ B ) {\displaystyle \pi (\delta _{A})\leq \pi (\delta _{B})} Thus, Agent A will concede if and only if δ A {\displaystyle \delta _{A}} does not yield the larger product of utilities. Therefore, the Zeuthen strategy guarantees a final agreement that maximizes the Nash Product.
Ballin' (Mustard and Roddy Ricch song)
"Ballin'" is a song by American record producer Mustard featuring American rapper Roddy Ricch. The track was released as the third single from Mustard's third studio album, Perfect Ten, on August 20, 2019, though it was available as early as the end of June 2019. The song and its accompanying video received acclaim from music critics, with Complex magazine naming it the Best Song of 2019. It peaked at number 11 on the Billboard Hot 100, marking Mustard's highest charting song in the US. The song received a nomination for Best Rap/Sung Performance at the 2020 Grammy Awards, making it the first time Ricch has been nominated for a Grammy and Mustard's first nomination as an artist. Later in 2019, the two released another collaboration, "High Fashion". == Background == Roddy Ricch revealed in an interview that the song was composed in late 2018, but Mustard wanted to keep it for his album, Perfect Ten, which he was still working on. The song was later included on the album, released in June 2019. Ricch said he knew the song was "hard enough" the first time he heard it, while Mustard proclaimed "this is going to be the one". == Composition and lyrics == "Ballin'" has a "rags to riches" theme. In its intro, the song samples girl group 702's 1997 top ten hit "Get It Together". The song features a "smooth, bouncy beat", with Roddy Ricch rapping about his come-up and ascent in the music industry. In the first verse, Ricch salutes fellow Los Angeles rapper, the late Nipsey Hussle and his girlfriend Lauren London: "I run these racks up with my queen like London and Nip". The line simultaneously references Ricch and Hussle's collaboration "Racks in the Middle", released earlier in 2019 as Hussle's last single before his death. Billboard's Heran Mamo noted that "in typical Hussle fashion", Roddy Ricch "narrates his life's hardships before delving into his newfound treasures". == Critical reception == The song was widely acclaimed by music critics. Charles Holmes of Rolling Stone magazine called it "a song of the year contender", while Complex and Billboard both named it as a "standout track" on the album. Pitchfork magazine included "Ballin'" in its list of The Best Rap Songs of 2019 and called it "the centerpiece of Mustard's underappreciated album Perfect Ten". Complex later named it the Best Song of 2019, calling it "a feel-good anthem so infectious you'll need antibiotics just to stop running it back". == Chart performance == "Ballin'" was at the time Mustard's highest charting song in the US, peaking at number 11 on the Billboard Hot 100. It was also Roddy Ricch's highest charting song, until he surpassed it a week later, with the release of his album track "The Box", which eventually reached number 1 on the chart. It reached number one on Billboard's Rhythmic Songs chart, becoming Mustard's second number one following "Pure Water" and Ricch's first number one. The song also topped the Rap Airplay chart. == Music video == The music video for the track was teased by Mustard on his Instagram page on September 29, 2019. The music video for the track was eventually released on October 2, 2019 to critical acclaim. The video features Mustard and Roddy Ricch driving a Lamborghini Aventador in Los Angeles, where they both are from, playing poker in a casino, and going to a strip club. This is contrasted with scenes in which Mustard and Roddy Ricch as children play cards with Monopoly money and playing with miniature toy Lamborghinis together, aspiring for wealth and luxury, representing how they went from "rags to riches". The video also pays tribute to rapper Nipsey Hussle, who had been killed a few months ago. == Live performances == On December 16, 2019, Roddy Ricch performed the song live, alongside an 8-piece orchestra, at Peppermint Club in Los Angeles for Audiomack's Trap Symphony series. Along with Mustard, he performed it at The Pop Out: Ken & Friends on June 19, 2024. == Other uses == The song can be heard on "Elyse's Skit", track 10 off Roddy Ricch's debut album Please Excuse Me for Being Antisocial. In the skit, which is an actual voicenote recording, the mother of a woman named Elyse sends her daughter a voicenote, with "Ballin'" playing in the background, while the mother proceeds to say "I can't get that damn song out my head", jokingly calling it "inappropriate music". Ricch called the skit "something natural". In 2023, AI covers of the song using models based on pop culture characters and real-world celebrities gained viral popularity. == Awards and nominations == 62nd Annual Grammy Awards == Charts == == Certifications ==
Knuth–Eve algorithm
In computer science, the Knuth–Eve algorithm is an algorithm for polynomial evaluation. It preprocesses the coefficients of the polynomial to reduce the number of multiplications required at runtime. Ideas used in the algorithm were originally proposed by Donald Knuth in 1962. His procedure opportunistically exploits structure in the polynomial being evaluated. In 1964, James Eve determined for which polynomials this structure exists, and gave a simple method of "preconditioning" polynomials (explained below) to endow them with that structure. == Algorithm == === Preliminaries === Consider an arbitrary polynomial p ∈ R [ x ] {\displaystyle p\in \mathbb {R} [x]} of degree n {\displaystyle n} . Assume that n ≥ 3 {\displaystyle n\geq 3} . Define m {\displaystyle m} such that: if n {\displaystyle n} is odd then n = 2 m + 1 {\displaystyle n=2m+1} , and if n {\displaystyle n} is even then n = 2 m + 2 {\displaystyle n=2m+2} . Unless otherwise stated, all variables in this article represent either real numbers or univariate polynomials with real coefficients. All operations in this article are done over R {\displaystyle \mathbb {R} } . Again, the goal is to create an algorithm that returns p ( x ) {\displaystyle p(x)} given any x {\displaystyle x} . The algorithm is allowed to depend on the polynomial p {\displaystyle p} itself, since its coefficients are known in advance. === Overview === ==== Key idea ==== Using polynomial long division, we can write p ( x ) = q ( x ) ⋅ ( x 2 − α ) + ( β x + γ ) , {\displaystyle p(x)=q(x)\cdot (x^{2}-\alpha )+(\beta x+\gamma ),} where x 2 − α {\displaystyle x^{2}-\alpha } is the divisor. Picking a value for α {\displaystyle \alpha } fixes both the quotient q {\displaystyle q} and the coefficients in the remainder β {\displaystyle \beta } and γ {\displaystyle \gamma } . The key idea is to cleverly choose α {\displaystyle \alpha } such that β = 0 {\displaystyle \beta =0} , so that p ( x ) = q ( x ) ⋅ ( x 2 − α ) + γ . {\displaystyle p(x)=q(x)\cdot (x^{2}-\alpha )+\gamma .} This way, no operations are needed to compute the remainder polynomial, since it's just a constant. We apply this procedure recursively to q {\displaystyle q} , expressing p ( x ) = ( ( q ( x ) ⋅ ( x 2 − α m ) + γ m ) ⋯ ) ⋅ ( x 2 − α 1 ) + γ 1 . {\displaystyle p(x)=\left(\left(q(x)\cdot (x^{2}-\alpha _{m})+\gamma _{m}\right)\cdots \right)\cdot (x^{2}-\alpha _{1})+\gamma _{1}.} After m {\displaystyle m} recursive calls, the quotient q {\displaystyle q} is either a linear or a quadratic polynomial. In this base case, the polynomial can be evaluated with (say) Horner's method. ==== "Preconditioning" ==== For arbitrary p {\displaystyle p} , it may not be possible to force β = 0 {\displaystyle \beta =0} at every step of the recursion. Consider the polynomials p e {\displaystyle p^{e}} and p o {\displaystyle p^{o}} with coefficients taken from the even and odd terms of p {\displaystyle p} respectively, so that p ( x ) = p e ( x 2 ) + x ⋅ p o ( x 2 ) . {\displaystyle p(x)=p^{e}(x^{2})+x\cdot p^{o}(x^{2}).} If every root of p o {\displaystyle p^{o}} is real, then it is possible to write p {\displaystyle p} in the form given above. Each α i {\displaystyle \alpha _{i}} is a different root of p o {\displaystyle p^{o}} , counting multiple roots as distinct. Furthermore, if at least n − 1 {\displaystyle n-1} roots of p {\displaystyle p} lie in one half of the complex plane, then every root of p o {\displaystyle p^{o}} is real. Ultimately, it may be necessary to "precondition" p {\displaystyle p} by shifting it — by setting p ( x ) ← p ( x + t ) {\displaystyle p(x)\gets p(x+t)} for some t {\displaystyle t} — to endow it with the structure that most of its roots lie in one half of the complex plane. At runtime, this shift has to be "undone" by first setting x ← x − t {\displaystyle x\gets x-t} . === Preprocessing step === The following algorithm is run once for a given polynomial p {\displaystyle p} . At this point, the values of x {\displaystyle x} that p {\displaystyle p} will be evaluated on are not known. ==== Better choice of t ==== While any t ≥ Re ( r 2 ) {\displaystyle t\geq {\text{Re}}(r_{2})} can work, it is possible to remove one addition during evaluation if t {\displaystyle t} is also chosen such that two roots of p ( x + t ) {\displaystyle p(x+t)} are symmetric about the origin. In that case, α 1 {\displaystyle \alpha _{1}} can be chosen such that the shifted polynomial has a factor of x 2 − α 1 {\displaystyle x^{2}-\alpha _{1}} , so γ 1 = 0 {\displaystyle \gamma _{1}=0} . It is always possible to find such a t {\displaystyle t} . One possible algorithm for choosing t {\displaystyle t} is: === Evaluation step === The following algorithm evaluates p {\displaystyle p} at some, now known, point x {\displaystyle x} . Assuming t {\displaystyle t} is chosen optimally, γ 1 = 0 {\displaystyle \gamma _{1}=0} . So, the final iteration of the loop can instead run y ← y ⋅ ( s − α i ) , {\displaystyle y\gets y\cdot (s-\alpha _{i}),} saving an addition. == Analysis == In total, evaluation using the Knuth–Eve algorithm for a polynomial of degree n {\displaystyle n} requires n {\displaystyle n} additions and ⌊ n / 2 ⌋ + 2 {\displaystyle \lfloor n/2\rfloor +2} multiplications, assuming t {\displaystyle t} is chosen optimally. No algorithm to evaluate a given polynomial of degree n {\displaystyle n} can use fewer than n {\displaystyle n} additions or fewer than ⌈ n / 2 ⌉ {\displaystyle \lceil n/2\rceil } multiplications during evaluation. This result assumes only addition and multiplication are allowed during both preprocessing and evaluation. The Knuth–Eve algorithm is not well-conditioned.
Source criticism
Source criticism (or information evaluation) is the process of evaluating an information source, i.e.: a document, a person, a speech, a fingerprint, a photo, an observation, or anything used in order to obtain knowledge. In relation to a given purpose, a given information source may be more or less valid, reliable or relevant. Broadly, "source criticism" is the interdisciplinary study of how information sources are evaluated for given tasks. == Meaning == Problems in translation: The Danish word kildekritik, like the Norwegian word kildekritikk and the Swedish word källkritik, derived from the German Quellenkritik and is closely associated with the German historian Leopold von Ranke (1795–1886). Historian Wolfgang Hardtwig wrote: His [Ranke's] first work Geschichte der romanischen und germanischen Völker von 1494–1514 (History of the Latin and Teutonic Nations from 1494 to 1514) (1824) was a great success. It already showed some of the basic characteristics of his conception of Europe, and was of historiographical importance particularly because Ranke made an exemplary critical analysis of his sources in a separate volume, Zur Kritik neuerer Geschichtsschreiber (On the Critical Methods of Recent Historians). In this work he raised the method of textual criticism used in the late eighteenth century, particularly in classical philology to the standard method of scientific historical writing. (Hardtwig, 2001, p. 12739) Historical theorist Chris Lorenz wrote: The larger part of the nineteenth and twentieth centuries would be dominated by the research-oriented conception of historical method of the so-called Historical School in Germany, led by historians as Leopold Ranke and Berthold Niebuhr. Their conception of history, long been regarded as the beginning of modern, 'scientific' history, harked back to the 'narrow' conception of historical method, limiting the methodical character of history to source criticism. (Lorenz, 2001) In the early 21st century, source criticism is a growing field in, among other fields, library and information science. In this context source criticism is studied from a broader perspective than just, for example, history, classical philology, or biblical studies (but there, too, it has more recently received new attention). == Principles == The following principles are from two Scandinavian textbooks on source criticism, written by the historians Olden-Jørgensen (1998) and Thurén (1997): Human sources may be relics (e.g. a fingerprint) or narratives (e.g. a statement or a letter). Relics are more credible sources than narratives. A given source may be forged or corrupted; strong indications of the originality of the source increases its reliability. The closer a source is to the event which it purports to describe, the more one can trust it to give an accurate description of what really happened A primary source is more reliable than a secondary source, which in turn is more reliable than a tertiary source and so on. If a number of independent sources contain the same message, the credibility of the message is strongly increased. The tendency of a source is its motivation for providing some kind of bias. Tendencies should be minimized or supplemented with opposite motivations. If it can be demonstrated that the witness (or source) has no direct interest in creating bias, the credibility of the message is increased. Two other principles are: Knowledge of source criticism cannot substitute for subject knowledge: "Because each source teaches you more and more about your subject, you will be able to judge with ever-increasing precision the usefulness and value of any prospective source. In other words, the more you know about the subject, the more precisely you can identify what you must still find out". (Bazerman, 1995, p. 304). The reliability of a given source is relative to the questions put to it. "The empirical case study showed that most people find it difficult to assess questions of cognitive authority and media credibility in a general sense, for example, by comparing the overall credibility of newspapers and the Internet. Thus these assessments tend to be situationally sensitive. Newspapers, television and the Internet were frequently used as sources of orienting information, but their credibility varied depending on the actual topic at hand" (Savolainen, 2007). The following questions are often good ones to ask about any source according to the American Library Association (1994) and Engeldinger (1988): How was the source located? What type of source is it? Who is the author and what are the qualifications of the author in regard to the topic that is discussed? When was the information published? In which country was it published? What is the reputation of the publisher? Does the source show a particular cultural or political bias? For literary sources complementing criteria are: Does the source contain a bibliography? Has the material been reviewed by a group of peers, or has it been edited? How does the article/book compare with similar articles/books? == Levels of generality == Some principles of source criticism are universal, other principles are specific for certain kinds of information sources. There is today no consensus about the similarities and differences between source criticism in the natural science and humanities. Logical positivism claimed that all fields of knowledge were based on the same principles. Much of the criticism of logical positivism claimed that positivism is the basis of the sciences, whereas hermeneutics is the basis of the humanities. This was, for example, the position of Jürgen Habermas. A newer position, in accordance with, among others, Hans-Georg Gadamer and Thomas Kuhn, understands both science and humanities as determined by researchers' preunderstanding and paradigms. Hermeneutics is thus a universal theory. The difference is, however, that the sources of the humanities are themselves products of human interests and preunderstanding, whereas the sources of the natural sciences are not. Humanities are thus "doubly hermeneutic". Natural scientists, however, are also using human products (such as scientific papers) which are products of preunderstanding (and can lead to, for example, academic fraud). == Contributing fields == === Epistemology === Epistemological theories are the basic theories about how knowledge is obtained and are thus the most general theories about how to evaluate information sources. Empiricism evaluates sources by considering the observations (or sensations) on which they are based. Sources without basis in experience are not seen as valid. Rationalism provides low priority to sources based on observations. In order to be meaningful, observations must be explained by clear ideas or concepts. It is the logical structure and the well definedness that is in focus in evaluating information sources from the rationalist point of view. Historicism evaluates information sources on the basis of their reflection of their sociocultural context and their theoretical development. Pragmatism evaluate sources on the basis of how their values and usefulness to accomplish certain outcomes. Pragmatism is skeptical about claimed neutral information sources. The evaluation of knowledge or information sources cannot be more certain than is the construction of knowledge. If one accepts the principle of fallibilism then one also has to accept that source criticism can never 100% verify knowledge claims. As discussed in the next section, source criticism is intimately linked to scientific methods. The presence of fallacies of argument in sources is another kind of philosophical criterion for evaluating sources. Fallacies are presented by Walton (1998). Among the fallacies are the ad hominem fallacy (the use of personal attack to try to undermine or refute a person's argument) and the straw man fallacy (when one arguer misrepresents another's position to make it appear less plausible than it really is, in order more easily to criticize or refute it.) === Research methodology === Research methods are methods used to produce scholarly knowledge. The methods that are relevant for producing knowledge are also relevant for evaluating knowledge. An example of a book that turns methodology upside-down and uses it to evaluate produced knowledge is Katzer; Cook & Crouch (1998). === Science studies === Studies of quality evaluation processes such as peer review, book reviews and of the normative criteria used in evaluation of scientific and scholarly research. Another field is the study of scientific misconduct. Harris (1979) provides a case study of how a famous experiment in psychology, Little Albert, has been distorted throughout the history of psychology, starting with the author (Watson) himself, general textbook authors, behavior therapists, and a prominent learning theorist. Harris proposes possible causes for these distortions and analyzes the Albert study as an ex
Glyph (data visualization)
In the context of data visualization, a glyph is any marker, such as an arrow or similar marking, used to specify part of a visualization. This is a representation to visualize data where the data set is presented as a collection of visual objects. These visual objects are collectively called a glyph. It helps visualizing data relation in data analysis, statistics, etc. by using any custom notation. In the context of data visualization, a glyph is the visual representation of a piece of data where the attributes of a graphical entity are dictated by one or more attributes of a data record. == Constructing glyphs == Glyph construction can be a complex process when there are many dimensions to be represented in the visualization. Maguire et al proposed a taxonomy based approach to glyph-design that uses a tree to guide the visual encodings used to representation various data items. Duffy et al created perhaps one of the most complex glyph representations with their representation of sperm movement.
Dependency network (graphical model)
Dependency networks (DNs) are graphical models, similar to Markov networks, wherein each vertex (node) corresponds to a random variable and each edge captures dependencies among variables. Unlike Bayesian networks, DNs may contain cycles. Each node is associated to a conditional probability table, which determines the realization of the random variable given its parents. == Markov blanket == In a Bayesian network, the Markov blanket of a node is the set of parents and children of that node, together with the children's parents. The values of the parents and children of a node evidently give information about that node. However, its children's parents also have to be included in the Markov blanket, because they can be used to explain away the node in question. In a Markov random field, the Markov blanket for a node is simply its adjacent (or neighboring) nodes. In a dependency network, the Markov blanket for a node is simply the set of its parents. == Dependency network versus Bayesian networks == Dependency networks have advantages and disadvantages with respect to Bayesian networks. In particular, they are easier to parameterize from data, as there are efficient algorithms for learning both the structure and probabilities of a dependency network from data. Such algorithms are not available for Bayesian networks, for which the problem of determining the optimal structure is NP-hard. Nonetheless, a dependency network may be more difficult to construct using a knowledge-based approach driven by expert-knowledge. == Dependency networks versus Markov networks == Consistent dependency networks and Markov networks have the same representational power. Nonetheless, it is possible to construct non-consistent dependency networks, i.e., dependency networks for which there is no compatible valid joint probability distribution. Markov networks, in contrast, are always consistent. == Definition == A consistent dependency network for a set of random variables X = ( X 1 , … , X n ) {\textstyle \mathbf {X} =(X_{1},\ldots ,X_{n})} with joint distribution p ( x ) {\displaystyle p(\mathbf {x} )} is a pair ( G , P ) {\displaystyle (G,P)} where G {\displaystyle G} is a cyclic directed graph, where each of its nodes corresponds to a variable in X {\displaystyle \mathbf {X} } , and P {\displaystyle P} is a set of conditional probability distributions. The parents of node X i {\displaystyle X_{i}} , denoted P a i {\displaystyle \mathbf {Pa_{i}} } , correspond to those variables P a i ⊆ ( X 1 , … , X i − 1 , X i + 1 , … , X n ) {\displaystyle \mathbf {Pa_{i}} \subseteq (X_{1},\ldots ,X_{i-1},X_{i+1},\ldots ,X_{n})} that satisfy the following independence relationships p ( x i ∣ p a i ) = p ( x i ∣ x 1 , … , x i − 1 , x i + 1 , … , x n ) = p ( x i ∣ x − x i ) . {\displaystyle p(x_{i}\mid \mathbf {pa_{i}} )=p(x_{i}\mid x_{1},\ldots ,x_{i-1},x_{i+1},\ldots ,x_{n})=p(x_{i}\mid \mathbf {x} -{x_{i}}).} The dependency network is consistent in the sense that each local distribution can be obtained from the joint distribution p ( x ) {\displaystyle p(\mathbf {x} )} . Dependency networks learned using large data sets with large sample sizes will almost always be consistent. A non-consistent network is a network for which there is no joint probability distribution compatible with the pair ( G , P ) {\displaystyle (G,P)} . In that case, there is no joint probability distribution that satisfies the independence relationships subsumed by that pair. == Structure and parameters learning == Two important tasks in a dependency network are to learn its structure and probabilities from data. Essentially, the learning algorithm consists of independently performing a probabilistic regression or classification for each variable in the domain. It comes from observation that the local distribution for variable X i {\displaystyle X_{i}} in a dependency network is the conditional distribution p ( x i | x − x i ) {\displaystyle p(x_{i}|\mathbf {x} -{x_{i}})} , which can be estimated by any number of classification or regression techniques, such as methods using a probabilistic decision tree, a neural network or a probabilistic support-vector machine. Hence, for each variable X i {\displaystyle X_{i}} in domain X {\displaystyle X} , we independently estimate its local distribution from data using a classification algorithm, even though it is a distinct method for each variable. Here, we will briefly show how probabilistic decision trees are used to estimate the local distributions. For each variable X i {\displaystyle X_{i}} in X {\displaystyle \mathbf {X} } , a probabilistic decision tree is learned where X i {\displaystyle X_{i}} is the target variable and X − X i {\displaystyle \mathbf {X} -X_{i}} are the input variables. To learn a decision tree structure for X i {\displaystyle X_{i}} , the search algorithm begins with a singleton root node without children. Then, each leaf node in the tree is replaced with a binary split on some variable X j {\displaystyle X_{j}} in X − X i {\displaystyle \mathbf {X} -X_{i}} , until no more replacements increase the score of the tree. == Probabilistic Inference == A probabilistic inference is the task in which we wish to answer probabilistic queries of the form p ( y ∣ z ) {\displaystyle p(\mathbf {y\mid z} )} , given a graphical model for X {\displaystyle \mathbf {X} } , where Y {\displaystyle \mathbf {Y} } (the 'target' variables) Z {\displaystyle \mathbf {Z} } (the 'input' variables) are disjoint subsets of X {\displaystyle \mathbf {X} } . One of the alternatives for performing probabilistic inference is using Gibbs sampling. A naive approach for this uses an ordered Gibbs sampler, an important difficulty of which is that if either p ( y ∣ z ) {\displaystyle p(\mathbf {y\mid z} )} or p ( z ) {\displaystyle p(\mathbf {z} )} is small, then many iterations are required for an accurate probability estimate. Another approach for estimating p ( y ∣ z ) {\displaystyle p(\mathbf {y\mid z} )} when p ( z ) {\displaystyle p(\mathbf {z} )} is small is to use modified ordered Gibbs sampler, where Z = z {\displaystyle \mathbf {Z=z} } is fixed during Gibbs sampling. It may also happen that y {\displaystyle \mathbf {y} } is rare, e.g. when Y {\displaystyle \mathbf {Y} } has many variables. So, the law of total probability along with the independencies encoded in a dependency network can be used to decompose the inference task into a set of inference tasks on single variables. This approach comes with the advantage that some terms may be obtained by direct lookup, thereby avoiding some Gibbs sampling. You can see below an algorithm that can be used for obtain p ( y | z ) {\displaystyle p(\mathbf {y|z} )} for a particular instance of y ∈ Y {\displaystyle \mathbf {y} \in \mathbf {Y} } and z ∈ Z {\displaystyle \mathbf {z} \in \mathbf {Z} } , where Y {\displaystyle \mathbf {Y} } and Z {\displaystyle \mathbf {Z} } are disjoint subsets. Algorithm 1: U := Y {\displaystyle \mathbf {U:=Y} } ( the unprocessed variables ) P := Z {\displaystyle \mathbf {P:=Z} } ( the processed and conditioning variables ) p := z {\displaystyle \mathbf {p:=z} } ( the values for P {\displaystyle \mathbf {P} } ) While U ≠ ∅ {\displaystyle \mathbf {U} \neq \emptyset } : Choose X i ∈ U {\displaystyle X_{i}\in \mathbf {U} } such that X i {\displaystyle X_{i}} has no more parents in U {\displaystyle U} than any variable in U {\displaystyle U} If all the parents of X {\displaystyle X} are in P {\displaystyle \mathbf {P} } p ( x i | p ) := p ( x i | p a i ) {\displaystyle p(x_{i}|\mathbf {p} ):=p(x_{i}|\mathbf {pa_{i}} )} Else Use a modified ordered Gibbs sampler to determine p ( x i | p ) {\displaystyle p(x_{i}|\mathbf {p} )} U := U − X i {\displaystyle \mathbf {U:=U} -X_{i}} P := P + X i {\displaystyle \mathbf {P:=P} +X_{i}} p := p + x i {\displaystyle \mathbf {p:=p} +x_{i}} Returns the product of the conditionals p ( x i | p ) {\displaystyle p(x_{i}|\mathbf {p} )} == Applications == In addition to the applications to probabilistic inference, the following applications are in the category of Collaborative Filtering (CF), which is the task of predicting preferences. Dependency networks are a natural model class on which to base CF predictions, once an algorithm for this task only needs estimation of p ( x i = 1 | x − x i = 0 ) {\displaystyle p(x_{i}=1|\mathbf {x} -{x_{i}}=0)} to produce recommendations. In particular, these estimates may be obtained by a direct lookup in a dependency network. Predicting what movies a person will like based on his or her ratings of movies seen; Predicting what web pages a person will access based on his or her history on the site; Predicting what news stories a person is interested in based on other stories he or she read; Predicting what product a person will buy based on products he or she has already purchased and/or dropped into his or her shopping basket. Another class of useful applications for dependency networks is related to data visualization, that is