Summary Intelligent Information Agents (c) 2004-09-23 Fabian M. Suchanek http://www.mpi-inf.mpg.de/~suchanek/personal/texts/summaries/iia.txt This is a summary of the course "Intelligent Information Agents for the Internet and the Web" held by Dr. Matthias Klusch in the summer semester 2004 at Saarland University. The summary follows the detailed slides of the lecturer. All more elaborate code samples stem from these slides. The online dictionary Wikipedia (http://www.wikipedia.org) has been used to enrich some of the definitions. By reading the following text, you accept that the author does not accept any responsibility for the correctness or completeness of this text. If you have any corrections or remarks, please send me a mail. This is the only way to make the publication of this summary useful for me, too. My e-mail address is f.m.suchanek@zweb.de, but the letter 'z' has to be removed from the address. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Prerequisites ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ // This section was not part of the lecture. It just establishes the // background and can be skipped savely. ------------------------------- Maths ------------------------------ Set: An unordered collection of different elements. S = {s1,...sn} S = { x | p(x) } is the set of all those x for which p(x) holds Size, cardinality of a set: The number of its elements. Notation: |{s1,s2,...sn}| = n Singleton set: A set of size 1. Epsilon of a set S: An element of S. Notation: eps(S) eps({x}) := x // This operator has been invented by Hilbert. Since there is no // other way to designate an x with special properties in a // mathematical syntax, this summary makes use of it. Example: eps({x | x in S, For all y in S: x>=y}) defines the maximum of a set S Intersection of two sets: The set of those elements which occur in both of them. Notation: X /\ Y Union of two sets: The set of all of their elements. Notation: X \/ Y Difference of two sets: The set of those elements which occur in the first one, but not in the second one. Notation: X \ Y Disjoint sets: Sets with an empty intersection. Partition of a set S: A set of disjoint sets, the union of which is S. List, Sequence, Tuple: An ordered collection of elements. Notation: t=(t[1],t[2],...t[n]) Example: t=(1,'A',abc) is a tupel Dimension of a tuple: The number of its elements. Pair: A tuple of dimension 2. Triple: A tuple of dimension 3. Quadruple: A tuple of dimension 4. Boolean value, Bit: An element of the set {0,1}. Byte: A sequence of 8 bits. Subset of a set S: A set, the elements of which are all contained in S. Notation: S' =< S Superset of a set S: A set, which contains all elements of S. Notation: S' >= S Cartesian Product of the sets A[1],A[2],...A[n]: The set of all possible tuples, the first element of which is in A[1], the second element of which is in A[2] etc. Notation: A x B x C = D Example: {1,2} x {a,b,c} = { (1,a), (2,a), (1,b), (2,b), (1,c), (2,c)} Relation on the sets A[1],...A[n]: A subset of the cartesian product of A[1],...A[n]. Notations for (a,b) is an element of the relation r: * r(a,b) * a r b * (a,b) is in r Example: The relation ">" is the set of all pairs of real numbers, in which the first number is greater than the second. It holds: ">" = { (1,0), (27.3,12.5), (17,-12), ... } One writes: >(3,2) or 3 > 2 or (3,2) is in ">". n-ary relation: A relation on n sets. n-th position of a relation: The set of all n-th components of the tuples in the relation. Binary relation on A and B, relation between A and B, relation from A to B: A relation on the sets A and B. Range of a binary relation on A and B: A. Domain of a binary relation on A and B: B. Relation on a set M: A relation on M and M. Left cardinality of a binary relation R: The number of different x, such that R(x,y) for a fixed y. Right cardinality of a binary relation R: The number of different x, such that R(y,x) for a fixed y. Function: A binary relation with a maximum right cardinality of 1. Ie a relation f on two sets X and Y, such that for every x in X there is either none or exactly one element y in Y with x f y. Notation for f: f:X->Y Notation for "x f y": f(x)=y. Note that X may also be a cartesian product, i.e. more than one value can be given to the function. Notation for "f(x,y)": x f y Notation for "f(x,y)": f[x](y) All notions in this summary, which are defined in dependence on another entity, can be seen as functions. Input, Argument of a function f: A value x, for which b with f(x)=b is to be determined. Output, Result of a function f:X->Y for an argument x: The element y of Y such that f(x)=Y. Operation on a set M: A function f: M x M -> M. Real: The set of real numbers. For a detailed definition and associated operations, cf "Analysis" (analysis.txt, German) Natural: The set of natural numbers. For a detailed definition and associated operations, cf "Analysis" (analysis.txt, German) Factorial: The function factorial, which takes a natural number n and returns factorial(n) = 1 if n=0 factorial(n) = factorial(n-1)*n else Notation: n! for factorial(n) Changeable function: A function, which has an additional hidden real argument. As a result, the function can be "modified" in the following sense: Notations: f(a,b,c,...) for f(a,b,c,...,t) with t being the greatest value smaller than the current time, for which there exists a y with f(a,b,c,...,t)=y f(a,b,c,...) := x for f(a,b,c,..., currentTime) := x // These acrobatics are necessary to introduce the notion of "change" // into the static world of mathematics... Changeable tuple: A tuple with an additional hidden component, such that it can be "modified" similarly to a changeable function. Vector: A tuple of real numbers. A vector can be seen as an "arrow", which points from the origin to the point identified by the vector components in a cartesian coordinate system. A 1-dimensional vector is a real number. // For a broader definition, see "Algebra" (algebra.txt, in // German) Vector space: A set of vectors of the same dimension. // For a broader definition, see "Algebra" (algebra.txt, in // German) Sparse vector: A vector, many values of which are unknown. Vector addition: The function '+', which takes two input vectors of the same dimension and returns a new vector, which has in each component the sum of the corresponding components of the input vectors. (x[0],...x[n]) + (y[0],...y[n]) := (x[0]+y[0],...x[n]+y[n]) In the view of vectors as arrows, the new arrow is the concatenation of the input arrows. Length of a vector: The square root of the dot product with itself. |(x[0],...x[n])| := sqrt(SUM {x[i]*x[i] | i=1...n}) In the arrow view, this corresponds to the actual length (eg. in cm) of the arrow line. Dot product: The function '*', which takes two input vectors of the same dimension and returns the sum of the products of the corresponding components of the input vectors: (x[0],...x[n]) * (y[0],...y[n]) := SUM {x[i]*y[i] | i=1..n} In the arrow view, the dot product measures the similarity of the vectors: If they point into the same direction, the dot product has a large positive value. If the arrows point into orthogonal directions, the dot product is 0 and if the arrows point into inverse directions, the dot product has a large negative value. But the value still depends on the lerngth of the arrows. Mean of a vector: The sum of its components, divided by its dimension. Notation: mean(x[0],...x[n]) := SUM {x[i] | i=1...n} / n Variance of a vector x: The value var(x) := SUM { (x[i]-mean(x))^2) | i=1..n } / n, Reduced vector of a vector x: The vector reduce(x) := sqrt(var(x))*(x-mean(x)). The normalized vector has a variance and a length of 1 and a mean of 0. Vector Cosine, Vector similarity: The function sim, which takes two vectors of the same dimension and returns their dot product, divided by the product of their lengths. sim(x,y) := cos(x,y) := x*y / |x| / |y| Much like the dot product, the vector cosine measures similarity, but the value does no longer depend on the lengths of the vectors. In the arrow view, vectors of the same direction have a similarity of 1, orthogonal vectors have a similarity of 0 and vectors of opposite directions have a similarity of -1. For reduced vectors, the similarity is equal to the dot product: sim(x,y) = x*y Vector scaling: The function '*', which takes a real number and a vector and multiplies each of the vector components by the number. r * (x[0],...x[n]) := (r*x[0],...r*x[n]) In the arrow view, scaling prolonges or shortens the vector, while keeping its direction. Matrix of size m*n: A tuple vectors of the same dimension. Notation: X=(x[1,1],... x[1,n], x[2,1],... x[2,n], ... x[m,1],... x[m,n]) Each vector of dimension m can be seen as a matrix of size m*1. // For a broader definition, see "Algebra" (algebra.txt, in // German). For lots of funny things with matrices, see // "Advanced Statistics" (maths.txt, in French) Transposition: The function t, which takes a matrix A of size m*n and returns a matrix B of size n*m with b[i,j]=a[j,i] Matrix multiplication: The function '*', which takes two matrices A and B of size m*n and n*m respectively and returns the matrix C with c[i][j] = SUM { a[i][k]*b[k][j] | i=1..m, j=..m, k=1..n} Eigenvector of a matrix M: A vector v, such that there is a non-zero real number r with M*v = r*v Graph: A pair of a set of "nodes" and a "link" relation on the nodes. A graph can be seen as a number of dots (the nodes) with arrows connecting them (the links). // See "Graphs and Complexity" (gc.txt, in French) for a detailed // introduction to graphs. Subgraph of a graph (N,L): A graph (N', L /\ (N' x N')), where N'={x | 0=0. As a result, elements of M can be "partially" elements of the fuzzy set. // For a detailed introduction to fuzzy sets, see "Softcomputing" // (sc.txt, in German) // The following notions introduce the basics of statistics. // For a detailed introduction, see "Statistics" (statistik.txt, // in German) and for more information, see "Advanced Statistics" // (maths.txt, in French). Deterministic: Known in advance. Basic event: A state of the world, which is said to "happen" or not. Examples: It rains and there is a party. It does not rain and there is a party. Ground set: The set of all basic events, exactly one of which happens. Notation: Omega Example: {It rains and there is a party, It does not rain and there is a party, It does not rain and there is no party, It rains and there is no party (worst case)} Random event: A subset of the ground set. A random event groups those states of the world, which have something in common Example: rain = {It rains and there is a party, It rains and there is no party} If one of the contained basic events happens, the random event is said to happen. It is impossible that the empty random event {} happens, and it is sure that the total event Omega happens. Sigma-Algebra on a ground set Omega: The set A of random events, such that * if a random event R is in A, then (Omega\R) is also in A * if the random events R1, R2, ... are in A, then their union is also in A This entails in particular: * R1,R2 in A => (R1\/R2) in A * R1,R2 in A => (R1/\R2) in A * R in A => (Omega\R) in A * {} in A * Omega in A The sigma algebra is the set of "possible" random events. Probability function on a sigma-algebra A on Omega: A function P:A->Real, such that * P(R)>=0 for all R in A * P(Omega)=1 * P(R1 \/ R2 \/ ...) = P(R1)+P(R2)+... (for distinct Ri) This entails in particular: * 0 <= P(R) <= 1 * P({}) = 0 * P(Omega) = 1 * P(Omega\R) = 1-P(R) * P(R1 \/ R2) = P(R1) + P(R2) - P(R1/\R2) The probability function returns the likelihood of a random event. Each basic event is a (trivial) random event and has a fixed probability. The probability of a complex random event is calculated by the sum of its basic events. // Note that this is an axiomatic definition. It defines how // P should work, but it does not define which events should // be probable or less probable. Probability of a random event A under the condition B: The probability of A, provided that the random event B happens. Notation: P(A|B) := P(A /\ B) / P(B) Bayes Theorem: The fact that P(A|B) = P(B|A) * P(A) / P(B) This means in particular that we can calculate P(A|B) if we know P(B|A). Random variable: A function, which takes a basic event and returns a real value. The random variable represents one characteristic of a basic event. Example: rain(It rains and there is a party)=1 rain(It does not rain and there is a party)=0 Probability of a random variable X taking the value y: The probability of the set of those basic events, for which X returns y. Notation: P(X=y) := P({w | w in Omega, X(w)=y}) --------------------------- Computer Science ----------------------- // The following definitions are needed just to set up the well-known // environment of computer science. Furthermore, it defines some // intentional notions like "goal" and "decision" for programs, in // order to simplify talking about agents. // Defining these notions is quite clumsy, especially since notions // related to human thinking and wishing cannot be defined at all, // see "Philosophy of Mind" (pom.txt, in German) Datum: A symbol. Unicode: A certain sequence of symbols, which include among others all letters, all spacing characters and all digits. Data: A sequence of symbols, mostly a sequence of bytes. Text: Human-readable data. Character: An element of the Unicode. String: A sequence of characters. Substring of a string: A sequence of characters, which occurs in the string. Name: A string referring to an entity. State: A changeable function from names to data. // In a computer, this is just the memory. Accessing a state: Applying the state to a name (i.e. retrieving data) or changing the state. Computer: A physical device which has a state and which can carry out instructions. // For a theoretical model of a computer, see "Theoretical // Computer Science" (infod.txt, in German). Screen of a computer: A physical part of the computer, which can display text and graphics. The state of the computer includes the screen. Algorithm: A sequence of instructions. Program: An algorithm, which can be carried out by a computer. // For a theoretical model of a program, see "Computational // Logic" (clog.txt, in German). Programming language: A set of rules how to write a program. // For a sample programming language see "FAST - A new // programming language" (fast.htm) Computer system: A set of programs. (?) Operating system: A computer system providing the basic functionality of a computer. Sun: A certain enterprise developing software systems. OMG, Object Management group: A certain enterprise developing software systems. Microsoft: A certain enterprise developing software systems. IBM: A certain enterprise developing software systems and computers. Java: A certain programming language developed by Sun. Java-Script: A certain programming language. C: A certain programming language. Perl: A certain programming language. Goal of a program: The state of a computer desired by the writers of the program, in dependence on the initial state. Subgoal of a program: A state which needs to be reached in order to reach the goal state. The goal state is also a subgoal. One uses human notions to describe the goals of a program: If the subgoal of a program is a state X, one says that "the program wants X". Example: "A factorial program wants the user to enter a number because it wants to calculate its factorial" Similarly, the notions of "desire", "intention" and "obligation" are sometimes applied (in a rather undefined way) to programs. Problem: A state which is not a goal state. Problem solving: Changing the current state to a goal state. Decision of a program: A jump to a certain instruction in dependence on the state of a computer. Example: "Since the input number was negative, the factorial program decided to display an error message" Internal state of a program: The subset of the state of a computer, which can be accessed solely by the program. Environment of a program: The subset of the state of a computer, which is accessed by the program, but not solely. Event for a program: A change of the environment, which is not caused by the program. Action of a program: A change of the state of a computer caused by the program. Knowledge of a program: The subset of the internal state of the program, which represents another (e.g. environmental) subset of the state. Meta-knowledge of a program: The subset of the internal state, which represents a subset of the internal state. Rationality of a program: Its property that it does not perform actions which are not necessary for its goal. Emotions of a program: The part of it which is intended to simulate human emotional behavior. Reasoning of a program: The process of executing instructions, which determine future actions. User of a program: The human, which causes a computer to execute the program because she/he is interested in the goal state of the program. Machine learning: The process of a program gathering information for better achieving its goal. // See "Neural Networks" (nn.txt, in German), "Artificial // Intelligence" (ai.txt or ia.txt, the latter in French) or // "Softcomputing" (sc.txt, in German) for further information. Machine learning system: A program calculating a changeable function, which can return outputs for previously unknown inputs. Machine learning is used to make a program improve with experience. Training machine learning system to a pair (i,o): Changing its function in such a way, that the system will calculate an output similar to o, if given an input similar to i. Neural network: A machine learning system, which is supposed to work similar to the human brain. The network is a set N of so-called "neurons" with a so-called "weight-relation" in N x N x Real. The weight relation establishes a real number weight between a pair of neurons. The weight relation elements are changeable. The network can calculate a changeable function from an input vector to an output vector. // For a detailed introduction to neural networks, see // "Neural Networks" (nn.txt, in German) Data type: A predefined set of similar data. This includes usually * string (for the set of all strings) * int (for the set of integers) Frame, Record: A sequence of pairs of names and data types. Filled record: A record with a state, which assignes data to the names of the record. The data assigned to a name must be an element of the corresponding type. One record may be used for multiple filled records. Thus, a record can be seen as the data type of all its filled records. Method: A (small) algorithm with a name and an input record. The input record is filled whenever the method is executed and the method may access its data. The method may also specify data to be the "result" of the method. Hence the method can calculate a function from the input state to the result. Hence the method name can be used like a function. Parameter of a method: An element of its input record. Method signature: The string of its name and its input record. Example: print(String printMe) Calling a method: Executing it or having it executed. A program may state the name of the method with values for the parameters. If the program is executed and the flow of control reaches the method name, the input record is filled and the method algorithm is executed. Afterwards, control resumes to the instruction in the program, which follows the method name. Object: A pair of a record and a set of methods. Some programming languages (such as Java) allow defining objects. // This is Java's view of objects. For a comparison with the view // of FAST (where the methods are part of the record) or with the // view of LISP (where the methods and the records are apart), cf // "Representing ontological structures in CLOS, Java and FAST" // (ba.doc) Queue: A changeable sequence, which can be modified as follows: * "enqueuing x" adds x at the end of the queue * "dequeuing" returns the first element of the sequence and removes it A queue can be imagined as a bus queue of people: He who comes first is served first (dequeue) and other people who come later (enqueue) have to wait until their predecessors have been served (dequeued). // For details and algorithms, see "Algorithms and Datastructures" // (ads.txt) Priority queue for a set M and a priority function f:M->Real: A changeable sequence, which can be modified as follows: * "inserting x" inserts x into the sequence, such that it holds for the predecessor p and successor s f(p)>f(x)>f(s * "retrieving the best" returns the first element of the sequence and removes it * "removing the worst" removes the last element of the sequence This is a bus queue, where the most important people stand in front. Whenever somebody new comes (insert), she/he may directly go to the place in the queue, which corresponds to her/his importance. // For details and algorithms, see "Algorithms and Datastructures" // (ads.txt) File: Data in form of bytes, with a name, stored on a computer. // In the slides, the notion "document" is used synonymously with // "file", whereas it later only refers to "text file". This is why // the notion of "document" is used only for "text file" in this // summary. Directory, folder: A set containing files and folders. Document: A file containing text. Order of a function f:Natural->Real: A function g:Natural->Real, such that there is x0 in Real and c in Real, such that f(x)x0. Class of an Order f:Natural->Real: The set of functions having f as an Order. Notation: O(f) Notation for "O(f) with f(n)=formula": O(formula) Notation for "g in O(f)": g is O(f) Polynomial function: A function f:Natural->Real, which is in O(n^c) for some constant c. If a value can be seen as a function from natural numbers to real numbers, the value can also be called "polynomial". Exponential function: A function f:Natural->Real, which is in O(c^n) for some constant c. Exponential functions grow much faster than polynomial functions. --------------------------- Languages ------------------------------ Entity: Anything. Mostly, the word "entity" refers to a thing of the real world. Property: A relation on entities. Unary Property: A unary relation on entities, i.e. a set of entities. Field of type X: A named binary relation from entities to X. Fields are used to represent properties. Example: "age" may be a field of type int, because it is a relation between humans and integers. Class, Concept, Categogy: A set of entities sharing some properties. Subclass-relation: The relation between a class C and another class, which contains C. Subclass of a class D: A class C with subclass(C,D). The subclass C is more special than the class D. Superclass of a class C: A class D with subclass(C,D). The superclass D is more general than the class C. Instance-relation, Is-A-Relation: The relation between an entity and its concept. Ontology: A graph, the nodes of which are concepts and the links of which are the subclass relation. The concept nodes may be equipped with further sets, tuples or properties. // For a detailed discussion of this, see // "Representing ontological structures in CLOS, Java and // FAST" (ba.doc) Non-monotonicity: The phenomenon that new knowledge may make something false, which has already been taken for true . Word: A string, which forms the smallest independent unit of information in human language. // There are different definitions, see "Introduction to Linguistics" // (lingu.txt) Denotation, Meaning, Semantics: A function mapping data to real-world entities. The denotation of a word is mostly a concept. // For details on word meaning, see "Introduction to Linguistics" // (lingu.txt). For details on the study of semantics, see // "Computational Logic" (clog.txt). For problems caused by this type // of denotational semantics, see "Philosophy of Mind" (pom.txt, // in German) Instance of a word: An element of its denotation. Grammatical root of a word: The part of it, which does not depend on the role the word takes in a sentence. Content of a text: Its meaning. Textual distance of two words in a document: The number of words (or characters) between them. // In the following, a very superficial introduction to logic is // given. For a detailed discussion, see "Computational Logic" // (clog.txt) or "Human-oriented Theorem Proving" (htp.txt) Variable: A symbol. A variable mostly represents a state of the world. Example: rain may be a variable standing for the phenomenon of raining Boolean formula: A string of one of the forms * A and B * (A or B) * not(A) * V where A and B are boolean formulae and V is a variable. Formulae mostly represent a set of possible states of the world. Example: (rain or snow) and wind and not(sun) may be a formula for really bad weather Conjunction: A boolean formula of the form A and B where A and B are formulae. Disjunction: A boolean formula of the form A or B where A and B are formulae. Equivalence-Transformation of a boolean formula: The transformation of a boolean formula according to the following schemata: A and (B or C) ~~~~> (A and B or A and C) A or (B and C) ~~~~> (A or B) and (A or C) not(not(A)) ~~~~> A A or B ~~~~> B or A A and B ~~~~> B and A where A, B and C are boolean formulae. The equivalence transformations do not change the set of states described by the formula. DNF, disjunctive normal form: A boolean formula of the form (A1 and A2 and ...) or (B1 and B2 and ...) or ... where A1, A2, ..., B1, B2, ..., ... are either variables or strings of the form "not(V)" with V being a variable. Every boolean formula can be transformed to a DNF by equivalence-transformations. A DNF is often noted as the set of the sets of its conjunctions: {{A1, A2, ...}, {B1, B2, ...}, ...} PL1-formula, First-order predicate formula: A string of the form * A and B * (A or B) * not(A) * R(V1, V2, ...) * (All V1: A) * (Ex V1: A) * V1=V2 where A and B are first-order formulae, R is a relation name and V1, V2, ... are variables. A PL1-formula represents a set of possible states of the world. If the current state of the world is in this set, the formula is said to "hold". Notations: A => B for not(A) or B A <=> B for (A => B) and (B => A) V1 != V2 for not(V1=V2) Example: All x: isa(x, student) => likes(x,UdS) PL1, First-order Predicate logic: The set of all first-order predicate formulae. Relation instance: An element of the relation, together with the name of the relation. Example: In the author-relation, the following is a relation instance: author(iia.txt, fabianSuchanek) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ The Internet ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Data element: A relation between data and entities. Data elements are used to describe documents by meta-data (s.b.). Example: "author" is a relation between data and humans. Meta-data about data D: Information about D, mostly a set of data element instances concerning D. Example for meta-data about this document: author(iia.txt, fabianSuchanek) date(iia.txt, September2004) title(iia.txt, "Summary Intelligent Information Agents"). Descriptive Meta-Data about data D: Meta-data concerning the creation of D, independently of the content of D. This may include the author, the date of creation etc. Semantic Meta-Data about a text D: Meta-data concerning the content of D. This may include information on its structure, keywords, summary, thematic category, content rating etc. Layout of a text: Its form on the screen. Extension of a file: The substring following the last dot in the file name. Usually, each file has an extension and the extension has 3 or 4 characters. Example: For this file (iia.txt), the extension is "txt". MIME-type, File Format: The way in which information is encoded in a file. Files can store different types of information (sound, pictures, text, text with layout, compressed other files etc.) and this information has to be encoded to a sequence of bytes. The extension is used to identify its file format. Common file formats are (with their extensions) * Text * Pure ASCII (directly human-readable) TXT * Formats to be displayed by specific programs DOC, RTF, PDF, PS, PPT * Annotated text (text with layout or additional information) HTML, XML/DTD/XSL, RDF * Binary media files * Graphics JPG, GIF * Video MPEG * Sound MP3, WAV * Compressed Files (files containing other files) ZIP, ARJ, RAR Hypertext format: A file format for documents, which can store references to other documents. Markup-Language: A file format for documents, which can store a text together with layout information or additional semantic information. Tag: A string of a specific form sprinkled into the text of documents in a mark-up language. HTML, Hypertext markup language: A certain markup language for hypertext, which is widely used today (2004). Its predecessors are GML (1969) and SGML (1985). HTML defines the layout and formatting of a document, but does not concern its content. HTML allows storing some meta-data in the document, such as its author, its date of creation, some keywords, its title etc. It is possible in a limited way to combine HTML with programs (Java-programs and JavaScript-programs). Example: A typical HTML-file looks like Peg the Pig This is the said but true story about.... Communication Network: A graph, the nodes of which are computers and the links of which tell which computers may communicate. Protocol: A set of rules, which govern the interaction of two computers in a network. Internet: The global network of computers. TCP/IP: The protocol used in the internet. WWW, World Wide Web, Web: The part of the internet which is concerned with the display of hypertext files. HTTP, Hypertext transfer protocol: The protocol used in the WWW. Web-site, web-page: A hypertext file used in the web. The web uses billions of sites, mostly human-readable files in English language. (This document is proud to be a part of it) It is assumed that * a reference to another site is a recommandation of this site * sites linked by references may concern the same topic * sites of different authors were created independently Browser: A program to display web-sites on the screen. Existing browsers include Microsoft Internet Explorer, Netscape and Opera. Server, host: A computer storing data accessible on the internet. Domain: A name for a set of servers. Country-code: A string of 2, 3 or 4 characters identifying a country or a type of information. Examples: de, uk, nz, com, info, org URI: Uniform resource identifier of a document: A string, which uniquely identifies the document in the world. A URI has the following form: ://../ //.../ URL, uniform resource locator of a document: A URI for a document on the Internet. A URL without the filename given refers to the file index.html Thus, a URL in the WWW is mostly of the form: http://www..com Referring to a web-site: Containing its URL. Hyperlink graph, HLG: The graph, the nodes of which are the existing web-sites and the links of which are the references stored in the sites. Download: Storing a file from one computer on another computer via the internet. Heterogeneity: Diversity. Internet heterogeneity: The fact that the data on the internet is highly heterogenous. This includes heterogeneity concering * structure * semantics * the operating systems used Internet volatility: The fact that the data provided by the internet is subject to frequent change. This includes * the dynamic creation of data * the relocation of data (and resulting "dead links") * network topology changes, i.e. changes in the availability of servers Internet redundancy: The fact that much of the data on the internet is available more than once. Citation: A use of material from another source in a text. A (correct) citation is annotated with a reference to the source. Citations and hyperlinks differ: Citation is enforced by the reviewers of the text, whereas hyperlinks are voluntary. As a result, companies usually do not refer to their competitors. Furthermore, many hyperlinks are purely navigational. Co-Citation of two texts: The number of texts, which cite both texts. Bibliographic coupling of two texts: The number of texts that are cited by both texts. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Intelligent Agents ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Unique name assumption: The assumption that an entity has no more than one name. Closed world assumption: The assumption that everything which is not known is false. Open world assumption: The assumption that there may be facts, which are true, but not known. Agent, Software Agent: A computer system that is capable of autonomous action in its environment on behalf of its user. An agent has control over its internal state. Agents are an appropriate means for problem solving under the open world assumption with an unpredictable and dynamic environment. Agents have been used in * process control and manufacturing * distributed traffic control * electronic commerce * distributed medical management * entertainment and telecommunication * information gathering on the internet Up to now, no agent has yet had a global perspective. Agents have always been limited to their domain. Stimulus-response-rule: An instruction, which commands a specific action if a specific environmental state is reached. Reactive action: An action carried out as a consequence of an event. Reactive agent: An agent capable of reactive action. A reactive agent maintains interaction with its environment and can respond to non-deterministic events in it. Adaptive reactivity: The property of an agent of being reactive through machine learning. Pure reactivity: The property of an agent of being reactive through stimulus-response-rules. Proactive action: An action which is not reactive. This is an action, which is carried out on the agent's own decision, when the agent wants to cause or prevent something. Proactive agent: An agent capable of proactive actions. In human terms, proactive agents tend to be rational and goal-directed, they recognize opportunities and take initiatives. Social action: An action which depends on the states of other agents. Social agent: An agent capable of social action. In human terms, social agents can cooperate, coordinate and negotiate with other agents. Intelligent agent: An agent that is capable of flexible action, i.e. reactive, social and proactive action. One says that the difference between an object and an intelligent agent is that the object does something upon instruction, whereas the agent does something when it decided that the action would help it to achive its goals. In practice, however, an agent will often be implemented as an object. Rational agent: An agent, the underlying programs of which are rational. Usually, this means that * the agent has an explicit representation of the environment, its possible actions and its goals * the agent reasons about what to do next and how to do it Truthfulness of an agent: Its property that it does not affect other agents' (and the user's) knowledge in such a way that the knowledge becomes false. Benevolency of an agent: Its property that it does not prevent other agents from reaching their goals. Mobility of an agent: Its property that it is not limited to a certain computer. Adaptivity of an agent: Its property of changing its subgoals when the environment changes. Sensor: The part of a program which gathers data from the environment. Effector: The part of a program which changes the environment. Agency: The properties of a computer system, which make it an agent. There are different views of the notion of agency: "Weak Agency": This corresponds to the above definition of Intelligent Agents, including * Autonomy * Social Ability * Reactivity * Pro-Activeness "Strong Agency": This includes weak agency and postulates aditional properties such as the presence of * knowledge and belief * intentions * desires and goals * obligations * emotions Additional properties: These properties are human properties, which are applied in a rather undefined way to agents: * Rationality * Truthfulness * Benevolency * Mobility * Adaptivity Different athors stress different aspects of agency: Some emphasize the assistance to the user, others stress its object-oriented properties, i.e. * the possession of an internal state * the ability to reason upon this internal state * encapsulation (i.e. hiding its internal state and receiving states by sensors and changing states by effectors) Human intelligence: The ability of a human being to attack any arbitrary problem at least in principle. AI, Artificial intelligence: The study with the goal of making computers exhibit behavior similar to human intelligent behavior. Agent intelligence: The property of an agent to exhibit behavior similar to human intelligence. This usually goes along with * the use of some form of inference * the attempt to deal with semantic meaning * the use of search techniques as well as of techniques developed in AI * the use of meta-knowledge * ability to deal with imperfect data Multi-Agent-System: A set of interacting agents. The agents of a multi-agent-system are social agents. Top-down problem solving: Solving a problem by breaking it into sub-problems, which are designed so that the solution of each of them entails the solution of the original problem. Usually, each sub-problem is solved by a separate agent, which may again carry out top-down problem solving. Emergent problem solving, swarm problem solving: The solution of a problem by a set of equal agents (?). Plan: An algorithm assembled by a program and to be executed by that program. BDI-Agent, Belief-Desire-Intention-Agent, Practical Reasoning agent, deliberative agent: A proactive agent with the following architecture: Sensors -> World Model Planner Plan executor -> Effectors It repeatedly * perceives the environment * updates its world model * chooses a subgoal to achieve next (its "Intention") * creates a plan to achive this subgoal * executes the plan The opposite of a BDI-Agent is a reactive agent. Hybrid agent: An agent, which is both reactive and proactive. The reactive part ensures appropriate behavior on the short term, whereas the proactive (BDI-) part guarantees that the behavior is successful on the long run. // This pattern is similar to a human reaction pattern: Humans use // the Amygdala for emotional shortterm-reactions and thought // for rational longterm reactions (at least in principle). // For details about the human brain, see "Introduction to // Neurobiology" (neurobio.txt, in German) Agent development platform: A computer system which allows a programmer to write agents. Existing agent development platforms are JADE, ZEUS, FIPA-OS, Aglets, Voyager, Grasshopper. Agent architecture: The overall concept of the underlying program(s). Agent architecture standardization consortium: A group of people aiming to create universally useful agent architectures. Agent architecture standardization consortia include: * FIPA (Foundation for Intelligent Physical Agents) * OMG MASIF ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Intelligent Information Agents ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Shannon's entropy, Shannon's discrete uncertainity of a random variable X: The value H(X) := -SUM {P(X=x)*log2(P(X=x)) | x in dom(X)} The entropy measures the diversity in X's result. If X always returns the same value, the entropy is small (positive value near 0). If X returns lots of different values, the entropy is large (positive value). Information: Data extended by a semantics. That is: Data that has been given "meaning" (Russel Ackhoff). Information can be used to answer "Who"-, "Where"-, "What"- and "When"-questions. Information exhibits relations in the data. There were different views on the notion of "information": * Information is the decrease of uncertainity after having received a bit sequence (Shannon) * Information is the set of properties of the result of a process which can be used to determine the input of this process (Losee) Knowledge: Information applied for some goal (Russel Ackhoff). Knowledge can be used to answer "How"-questions. Knowledge exhibits patterns in the information. Rainer Kuhlen defines Knowledge and Information vice versa. Understanding: Knowledge, extended by information inferred from it (Russel Ackhoff). Understanding is thus the deductive closure of knowledge, see "Computational Logic" for a definition (clog.txt). Understanding can be used to answer "Why"-questions. Wisdom: Understanding, extended by holistic information, which cannot be derived by inference alone. Whereas understanding interpolates and fills the holes of knowledge, wisdom extrapolates and adds completely new and principal information. Wisdom exhibits principles in the understanding. Information Agent: An agent, that is able to * access * maintain * mediate information on behalf of its user or other agents. Existing information agents include: * cooperative agents RETSINA, IMPACT, InfoSleuth, TSIMMIS, OBSERVER * adaptive agents MySpiders, Amalthaea, Histos, LikeMinds * rational agents AuctionBot, NOMADS, UMDL, FishMarket, Bazaar, Kasbah, CASA, AGRICOLA * mobile Agents2Go, MIA, NOMADS, ACTS-MIAMI * non-cooperative agents * adaptive agents ExpertFinder, Butterfly * rational agents ShopBots * mobile D'Agents, Smart, MIAOW Primary information need: The need of information about the environment. Secondary information need: The need of information about the sources of the information. Objective information need: The need of information for the solution of a problem. Constitutive information need: The part of objective information need related to the fundamental problem characteristics. Situative information need: The part of objective information need related to potantially changing problem components. Subjective information need: The need of information for the solution of a problem in the view of a human. Objective information supply: The information which is actually available. Subjective information supply: The information which is perceived by the user. Requested information supply: The information which is demanded by the user. Affective computing: Using a computer, which measures the user's emotion by physical sensors. Interface, User interface: A means for communication between a computer system and a human. User profile: Knowledge of a program about the user. Adaptive user profiling, Personalization: The process of a program gathering information about the user. This can be supported by machine learning. Personal agent: An agent, which gathers information about the user for personalization. Requested information need: The need of information for the solution of a problem demanded by an agent. The requested information need of an agent depends on * The requested information supply (what is the goal) * The objective information need (what is needed to solve the prob) * The objective information supply (what is available) * Subjective information supply (what does the user expect) * Subjective information need (what does the user think is necessary) Key techniques for determining the information need are * Recognizing and anticipating the user's information need and supply through Intelligent User Interfaces, Affective computing, Adaptive user profiling and the presentation of information. * Dynamically replanning what kind of information might be needed. Sources for determining the information need may be * the environment * the user profile * local data * communication with the user Internet information acquisition: The process of gathering information from the internet by an agent. Key techniques are * discovering, accessing, searching and filtering data from the available resources * understanding, processing and fusing the data * cooperation with other agents, including joint planning, negotation and recommandation * adaption and dynamical reaction to non-deterministic changes of data, resources and agents. Internet information acquisition can either follow * existing hyperlinks noted in the web-sites or * content-based similarities between web-sites Brokerage: (?) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Information Retrieval ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -------------------- Basics ------------------------------------------ String matching: The process of finding the occurences of a string in a text file. Brute force string matching: The following algorithm for string matching: Compare the first character of the string with the first character of the text, then compare the next character of the string with the next character in the text etc. If a character does not match, abort, else if all characters match, report a match. Repeat this process for every position in the text. In the worst case, this algorithm requires O(n*m) steps, where m and n are the lengths of the text and the string respectively. Example: Finding the string "bonbons" in the text "bonbonbonbonbonbonbon": bonbons all characters compared, last fails b first character compared, fails b first character compared, fails bonbons all characters compared, last fails b ... Knuth-Morris-Pratt string matching: The following algorithm for string matching: Preprocess the string as follows: For each position i in the string, note the length of the largest substring, which starts at a position j store length 2 Now proceed as in the brute force matching, but whenever a character does not match, advance the string by the stored number: "bonbonbonbonbonbonbon": bonbons 's' mismatches, advance by 3 bonbons 's' mismatches, advance by 3 bonbons ... This algorithm only needs O(n) steps, if n is the length of the text. // For details, an implementation in pseudo-code and a // proof of the runtime, see "Algorithms and Datastructures" // (ads.txt) Semantic relation: A relation between two words, which holds because of a relation of their denotations. Synonymy: The semantic relation between those words with the same denotation. Hyponymy: The semantic relation between a word and another word, which denotes a more general concept. Hyperonymy: The semantic relation between a word and another word, which denotes a more special concept. Hyperonymy is thus the inverse relation of hyponymy. Meronymy: The semantic relation between a two words, where an instance of the first is a part of an instance of the second. Homonymy: The property of a word of having two distinct denotations. Example: Java can denote both the island and the programming language. Thesaurus: An alphabetically sorted sequence of (ideally all) words of a language with information for each of them. This information may include a definition and semantic relations. WordNet: A popular thesaurus, which is available on the web (http://www.cogsci.princeton.edu/~wn) with more than 1E5 words. Content of a document: The meaning of its text. // This definition relies upon the semantics function to establish // the "meaning of the text". Approaches can be found in // "Computational Linguistics" (cl.txt). Classification: The grouping of entities into categories. -------------------- General Techniques ----------------------------- Information retrieval: The process of finding documents with a specific user-desired content. Information retrieval techniques can be classified according to * the representation of documents (the indexing, s.b.) * user activity either the user is active (interactive query answering, s.b.) or inactive (adhoc query answering, s.b.) * the way documents are sorted for relevance (defined by the information retrieval model, s.b.) Information retrieval usually comprises the following steps: * document pre-processing (s.b.) * query operations * retrieval of documents similar to query * presentation of ranked and grouped documents * performance evaluation * relevance feedback to improve retrieval Document collection of an information retrieval: The sequence of available documents. The j-th document is noted d[j]. User query of an information retrieval: A sequence of words given by the user with the desire to get related documents. For simplification, the user query is supposed to be stored as a document, such that all notions defined on documents may also be applied to the user query. Relevant document of an information retrieval: A document of the document collection, the content of which is highly related to the user query. Answer of an information retrieval: The sequence of documents returned by the information retrieval. The documents are sorted according to their estimated relevance. Adhoc information retrieval, One-time information retrieval: Information-retrieval for one given, unchanging user query. Interactive information retrieval, Browsing information retrieval: An information retrieval, where the user iteratively develops the query while she/he browses through a subset of the document collection. Index term of a document: A word associated to the document in order to classify its content. Multiple words may serve as index terms to one document and the same index term may be associated to multiple documents. Mostly, words contained in the document itself are chosen as index terms. Significance of an index term for a document: The degree to which the document contributes to the satisfaction of a user query containing the index term. Weight of an index term for a document: A real value estimating the significance. Index vocabulary of an information retrieval: The sequence of all index terms of all documents. The i-th index term is noted t[i]. Index: The index vocabulatory with additional information for each index term, especially the set of those documents which the index term is associated to. The term "inverted index" is used to stress the fact that documents have index terms, but the index stores index terms with their documents. Posting: (?) Structure of a text document: Its chapters, sectios and subsections. Structure-index: An index, which takes into account the structure of the documents. Index term clustering in an information retrieval: Arranging the index terms into sets according to * their syntactic vicinity Words which appear closely together in a text document are grouped together. * their semantic vicinity Words which are closely related in an ontology are grouped together. Full-text index: An index which uses all distinct words of a document as its index terms. Stop word: A word with a grammatical role, which is played only by a limited number of words. Stop words are said to have no meaning per se. Examples: Articles and prepositions // The characteristic of a stop word is that it does not carry // content as do nouns and verbs. Since this distinction is // quite vague, I defined stop words by the coextensional notion of // "closed word class". These are words of classes, which cannot be // extended by inventing new words (such as articles). // For a detailed discussion see "Computational Linguistics" // (cl.txt) at "closed word class" Content word: A word, which is not a stop word. Examples: Nouns, verbs, adjectives, adverbs // For a detailed discussion see "Computational Linguistics" // (cl.txt) at "open word class" Stemming: The reduction of a word to its grammatical root. Stemming can be done by * suffix stripping (cutting off suffixes such as the plural-s) * table lookup (seeking the word stem in a dictionary) * use of successor variety (determining word part boundaries by methods developed in linguistics) Example: The stem of "computer", "computing" and "computes" is "comput". This may lead to bizarre errors, such as "polic", which is the stem of both "police" and "policies". Lexical analysis: The process of converting a text file to the sequence of its words. This includes the elimination of spaces and accents. Index term selection: The choice of those stemmed words of a text document, which are to serve as index terms. Document pre-processing: The preparation of a document for indexing. This usually involves the following steps: * Structure recognition The results can already be used for structure-indexing. * Lexical analysis The results can already be used for full-text-indexing. * Removal of stop words * Identification of nouns * Stemming * Index term selection, either manually or automatically * Index term weightening Word occurance in a document: A position in the document, where the word or one of its grammatical forms appears. This notion can also be applied to stemmed words. Heap's power law: The fact that the number of different words in a text increases logarithmically with the total number of words in the text. Zipf's power law: The fact that the number of occurances of the r-th most frequent word in a text is proportional to 1/r times the number of occurances of the most frequent word in the text. numberOcc(Word) = constant / rank(Word) * numberOcc(MostFrequentWord) // The slides state furthermore // numberOcc = rank^-constant // which is different from the above formula (?). Each text has its own constant, for English texts about 0.1. Discrimination in an information retrieval: Sorting the answer documents as closely as possible to their relevance. Index vocabulary reduction: The elimination of certain index terms from the index vocabulary, because of their limited significance. According to Luhn, this applies to both highly frequent words and very rare words. Index term vector: A vector of the same dimension as the index vocabulatory. As a result, each position in an index term vector is associated to an index term. IR-model, Information retrieval model of an information retrieval: A quadruple of * a set D of document representations * a set Q of user query representations * a ranking function R:Q x D -> Real, which estimates the relevance for each pair of a user query and a document. * a framework F The framework seems to be a name for the type of the IR-model (?) The IR-model specifies the way in which an information retrieval program works. The answer sequence is determined by evaluating the ranking function on each document representation and sorting the documents by their results. There are many different IR-models: * IR-models for adhoc information retrieval * Classic IR-models * Boolean IR-model (s.b.) * Vector space IR-model (s.b.) * Probabilistic IR-model The framework is a set of sets of documents with probabilistic set operations * Set-theoretic IR-models * Fuzzy IR-model The framework is a fuzzy set of documents * Extended boolean IR-model (?) * Algebraic IR-models * Generalized vector IR-model (?) * Latent Semantics Index IR-model (?) // For more information on latent semantics, see "Artificial // Intelligence" (ia.txt, in French) * Neural Network IR-model * Probabilistic IR-models * Inference IR-model (?) * Belief IR-model (?) * Structured IR-models * Proximal nodes IR-model (?) * Non-overlapping lists IR-model (?) * IR-models for interactive information retrieval * Flat IR-model (?) * Structure guided IR-model (?) * Hypertext IR-model (?) -------------------- Boolean IR-model ------------------------- Boolean index term vector of a set of words M: An index term vector, which contains a '1' for each index term, which is in M, and a '0' for all other index terms. Boolean IR-Model: The following IR-Model: * The documents are represented by the index term vectors of their set of words ("document vector"). * The user query takes the form of a boolean formula, the variables of which are words. These words are stemmed and the formula is transformed to disjunctive normal form. Then, each conjunction of the DNF is given its index term vector. Thus, the query translates into a set of index term vectors ("query vector set"). * The ranking function ranks a document with '1', if the document vector is in the query vector set. Else, the document is ranked '0'. A boolean information retrieval returns the set of those documents, which exactly contain the words specified by the user. -------------------- Vector space IR-model ------------------------- TF, Term frequency of an index term t[i] in a document d[j]: The number of times which t[i] occurs in d[j], noted tf[i,j]. The more often an index term occurs in a document, the more likely it is that the term is significant for the document. However, the tf-measure favors common words, which are per se more likely to occur. DF, Document frequency of an index term t[i]: The number of documents which contain the index term i, noted df[i]. The smaller the value of df[i], the more useful index term t[i] will be for discrimination. IDF, Inverse document frequency of an index term t[i]: The document frequency of t[i] to the power of -1: idf[i] := 1/df[i] The greater the value of idf[i], the more useful index term t[i] will be for discrimination. Normalized term frequency of an index term t[i] in a document d[j]: The real value ntf[i,j] := tf[i,j] / max {tf[m,j] | m in index terms of j} This value normalizes the number of occurances of t[i] by the number of occurances of the most frequent index term. TF/IDF,Weight of index term t[i] for document d[j]: The value w[i,j] := ntf[i,j] * idf[i] This value estimates the relevance of index term t[i] for document d[j]: It increases with its number of occurences (normalized) and with its discriminatory power (in form of the inverse document frequency). Weight of index term t[i] for the query: The real value w[i,q] := (0.5 + tf[i,q]/2/max {tf[m,q] | m in index terms of query}) * idf[i] The weight is thus the normalized term frequency, shifted towards 1 and multiplied by the inverse document frequency. Vector IR-Model, Vector space IR-Model: The following IR-Model: * Each document is represented by an index term vector, which contains the weights of the index terms for the document ("document vector"). * The query is represented by an index term vector with the weights of the index terms for the query ("query vector"). * The ranking function is the vector similarity sim. In a naive implementation, this requires the comparison of each of the document vectors to the query vector. A vector information retrieval returns documents with frequent occurances of the query words first and documents with rare (and also possibly inexisting) occurences last. Problems with the vector space framework: * There is no semantic information (meaning) contained in the index term vectors. * There is no syntactic information (as about the sentences which the words occur in) contained in the index term vectors. * The approach assumes index terms to be independent -- and thus ignores the phenomenon of synonyms. * Given a user query with two words, the approach might also return documents with only one of them -- if it occurs very frequently in the document. Query expansion: The modification of the query vector in an information retrieval with a vector IR-model in order to make the comparisons of document vectors to the query vector more discriminatory. Roccio-Algorithm: The following query expansion algorithm: Proceed as usual in a vector information retrieval and present a small sequence of documents as a preliminary answer. Have the user specify which documents are considered useful and which are not. Calculate the sum of all useful document vectors, scale it and add it to the query vector. Calculate the sum of all useless document vectors, scale it, negate it and add it to the query vector. As a result, the query vector becomes more similar to the useful document vectors and less similar to the useless document vectors. Repeat this process with the new query vector. As a drawback, this algorithm eliminates potentially important information in the query vector on the basis of maybe unrepresentative and sub-optimal documents. Local clustering: A query expansion algorithm, which gives values to those index terms in the query vector, which are found in best-ranked documents. This makes the query vector more similar to the best-ranked document vectors. Global analysis: A query expansion algorithm, which gives values to those index terms in the query vector, which are semantically related to other index terms of the query. This makes the query vector broader, while maintaining its semantics. Recall of an information retrieval: The number of relevant documents in the answer sequence divided by the total number of relevant documents. The recall measures how many of the good ones have been found. Precision of an information retrieval: The number of relevant documents in the answer sequence divided by the total number of documents in the answer sequence. The recall measures how much of the answer is useful. Recall and precision together offer a good means for the judgement of an information retrieval, but * they are difficult to calculate, as the total number of relevant documents has to be known. * both values are necessary to judge one single phenomenon * the measurement does not work for interactive query answering * the measurements ignore that different users might have different views of relevance. Harmonic mean judgement of an information retrieval: The value H := 2 / (1/precision + 1/recall) which combines the usefulness of precision and recall in one value. // The slides mention an index 'i' (?) // For details, see "F-Measure" in "Computational // Linguistics" (cl.txt) Novelty ratio of an information retrieval: The number of retrieved relevant documents, which were previously unknown to the user, divided by the total number of retrieved relevant documents. This ratio measures the gain of information which the user has from the answer. Coverage ratio of an information retrieval: The number of retrieved relevant documents, divided by the number of relevant documents known by the user. This ratio measures the satisfaction of the expectation of the user. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Web Retrieval ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Spider, Crawler: An agent, which indexes or searches web-sites. i-th level of a graph relative to a node n: The set of nodes reachable by i links from n. Graph search algorithm: An algorithm, which looks at all nodes of a graph, starting from a given root node. Graph search algorithms are mostly used to search for a node fulfilling certain criteria. // For a detailed discussion of graph algorithms, see // "Graphs and Complexity" (gc.txt, in French) or // "Algorithms and Datastructures" (ads.txt) BFS, Breadth-first search: A graph search algorithm, which first looks at the first level relative to the root node, then at the second level, etc. It is taken care that no node is looked at twice. Example for a BFS in a tree-like graph: 1 /|\ / | \ 2 3 4 /| / \ | \ 5 6 7 8 9 10 The problem is that the algorithm has to remember all nodes of one level. DFS, Depth-first search: A graph search algorithm, first looks at a root node and then performs a depth-first search for all nodes reachable by one link from the root node. It is taken care that no node is looked at twice. Example for a DFS in a tree-like graph: 1 /|\ / | \ 2 5 8 /| / \ | \ 3 4 6 7 9 10 The problem is that the algorithm may run forever if the graph is infinite, even if a desired node is close to the root node. Best-first search: A graph search algorithm, which maintains a priority queue of nodes. Whenever a new node is hit, the node is inserted into the queue according to its estimated usefulness. Then the best node is retrieved, looked at and all nodes linked to this node are inserted into the queue. It is taken care that no node is looked at twice. Simple spider algorithm: The breadth-first search on the hyperlink graph for indexing web-sites. More concretely, this is: * Define a time limit * Define a maximal index size * Be Q a queue of URLs * Enqueue initially known URLs to Q * Repeat the following until Q is empty or the time limit is exceeded or the index size limit is exceeded * Dequeue the URL L from Q * If L has already been visited, continue the loop * Download web-site w with URL L * If an error occurred during the download, continue the loop * Index w * Collect all hyperlinks in w and enqueue them to Q Thread: A program being executed simultaneously to other programs. Multi-Thread Spidering: The use of multiple spiders as threads. As an advantage, a delaying download does not block the whole spidering. In multi-thread spidering, different spiders search different areas of the web to avoid overloading a single server. Web retrieval: Adhoc information retrieval on the web. Search engine: A web retrieval program. Usually, the search engine asks the user for a number of keywords and returns all those documents on the web, which contain these keywords, possibly in a ranked order. A search engine is a (very simple) information agent, but not an intelligent information agent, because is neither proactive, nor reactive nor social. Most search engines violate the data privacy of the user by locally tracking user queries. The main limitations of search engines are * insufficient coverage (not all web-sites are indexed) * insufficiently updated indices (the web-sites referred to do no longer exist) * missing access to the invisible web (sb.) Robot exclusion protocol: A convention which prevents certain documents from being indexed by a search engine. If a document is declared as non-indexable, a search engine should not index it -- and most search engines obey this convention. Robot.txt: A text file stored on a server, listing the web-sites which shall not be indexed by a search engine. Robot.txt is part of the Robot exclusion protocol. Robots META Tag: Meta-data in a web-site, which declares that the site shall not be indexed by a search engine. The Robots META Tag is part of the Robot exclusion protocol. Invisible web: The part of the web, which cannot be accessed by search engines. Missing access can have numerous reasons: The site can be * protected by the robot exclusion protocol * created dynamically (and possibly password-protected) * regarded as "unethical", which causes its exclusion from the index Some sites are also not indexed because the index of the search engine is not updated often enough. Google: A popular search engine at www.google.com // At our time (2004), Google is so popular that the notion // "search engine" has become nearly synonymous to "Google". Best first web retrieval: Vector space web retrieval by a best-first search in the hyperlink graph. That is web retrieval by the following algorithm: * Be Q the user query * Calculate the index term vector for Q as specified by the vector space IR-model (the "query vector") * Be P a priority queue of URLs * insert some known URLs somewhere into P * Define a time limit * Define a maximal number of sites * Repeat the following until P is empty or the time limit is exceeded or the site limit is exceeded * Get the best URL from P * Download the corresponding hypertext document d * Calculate the index term vector of d (the "document vector") * Calculate the similarity of the document vector and the query vector, use the meta-data of d to further estimate the usefulness of d * insert all links found in d in P according to the usefulness of d * The answer is the sequence P This corresponds to a search in the full HLG, the direction of which is guided by the estimated relevance of the encountered sites. Best first web retrieval is one of the most efficient and most successful web retrieval algorithms. Web directory, subject directory: An ontology, the concepts of which are equipped with URLs of relevant web-sites. The URLs may furthermore be annotated by reviews, ratings and summaries. Web directories are maintained by human domain experts. They are available as web-sites and often support web retrieval. Web directories are more popular than search engines. Existing web directories: yahoo, suite101, looksmart, dmoz, informien, altavista, scirus (?) Web index harvest: (?) Authority for a concept: A web-site relevant for the concept, which many other relevant web-sites refer to. The underlying assumption is that a popular site is also a highly relevant site. Authority for a user query: An authority for the denotations of the words of the user query. Hub for a concept: A web-site, which refers to many authorities for the concept. Root set of a user query Q: A set RS(Q) of web-sites known to be relevant for the user query. These sites are either selected manually or by querying existing web directories. The assumption is that if there exists an authority for Q, it is likely that some web-site in RS(Q) refers to it. The root set is usually limited to 200 sites. Base set of a user query Q: The set BS(Q), which is the union of * the root set RS(Q) * all web-sites which the sites in RS(Q) refer to * for each web-site w in RS(Q): the set of sites which refer to w if this set is too large, it is arbitrarily restricted That is: The root set extended by some linked sites. To eliminate purely navigational links, links between two sites on the same host are skipped. To eliminate non-authority-conveying links, only 4-8 sites from the same host are allowed to point to an indivial site. Query-oriented hyperlink graph, Query-oriented HLG of a user query: The HLG restricted to the base set of the user query. Notation: HLG(Q) where Q is the user query. HLA-ranking of a set of web-sites according to a user query: Sorting the web-sites by their authoritative quality for the user query. HLG-algorithm: A web retrieval algorithm, which calculates a query- oriented hyperlink graph, does a HLA-ranking on them and returns the most authoritative nodes as the answer. Topic-shift: The problem that following the references of universal hubs (such as web directories) may mislead a HLG-algorithm, because homonyms cause the search to spread for both denotations. Page rank of a web-site p for a user query Q: The real value PageRank(p) := s / |BS(Q)| + (1-s) * SUM {PageRank(q)/outdegree(q) | q is in BS(Q) and refers to p} where s is a real value between 0.0 and 1.0. The page rank estimates the relevance of a site for a user query. It bases on the assumption that a site is highly relevant if sites point to it and if these sites have themselves a high page rank. Their page rank is normalized by their outdegree, to rule out hubs. The page rank is defined recursively, such that calculating it for a set of sites means searching for values such that the above equation is fulfilled. In practice, the page rank is first set to 1.0 for all sites of the set. Then, a new page rank is calculated for each site, basing on the initial 1.0 values. Next, a new page rank is calculated basing on the former values. This process is repeated until no value changes. Be A a modified adjacency matrix of HLG(Q), such that a[i,j]=1/outdegree(i) if node i is linked to node j a[i,j]=0 else Then the sequence of page rank values for the nodes is an eigenvector of A. The "proof" mentioned in the slides is the following: Consider a line i of A, be v the vector of page rank values and c the corresponding realvalue of the eigenvector. Then it is v[1]/outdegree(1) + ... v[n]/outdegree(n) = c * v[i] With an addition of s/|BS(Q)| (by eg. an additional vector component) and a scaling by (1-s), this is the definition of the page rank value for node i. // Slide 36 erroneously uses the identity matrix for adjustment // of x'. The line should simply be x':=(1+c)*x'. Furthermore, // the algorithm should output x' instead of the (constant) x. Page rank algorithm: The following HLG-algorithm: * Calculate HLG(Q) * Take any site s in HLG(Q) * While the number of visited pages does not exceed a limit * Calculate and store the page rank of s * Be s a site which s refers to * if s has already been visited take an arbitrary unvisited site in HLG(Q) * Return the sequence of visited sites in HLG(Q), sorted by their page rank This algorithm performs a random walk on the HLG(Q) to simulate a human searching for relevant sites. The page rank algorithm has been developed by Larry Page and Sergey Brin for Google. Page rank based search: The following algorithm for web retrieval: * Get the user query * Calculate its query vector as in the vector IR-model * Be S a a priority queue of URLs with their page rank value as priority (the "search queue") * Insert a number of URLs known to be relevant into S, each with page rank 1.0 * Be R a priority queue of web-sites with a similarity score as priority (the "resukt queue") * While the number of visited pages is below a limit and S is not empty * If the number of loop executions is a multiple of 25 * Recalculate the page rank values in S * Select the URL with with maximum page rank from S * Download its document d * Calculate its index term vector as in the vector IR-model * Insert the document d into the result queue R according to the similarity of the index term vectors of the document and the query. (If the number of URLs in R exceeds a maximum, remove the worst) * For each reference in the document d * Calculate the page rank for the document and insert it into S. (If the size of S exceeds a limit, remove the worst) * Return the result queue R as the answer This algorithm uses the page rank to navigate through the web (making the initial choice of sites crucial!) and the vector similarity to estimate the relevance of the found documents. HITS, Hyperlink Induced Topic Search: The following HLG-algorithm: * Be Q the user query * Calculate BS(Q) * Be n:=|BS(Q)| * Be auth and hub n-dimensional vectors * While a limit of loops has not been exceeded * auth' := auth * For all sites i=1..n in BS(Q) * auth[i] := SUM { hub[j] | j refers to i } * hub[j] := SUM { auth'[j] | i refers to j } * Return the set of nodes in BS(Q) as the answer, ranked according to the values in auth This algorithm models the mutual relationship of hubs and authorities: An authority is a site quoted by many hubs and a hub is a site quoting many authorities. Theory says that there is a number of loop executions such that the values of auth and hub don't change any more. Experiments have shown that this is the case after ca 20 loops. One can show that auth and hub are the eigenvectors of A*t(A) and t(A)*A respectively. SALSA: The following HLG-algorithm: * Be Q the user query * Calculate HLG(Q) * Be auth and hub adjacency matrices of HLG(Q) * For each link (i,j) in HLG(Q) * auth[i,j] := SUM { 1/indegree(i)/outdegree(k) | k refers to both i and j } * hub[i,j] := SUM { 1/indegree(k)/outdegree(i) | both i and j refer to k} * Return BS(Q) as the answer, ranked by the values in auth (?) This algorithm estimates the authoritative quality of a link by counting how many sites refer to both sites of the link. It estimates the hub quality of a link by counting how many sites are referred to by both sites of the link. SALSA assumes no mutually reinforcing structure. The relative authorities is determined solely from local links but not from the whole graph like HITS does. That may avoid a topic shift. Meta search engine: A search engine, which forwards the user query to other search engines. The meta search engine collects the answers of the other search engines and merges them. Thus, it unites the power of multiple search engines while providing a uniform user interface for both query and answer. Limitations: * The answers are still restricted to the union of the answers of the used search engines * It is hard to check whether the query is forwarded correctly to the other engines (possibly, information is lost or not translated equivalently) * The respective results of the search engines are difficult to compare and may result in a misleading merged answer Existing meta search engines are: SurfWax, Vivismo, metacrawler, ProFusion Searchable database: A set of web-sites, which is only made available on user query. Usually, searchable databases are provided by universities, libraries and associations. Such an association maintains a web-site, where the user can post a query. Then, relevant documents are searched in the internal document collection and made available to the user in form of web-sites. Searchable databases belong to the invisible web. An existing searchable database is citeseer. Local web search: Web retrieval on an individual site and on all sites reachable from this site by a restricted number of links. Database: A set of data. Relational database: A database in form of a set of relations, where each relation has a name and each position of each relation has a name, too. // For an extensive discussion of databases, see "Databases" // (bd.txt, in French) Maintaining a database: Having a reference to its data, being able to retrieve and modify data and offering access to the data for other programs. Database system: A computer system maintaining a database. SQL: A certain programming language, which allows instructing a database system to find, insert or delete data in a relational database. Attribute in a relational database: The name of a position of a relation. Example: The "has" relation with the attributes "Person" and "Object" Person Object has( bob , car) has( bob , computer) has( bob , house) Notation: (, , ...) for the presence of the relation with the specified attributes. Structured web search: Web retrieval on a relational database with the following relations: document(url, title, text, file format, size, dataOfModification) anchor(referringURL, label, referredURL) The elements of these relations are calculated and then the user may ask SQL-like queries of the form: SELECT . ... FROM document ... SUCH THAT WHERE . CONTAINS where is one of the following * * MENTIONS * AND * OR where is one of the following * -> meaning a link on the same host from the document at left to the document at right * => meaning an arbitrary link from the document at left to the document at right * meaning a (multiple-step) link from the document at left to an intermediate document and from there a (multiple-step) link to the document at right * // There is also something with "|" and "*", but I don't know what // this is supposed to be (?) A variable with the same name refers to the same document throughout the whole query. The answer is the set of attribute values mentioned in SELECT, which belong to those documents, which fulfill the conditions stated by SUCH THAT and WHERE. Reward in a machine learning process: A real number judging the usefulness of the current state for reaching the goal of the program. Expected reward: A function mapping a state and an action to a real number, which estimates the reward which the action would bring in the given state. Notation: e(state, action) = estimatedReward Q-reward: A changeable version of the expected reward function. Notation: Q(state, action) = estimatedReward Policy for a Q-reward: A function, which takes a state and returns the action with the highest Q-reward. Notation: F(state) = MAX { Q(state, x) | x is an action executable in } Reinforcement learning: Machine learning by the following (abstract) algorithm: * Calculate the expected reward function and establish a Q-reward * Repeat the following * Choose and execute the action returned by the policy for the current state * Receive the reward * Judge the usefulness of the current state for the overall goal * If the usefulness is high, increase the Q-reward for this action, else decrease it Q-Learning: The following reinforcement learning algorithm: * Be Q a Q-reward, which initially returns Q(s,a) = e(s,a) * Be F a policy for Q * Be w1 and w2 real values between 0.0 and 1.0 * Repeat the following until Q does not change any more * Be x the current state * Be u=F(x) * Execute u * Be r the reward of u * Be y the resulting state * Update Q(x,u) := (1-w1)*Q(x,u) + w1 * (r + w2*Q(y,F(y))) * // The update of F is not necessary, since it is a function, // which always returns the best action according to Q This reinforcement algorithm adjusts the expected reward Q(x,u) of an action u in a state x by paying attention to 3 values: * the old value Q(x,u), weighted by (1-w1) * the reward received, weighted by w1 * the reward expected from the new state on, weighted by w2 Policy improvement theorem: The idea that reinforcement learning will finally cause the program to estimate the usefulness of an action correctly. Ie. although the program just judges one action in one state locally, it will finally learn what a reasonable action is globally. Individual: An entity (mostly an animal). Species: A concept of individuals sharing essential properties. Population: A subset of a species. Genotype: The set of properties, which distinguishes one individual from another in the same species. Reproduction: The creation of a new individual with a similar genotype from an existing individual. // We need this notion purely for the discussion of evolution... Mutation: The fact that the genotype of a reproduced individual differs slightly from the genotype of its creator. Fitness of an individual: Its ability to survive. Mostly, this refers to an adaptation to the natural environment or its ability to pursue its goals. Survival of the fittest, Evolution, Darwinian principle: The idea that the fitness of the individuals of a species increases, because fitter individuals are more likely to reproduce (Charles Darwin). // Although this theory is widely agreed on in the scientific // domain, there are countries in which evolution is not // taught as a scientific evidence or even not taught at all... Evolutionary agent: An agent, which works according to the Darwinian principle. Species of evolutionary agents: A set of evolutionary agents with the same underlying program. Genotype of an evolutionary agent: Its internal state. Energy of an evolutionary agent: A real number representing the fitness of the agent. Reproduction threshold of a species of evolutionary agents: A fixed real number. When the energy trespasses the threshold, the agent reproduces. InfoSpider neural network: A neural network, which calculates a function taking an n-dimensional vector and returning a 1-dimensional vector (a real value). The InfoSpider neural network is used in web retrieval. It estimates the usefulness of a specific link in a web-site, depending on the presence of user query words in the lines around the link in the web-site. Each component of the input-vector stands for a user query word. The i-th component measures the importance of the i-th user query word in the textual environment of the link: vector[i] := SUM { 1/textualDistance(o,link) | o is an occurance of the i-th word in the user query } The output is a real number, which tells how useful it is to follow the link. InfoSpider: An evolutionary spider for web retrieval. Its genotype consists of * A keyword list (a sequence of words), initialized with the user query * An InfoSpider neural network, initialzed randomly * A mutation rate (a real number between 0.0 and 1.0), initialized randomly * An energy (a real number), initialized as half of the reproduction threshold * A current URL, initialized with an element of the root set There are numerous spiders, each of which repeats the following algorithm: Download the document d for the current URL Calculate the vector IR-model similarity s of the keyword list and d Train the neural network to predict s from the link wich led to d Increase the energy by s Decrease the energy by a fixed cost value if energy >= reproductionThreshold && numSpiders < maxNumSpiders Reproduce Set the energy of the new spider to half of my energy Divide my energy by 2 Take a random value between 0.0 and 1.0 If the random value is below the mutation rate Mutate the new spider: Identify the least useful keyword by help of the neural network Replace it by an index term of a document of the root set Readjust the neural network Add some small random values to the weights of the neural network Set the mutation rate to a random value between 0.0 and 1.0 else if energy < 0 die be the current URL the link in d with maximum estimated usefulness according to the neural network The InfoSpiders learn to select links, which lead to desired documents. Following links decreases the energy, but hitting a desired document increases the energy. Successful InfoSpiders reproduce and the others die out. InfoSpiders are more successful than a page rank based search, but both are less successful than best first web retrieval. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Recommandation ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -------------------------- MAUT -------------------------------------- Item: An available entity. Filtering, Recommandation: The process of finding an item, which fits best to the wishes of a user. Attribute: A concrete unary property. // This definition is rather vague. "concrete" means that the // property applies only to entities of a specific concept and // not to too many super-concepts. Example: "hasTennisField" may be the attribute of those hotels, which have a tennis field hasTennisField(hotelBelleVue) says that hotelBelleVue has a tennis field Utility dimension: An abstract unary property, desired or not desired by a human. In the following model, utility dimensions and attributes are distinct. Example: "sportiness" may be a utility dimension of hotels Attribute-Utility-Weight: The function r, which takes an attribute and a utility dimension and returns a real value between 0.0 and 1.0. This value is the degree, to which the presence of the attribute entails the presence of the utility dimension. r(attribute, utility) = degreeOfEntailment Examples: r(hasTennisField, sportiness) = 0.8 r(hasGolfField, sportiness) = 0.2 Attribute evaluation: The function a, which takes an attribute and an item and returns the degree to which the item has the attribute. Example: a(hasTennisField, hotelBelleVue) = 0.9 Utility evaluation: The function v, which takes an item and a utility dimension and returns the degree, to which the item fulfills the utility dimension. v(item, utilityDimension) = SUM {r(attribute, utilityDimension) * a(attribute, item) | is an attribute } This function is the bridge from the concrete attributes of an item to the abstract utility dimensions. User interest: A pair of a desired concept and a fuzzy set of utility dimensions (the "importance set"). The desired concept designates a thing which the user would like to find. The importance set specifies for each utility dimension how important it is for the user that the thing fulfill the utility dimension. Example: concept: hotel utility dimensions: sportiness (0.5) cheapness (0.4) culture (0.1) MAUT, Multi-Attribute Utility Theory: The following idea for recommandation: Be a user interest given For each available item of the desired concept, calculate SUM { v(item, u) * importance(u) | u is a utility dimension } recommand the item which gets the highest value. This algorithm first calculates how much the available entities fulfill the utility dimensions (by the utility evaluation function). These values are then weightened by the importance which the utility dimensions have for the user. One existing MAUT system is MAPPA (Multimedia Access through persistent personal agent (some acronyms are really awful)). This is an agent, which recommands wines by MAUT. ------------------------ Content-based recommendation ---------------- Text categorization: Given a textual description of an item and a set of categories, determining the category which the item belongs to. Example: Textual description: "She is sneezing and coughing, but has no fever" Categories: Well, Cold, Allergy Text categorization can be used to recommand web-sites basing on a textual description of what the user seeks. Naive Bayes text categorization: The following machine learning approach to text categorization: Assume that the textual description is a set of properties {p1,p2,...}. Example: textual description: {sneeze, cough, no fever} Assume a random space, in which the basic events are all possible pairs of a set of unary properties and a category. Example: basic events: { ({sneeze, cough}, allergy), ({sneeze, no fever, cough}, allergy), ... } Each of these basic events has an unknown probability. The goal is to determine the most likely basic event with a property set matching the textual description. Assume that a set D of basic events is given as correct categorizations. Example: D = { ({sneeze, cough}, cold), ({cough, fever}, allergy), ... } Now define a random event for each category as the set of all basic events in which the category appears. Define a random event for each property as the set of all basic events, in which the property appears. Example: The random event for the category "cold": c = { ({sneeze, cough}, *cold*), ({cough, fever}, *cold*), ... } The random event for the property "sneeze": p={ ({*sneeze*, cough}, cold), ({fever,*sneeze*}, allergy), ... } We want to find the category c for which P(c | p1 /\ p2 /\ ...) is maximal. This value is equivalent to P(c /\ p1 /\ p2 /\ ...) / P(p1 /\ p2 /\ ...) Since the nominator is constant, we need to maximize = P(c /\ p1 /\ p2 /\ ...) = P(p1 /\ p2 /\ ... | c) * P(c) = P(p1|c)*P(p2|c) * ... * P(c) We need to estimate each component separately: Estimate P(c) by the number of times which the category c occurs in D: P(c) = |{ (d,c) | (d,c) in D }| / |D| Estimate P(p|c) for a property p by P(p|c) = P(p /\ c) / P(c) = |{(d,c) | (d,c) in D and p in d}| / |{(d,c) | (d,c) in D }| Now we find the category c, which maximizes PRODUCT { P(p[i]|c) } * P(c) Naive bayes text categorization is machine learning, because it computes an output (the category) for a previously unknown input (the description). It "learns" on the basis of the set D. Content-based recommandation: Recommandation of documents based on the content of the documents. Content feature of a document: A datum associated to the content of the document. A content feature can for instance be an index term in the document. Adaptive content-based recommandation: Recommandation, which learns the user's wishes while the user interacts with the recommandation computer system. The user chooses and retrieves documents as she/he needs them. In the meantime, the recommandation system observes the user's actions, indexes the chosen documents and uses machine learning to learn distinguishing desired documents from non-desired ones. This can for instance be done by a neural network, which learns to map an index term vector to a real number estimating the user preference. This information is then used to classify documents and to recommand new documents. Contrary to collaborative recommandation, the user does not have to specify explicitly her/his wishes, since they are inferred automatically from the user's actions. Advantages: * No cold-start or sparsity problem, since there is no need for data from other users * No first-rater problem; the approach is able to recommend new and unpopular items to users with unique tastes not shared by any other user. * Explanation of recommendation can be provided by listing content feature that caused an item to be recommended. Challenges: * The content has to be very carefully encoded in terms of meaningful features (e.g. by use of index terms). * Users’ tastes must be represented as a learnable function of these content features. * The approach is unable to exploit quality judgments of other users, unless these are somehow included in the content features Existing Adaptive content-based Recommandation systems are NewsWeeder, Syskill and Webert, LIBRA, Letizia, WebWatcher, WebPersona and AiA. Amazon: A certain web-site used for selling books. LIBRA, Learning Intelligent Book Recommanding Agent: A certain adaptive content-based recommandation computer system for books. The user browses book descriptions of amazon, rates the books on a scale from 1 to 10 and after a few books, LIBRA is able to recommand new books to the user. While the user reads a book description, LIBRA encodes it to a set of content features. It uses very simple book description features, such as author, title and description of the book. After each browsed book description, LIBRA asks the user to rate the book. LIBRA encodes this rating to two categories: "positive" (ratings 1-5) and "negative" (6-10). LIBRA uses naive bayes text categorization to learn categories for content feature sets. The actual numeric value of the user rating contributes as a factor. Basing on these data, LIBRA is able to recommand new books: For each new book description, LIBRA extracts the content features. Then, it calculates the probabilities of belonging to the positive category and the negative category, respectively. The predicted user rating for the new book description is the ratio predictedUserRating(b) := P(positive|b) / P(negative|b) LIBRA sorts new book descriptions according to their predicted user rating and presents the top books as recommandation. Thereby, it can "explain" its rating by listing the books, the ratings of which contributed most to the predicted ratings. ------------------- Collaborative recommandation -------------------- User rating of a sequence S of items: A vector, each component of which stands for an item of S. The component is a large value if the user likes the item and else a small value. The component may also be left undefined. Example: S: computer, car, horses, barbies, hexamol User rating: 10 3 -4 -10 - Vicinity of two user ratings: Their degree of similarity. This may be calculated by the cosine similarity, but possibly also by other functions. The vicinity does not need to be transitive: If A is close to B and B is close to C, then A does not need to be close to C. Notation: w(userRating1, userRating2) Significance function: A function, which takes two user ratings and returns a real number. This number estimates whether it is useful to take into account the vicinity of the two ratings. If two user ratings are very far away, it may be useful to ignore their (small) vicinity all together, because a correlation basing on only a few items may be misleading. Reliability significance: The following significance function: s(x,y) = 1 if m>50 = 1/m if 0 // Use of the name http://www.w3.org/RDF/RDF/description ... DL, Description logic: A subset of first-order predicate logic designed to represent ontologies. A description logic allows definining classes and binary properties. It allows the definition of a class of those entities, which have a certain property. It also allows defining classes as intersections or unions of other classes. The set of these definitions is called the "T-Box". It is also possible to define instances of classes. The set of these definitions is called the "A-Box". Then, a "model" (i.e. the set of facts derivable from the definitions) can be calculated. It is also possible to pose a "query", i.e. to ask for the instances of a class or for subclasses of a class. A description logic may use notations, which differ slightly from the standard PL1-notations. Example: T-Box: man = (and male human) // A man is a male human // man(X) <=> male(X) and human(X) woman = (and female human) human = (or woman man) // humans are men or women // human(X) <=> (man(X) or woman(X)) gender = {m, f} // gender is one of 'm' and 'f' // gender(X) <=> (X=m or X=f) happyParent = All hasChild.Healthy // Happy parents are those with // all children healthy // (All Y: hasChild(X,Y) <=> // healthy(Y)) // => happyParent(X) happyGuy > Ex isWinnerOf.Lotto // The winner of a lotto is happy // (Ex Y: isWinnerof(X,Y) and lotto(Y)) // => happyGuy(X) stressed > >=3hasChild.Young // Having more than 3 young children // is stressy // (Ex C1: hasChild(X,C1) & young(C1)) // and (Ex C2: ...) // and (Ex C3: ...) // and C1!=C2 and C2!=C3 and C1!=C3 // =>stressed(X) happy > =<1has.Problem // We're happy if we have less than // 1 problem // not(Ex P: has(X,P) and problem(P)) // => happy(X) A-Box: (man bob) // Bob is a man // man(bob) Model: (man bob), (human bob), (male bob) Sample query: human Sample answer: bob // This is an invented example. I don't know what description // logics can do or can't do in general, but most of them should // be able to compute the above inference. (?) // For more information on the Description Logic KL-One, see // "Artificial Intelligence" (ai.txt) EER-Schema: A graph, the nodes of which are n-ary relations and classes. The classes are equipped with a set of fields meant to indentify properties of the instances of the class. The links of the graph are binary relations, the cardinalities of which may be given. Thus, an EER-Schema is a form of an ontology. It is possible to translate an EER-Schema to a Description Logic. ----------------------- XML ----------------------------------------- XML, eXtensible Markup-Language: A set of 3 markup-languages designed by the W3C. XML is used to represent any type of information in a human-readable way. Information in XML is distributed on 3 files, which all have the same name, but different extensions: * a file containg the layout (XSL) * a file containing the actual data (XML) * a file containing the structure (DTD) Each of the files is written in one of the XML markup-languages. The key concept is that the markup-language of the data file is very liberal, such that any type of information can be encoded. It is the structure file, which defines the tags actually used in the data file. The tags in all 3 markup-languages follow the same pattern: text where the '<', '>', '=' and '/'are part of the markup-language. XML supports namespaces and allows defining abbreviations for them. If XML is to be used as a global data exchange format, the tags defined in the structure file have to be agreed on globally. This is not the case. // XML requires an immense amount of declarations and of // repetitions of these declarations, making it very clumsy to // type by hand Domain, Document type definition, DTD: The markup-language of XML used for the structure file. This file defines the tags used in the data file. Example: The tag "" defines a data file tag "seller", which is followed by a tag "name". XML-data definition: The markup-language of XML used for the data files. The actual tags used depend on the document type definition. Example: Bob Style sheet language, XSL: The markup-language of XML used for the layout file. XML specification, XML Domain ontology: A DTD-file used for several XML data files. An XML domain ontology defines a common terminology for a set of XML data files. Several domain ontologies are being developed, among others CBL (Common Business Library), cXML (Commerce XML), OCF (Open Catalog Format), OFX (Open Financial Exchange), RosettaNet, UN/SPSC, UCEC, OSD (Open Software Description Format), CDF (Channel Definition Format), MathML (for mathematical formulae), SMIL (Synchronized Multimedia Integration Language), TEI (Text Encoding Initiative), NITF (for news articles), CML (for chemicals), AIML (for astronomical instruments). Notation: "-file" for "an XML-file following the specification" RDF, Resource Description Framework: A certain XML specification. RDF was developed because XML lacks formal semantics. RDF provides a framework, which allows to encode any type of information into * "resources" A resource is an entity being described. It is given by a URI. * "atomic values" An atomic value is a string. * "properties" A property is a binary relation from resources to other resources or to atomic values, ie. property =< resource x (resource \/ atomicValue) Thus, an RDF-file can be seen as a graph, the nodes of which are resources and atomic values. The links are properties. A RDF-file can also be seen as a set of triples of the form (resource, property, resource|atomicValue) A typical RDF-file looks as follows: // Namespace definitions ... // Begin // State a resource // List all properties of this resource // List a property p pointing to a resource

