Hidden Markov model

A hidden Markov model (HMM) is a Markov model in which the observations are dependent on a latent (or hidden) Markov process (referred to as X {\displaystyle X} ). An HMM requires that there be an observable process Y {\displaystyle Y} whose outcomes depend on the outcomes of X {\displaystyle X} in a known way. Since X {\displaystyle X} cannot be observed directly, the goal is to learn about state of X {\displaystyle X} by observing Y {\displaystyle Y} . By definition of being a Markov model, an HMM has an additional requirement that the outcome of Y {\displaystyle Y} at time t = t 0 {\displaystyle t=t_{0}} must be "influenced" exclusively by the outcome of X {\displaystyle X} at t = t 0 {\displaystyle t=t_{0}} and that the outcomes of X {\displaystyle X} and Y {\displaystyle Y} at t < t 0 {\displaystyle t

Similarity learning

Similarity learning is an area of supervised machine learning in artificial intelligence. It is closely related to regression and classification, but the goal is to learn a similarity function that measures how similar or related two objects are. It has applications in ranking, in recommendation systems, visual identity tracking, face verification, and speaker verification. == Learning setup == There are four common setups for similarity and metric distance learning. Regression similarity learning In this setup, pairs of objects are given ( x i 1 , x i 2 ) {\displaystyle (x_{i}^{1},x_{i}^{2})} together with a measure of their similarity y i ∈ R {\displaystyle y_{i}\in R} . The goal is to learn a function that approximates f ( x i 1 , x i 2 ) ∼ y i {\displaystyle f(x_{i}^{1},x_{i}^{2})\sim y_{i}} for every new labeled triplet example ( x i 1 , x i 2 , y i ) {\displaystyle (x_{i}^{1},x_{i}^{2},y_{i})} . This is typically achieved by minimizing a regularized loss min W ∑ i l o s s ( w ; x i 1 , x i 2 , y i ) + r e g ( w ) {\displaystyle \min _{W}\sum _{i}loss(w;x_{i}^{1},x_{i}^{2},y_{i})+reg(w)} . Classification similarity learning Given are pairs of similar objects ( x i , x i + ) {\displaystyle (x_{i},x_{i}^{+})} and non similar objects ( x i , x i − ) {\displaystyle (x_{i},x_{i}^{-})} . An equivalent formulation is that every pair ( x i 1 , x i 2 ) {\displaystyle (x_{i}^{1},x_{i}^{2})} is given together with a binary label y i ∈ { 0 , 1 } {\displaystyle y_{i}\in \{0,1\}} that determines if the two objects are similar or not. The goal is again to learn a classifier that can decide if a new pair of objects is similar or not. Ranking similarity learning Given are triplets of objects ( x i , x i + , x i − ) {\displaystyle (x_{i},x_{i}^{+},x_{i}^{-})} whose relative similarity obey a predefined order: x i {\displaystyle x_{i}} is known to be more similar to x i + {\displaystyle x_{i}^{+}} than to x i − {\displaystyle x_{i}^{-}} . The goal is to learn a function f {\displaystyle f} such that for any new triplet of objects ( x , x + , x − ) {\displaystyle (x,x^{+},x^{-})} , it obeys f ( x , x + ) > f ( x , x − ) {\displaystyle f(x,x^{+})>f(x,x^{-})} (contrastive learning). This setup assumes a weaker form of supervision than in regression, because instead of providing an exact measure of similarity, one only has to provide the relative order of similarity. For this reason, ranking-based similarity learning is easier to apply in real large-scale applications. Locality sensitive hashing (LSH) Hashes input items so that similar items map to the same "buckets" in memory with high probability (the number of buckets being much smaller than the universe of possible input items). It is often applied in nearest neighbor search on large-scale high-dimensional data, e.g., image databases, document collections, time-series databases, and genome databases. A common approach for learning similarity is to model the similarity function as a bilinear form. For example, in the case of ranking similarity learning, one aims to learn a matrix W that parametrizes the similarity function f W ( x , z ) = x T W z {\displaystyle f_{W}(x,z)=x^{T}Wz} . When data is abundant, a common approach is to learn a siamese network – a deep network model with parameter sharing. == Metric learning == Similarity learning is closely related to distance metric learning. Metric learning is the task of learning a distance function over objects. A metric or distance function has to obey four axioms: non-negativity, identity of indiscernibles, symmetry and subadditivity (or the triangle inequality). In practice, metric learning algorithms ignore the condition of identity of indiscernibles and learn a pseudo-metric. When the objects x i {\displaystyle x_{i}} are vectors in R d {\displaystyle R^{d}} , then any matrix W {\displaystyle W} in the symmetric positive semi-definite cone S + d {\displaystyle S_{+}^{d}} defines a distance pseudo-metric of the space of x through the form D W ( x 1 , x 2 ) 2 = ( x 1 − x 2 ) ⊤ W ( x 1 − x 2 ) {\displaystyle D_{W}(x_{1},x_{2})^{2}=(x_{1}-x_{2})^{\top }W(x_{1}-x_{2})} . When W {\displaystyle W} is a symmetric positive definite matrix, D W {\displaystyle D_{W}} is a metric. Moreover, as any symmetric positive semi-definite matrix W ∈ S + d {\displaystyle W\in S_{+}^{d}} can be decomposed as W = L ⊤ L {\displaystyle W=L^{\top }L} where L ∈ R e × d {\displaystyle L\in R^{e\times d}} and e ≥ r a n k ( W ) {\displaystyle e\geq rank(W)} , the distance function D W {\displaystyle D_{W}} can be rewritten equivalently D W ( x 1 , x 2 ) 2 = ( x 1 − x 2 ) ⊤ L ⊤ L ( x 1 − x 2 ) = ‖ L ( x 1 − x 2 ) ‖ 2 2 {\displaystyle D_{W}(x_{1},x_{2})^{2}=(x_{1}-x_{2})^{\top }L^{\top }L(x_{1}-x_{2})=\|L(x_{1}-x_{2})\|_{2}^{2}} . The distance D W ( x 1 , x 2 ) 2 = ‖ x 1 ′ − x 2 ′ ‖ 2 2 {\displaystyle D_{W}(x_{1},x_{2})^{2}=\|x_{1}'-x_{2}'\|_{2}^{2}} corresponds to the Euclidean distance between the transformed feature vectors x 1 ′ = L x 1 {\displaystyle x_{1}'=Lx_{1}} and x 2 ′ = L x 2 {\displaystyle x_{2}'=Lx_{2}} . Many formulations for metric learning have been proposed. Some well-known approaches for metric learning include learning from relative comparisons, which is based on the triplet loss, large margin nearest neighbor, and information theoretic metric learning (ITML). In statistics, the covariance matrix of the data is sometimes used to define a distance metric called Mahalanobis distance. == Applications == Similarity learning is used in information retrieval for learning to rank, in face verification or face identification, and in recommendation systems. Also, many machine learning approaches rely on some metric. This includes unsupervised learning such as clustering, which groups together close or similar objects. It also includes supervised approaches like K-nearest neighbor algorithm which rely on labels of nearby objects to decide on the label of a new object. Metric learning has been proposed as a preprocessing step for many of these approaches. == Scalability == Metric and similarity learning scale quadratically with the dimension of the input space, as can easily see when the learned metric has a bilinear form f W ( x , z ) = x T W z {\displaystyle f_{W}(x,z)=x^{T}Wz} . Scaling to higher dimensions can be achieved by enforcing a sparseness structure over the matrix model, as done with HDSL, and with COMET. == Software == metric-learn is a free software Python library which offers efficient implementations of several supervised and weakly-supervised similarity and metric learning algorithms. The API of metric-learn is compatible with scikit-learn. OpenMetricLearning is a Python framework to train and validate the models producing high-quality embeddings. == Further information == For further information on this topic, see the surveys on metric and similarity learning by Bellet et al. and Kulis.

John F. Sowa

John Florian Sowa (born 1940) is an American computer scientist, an expert in artificial intelligence and computer design, and the inventor of conceptual graphs. == Biography == Sowa received a BS in mathematics from Massachusetts Institute of Technology in 1962, an MA in applied mathematics from Harvard University in 1966, and a PhD in computer science from the Vrije Universiteit Brussel in 1999 with a dissertation titled "Knowledge Representation: Logical, Philosophical, and Computational Foundations". Sowa spent most of his professional career at IBM, starting in 1962 at IBM's applied mathematics group. Over the decades he has researched and developed emerging fields of computer science from compilers, programming languages, and system architecture to artificial intelligence and knowledge representation. In the 1990s Sowa was associated with the IBM Educational Center in New York. Over the years he taught courses at the IBM Systems Research Institute, Binghamton University, Stanford University, the Linguistic Society of America and the Université du Québec à Montréal. He is a fellow of the Association for the Advancement of Artificial Intelligence. After early retirement at IBM, Sowa in 2001 cofounded VivoMind Intelligence, Inc. with Arun K. Majumdar. With this company he was developing data-mining and database technology, more specifically high-level "ontologies" for artificial intelligence and automated natural language understanding. Currently Sowa is working with Kyndi Inc., also founded by Majumdar. John Sowa is married to the philologist Cora Angier Sowa, and they live in Croton-on-Hudson, New York. == Work == Sowa's research interests since the 1970s were in the field of artificial intelligence, expert systems and database query linked to natural languages. In his work he combines ideas from numerous disciplines and eras modern and ancient, for example, applying ideas from Aristotle, the medieval scholastics to Alfred North Whitehead and including database schema theory, and incorporating the model of analogy of Islamic scholar Ibn Taymiyyah in his works. === Conceptual graph === Sowa invented conceptual graphs, a graphic notation for logic and natural language, based on the structures in semantic networks and on the existential graphs of Charles S. Peirce. He introduced the concept in the 1976 article "Conceptual graphs for a data base interface" in the IBM Journal of Research and Development. He elaborated upon it in the 1983 book Conceptual structures: information processing in mind and machine. In the 1980s, this theory had "been adopted by a number of research and development groups throughout the world. International conferences on conceptual structures (ICCS) have been held since 1993, following a series of conceptual graph workshops that began in 1986. === Sowa's law of standards === In 1991, Sowa first stated his Law of Standards: "Whenever a major organization develops a new system as an official standard for X, the primary result is the widespread adoption of some simpler system as a de facto standard for X." Like Gall's law, The Law of Standards is essentially an argument in favour of underspecification. Examples include: The introduction of PL/I resulting in COBOL and FORTRAN becoming the de facto standards for business and scientific programming respectively The introduction of Algol-68 resulting in Pascal becoming the de facto standard for academic programming The introduction of the Ada language resulting in C becoming the de facto standard for US Department of Defense programming The introduction of OS/2 resulting in Windows becoming the de facto standard for desktop OS The introduction of X.400 resulting in SMTP becoming the de facto standard for electronic mail The introduction of X.500 resulting in LDAP becoming the de facto standard for directory services == Publications == 1984. Conceptual Structures - Information Processing in Mind and Machine. The Systems Programming Series, Addison-Wesley 1991. Principles of Semantic Networks. Morgan Kaufmann. Mineau, Guy W; Moulin, Bernard; Sowa, John F, eds. (1993). Conceptual Graphs for Knowledge Representation. LNCS. Vol. 699. doi:10.1007/3-540-56979-0. ISBN 978-3-540-56979-4. S2CID 32275791. 1994. International Conference on Conceptual Structures (2nd : 1994 : College Park, Md.) Conceptual structures, current practices : Second International Conference on Conceptual Structures, ICCS'94, College Park, Maryland, USA, August 16–20, 1994 : proceedings. William M. Tepfenhart, Judith P. Dick, John F. Sowa, eds. Ellis, Gerard; Levinson, Robert; Rich, William; Sowa, John F, eds. (1995). Conceptual Structures: Applications, Implementation and Theory. LNCS. Vol. 954. doi:10.1007/3-540-60161-9. ISBN 978-3-540-60161-6. S2CID 27300281. Lukose, Dickson; Delugach, Harry; Keeler, Mary; Searle, Leroy; Sowa, John, eds. (1997). Conceptual Structures: Fulfilling Peirce's Dream. LNCS. Vol. 1257. doi:10.1007/BFb0027865. ISBN 3-540-63308-1. S2CID 1934069. 2000. Knowledge representation : logical, philosophical, and computational foundations, Brooks Cole Publishing Co., Pacific Grove Articles, a selection Sowa, J. F. (July 1976). "Conceptual Graphs for a Data Base Interface". IBM Journal of Research and Development. 20 (4): 336–357. doi:10.1147/rd.204.0336. Sowa, J. F.; Zachman, J. A. (1992). "Extending and formalizing the framework for information systems architecture". IBM Systems Journal. 31 (3): 590–616. doi:10.1147/sj.313.0590. 1992. "Conceptual Graph Summary"; In: T.E. Nagle et al. (Eds.). Conceptual Structures: Current Research and Practice. Chichester: Ellis Horwood. 1995. "Top-level ontological categories." in: International journal of human-computer studies. Vol. 43, Iss. 5–6, Nov. 1995, pp. 669–685 2006. "Semantic Networks". In: Encyclopedia of Cognitive Science.. John Wiley & Sons.

Feigenbaum test

A Feigenbaum test is a variation of the Turing test where a computer system attempts to replicate an expert in a given field such as chemistry or marketing. It is also known, as a subject matter expert Turing test and was proposed by Edward Feigenbaum in a 2003 paper. The concept is also described by Ray Kurzweil in his 2005 book The Singularity is Near. Kurzweil argues that machines who pass this test are an inevitable consequence of Moore's Law.

Turing's Wager

Turing's Wager is a philosophical argument that claims it is impossible to infer or deduce a detailed mathematical model of the human brain within a reasonable timescale, and thus impossible in any practical sense. The argument was first given in 1950 by the computational theorist Alan Turing in his paper Computing Machinery and Intelligence, published in Mind (Turing 1950, p. 453). The argument asserts that determining any mathematical model of a computer (its source code or any isomorphic equivalent such as a Turing machine or virtual simulation) is not possible in a reasonable timeframe. As a consequence, determining a mathematical model of the human brain (which is, by its nature, more complicated) must also be impossible within that timeframe. == Effect of modern technology on the wager == It has been argued that modern neuroimaging techniques will allow researchers to create accurate simulations of the human mind within the 21st century (Kurzweil 2012; Markram 2012, Fildes 2009), thereby overcoming the wager. Others have argued that such claims are unjustified (Thwaites et al. 2017). == Relationship between Turing's Wager and the Turing Test == The Turing Test attempts to define when a machine might be said to possess human intelligence, while Turing's Wager is an argument aiming to demonstrate that characterising the brain mathematically will take over a thousand years. While building an artificial intelligence and mapping the human brain are both difficult endeavours, the former is actually a sub-problem of the latter (Thwaites et al. 2017).

Automated Mathematician

The Automated Mathematician (AM) is one of the earliest successful discovery systems. It was created by Douglas Lenat in Lisp, and in 1977 led to Lenat being awarded the IJCAI Computers and Thought Award. AM worked by generating and modifying short Lisp programs which were then interpreted as defining various mathematical concepts; for example, a program that tested equality between the length of two lists was considered to represent the concept of numerical equality, while a program that produced a list whose length was the product of the lengths of two other lists was interpreted as representing the concept of multiplication. The system had elaborate heuristics for choosing which programs to extend and modify, based on the experiences of working mathematicians in solving mathematical problems. == Controversy == Lenat claimed that the system was composed of hundreds of data structures called "concepts", together with hundreds of "heuristic rules" and a simple flow of control: "AM repeatedly selects the top task from the agenda and tries to carry it out. This is the whole control structure!" Yet the heuristic rules were not always represented as separate data structures; some had to be intertwined with the control flow logic. Some rules had preconditions that depended on the history, or otherwise could not be represented in the framework of the explicit rules. What's more, the published versions of the rules often involve vague terms that are not defined further, such as "If two expressions are structurally similar, ..." (Rule 218) or "... replace the value obtained by some other (very similar) value..." (Rule 129). Another source of information is the user, via Rule 2: "If the user has recently referred to X, then boost the priority of any tasks involving X." Thus, it appears quite possible that much of the real discovery work is buried in unexplained procedures. Lenat claimed that the system had rediscovered both Goldbach's conjecture and the fundamental theorem of arithmetic. Later critics accused Lenat of over-interpreting the output of AM. In his paper Why AM and Eurisko appear to work, Lenat conceded that any system that generated enough short Lisp programs would generate ones that could be interpreted by an external observer as representing equally sophisticated mathematical concepts. However, he argued that this property was in itself interesting—and that a promising direction for further research would be to look for other languages in which short random strings were likely to be useful. == Successor == This intuition was the basis of AM's successor Eurisko, which attempted to generalize the search for mathematical concepts to the search for useful heuristics.

Information Coding Classification

The Information Coding Classification (ICC) is a classification system covering almost all extant 6500 knowledge fields (knowledge domains). Its conceptualization goes beyond the scope of the well known library classification systems, such as Dewey Decimal Classification (DDC), Universal Decimal Classification (UDC), and Library of Congress Classification (LCC), by extending also to knowledge systems that so far have not afforded to classify literature. ICC actually presents a flexible universal ordering system for both literature and other kinds of information, set out as knowledge fields. From a methodological point of view, ICC differs from the above-mentioned systems along the following three lines: Its main classes are not based on disciplines but on nine live stages of development, so-called ontical levels. It breaks them roughly down into hierarchical steps by further nine categories which makes decimal number coding possible. The contents of a knowledge field is earmarked via a digital position scheme, which makes the first hierarchical step refer to the nine ontical levels (object areas as subject categories), and the second hierarchical step refer to nine functionally ordered form categories. Respective knowledge fields permit to step down by the same principle to a third and forth level, and even further to a fifth and sixth level. Finally, knowledge field subdivisions will have to conform to said digital position scheme. Hence, for a given knowledge field identical codes will mark identical categories under respective numbers of the coding system. This mnemotechnical aspect of the system helps memorizing and straightaway retrieving the whereabouts of respective interdisciplinary and transdisciplinary fields. The first two hierarchical levels may be regarded as a top- or upper ontology for ontologies and other applications. The terms of the first three hierarchical levels were set out in German and English in Wissensorganisation. Entwicklung, Aufgabe, Anwendung, Zukunft, on pp. 82 to 100. It was published in 2014 and available so far only in German. In the meantime, also the French terms of the knowledge fields have been collected. Competence for maintenance and further development rests with the German Chapter of the International Society for Knowledge Organization (ISKO) e.V. == Historical development == At the end of 1970, Prof. Alwin Diemer, Univ.of Düsseldorf proposed to Ingetraut Dahlberg to undertake a philosophical dissertation on The universal classification system of knowledge, its ontological, epistemological, and information theoretical foundations. Diemer had in mind an innovating ontological approach for such a system based on the whole spectrum of kinds of being and complying with epistemological requirements. The third requirement had already been taken up somehow in the Indian Colon Classification, yet it still called for explanations and additions. In 1974, the dissertation was published in German entitled Grundlagen universaler Wissensordnung. It started with conceptual clarifications, and why and how the term „universal“ was linked to knowledge, including knowledge fields, such as commodity science, artefacts, statistics, patents, standardization, communication, utility services et al. In chapter 3, six universal classification systems (DDC, UDC, LCC, BC, CC and BBK) were presented, analyzed and compared. While preparing the dissertation, Dahlberg started with elaborating the new universal system by first gleaning a lot of extant designations of knowledge fields from whatever available reference works. This was funded by the German Documentation Society (DGD) (1971-2) under the title of Order system of knowledge fields. In addition, the syllabuses of German universities and polytechniques were explored for relevant terms and documented (1975). Thereafter, it seemed necessary to add definitions from special dictionaries and encyclopediae; it soon appeared that the 12.500 terms included numerous synonyms, so that the whole collection boiled down to about 6.500 concept designations (Project Logstruktur, supported by the German Science Foundation (DFG) 1976-78). The outcome of this work was the formulation of 30 theses which ended up in 12 principles for the new system, published 40 years later under. These principles refer not only to theoretical foundations but also to structure and other organizational aspects of the whole array of knowledge fields. In 1974, the digital position scheme for field subdivision had already been developed to allow for classifying classification literature in the bibliographical section of the first issue of the Journal International Classification. In 1977, the entire ICC was ready for presentation at a seminar in Bangalore, India. A publication of the first three hierarchical levels appeared however only in 1982. It was applied to the bibliography of classification systems and thesauri in vol.1 of the International Classification and Indexing Bibliography; it has been updated. == Governing principles == These were published in full length in the book Wissensorganisation. Entwicklung, Aufgabe, Anwendung, Zukunft and the article Information Coding Classification. Geschichtliches, Prinzipien, Inhaltliches, hence it suffices to just mention their topics with some necessary additions. Principle 1: Concept theoretical approaches. Concepts are the contents of ICC, they are understood as being units of knowledge. The „birth“ of a concept. Where do the characteristics, the knowledge elements come from? How do conceptual relations arise? Principle 2: The four kinds of concept relations and their applications. Principle 3: Decimal numbers form the ICC codes as its universal language. Principle 4: The nine ontical levels of ICC. They were grouped under three captions: Prolegomena (1-3), life sciences (4-6) and human output (7-9): Structure and form Matter and energy Cosmos and earth Biosphere Anthroposphere Sociosphere Material products (economics and technology) Intellectual products (knowledge and information) Spiritual products (products of mind and culture) Principle 5: Knowledge fields are structured by categories, based on the Aristotelian form-categories, under a digital position scheme, a kind of scaling rule for subdividing a given field as follows: General area: problems, theories, principles (axiom and structure) Object area: objects, kinds, parts, properties of objects Activity area: methods, processes, activities Field properties or first characterization Persons or secondary characterization Societies or tertiary characterization Influences from outside Applications of the field to other fields Field information and synthesizing tasks The digital position scheme, called Systematifier, has also been used for structuring the entire system via the categories figuring on the upper zero level. An example of its application is the structure of the classification system for knowledge organization literature Gliederung der Klassifikationsliteratur. (A simplified version with an additional introduction is given in, p. 71) Principle 6: The ontical levels outlined under principle 4 conform to the „integrative level theory“ which means that every level is integrated in the following one. In addition, each knowledge area presumes the following one. Principle 7: The combination potential of knowledge fields (interdisciplinarity and transdisciplinarity)is determined by the digital position scheme. (Examples are given in, p. 103-4) Principle 8: The categories of the zero-level are general concepts, their possible subdivisions could once be used for classificatory statements. (These subdivisions still need elaboration) Principle 9 and 10: These relate to the combination potential of classificatory statements with space and time concepts. (Still to be elaborated) Principle 11: The system's mnemotechnical aspect relies on the fixed system position codes and on the 3x3 form- and subject-categories. Principle 12: The combination potential of system position 1, 8 and 9 make ICC to a self-networking system which complies with the present scientific development. == In matrix form == The first two levels of ICC can be represented by following matrix. The first hierarchical level of the 9 subject categories results from the first vertical array under codes 1-9. The second hierarchical level of subject categories is structured by the 9 functionally ordered form categories, listed in the first horizontal line under codes 01-09. Some exceptions are mentioned in principle 7. == Research == === Exploration of automatic classification === For classifying web documents as conceived by Jens Hartmann, University of Karlsruhe, Prof.Walter Koch, University of Graz, has explored in his Institute for Applied Information Technology Research Society (AIT) the application of ICC to automatically classifying metadata of some 350.000 documents. This was facilitated by data generated within the framework of an E