|
Teaching Dimension
In computational learning theory, the teaching dimension of a concept class ''C'' is defined to be \max_\, where is the minimum size of a witness set for ''c'' in ''C''. Intuitively, this measures the number of instances that are needed to identify a concept in the class, using supervised learning with examples provided by a helpful teacher who is trying to convey the concept as succinctly as possible. This definition was formulated in 1995 by Sally Goldman and Michael Kearns, based on earlier work by Goldman, Ron Rivest, and Robert Schapire Robert Elias Schapire is an American computer scientist, former David M. Siegel '83 Professor in the computer science department at Princeton University, and has recently moved to Microsoft Research. His primary specialty is theoretical and app .... The teaching dimension of a finite concept class can be used to give a lower and an upper bound on the membership query cost of the concept class. In Stasys Jukna's book "Extremal Combinato ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Computational Learning Theory
In computer science, computational learning theory (or just learning theory) is a subfield of artificial intelligence devoted to studying the design and analysis of machine learning algorithms. Overview Theoretical results in machine learning mainly deal with a type of inductive learning called supervised learning. In supervised learning, an algorithm is given samples that are labeled in some useful way. For example, the samples might be descriptions of mushrooms, and the labels could be whether or not the mushrooms are edible. The algorithm takes these previously labeled samples and uses them to induce a classifier. This classifier is a function that assigns labels to samples, including samples that have not been seen previously by the algorithm. The goal of the supervised learning algorithm is to optimize some measure of performance such as minimizing the number of mistakes made on new samples. In addition to performance bounds, computational learning theory studies the t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Concept Class
In computational learning theory in mathematics, a concept over a domain ''X'' is a total Boolean function over ''X''. A concept class is a class of concepts. Concept classes are a subject of computational learning theory. Concept class terminology frequently appears in model theory associated with probably approximately correct (PAC) learning. In this setting, if one takes a set ''Y'' as a set of (classifier output) labels, and ''X'' is a set of examples, the map , i.e. from examples to classifier labels (where and where ''c'' is a subset of ''X''), ''c'' is then said to be a ''concept''. A ''concept class'' is then a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Witness Set
In computational learning theory, let ''C'' be a concept class In computational learning theory in mathematics, a concept over a domain ''X'' is a total Boolean function over ''X''. A concept class is a class of concepts. Concept classes are a subject of computational learning theory. Concept class terminolog ... over a domain ''X'' and ''c'' be a concept in ''C''. A subset ''S'' of ''X'' is a witness set for ''c'' in ''C'' if ''c''(''S'') verifies ''c'' (i.e., ''c'' is the only consistent concept with respect to ''c''(''S'')). The minimum size of a witness set for ''c'' is called the ''witness size'' or ''specification number'' and is denoted by w_C(c). The value \max\ is called the teaching dimension of ''C''. Computational learning theory {{Compu-AI-stub ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Supervised Learning
Supervised learning (SL) is a machine learning paradigm for problems where the available data consists of labelled examples, meaning that each data point contains features (covariates) and an associated label. The goal of supervised learning algorithms is learning a function that maps feature vectors (inputs) to labels (output), based on example input-output pairs. It infers a function from ' consisting of a set of ''training examples''. In supervised learning, each example is a ''pair'' consisting of an input object (typically a vector) and a desired output value (also called the ''supervisory signal''). A supervised learning algorithm analyzes the training data and produces an inferred function, which can be used for mapping new examples. An optimal scenario will allow for the algorithm to correctly determine the class labels for unseen instances. This requires the learning algorithm to generalize from the training data to unseen situations in a "reasonable" way (see inductive b ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Sally Goldman
Sally Ann Goldman is an American computer scientist specializing in computational learning theory. She was a professor in the Department of Computer Science and Engineering at Washington University in St. Louis, and Edwin H. Murty Professor of Engineering, before leaving academia to join Google Research. She is also a successful amateur powerlifter. Education and career Goldman is originally from St. Louis, Missouri. She majored in computer science at Brown University, and then went to the Massachusetts Institute of Technology (MIT) for graduate study in computer science. She completed her Ph.D. there in 1990, with the dissertation ''Learning Binary Relations, Total Orders, and Read-Once Formulas'' supervised by Ron Rivest. As a faculty member at Washington University in St. Louis, she became Edwin H. Murty Professor of Engineering before leaving academia in 2008 to work for Google Research. Personal life Goldman was married to Kenneth J. Goldman, also a computer scientist from ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Michael Kearns (computer Scientist)
Michael Kearns is an American computer scientist, professor and National Center Chair at the University of Pennsylvania, the founding director of Penn's Singh Program in Networked & Social Systems Engineering (NETS), the founding director of Warren Center for Network and Data Sciences, and also holds secondary appointments in Penn's Wharton School and department of Economics. He is a leading researcher in computational learning theory and algorithmic game theory, and interested in machine learning, artificial intelligence, computational finance, algorithmic trading, computational social science and social networks. He previously led the Advisory and Research function in Morgan Stanley's Artificial Intelligence Center of Excellence team, and is currently an Amazon Scholar within Amazon Web Services. Biography Kearns was born into an academic family, where his father David R Kearns is Professor Emeritus at University of California, San Diego in chemistry, who won Guggenheim Fellow ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Journal Of Computer And System Sciences
The ''Journal of Computer and System Sciences'' (JCSS) is a peer-reviewed scientific journal in the field of computer science. ''JCSS'' is published by Elsevier, and it was started in 1967. Many influential scientific articles have been published in ''JCSS''; these include five papers that have won the Gödel Prize. an 2014 Gödel Prize Its managing editor is |
Ron Rivest
Ronald Linn Rivest (; born May 6, 1947) is a cryptographer and an Institute Professor at MIT. He is a member of MIT's Department of Electrical Engineering and Computer Science (EECS) and a member of MIT's Computer Science and Artificial Intelligence Laboratory (CSAIL). His work has spanned the fields of algorithms and combinatorics, cryptography, machine learning, and election integrity. Rivest is one of the inventors of the RSA algorithm (along with Adi Shamir and Len Adleman). He is the inventor of the symmetric key encryption algorithms RC2, RC4, RC5, and co-inventor of RC6. The "RC" stands for "Rivest Cipher", or alternatively, "Ron's Code". (RC3 was broken at RSA Security during development; similarly, RC1 was never published.) He also authored the MD2, MD4, MD5 and MD6 cryptographic hash functions. Education Rivest earned a Bachelor's degree in Mathematics from Yale University in 1969, and a Ph.D. degree in Computer Science from Stanford University in 1974 for rese ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Robert Schapire
Robert Elias Schapire is an American computer scientist, former David M. Siegel '83 Professor in the computer science department at Princeton University, and has recently moved to Microsoft Research. His primary specialty is theoretical and applied machine learning. His work led to the development of the boosting ensemble algorithm used in machine learning. His PhD dissertation, ''The design and analysis of efficient learning algorithms'', won him the ACM Doctoral Dissertation Award in 1991. Together with Yoav Freund, he invented the AdaBoost algorithm in 1996. They both received the Gödel prize in 2003 for this work. In 2014, Schapire was elected a member of the National Academy of Engineering for his contributions to machine learning through the invention and development of boosting algorithms. In 2016, he was elected to the National Academy of Sciences.. Personal life His son, Zachary Schapire, recently graduated from his alma mater, Brown University. His daughter, Jeni S ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
SIAM Journal On Computing
The ''SIAM Journal on Computing'' is a scientific journal focusing on the mathematical and formal aspects of computer science. It is published by the Society for Industrial and Applied Mathematics (SIAM). Although its official ISO abbreviation is ''SIAM J. Comput.'', its publisher and contributors frequently use the shorter abbreviation ''SICOMP''. SICOMP typically hosts the special issues of the IEEE Annual Symposium on Foundations of Computer Science (FOCS) and the Annual ACM Symposium on Theory of Computing (STOC), where about 15% of papers published in FOCS and STOC each year are invited to these special issues. For example, Volume 48 contains 11 out of 85 papers published in FOCS 2016. References * External linksSIAM Journal on Computing on |
Membership Query Cost
Member may refer to: * Military jury, referred to as "Members" in military jargon * Element (mathematics), an object that belongs to a mathematical set * In object-oriented programming, a member of a class ** Field (computer science), entries in a database ** Member variable, a variable that is associated with a specific object * Limb (anatomy), an appendage of the human or animal body ** Euphemism for penis * Structural component of a truss, connected by nodes * User (computing), a person making use of a computing service, especially on the Internet * Member (geology), a component of a geological formation * Member of parliament * The Members, a British punk rock band * Meronymy, a semantic relationship in linguistics * Church membership, belonging to a local Christian congregation, a Christian denomination and the universal Church * Member, a participant in a club or learned society A learned society (; also learned academy, scholarly society, or academic association) is an ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Stasys Jukna
Stasys is a popular Lithuanian given name, derived from Slavic name Stanislav. Feminine variation is Stasė. *Stasys Antanas Bačkis (1906–1999), Lithuanian diplomat *Stasys Eidrigevičius (born 1949), graphic artist *Stasys Girėnas (1893–1933), Lithuanian-American pilot *Stasys Lozoraitis (1898–1983), Lithuanian diplomat *Stasys Lozoraitis Jr. (1924–1994), Lithuanian diplomat *Stasys Povilaitis (1947–2015), Lithuanian singer *Stasys Raštikis (1896–1985), Lithuanian general *Stasys Razma (1899–1941), Lithuanian footballer *Stasys Šilingas (1885–1962), Lithuanian lawyer and statesman *Stasys Šimkus (1887–1943), Lithuanian composer *Stasys Stonkus Stanislovas "Stasys" Stonkus (29 December 1931 – 19 February 2012) was a Soviet and Lithuanian basketball player who competed for the Soviet Union in the 1952 Summer Olympics and in the 1956 Summer Olympics. He was born in Telšiai. In 195 ... (born 1931), Lithuanian basketball player {{given name Lithuania ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