// List a property p pointing to an atomic value x

x

 There exist several programs, which can read RDF-documents, among others SiLRI (Simple Logic-based RDF-Interpreter), SiRPAC (Simple RDF Parser and compiler), IMB's RDF, Perl RDF:Parser. Semantic Web Language: A markup-language, the tags of which have a counterpart in a Description Logic. Thus, a document is given "meaning" in that strings in the document have a counterpart in a description logic ontology. This can allow a computer to "understand" what is written in a web-site. This may enable it to answer questions of the user. Example: Web-site: Bob, Clara // define students T-Box: student < human // student(X) => human(X) Sample query: human Sample answer: Bob, Clara // This is an invented example, which might not match exactly // the actual state of the art. Semantic annotation: The use of a semantic web language for a web-site. RDF Schema, RDFS: A certain extension of RDF to a semantic web language. An RDF-Schema-file can define * classes * the subclass-relation * the instance-relation * properties * constraints on these properties, especially their range and domains RDF Schema can be used to describe classical RDF properties and resources. It can establish "meaning" (in the sense of interrelations) for RDF properties and resources. RDF as well as RDFS can be seen as a subset of first-order predicate logic without the closed world assumption. RDFS ontology engineeering: The design of the RDFS ontology. This work is done by a number of domain experts, which discuss and implement concepts in RDFS. RDFS import: The use of an external ontology in an RDFS ontology. This can be done by the XML namespace mechanism. In this way, work of other ontology designers can be re-used in any RDF document. RDFS allows the import of various formats, notably XML Schema and Dublin Core. RDFS query: A question expressed in RDFS. An RDFS query may ask for a specific resource or property. There are programs which can find the desired entity in an RDFS ontology, eg. RQL. Semantic Web Vision: The idea that web-sites might get "meaning" by use of * Unicode and URIs as the basis of web-sites * RDF and RDFS as a semantic anotation for the web-sites * a large set of RDFS ontology terms agreed on by everybody * a description logic for RDFS * proof mechanisms for the description logic This could enable a computer to "understand" what a human seeks and to provide common sense answers to her/his questions. OIL, Ontology Inference Layer: An extension of RDF to a semantic web language, developed in 1999 in Europe. DAML: A semantic web language developed in 2000 in the USA. DAML+OIL: The combination of DAML and OIL, created in 2000. DAML+OIL allows expressing all definitions of a Description logic, including classes, properties, properties of classes and restrictions on properties. DAML+OIL can either be RDF-like or DL-like, here is an RDF-like example for the definition of the class male /\ human: // Ie we need 6 lines to express a simple intersection of // classes... OWL, Ontology Web Language: A successor of the RDF-like variant of DAML+OIL, created by the W3C in 2004. Ie OWL is a specification for XML-files. The tags have direct counterparts in a description logic. OWL is totally compatible with RDF. OWL is undecidable, i.e. it is not always possible to calculate whether a certain fact follows from the ontology. Limitations: * OWL has the unique name assumption, which is not realistic in the web. * OWL does not have the closed world assumption. As a result, non-monotonicity is not possible. * Composition of properties ("chaining") is not allowed (?) * It is not possible to define properties by methods ("procedural attachment"). * The decidable part of OWL is computationally expensive, i.e. it may take exponential time to compute a fact in an OWL ontology. OWL-DL: A restricted version of OWL, which is decidable. Ie. It is possible to decide whether a certain fact follows from an OWL-DL ontology. Contrary to OWL, OWL-DL prohibits the treatment of classes as instances (?). OWL-Lite: A restricted version of OWL-DL, in which inferences can be computed in polynomial time. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Services ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ // This part addresses services, the names and parameters of which // are fixed and known. -------------------------------------------------- Basics ---------- // For superficial further information on internet programming // with Java, see "Computer Science C" (infoc.txt) Internet data: Data provided on the internet. Internet data sources are extremely heterogenous. They include relational databases as well as web-sites or other types of data. // This data is called "Web data source" in the slides, but the // "web" is only concerned with HTML-documents Service: A method of a computer system, which may be called from another computer. Data service: A service returning internet data. Service provider: A computer system providing a service. Service requester: A computer system desiring to use a service. Client: A computer running a service requester. The "client" is opposed to the "server", which hosts the service provider. Request: A description of a service desired by a service requester. Advertisement: A description of a service provided by a service provider. Thin client: A client running a program, which has most of its work done by the server. Thick client: A client running a program, which does all the work by itself and does not make too much use of the server. Communication: Exchange of data. Session: A filled record storing information about a client/server connection. Persistent connection: A connection between a client and a server, which has a session. As a result, a whole set of subsequent connections may re-use that session and work on the same problem. Server demon: A low-level server program mediating data between high-level server programs and clients. Existing server demons are Apache and Tomcat. // Server demons are also called "Web servers", but this notion // is ambiguous since it also refers to the computers. API, Application programmable interface: A set of method signatures. The API defines how the methods are called and what these methods shall do, but it does not provide the actual algorithms. Implementation of an API: A set of methods corresponding to the method signatures given in the API. Implementations of the same API may differ between computers or operating systems, but the way a method is called and its effect are always the same. Example: The Java API includes the method "System.out.println", which prints a string on the screen. The actual implementation of the method depends on the operating system. RPC, Remote procedure call: The call of a method stored on one computer by another computer. The computer hosting the method receives the call, executes the method, collects the result and sends it back to the caller. ORB, Object request broker: A program, which takes care that an object residing on one computer can be used by a program on another computer. This includes the handling of references to remote objects as well as RPCs. Middleware: A computer system allowing a client program to locate and use a known service. This includes an ORB. ------------------------------------- CGI ---------------------------- CGI program, Common Gateway Interface program: A data service, which receives a client request and returns the answer as an HTML document. A client program asks the server to execute the CGI-program in order to retrieve certain data. The CGI-program accesses the database system on the server, translates the requested data to a HTML document and returns this document to the server. The server forwards the document to the client. Advantages: * Minimal requirements for the client browser, since the returned information is in HTML * Fast and flexible access to a database Disadvantages: * Only one access can be handled per run, as the CGI program does not remember prior accesses (non-persistent) * the CGI program does not have a direct connection to the client program, making it necessary to route huge amounts of data through the server. * CGI programs are difficult to write, since there are no programs supporting their development and since the interaction of server, HTML-document and CGI program can only be verified by trial and error. An example of a CGI program written in a C-like programming language follows. This program prints its result (the HTML-file containing the result of the query) to the standard-out stream: main(){ /* write the body of the HTML-document*/ printf(""); printf("

Result of query:

"); printf("
    "); /* Connect to the database system */ dbprocess = dbopen(login, "Personal_DB"); /* create and send SQL query */ dbcmd(dbprocess, "SELECT name FROM person"); /* bind database result to a program variable*/ dbbind(dbprocess, param1, progvar.name); /* Write the result to the HTML-document */ for(i=0; i<= max_rows; i++) printf("
  • %s
    • ", progvar[i]); printf("
"); /* close connection to database system */ dbexit(); printf(""); } FastCGI program: A CGI program supporting persistent connections. ECMA-Script: A server side program embedded in an HTML-document. The program is executed by the server. (?) Example: (?) Result of Query <%begindetail%> NAME=%FirstName% %Surname% <%enddetail%> ------------------------------------- Java --------------------------- Java Remote Method Invocation, RMI: An RPC with Java methods. RMI enables communication between distributed Java programs. The client program stores a reference to the server object. If the client program calls a method of the server object, a client program part called "Stub" translates the call to a low-level representation. The stub sends this information to the server, where it is received by a server program part called "Skeleton". The skeleton translates the low-level call back to a Java call and sends this call to the object. The result of the call is sent back to the caller on the same way. Applet: A Java program running in the client browser. Servlet: A Java program residing on and executed by the server. As opposed to CGI, an applet/servlet communication is persistent. Any applet/servlet communication bases on the Java RMI. There are several programs supporting the development of applets and servlets, notably JSDK (Java Servlet Development Kit) and the JavaSoft JavaWebBrowser. Example for a servlet: import java.io.*; import java.util.*; import javax.servlet.*; import javax.servlet.http.*; ... /** This method is called if the client desires the HTML-document which this servlet is resposible for */ public void doGet(HttpServletRequest req, HttpServletResponse res) throws ServletException, IOException { res.setContentType("text/html"); //output document type PrintWriter out = res.getWriter(); //output out.println("My servlet"); out.println("This is a servlet action. "); out.close(); } ------------------------------------- Database APIs ------------------ Database API: An API, which offers methods to access database systems. There are different API implementations for different database systems. Although the database systems may provide their services in different forms, the methods defined in the API are always called in the same way and have the same effect. ODBC, Microsoft Open Database Connectivity: A certain database API with its implementations by Microsoft. JDBC, Sun Java Database Connectivity, SQLJ: A certain database API (with its implementations) by Sun for Java programs. If a client Java program wants to access the server database, it has 3 choices: * It may communicate to a servlet. The servlet communicates with the database by JDBC. This allows for a thin client, but increases the work of the server. * It may download an applet, which communicates to the server. The server uses JDBC for communication with the database system. * It may communicate directly to the database system by JDBC. Then, all the work has to be done by the client program (thick client). The JDBC consists of several parts. The "high-level parts" accessed by the Java program are Java-conform. The "low-level parts" concerned with the direct interaction with the database are database-specific. If the database supports ODBC, the JDBC may also forward the requests to the OBDC by a program part called "JDBC-ODBC bridge" or "ODBC gateway". Example for use of a JDBC: import java.util.Properties; import java.lang.Class; import java.sql.*; ... // Load the JDBC API Class.forName("sun.jdb.odbc.JdbcOdbcDriver"); // Gather user account information in a property-object p = new Properties(); p.put("server", hostName); p.put("user", userID); p.put("password",passwd); // Store the reference to the database system in a string String db-url = "jdbc:odbc:Oracle7 tables"; // Open database connection Connection con = DriverManager.getConnection(db-url2, p); // Create and execute SQL query Statement query = con.createStatement(); ResultSet rs = query.executeQuery("DELETE * FROM Branches"); // Close database connection con.commit() ; con.close(); ------------------------------------- JINI --------------------------- Proxy object: A client object representing a server object. If a method of a proxy object is called by the client, a RPC is executed to the corresponding method of the object on the server. The methods of a proxy object usually correspond to the services provided by the server. Lookup-service, LS: A database system for services. JINI: A certain middleware for Java programs by Sun. If a server wants to provide services, it registers these services in the JINI Lookup-service. The server uploads a proxy-object, the methods of which correspond to the services. If a client wants to use these services, it asks the JINI lookup-service for the corresponding proxy object. The proxy object is downloaded to the client. The client uses the services by calling the methods of the proxy object. ------------------------------------- CORBA -------------------------- IDL, Interface Definition Language, Interface Description Language: A way of describing how methods are called. In its simplest form, an IDL document can be an API. CORBA: A certain middleware by OMG. CORBA consists of different components, organized in the "OMA" (Object Management Architecture): * "common object services", i.e. services related to the naming of objects, to security, concurrency, transactions, events etc. (?) * "common object facilities", i.e. a set of objects useful for building programs in different domains. (?) * Domain APIs (?) * Object Request Brokers (ORBs). In CORBA, an ORB is a program residing on one computer and communicating to the ORB on another computer in order to access an object on that computer. For this communication, a protocol following the "General Inter-ORB Protocol" (GIOP) is used, eg. the protocol called "IIOP". This protocol uses the CORBA IDL to exchange information on objects and methods. There exist mappings (functions) from the specifications of the CORBA IDL to a number of programming languages, such that the ORBs can talk about methods independently of the programming language which these methods are written in. Juxtaposition with JINI: * In JINI, the client program communicates in a standardized way (namely in Java) to its proxy object and the proxy object communicates in a server-dependent way to the server. * In CORBA, the client program communicates in a client-specific way to its ORB, the ORB communicates in a standardized way (namely in IDL) to the server ORB and the server ORB commicates in a server-specific way to its server program. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Web Services ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ // This part addresses services, the names and parameters of which // are not known to everybody. Such services are seeked by their // functionality description. -------------------------------------------------- Basics ---------- Web service: A commercial service. Usually, neither the location nor the name nor the parameters of a web service are known a priori. Thus, a web service has to be seeked by matching the request with the service functionality. In nicer words: A web service is a task-oriented, coarse-grained, XML-based business computer system that is internet-accessible via an API from any computer (it is "location transparent") with one or multiple protocols. A web service is registered and located through a Web Service Registry. It may be enlarged with additional descriptive metadata for service consumers, but does not provide any human-centered interface. Web services are mainly designed for processes across enterprises and use common protocols and technologies. Web services shall be used by information agents, which must be able to * locate a service, although different terms may be used for the advertising of the service and the request * execute a service, although the operating system, the programming language and the parameters of the service may differ from the agent's * understand a service, i.e. interpret its result * compose services, i.e. use multiple services to achive one goal Examples for web services: * Reporting Services (e.g. weather information) * Directory Services (e.g. yellow pages) * Manufacturing or Retail Services Web service architecture: The way a web service is designed. Existing web service architectures include SOA, JWS and JSR109. Web service engineering: The creation of web services. Existing programs for the support of Web service engineering include WebSphere, JAXR (Java API for XML registries) and Apache Xerxes 2. Wrapper site: An internet-accessible database system. The data can be of any format. The wrapper site usually provides web services in form of a query language to access the data. It may whish to interact with other wrapper sites, but the heterogenity of the data and the services prevents a direct communication. Port, Binding, Grounding, technical details of a web service: Information on its location, its protocols and its file-formats. Service composition: The execution of multiple services to fulfill a request. Services can be called one after the other with the results of the first being the inputs of the second. -------------------------------------------- Describing services ---- SOAP: A certain protocol for acessing web services. SOAP also contains an XML specification. // The acronym formerly stood for "Simple Object Access Protocol" SOAP message: An XML-document following the SOAP XML specification. SOAP messages are used to represent client requests as well as web service results. A SOAP message consists of several parts: * a SOAPAction HTTP header The header names a method which the HTTP server demon has to execute before processing the rest of the message. Such methods can be used to pre-filter unacceptable requests. * an envelope, which has the following parts * a message header The message header specifies meta-data about the client request or the service result * a message body For requests, the message body contains the name of the service method with values for its parameters. For results, the message body contains the data of the result. * attachment parts Attachment parts may refer to additional files (?) involved in the request or result. Example for Request Message: POST /StockQuote HTTP/1.1 Content-Type: text/xml Content-Length: nnnn; charset="utf-8" SOAPAction: "http://www.nyse.com/customerchecking" 1234 IBM Smith Example for Result: HTTP/1.1 200 OK Content-Type: text/xml Content-Length: nnnn 98.06 Web Services Description Language, WSDL: An XML specification for describing a set of web services and their technical details. A WSDL-file contains * data types This part defines the data types used by the services. This is done by referring to the XML namespaces corresponding to the data types Example: * messages A message defines the signature of a web service, similar to how they are called by a SOAP envelope. A message can also describe a request, a result, or a parameter of a request or result. Example: * I/O-Interface This defines again the signatures of the methods (?) Example: ... * Interaction This part defines the technical details, i.e. the physical location of the methods, how the methods are called and which protocol is used. Example: ... WSFL, Web Services Flow Language: A certain record describing the process of a complex web service. It defines what steps the server and the client have to follow in order to execute a complex web service. A WSFL record consists of 2 parts: * The flow model This is a graph, the nodes of which are "activities". An activity is an action by the server or the client. The links of this graph are "data and control links". They specify which activity follows which other activity. The links may be equipped with "transition conditions", which say when a link may be trespassed. Activities may be * fork activities. These activities have several successor activities. Transition conditions are used to choose the successor in the actual process. It is also possible that all successor activities are to be executed in parallel. * join activities These are activities, which have more than one incoming link. The transition conditions may cause the activity to wait until all preceding activities have been finished ("synchronization"). The graph is much like a control flow graph used for the description of programs. WFSL plug links establish the relation between the activities and the actual methods. * The global model This is a description of the interaction between the client and the server (?). ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Service Mediation ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ // This part describes how to find web services matching a request Service Mediation: The seek of a service satisfying a request. ------------------------------------------- Service Registries ------- Service registry: A data base system for web services. Mostly, service registries support service mediation. UUID, Universally Unique Identifier: A unique name for data. TModel: An XML-specification for XML-files storing a textual description of an entity. Each TModel-file has a UUID. Example for a TModel-file: NYSE getQuote business service Returns stock quotes how to use the service getQuote http://localhost/getQuoteInterface.wsdl Category bag: An XML-file (or part of it) containing a set of category names. These categories are supposed to give semantic information about another XML-file. UDDI, Universal Description Discovery and Integration: A service registry. The database contains 3 types of elements, all of which store a reference to a describing TModel-file, and all of which have a UUID: * White Pages A white page is an XML-document presenting the business, including a business identifier ("key"), the name, a description, contacts and a category bag. A business may offer several web services, as specified in the Yellow Pages. Example: NYSE Services Ltd New York Stock Exchange Service Company ... * Yellow Pages A yellow page is an XML-document presenting a web service, including its name, a textual description and a category bag. It refers to the business, which provides the service, by the UUDI of the business. A web service may be accessed in several ways, as specified in the Green Pages. // There should be some use of WSDL here (?) Example: getQuote Information service on NYSE stock quotes ... * Green Pages/Binding Templates A green page is an XML-document, which gives technical information about a web service, including the actual address of the service. It refers to the web service by the UUDI of the web service. Example: http://localhost:8080 // Seems as if it's just universally unique identifiers, which // universally uniquely identify other universally unique // identifiers.... The UDDI allows service mediation: UDDI ^ ^ find / \ advertise service / \ service / \ Client -----> Server use The UDDI provides the following web services to clients, allowing them to search a registered web service: * find_Business * find_Service * find_Binding * find_tModel Each of these methods takes keywords as parameters. The services are called by exchanging SOAP messages ("InquireSOAP"). Although the methods are called by agents, humans need to verify whether the service description really matches the user interest. If the client found the desired service, it may retrieve the binding information and establish a connection to the business server. Then, it can download a WSDL-description of the service and send a SOAP message to execute it. UDDI does not support the automatic composition of web services. The UDDI also provides web services to servers, allowing them to advertise their business web services. This communication is also done by SOAP messages ("PublishSOAP"). Example for advertising a web service in the UDDI: // Connect to UDDI registry using UDDI proxy object UDDIProxy proxy = new UDDIProxy(); proxy.setInquiryURL("http://www-3.ibm.com/.../inquiryapi"); proxy.setPublishURL("https://www-3.ibm.com/.../publishapi"); AuthToken authToken = proxy.get_authToken("admin", "changeit"); // Create a TModel (type) for WSDL getQuote // service interface description TModel gQI_Tmodel = new TModel(); gQI_Tmodel.setName("NYSE getQuote service interface") // Set name of public web server where the WSDL file // can be accessed OverviewDoc gQodoc = new OverviewDoc(); gQodoc.setOverviewURL("http:/...getQuoteInterface.wsdl"); // Indicate to UDDI that this TModel (type) is for // WSDL service specification CategoryBag cbag = new CategoryBag(); KeyedReference kr = new KeyedReference(); kr.setKeyName("uddi-org:types"); kr.setKeyValue("wsdlSpec"); gQI_Tmodel.setOverviewDoc(gQodoc); gQI_Tmodel.setTModelKey(kr); // Save the TModel in the UDDI registry Vector TModels = new Vector(); TModels.add(gQI_Tmodel); TModelDetail d = proxy.save_TModel(authToken.getAuthInfo() .getText(),TModels); // Save the returned automatically generated key of the // registered TModel gQI_Tmodel = (Tmodel)detail.getTModelVector().elementAt(0); String gQI_TmodelKey = gQI_Tmodel.getTModelKey(); // Define the gQuote business service name BusinessService gQuoteService = new BusinessService(); gQuoteService.setName("NYSE getQuote business service") // Define the gQuote service binding(s) BindingTemplates gQBindings = new BindingTemplates(); BindingTemplate gQBinding1 = new BindingTemplate(); // Define the gQuote service binding(s) AccessPoint gQuoteAccessPoint = new AccessPoint(); gQuoteAccessPoint.setURLType("HTTP"); gQuoteAccessPoint.setText("http://localhost:8080"); gQBinding1.setAccessPoint(gQuoteAccessPoint); gQBindings.getBindingTemplateVector().add(gQBinding1); gQuoteService.setBindingTemplates(gQBindings); // Bind the getQuote service to its proper interface: // Namely as an instance of the registered gQI_TModel with key TModelInstanceDetails gQI_details = new TModelInstanceDetails(); TModelInstanceInfo gQI_instance = new TModelInstanceInfo(); OverviewDoc gQI_instance_odoc = new OverviewDoc(); gQI_instance.setModelKey(gQI_TModelKey); ... gQI_instance_odoc.setOverviewDoc("...getQuoteInterface.wsdl"); gQBinding1.setTModelInstanceDetails(gQI_details); // Finally, publish the getQuote service in the UDDI registry proxy.save_service(authToken, gQuoteService); Example for finding a service: // Get a UDDI proxy object UDDIProxy proxy = new UDDIProxy(); // Find the getQuote service (key) in the registry FindQualifiers fq = new FindQualifiers(); ServiceList list=proxy.find_service(businessKey,"getQuote",fq,0); ServiceInfos infos = list.getServiceInfos(); ServiceInfo info = (ServiceInfo)Infos.getServiceInfoVector().elementAt(0); String serviceKey = info.getServiceKey(); ServiceDetail detail = proxy.get_serviceDetail(serviceKey); // Retrieve technical data on getQuote service from the registry BusinessService service_info = (BusinessService)detail.getBusinessServiceVector().elementAt(0); BindingTemplate template = (BindingTemplate)service_info .getBindingTemplates().getBindingTemplateVector().elementAt(0); TModelInstanceDetails details = template.getTModelInstanceDetails(); InstanceDetails instance = details.getTModelInstanceInfoVector() .elementAt(0).getInstanceDetails(); // Get the path to the WSDL service description document // which includes the detailed interface definition of the // getQuote service OverviewDoc odoc = instance.getOverviewDoc(); String wsdlpath = odoc.getOverviewURLString(); Definition def = WSIFUtils.readWSDL(null, wsdlpath); // Create a reference to the getQuote service Service real-service = WSIFUtils.selectService(def, null, "getQuote"); // Retrieve the getQuote service interface PortType portType = WSIFUtils.selectPortType(def, null, "getQuoteInterface"); WSIFDynamicPortFactory dpf = new WSIFDynamicPortFactory(def, real-service, portType); WSIFPort port = dpf.getPort(); // Create default input, output, error messages for // service invocation WSIFMessage input = port.createInputMessage(); WSIFMessage output = port.createOutputMessage(); WSIFMessage fault = port.createFaultMessage(); // Bind service input to command line arguments WSIFPart symbolVal = new WSIFJavaPart(String.class, args[0]); input.setPart("symbol", symbolVal); WSIFPart customerVal = new WSIFJavaPart(String.class, args[1]); input.setPart("customer", customerVal); // Finally, invoke the service (pre-operation, input, // output, fault parameters) port.executeRequestResponseOperation("", input, output, fault); // And get the service results System.out.print((float)output.getPart("return").getJavaValue()); An existing UDDIs is UDDI4J by IBM. ----------------------------------------- Matchmaker Agents --------- Cooperative Information System: A set of information agents establishing a communication between wrapper sites. Each of these agents has its own view of the world, represented by an ontology. Agent service, agent capability: A service provided by an agent. Such a service may be a data service. ACDL, Agent capability description language: A file format used to describe agent services. Service provider agent: An agent of a cooperative information system, which provides an agent service. The agent advertises this service with its name, the agent's name and its location in ACDL. Resource agent: A service provider agent, which offers the services of a wrapper site. Service request agent: An agent of a cooperative information system, which wants to use an agent service. The service request agent uses ACDL to formulate its request. The agent is usually just a delegate of a more complex computer system or the user, which needs the service. Middle Agent: An agent of a cooperative information system, which does service mediation. The middle agent maintains a database of all known agents and agent services. It uses ACDL matching to find an appropriate service provider for a service requester. The middle agent also guarantees the security and reliablity of the service to the requester. Matchmaker: A middle agent, which hands a ranked list of matching service providers to the service requester. Existing matchmakers include RETSINA/LARKS and IMPACT. Broker: A matchmaker, which hands the service requester to another agent, which does the actual mediation. One existing broker is InfoSleuth. Mediator: A broker with an integrated global information model (?) and distributed query processing (?). A mediator does service mediation between wrapper sites. It knows the terminologies used by the wrappers sites and structures them in ontologies. Existing mediators are TSIMMIS, OBSERVER, SIMS/Ariadne, MIX, XML Broker Agent and MOMIS/MIKS. Mediator's information model: (?) Federated database model: (?) The opposite of the mediator's information model. ---------------------------------- Existing Matchmaker Agents -------- SIMS: A certain mediator. SIMS collects information from all types of wrapper sites, including offsite databases, text sources, local databases, knowledge databases, the web itself and other computer programs. It makes them available to automatic planners, information retrieval systems and decision support systems. SIMS queries the wrapper sites, models the retrieved information in cooperation with a human ("semi-automatedly") and uses machine learning to deduces rules in the information ("knowledge discovery") (?). The result is a description of entities and services (the "Domain Model"). If a service requester posts a request, a plan is made of how to find the requested information, the appropriate wrapper sites are chosen, the plan is optimized by the rules learned and then executed. The result is passed back to the service requester. InfoSleuth: A certain broker. InfloSleut receives a request from an interface agent. The request takes the form of a record, as in this example: Need attributes :: agent name, agent address For agents described by : agent type :: resource content ontology :: TechTracking content language :: SQL data constraints :: "Technology products in central Texas from 1998 to 2000." The service provider agents advertise their services in a similar record, as in this example: agent address ::
agent name :: AustinTechProducts agent type :: resource supported content ontologies :: TechTracking supported content language :: SQL resource description :: "Provision of technology products in the area of Austin, Texas." InfloSleut represents the service advertisements and the request in an internal format. Then, it uses an ontology to match the data constraints of the request with the resource description of an advertisement. Two intermediate agents are used: The "Task Execution Agent" and the "Multi-Resource Agent" (?). XML-based broker agent: A certain mediator. The request comes from an XML-based browser and uses the file format "XQL"("XML query language"). The request is analyzed by an agent (the "XQL Query Processor") and satisfied by a large database of XML-documents (the "XML document Data Warehouse"). This database is updated from the WWW. For this purpose, an agent monitors the WWW (the "Web monitor") and passes new HTML-web-sites to a converter agent (the "JEDI XML-Wrapper"). The converter produces DTD and XML-files from the web-sites and adds these to the database. RETSINA: A certain matchmaker computer system. It handles multiple requests at a time. Each of them has its own set of agents: The request comes from an interface agent and is forwarded to a task agent. The task agent uses a matchmaker to find the appropriate resource agent. While doing so, it collaborates with other task agents. The matchmakers also collaborate. ------------------------------------ Semantic mediation -------------- Distance of two concepts in an ontology: The number of links to be traversed in the ontology to get from the first concept to the second concept. The links in the ontology may be equipped with a real number ("weighted"). Then, the distance is the sum of the weights of the traversd links. Distance of two words in an ontology: The distance of the two denotations in the ontology. If the words have mutliple meanings, compute the distance for all of them and take the minimum. LARKS, Language for Advertisement and Request for Knowledge Sharing: A certain record used to describe services and requests. Its names are * context This is a list of keywords and related concepts * types This is a set of definitions of types, which are used in the following * input This is the input record of the service * output This is the result record of the service * inConstraints This is a set of PL1-formulae, which must hold before the service is called * outConstraints This is a set of PL1-formulae, which holds after the service has been called * concDescriptions This is a set of concept definitions in a description logic. * textDescription This is a string describing the service textually. Example for a record describing a service: // This record describes a service, which returns a list of // military missions which took place in a given time interval Context: mission*AWAC-Mission, attack, air warfare Types: Date = (mm: Int, dd: Int, yy: Int); Mission = ListOf( mType: String, mID: String|Int, mStart: Date, mEnd: Date); Input: Start: Date, End: Date Output: m: Mission; InConstraints: Start <= End OutConstraints: mType = AWAC, deployed(mID), launched_after(mID,mStart), mStart >= Start, launched_before(mID,mEnd), mEnd <= End. ConcDescriptions: AWAC-Mission = (and AirMission (exactly 1 has-airplane) (all has-airplane aset(E-2))) TextDescription: "This service returns information (type, id, period) on deployed AWAC air missions that are launched in a given time interval." Example for a record describing a request: Context: Attack, Mission*AirMission Types: Date = (mm: Int, dd: Int, yy: Int); Mission = ListOf(mType: String, mID:String|Int, mStart: Date, mEnd: Date); Input: sd: Date, ed: Date; Output: missions: Mission; InConstraints: sd <= ed. OutConstraints: deployed(mID), launched_after(mID,sd), launched_before(mID,ed), sd >= mStart, ed <= mEnd. ConcDescriptions: AirMission = ... TextDescription: "information on deployed air combat missions launched in a given time interval" LARKS registry: A certain service registry basing on LARKS. It maintains a data base of service descriptions and receives a request from a request agent. It uses the following algorithms to compute the similarity of a service description and a request description: * Context Matching Take an ontology. Mostly, WordNet is used, enriched by some further relations. For all keywords in the context of the service compute the ontology distances to all keywords in the context of the request. For all concepts in the context of the service, compute the ontology distances to all concepts of the context of the request. * Profile Matching Compute the vector space IR-model simlarity of the two text descriptions. That is: Find index terms for the text descriptions, calculate the index term vectors and determine their cosine. Furthermore, calculate and sum up the word distances of all words appearing in the input-, output- and constraint- declarations. * Signature Matching Do the following first for the Input declarations and then for the Output declarations: For each record name in the service, compute the similarity to the record names in the request. For each record data type in the service, compute the similarity to the record data types in the request. Similarity of data types can be computed by help of software engineering data bases. Basically, a data type is similar to another one, if it is a superset or subset of the other one. Try to match the record entries of service and request. * Constraint Matching Check whether the Inconstraints of the request imply the Inconstraints of the service, i.e. RequestInConstraint1 and RequestInConstraint2 ... => ServiceInConstraint1 and ServiceInConstraint2 ... This means that the constraints guaranteed by the request are stronger than the ones desired by the service. Then, check whether the OutConstraints of the service imply the OutConstraints of the request. This means that the service satisfies the request. The implications are called "eta-subsumptions". If both implications hold, one says that the request "plug-in matches" the service. The algorithm computes the similarity of each service description to the request description and returns a ranked list of service provider agents. The user may choose which matchings are actually performed: * complete matching performs all matchings * relaxed matching omits the signature matching * profile matching does only the profile matching * plug-in matching does the signature matching and the context matching only Semantic mismatch: A pair of words, which have the same or similar meanings, but are not identical. Semantic mismatches may cause problems for service mediation. Examples: * Semantic Mismatch at the Content Level Provider returns value Pennsylvania, but requester only understands two letter state codes (i.e. PA) * Semantic Mismatch at the Attribute level Requester needs rainfallbut provider provides precipitation * Semantic Mismatch at the level of Units Requester has value in inches, but provider requires cm * Semantic Mismatch at the Input/Output level Requester has length and width, provider requires area Semantic mismatches could be solved by ontological knowledge. OWL-S: An extension of OWL to describe services. Since OWL-S bases on OWL, we have the following hierarchy of XML specifications: OWL-S OWL RDFS RDF An OWLS-S-file consists of 5 parts * an introduction, which refers to the other parts Example: * Resource (describing the service provider) * Service Profile (describing the service itself, sb.) * Service Model (describing the process of a service use, sb.) * Service Grounding (describing technical details) OWL-S can be used * as a file format for service registries and for service mediation * as classification schema for real-world products * to augment service requests * to establish industry ratings to denote quality guarantees * to describe security parameters * to describe contract parameters Juxtaposition with WSDL: * WSDL cannot specify service preconditions and effects * WSDL does not give an ontological description of the service, but just a technical one Juxtaposition with the principles of UDDI: * UDDI matching of advertisements and requests is based on keywords only * OWL-S could be a language candidate to be used on top of UDDI * UDDI descriptions still need to be interpreted by humans, whereas OWL-S allows agents themselves to "understand" what the service is about. * UDDI does not support service process model descriptions and hence it does not support automatic composition of services. Questions for OWL-S: * Shall the Service Model also be used for semantic mediation or just the Service Profile ? * How can the quality of the mediation be measured and guaranteed? * Shall the mediation be done at the time of the request or shall possible matches be calculated in advance? (On-line vs off-line use of same OWL ontology for matching of service request and advertised service) * Shall translation-functions for different OWL-ontologies be calculated during the request or in advance? (On-line vs. Off-line computation of mappings between different OWL ontologies of service request and advertisements) * How shall the system react if a service involved in a service composition stops existing? OWL-S Service Profile: The part of an OWL-S-file, which describes what the service does. The profile can be used to advertise the service in a service data base and for service mediation. The service profile consists of three parts: * a description of the service provider ("actor") with contact details (the "Provenance description"). Example: BravoAir Bravo@Bravoair.com Airstrip 2, Cliff Heights, FL http://www.daml.org/s/BAir.html 412 268 8780 412 268 5569 * a description of what the service does (the "Functionality Description"). This includes a human-readable description of the service as well as a LARKS-like description with Inputs, Outputs, Preconditions and Effects. Inputs and Outputs are concepts of an OWL-ontology and thus "understandable" to agents. Example: BravoAir_Agent This service provides flight reservations based on the specification of a flight request. This typically involves a departure airport, an arrival airport, a departure date, and a return date. Departure Airport ... * additional information about the service ("Service Attributes"). This includes a geographical scope, quality descriptions, service types and average response times. Example: Service process: A method called during the execution of a service. The service is split into a set of service processes, which are invoked one after the other, depending on the algorithm of the service. Processes may call other processes. Each process has a WSDL-description. OWL-S service model: The part of an OWL-S-file, which describes the service process. The service model can be used to facilitate automated service invocation, to allow service composition and to coordinate the actions of different agents. The service model states whether the service is atomic (ie has just one process) or composite. Example for an atomic service model: Example for a composite service model: OWL-S Service Grounding: The part of an OWL-S-file, which describes techical details. This includes protocols, transport mechanisms, agent communication languages and file formats. These details are specified by referring to a WSDL-document. Example: http://www.winisp.net/cheeso/books/books.asmx?WSDL http://www.winisp.net/cheeso/books/LookyBookServiceSoap http://www.winisp.net/cheeso/books/DoKeywordSearch http://www.winisp.net/cheeso/books/DoKeywordSearchSoapIn http://www.winisp.net/cheeso/books/keyword http://www.winisp.net/cheeso/books/DoKeywordSearchSoapOut http://www.winisp.net/cheeso/books/DoKeywordSearchResult .... Example for the corresponding WSDL-file: ... (?) http://www.winisp.net/cheeso/books/LookyBookServiceSoap http://www.winisp.net/cheeso/books/DoKeywordSearch .... Retrieves an array of bookInfo (author, title, isbn) given a keyword. OWLS/UDDI-Matchmaker: A matchmaker using UDDI with OWL-S-files for the description of services and requests. The service provider advertises its web services by a WSDL-description and a OWL-S-description. The service requester uses OWL-S to ask the OWLS/UDDI-Matchmaker for a service. The OWLS/UDDI-Matchmaker uses the techniques of the LARKS registry to find a matching service and returns both the OWL-S-description and the technical details as usually stored in the UDDI. For the matching, the matchmaker compares the Outputs of the advertisement (these are concepts) to the Outputs of the request. It distinguishes 4 types of situations, with decreasing usefulness: * exact match The provided concept and the requested concept are identical or the requested concept is an immediate subconcept of the provided concept. * plugIn The requested concept is a non-immediate subconcept of the provided concept. * Subsumption The requested concept is a superconcept of the provided concept. * Failure If none of the above cases applies. Using these criteria, it is tried to match each requested concept with a provided concept. The overall usefulness of the service for the request is the minimum of these matches (with exact match > plugIn > subsumption > failure). This implies that if only one requested concept is not provided, the service dropped. If two services are equally useful, the inputs of the service and the inputs of the request are compared similarly -- but with swapped roles: The inputs of the request may be less restrictive than the inputs of the advertisement. Example for a service request in OWL-S: Price Toyota_Corolla Juxtaposition with LARKS: * LARKS offers five different types of matching filters including the only one of the OWLS/UDDI-Matchmaker * LARKS requires the provided concept to be a subconcept of the requested concept (I want a vehicle, so you may give me a car. But if I want a car, don't give me (any) vehicle). By contrast, the OWLS/UDDI matchmaker accepts superconcepts (I want a car, so you can give me a vehicle) but punishes non-immediate superconcepts (I want a car, so prefer not to give me any device) // OWLS/UDDI behaves quite counterintuitively... * LARKS does not have a defined semaqntics, but operates on words. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Rational Agent Coalitions ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ // For Rational Agent Coalitions, the slides are not that useful: // Some formulae are ill-formed or not well-typed and some conditions // and explications seem to miss. Search on the internet did not help // too much, since each author has her/his own notions and // definitions. So here are mine, which seem to be consistent with // the slides and are equipped with a nation-metaphor: ---------------------- Basics ----------------------------------------- Gain: A real number measuring usefulness. The gain can be thought of as measured in Euros or Dollars. Player: An agent, which wishes to gather gain. Coalition in a set S of players: A subset of S. Grand coalition in a set S of players: The coalition S. Coalition structure of a set S of players: A partition of S. Its elements are coalitions. Formed coalition of a coalition structure: One of its elements. Local value: A function mapping a player and a coalition to the gain, which the player gets if the coalition forms. The local value is the "personal brutto income" of each player. Notation: worth(Agent,Coalition)=RealValue Coalition value: A function mapping a coalition to the sum of the local values of all players in the coalition: v(Coalition) := SUM { worth(a,Coalition) | a in Coalition } The coalition value is the sum of all "brutto incomes" or the "wealth" of the "nation" formed by the coalition. In the following, the coalition value is seen as fixed and atomic. It is assumed that v(Coalition) >=0 for all possible coalitions. Furthermore, it is assumed that by default all singleton coalitions are gainless: v({x}) = 0 This fact plus the fact that coalitions do have positive values mirrors the fact that the value of a group can be greater than the sum of the values of its members. Payoff: A function mapping each player to a gain. Notation: u(Agent) := RealValue Feasible payoff in a coalition strcuture P: A payoff, such that the sum of the payoff values in a coalition is not larger than the value of the coalition: For all C in P: SUM {u(a) | a in C} =< v(C) The payoff is a "redistribution" of the "wealth" of the coalition. The payoff is the "netto income" for each player, decreased by taxes and increased by subsidiaries. Some taxes may get lost. Cooperative game: A pair of a finite set S of players and a coalition value for S. Notation: (S,v) Allocation of a cooperative game (S,v): A pair of a coalition structure for S and a feasible payoff for this coalition structure. Notation: (P,u) Stable allocation, Solution of a cooperative game: An allocation of this game, in which no player has an incentive to leave its coalition. What this means exactly depends on the used theory is and defined in the following. Games and their solutions are used to * Negotiate access to pay-per-use data and services in cooperative information systems * Maximize individual bargains on free e-markets * Completely decentralize power transmission planning Dynamic cooperative game: A cooperative game, where non-deterministic changes may occur during the coalition forming process, such as * the information on used data, knowledge, network, and user environment of each player, and the system as a whole * the tasks to be accomplished, and availability of computational resources * players hiding, entering or leaving the game at any time Dynamic cooperative games have been applied for dynamic resource allocation planning of cereal harvesting in the agricultural domain (AGRICOLA). Super-additive cooperative game: A game (S, v), where the union of two coalitions has a higher value than the sum of the single coalition values: For all disjoint coalitions C1, C2: v(C1 \/ C2) >= v(C1) + v(C2) In this case, the grand coalition of all players is the optimal solution. Sub-additive cooperative game: A non-super-additive cooperative game. Ie there are two coalitions, the union of which has a smaller value than the sum of the single coalition values: There exist disjoint coalitions C1, C2: v(C1 \/ C2) < v(C1) + v(C2) // Other authors say that, in sub-additive games, the inequality // must hold for *all* coalitions. Essential cooperative game: A game (S, v), such that there exist two coalitions, the union of which has a larger value than the sum of the single coalition values: There exist disjoint coalitions C1, C2: v(C1 \/ C2) > v(C1) + v(C2) Hence a super-additive game is essential. Symmetric players of a game (S,v): Two players x and y in the game, which bring the same gain to any coalition: For all coalitions C: v( C \/ {x} ) = v( C \/ {y} ) Desirable player for a coalition C: A player x, which increases the coalition value: v(C \/ {x}) > v(C) Hence each player is desirable in a super-additive game. // The definition in the slides is somehow unclear, since the // variables are not quantified Efficient payoff of an allocation (P,u): Its property that For all C in P: SUM {u(a) | a in C} = v(C) Ie no "taxes" get lost, the whole "wealth" of a "nation" is distributed to its members. For efficient payoffs, it holds in singleton coalitions that u(x) = v({x}) if {x} in P Social welfare of an allocation (P,u): The sum of all payoff values. For efficient payoffs equivalently: The sum of all coalition values of coalitions in P. SocialWelfare((P,u)) = SUM {u(x) | x in UNION P} = SUM {v(C) | C in P} if u efficient The social welfare measures the "wealth" of the "player world" as the sum of the wealths of all nations. Individual rationality of an allocation (P,u): Its property that each player has a payoff at least as big as it would have on its own: For all players x: u(x) >= v({x}) This reflects the "egoism" of each player, which only joins a "nation", if its personal "netto income" increases. It is supposed that every allocation taken into consideration is individually rational. If the value of singleton coalitions is 0, then group rationality holds anyway. Group rationality of an allocation (P,u): Its property that the social welfare is at least the coalition value of the grand coalition: SUM {u(p) | p in S} >= v(S) // Slides: "=" where S=UNION P is the set of players. It reflects "responsibility" of the players for the "world" of all players: Assume that group rationality is postulated. If we have a payoff with player x getting a big piece of the cake, then player x would give up this piece of cake, when it sees that a grand coalition would be more reasonable for the world -- even if its piece of the cake might shrink. In a super-additive game, the grand coalition is the one with optimal social welfare (=v(S)) and it is group rational. If another solution can be found, which is also group rational, then it is an optimal alternative. In a super-additive game, group rationality implies individual rationality. Pareto-optimal payoff for a coalition structure P: A payoff u, such that no player can get more payoff without another player getting less: There is no feasible payoff u' for P, such that There is a player x in UNION P, such that u'(x)>u(x) and For all other players y in (UNION P)\{x} u'(y)>=u(y) // The formulae in the slides are probably wrong: a' is bound, but // never used. A coalition structure with pareto-optimal payoff is not necessarily the one with a maximum social welfare! Locally pareto-optimal payoff in a set L of players for a coalition structure: A payoff, such that no player in L can get more payoff without another player in L getting less. Coalitional rationality of a solution (P,u): Its property that the sum of the payoffs within any subset of players is at least the coalition value of this subset: For all C== v(C) where S=UNION P is the set of players Ie there is no other possible "nation", which could guarantee its players more nation-wide wealth. Coalitional responsibility reflects a kind of "responsibility" for all other possible ally players. Coalitional rationality implies group rationality (with C=S). ---------------------- Core stability -------------------------------- Core of a coalition game (S,v): The set of those allocations, which have coalition rationality: Core((S,v)) = { (P,u) | For all C =< S : SUM { u(a) | a in C } >= v(C) } This is the set of all those allocations, in which the players show "responsibility" for potential ally players. It takes exponential time to determine the core. The core is not unique and it may be empty. Example for an empty core: Be S={a1,a2,a3}, v({a1,a2})=90, v({a1,a3})=80, v({a2,a3})=70, v({a1,a2,a3})=105. Look at all possible coalition structures P: P={{a1},{a2},{a3}} With singleton coalitions having value 0 and hence payoffs of 0 any real coalition has a higher value => not a core P={{a1, a2}, {a3}} Assume a fair distribution of the coalition value in {a2, a2} with u(a1) = u(a2) = v({a1,a2})/2 = 45 Then the coalition C={a2, a3} looks more attractive to a2 and a3, it prevents P from being in the core: u(a2)+u(a3) = 45 < v({a2,a3})=70 But if we increase u(a2) to 70 to make a2 stay with a1, we have to decrease u(a1) to 20. Then, the coalition {a1,a3} looks more attractive to a1 and a3, it prevents P from being in the core: u(a1)+u(a3) = 20 < v({a1,a3})=80 P={{a1}, {a2, a3}} Similarly P={{a1, a3}, {a2}} Similarly P={{a1, a2, a3}} Assume a fair distribution of the coalition value with u(a1) = u(a2) = u(a3) = v({a1,a2,a3})/3 = 35 Then the coalition {a1,a2} looks more attractive to a1 and a2: u(a1) + u(a2) = 70 < v({a1,a2})=90 But any change in the payoffs makes other coalitions more attractive => P is not in the core Core-solution of a coalition game (S,v): An element of the core of (S,v). The core-solution maximises social welfare for any subset of players, but it is exponentially hard to compute and eventually non-existant. Transfer, Sidepayment: A change in the payoff of an allocation (P,u), while still keeping the payoff feasible. Usually, this is done by the following schema (Stearns): u(x) := u(x) + alpha u(y) := u(y) - alpha where alpha is a real value and x any y are in the same coalition Ie player y gives agent x a part of its payoff-value. Often, sidepayments are iterated to obtain a solution for the game. // The same-coalition condition is not stated in the slides, I // just suppose it. Transfer schema for Core-stability: The following transfer u(x) := u(x) + (v(C) - SUM {u(y) | y in C}) / |C| where C=eps({c| c in P, x in c}) is the coalition of x in P This transfer makes a payoff feasible and efficient. After all players are updated, the coalitions are changed. // How (?) If this scheme is iterated, it converges towards a core-solution. ---------------------- Shapley stability ----------------------------- Shapley value in a coalition game (S,v): The function mapping a player x to the real number sv(x) := SUM { (|S|-|C|)!*(|C|-1) / |S|! * (v(C) - v(C\{x})) | C is a subset of S } This number simultaneously reflects * the importance of the player in the grand coalition. * the gain which the player contributes to the grand coalition * the fair payoff which the player should get when it joins the grand coalition The formula expresses the gain, which the coalition gets by absorbing x v(C) - v(C\{a}) and averages it over all possible orders, in which the players could join one after the other the grand coalition. The Shapley-value exists and is unique. // ...as already demonstrated by its property of being a function The Shapley-value can be used as a payoff distribution. Then it is the only payoff distribution for the grand coalition, which satisfies * symmetry Two symmetrical players get the same Shapley-value * individual rationality Each player gets a higher payoff than it would get if it formed a coalition on its own. * group rationality The sum of the payoff values equals the gain of the grand coalition * efficiency The whole coalition value is distributed to its players The Shapley-value is exponentially hard to compute. Shapley-solution of a cooperative game (S,v): The allocation ({S},sv) ie the grand coalition with a payoff given by the Shapley-value. The Shapley-solution provides a fair payoff based on the contributions of the players to the grand coalition, averaged over joining orders. Coalition algorithm: An algorithm executed by each player in a cooperative game in order to find a solution of the game. Usually, the coalition values are unknown and are computed from the sum of the local values. The algorithm can be interpreted as having the players "negotiate" in a decentralized way about how to distribute the value of a coalition as payoff among the members. // For more information about algorithms executed by multiple // computers simultaneously, see "Parallel and Distributed // Algorithms" (pda.txt) SCA, Shapley Coalition Algorithm: The following coalition algorithm, leading to a Shapley-solution for a set S: Calculate v({x}) Calculate worth(x,{y}) for all other players y Communicate these values to all other players Compute the coalition value for each possible coalition C: v(C) = SUM { worth(y,z) | y in C, z in C } - (|C|-2) * SUM {v({y}) | y in C} Since the "worth" includes the personal productivity v({y}) of each player y, the sum contains this value multiple times. It needs to be subtracted in the end. Calculate the Shapley-value sv(x) Calculate what x should receive as sidepayment. This is the difference of what x *should* get (Shapley value) and what x actually *does* get (local value): sv(x) - worth(x,S) Take the Shapley-value as a payoff-distribution and form a grand coalition. Ie form the solution ({S}, sv) If a player has a negative sidepayment (ie. its actual gain (local value) is greater than what it should get (Shapley-value)), then it pays the difference into a big pot. Players with positive sidepayment are paid from this pot. The SCA takes exponential time: for n agents, it requires O(2^n*n^2) calculation steps and O(n^2) communication steps. ---------------------- Bilateral Shapley stability ------------------ Bilateral coalition: A singleton coalition or a union of two disjoint bilateral coalitions. Founder of a bilateral coalition: One of the subcoalitions, which composed the bilateral coalition. The founders of each bilateral coalition are stored with the coalition. Bilateral coalition structure: A coalition structure of bilateral coalitions. BSV, Bilateral Shapley-value of a bilateral coalition C: A function mapping a founder C1 of C to BSV[C](C1) := (v(C) + v(C1) - v(C2)) / 2 where C2=C\C1 is the second founder of C // The formula in the slides is more complicated, // but equivalent. It seems as if both formulae are only // valid for top-level (formed) coalitions C The Bilateral Shapley-value of a founder is its "superiority" compared to the other founder, moved towards the value of the resulting coalition. The sum of the bilateral Shapley-values of a bilateral coalition is equal to the coalition value: BSV[C](C1) + BSV[C](C2) = v(C) Recursive BSV-payoff: The payoff u for a bilateral coalition structure P with BSV[C](C1) := (v(C) + v(C1) - v(C2)) / 2 if C in P BSV[C](C1) := (BSV[C0](C) + v(C1) - v(C2)) / 2 if C not in P where C0 is the (non-formed) coalition co-founded by C u(x) := BSV[C]({x}) where C is the (non-formed) coalition co-founded by {x} Thus, one looks at the resulting coalition structure P. One calculates the coalition values v(C) for all formed coalitions C in P. Then one uses the BSV to distribute v(C) among the two founder coalitions of C. Each founder coalition c gets its share BSV[C](c). Then, one proceeds recursively and distributes each founder coalition's share to its founder coalitions, again according to the BSV. This continues until one reaches the singleton founder coalitions. The BSV of these is their payoff. Properties: * Efficiency The whole coalition value is distributed to its players * Individual rationality for super-additive games Each player gets more than it would get on its own. * Non-essential players get no payoff A player, whose contribution to a bilateral coalition is 0 does not get any payoff. // The formula in the slides produces a type mismatch * Symmetry Coalition founders with an equal value get an equal payoff. The BSV takes polynomial time to compute. Equal BSV-payoff: The payoff u for a bilateral coalition structure P with u(x) := v({x}) + (BSV[C](C[i]) - SUM {v({y}) | y in C, y!=x}) / |C[i]| where C is the formed coalition of x and C[i] is the founder of C, which contains x (i=1 or i=2). This payoff takes the value of a formed coalition, distributes it with the BSV among the two founder coalitions and then gives each player in the founding coalition an equal share. It is taken care that each player x gets at least its self value v({x}). Properties: The same as for the Recursive BSV-payoff. BSV-solution of a coalition game: An allocation with an equal or recursive BSV-payoff. BSCA, Bilateral Shapley-value algorithm: The following coalition algorithm, which starts from an allocation of singleton coalitions and leads to a recursive BSV-solution: Vote for a player of my coalition C as a leader If the leader of C is me For all other coalitions C' in the coalition structure Communicate with the leader of C' Receive their value v(C') Send our value v(C) Compute BSV[C\/C'](C) as the expected profit for a bilateral coalition with C' Sort all coalitions C' in a list according to the expected profit BSV[C\/C'](C) Send offers to all coalitions C', starting from the first in the list If a coalition C*\/C is accepted by both me and the leader of C*, form this coalition and tell all other coalitions about it. Calculate the coalition value of C\/C*, distribute it according to the BSV to the players Repeat this algorithm until we have a grand coalition The BSCA leads to a grand coalition and guarantees the properties of the recursive BSV-payoff. It is computationally much less expensive than the SCA, it takes polynomial time: O(n^3) steps for computation and O(n^2) steps for communication with n players. ---------------------- Kernel stability ------------------------------ Excess in an allocation (P,u): A function mapping u and a coalition to the difference of the coalition value and the accumulated payoff of its members: e(C,u) := v(C) - SUM {u(x) | x in C} // In the slides, C is written where C' should be written // Furthermore, the function is restricted to non-formed coalitions, // which is an unnecessary limitation. For formed coalitions and efficient payoffs, the excess is 0. But for non-formed ones, it measures their potential attractivity. Surplus in an allocation (P,u): A function mapping a pair (x,y) of players to the maximum of all excesses of non-formed coalitions with x and without y: s(x,y) := MAX { e(C,u) | C is a subset of UNION P, C not in P, x in C, y not in C } The surplus measures the attractivity for player x to get rid of player y. Player outweighting another player y in an allocation (P,u): A player x, such that s(x,y) > s(y,x) and u(y) > v({y}) // Seems to be swapped in the slides, compare // f-icmas96 paper by Klusch This means that x could be happier without y. Equilibrium pair, Balanced pair of players in an allocation (P,u): A pair (x,y) of players in a formed coalition, where none of them outweights the other: s(x,y) = s(y,x) or (s(x,y) > s(y,x) and u(x) = v({x})) or (s(y,x) > s(x,y) and u(y) = v({y})) Ie there is no potential (non-formed) coalition with one of the players and without the other, where the former gets more payoff than it does at the moment. The idea is that a player is more worthful than another, if it could get more without the other than the other could get without the first. Equilibrium coalition, Balanced coalition in an allocation (P,u): A coalition in P, in which every pair of players is balanced. Balanced allocation, Equilibrium allocation for a cooperative game: An allocation, such that all coalitions are balanced. Kernel of a cooperative game (S,v) for a coalition structure P: The set of all those allocations (P,u), which are balanced. The Kernel exists and is unique for any 3-player cooperational game. Kernel solution of a cooperative game (S,v): An element of the kernel of (S,v) for a given coalition structure. Ie in each coalition no player can outweigh another player by having the option to get a better payoff in an alternative coalition without the opponent player. Properties: * Symmetry Players making the same contribution to a coalition get equal payoff * Local pareto-optimality Calculating the kernel takes exponential time. If the size of the coalitions is limited to a constant, the computation becomes easier (polynomial). Problems of kernel solutions: * Problem of interpersonal comparison of an utility for the whole set of players (?) * In a coalition algorithm for a kernel solution, the players negotiate, but not all players may be contended (?) Kernel-Sidepayment for an allocation (P,u): The following sidepayment for player x from player y: s := MIN { (s(x,y)-s(y,x))/2, u(y)-v({y}) } if s(x,y)>s(y,x) 0 else u(x) := u(x) + s u(y) := u(y) - s If player x outweights player y, two conditions hold: s(x,y) > s(y,x) and u(y) > v({y}) The MIN-term seeks the sum to be paid from y to x in order to destroy the condition, which is the cheapest to destroy. Approximate Kernel-Sidepayment for an allocation (P,u): The Kernel-Sidepayment for (P,u), which only takes place if the relative error re(u) := MAX {s(x,y)-s(y,x) | x and y are players in P} / SUM {u(x) | x is a player in P} is above a threshold epsilon. Kernel Coalition Algorithm, KCA: The following coalition algorithm, which starts with an allocation (P,u) and leads to a kernel solution: Be x this agent and C this agent's coalition in P Calculate my worth(x,C') for all coalitions C' in P Vote for a coalition leader of my coalition If I am the leader of my coalition C For each coalition C' in P Use the approximate Kernel-Sidepayment to calculate a new payoff, which balances the coalition C\/C' If the new payoff augments the social welfare in C and C', propose the coalition to the leader of C' Evaluate incoming proposals Accept the proposal maximizing the social welfare in C Form the new coalition and tell the other leaders about it The algorithm takes exponential time: O(n*log2(re(u)/epsilon)*n*2^n) steps. ---------------------- Other games ---------------------------------- Fuzzy coalition value: A function mapping a coalition to a fuzzy set on the real numbers. Cooperative game with fuzzy-valued coalitions: A pair of a set of players and a fuzzy coalition value. Fuzzy coalition: A fuzzy set on the set of players. Cooperative game with fuzzy coalitions: A coalition game, the allocations of which provide fuzzy coalitions. Stochastic cooperative game: A cooperative game, in which the players can perform actions, which give a certain payoff with a certain probability.