Recent Changes · Search:

en pl

Functional Programming

Type Inference

Toss

  • (incorporates former Speagram)

Emacs

Kurs Pascala

Artificial General Intelligence

AI: Artificial Intelligence lab

Algorithmic Game Theory: Prediction Markets (po polsku)

Programming in Java

kurs pracy w systemie Linux

Evolutionary Algorithms

Animation

Data Stores and Data Mining

Language Understanding

Systemy Inteligentnych Agentów

Przetwarzanie Języka Naturalnego

Programowanie Funkcjonalne

PmWiki

pmwiki.org

add user

edit SideBar

SI /

SI

en pl

Interesting news on the page:

Labs and projects:

  1. Lab on Bayes Nets Dependence modeling trails (online course from Helsinki)
  2. Lab on Bayes Nets 2:
  3. Rules for small projects scoring
    1. For the basic version you can get at most 15 points (for a nice report with attached sources: programs, experiment scripts, datasets etc. — sent by mail or pointed by url).
    2. One extension is enough to score the maximum 20 points for a small project (the work needs to deserve it to score max, I’m not tough on it though). If you implement more extensions, the better.
    3. Additional extensions may serve as the large project. The work for the large project should be at least about three times the work for a small project (counting only what goes beyond what you have submitted as a small project).
    4. Lots of proposed extensions come in two flavors: “theoretical” (propose an idea, a plan) and “practical” (code it down). For a small project, the theoretical variant is definitely enough; it might even suffice for the large project for some extensions.
    5. You may find it worthwhile to read all proposed variants of projects.
    6. Grading requirements:
      • You need two small extended projects without considerable flaws (scoring the maximal 20 points each) or three basic projects (40/3=13 points each) to have chances for the 5.
      • You need two basic projects without considerable flaws (the maximal 15 points each) or three mediocre projects (30/3=10 points each) to have chances for the 4,5.
      • You need two mediocre projects (2*10=20 points) or a single extended project without flaws to have chances for the 4,0.
    7. Don’t wait until the last minute, you have more opportunities to score more points if you turn your projects earlier.
    8. You can negotiate to turn in partial results for the large project as a small project. But then the large project is graded based on further work.
    9. If a project has several basic variants, then they are also extensions — when doing more than one basic variant, the other is counted as extension.
  4. Belief networks project: variants
    1. Data Mining. Find the structure of the network from data, using one of available tools.
      1. Basic version: find in the internet a dataset for a subject that interests you and/or which you understand. Interpret the dependencies in the resulting net (like, look at their strength, do they imply causal dependency, is the causality obvious). Describe results of several queries to the network (that is, probability distributions for some variables with set values for some other variables): are they intuitive, is there some “explaining away”, etc.
      2. Extension 1: collect the data yourself. You can acquire it from some application by logging its data. You can build a deterministic model for some process (only the input variables will be random) but leave out some input variables from statistical modelling (which will introduce additional stochastic dependencies).
      3. Extension 2: express the knowledge about the problem as constraints (hard, and perhaps also soft), or as an initial belief network. Compare the result acknowledging this information with a structure found without prior knowledge (with, in some sense, a uniform prior).
      4. Extension 3: enrich the network, e.g. by introducing different types of nodes (e.g. true continuous, discrete but not simply tabulated), or unobservable variables.
    2. Acquisition and representation of knowledge. Build the belief network manually (its structure and parameters).
      1. Basic version: build a simpler network (case a) or import a network found in the internet (case b). Describe the dependencies in the network and several queries to the network (just as in the project Data Mining).
      2. Extension 1: build the network by performing an interview with a preson that is knowledgeable in the problem analyzed; it’s good if that person is not a computer science student. Place a fragment of the talk with that person into the report.
      3. Extension 2: design (and perhaps also implement) a data collecting regime for the use of the model, and a periodic update of the model parameter (and perhaps structure); you might need a tool that allows for unobservable variables in training data. Consider the trade-off between the preservation of the prior knowledge and the tracking of experience due to collected data. Try to use the old model directly, e.g. as the a priori parameters for the Dirichlet distributions. If the tool doesn’t allow it, consider generating samples from the prior model; but this can result in sampling artifacts. Examples of data collection:
        • If the model is used for prediction, the user can later tell, what really happened.
        • If the model supports decision making, then the user can valuate the decision made.
        • If the evidence in the queries to the model is observed (i.e. not hypothetical), e.g. they are the sympthoms of a disease in a patient, then register, or log, them; a good model between the sympthoms can spare on diagnostic tests. Additionally, epidemic information can be mined from the data, etc.
      4. Extension 3: enrich the network structure (like in the extension 3 for the project Data Mining): nodes of type other than discrete tabulated, hidden variables etc.
    3. Decisiontheoretic heuristics in search and in games. Build a belief network with a decision node/nodes and a value/reward/utility/cost node; see Basic Decision Making with Bayes Nets. The domain of the model should be a search problem (one-person game) or a two-person game.
      1. Basic version: “Environmental” variables are the search or game state parameters. Decision variable(s) provide parameters for the state transition operator (they represent actions). The state of the game can decide, which variables are observable when the model is used (e.g. the consecutive decisions of players in a limited moves game, like poker or black jack). Some variables can be not observable when the model is used, but be easily available for training (e.g. the next move of the opponent).
      2. Extension 1: instead of building a model from intuition or finding it in the internet, implement a data generator, and learn the model from the generated data. In the data, substitute for the variable “heuristic” the estimated distance from a solution (by the shortest of actually found paths), or the sample probability of winning (what fraction of games that pass through the given state ended with winning). In the generator, you can use the best available heuristics to speed up the generation and achieve better data quality.
      3. Extension 2: propose / implement model update mechanism, to be applied during the match or after several matches.
      4. Extension 3: propose / implement a search or game strategy, which will not aim at reward maximization, but at information gain maximization, so that the model can be updated well.
        1. Extension 4: propose, using the Bayesian Reinforcement Learning theory, an optimal action selection mechanism, taking into account that a good model update will improve the maximization of reward.
  5. Lab on statespace search
  6. Lab on constraints and on games
  7. Project on heuristic search and games: the set of exercises
    1. Finding a path in a dynamical environment: code an agent to go from a source to a goal in case, where the map at its disposal is not exactly the reality, or if the reality changes over time.
      1. Basic version: we have a case similar to the one dealt with in the lab: searching for a path on a two-dimensional arena. But we are working with two maps: a map fully available to the algorithm and an arena, which will be made available to the algorithm only for the cells neighboring with the agent (immediately, or within some radius); the algorithm should memorize the required information. Minimise, from more to less important: the amount of agent steps taken, the amount of computation per step, the amount of computation before the first step. Suggested algorithms: “Adaptive A*”, “Real-Time Adaptive A*”, “Proritorized Learning Real-Time A*”.
        • Looking at it differently, the agent has access to complete information about the arena, but there are new obstacles popping up on the arena.
      2. Extension 1: if in the basic version you made available to the agent only the cells directly neighboring the agent, now introduce a broader scope of vision. Case (1a): introduce failing observations: special cells that look like passable, but when entered turn out to be obstacles. Case (1b): introduce variable goal: in the arena the goal can turn out to be in a different place than on the map (the agent must observe the false target to realise that), but not far from the map’s target.
        1. Extension 2: slowly moving target: when the agent approaches the target, the targets starts to move away.
      3. Extension 3: consider “opportunities”, cells that are obstacles on the map but are passable on the arena. Suggested algorithms: “Lifelong Planning A*”, “D*”, “D* Lite”.
        • In case the agent has full knowledge of the arena, the arena can change with time.
    2. Heuristics Design: solve (write a solver) using the A* algorithm one of puzzles from the Budapest Competition.
      1. Basic version: select one that you like, e.g. Hiroimono or Divide into Squares
      2. Solve another puzzle. Compare the heuristics you have built,: what ideas they share, and what is puzzle-specific?
      3. Extension 2: first solve the puzzle algorithmically (that is, by devising a puzzle-specific solution algorithm) case a, or with constraints (case b), and only then solve it using A*. How have you transformed the algorithm into the heuristic?
    3. Sokoban: solve (write a a solver) using the A* algorithm, the puzzles of Sokoban.
      1. Extension 1 — strategy vs. tactic: divide the solver into two layers. On the strategic layer, use A* to search in the space of tactically important states, where a single action requires several steps of barrel pushing. On the tactical level, implement a mechanism to find important states reachable from a given state, where the path is a single “abstract” action of the strategic level. The tactic layer should be able to play the game from the abstract-action path found by the strategic layer (e.g. remember the pushes associated with each abstract action). Example: # is a wall, * is a barrel, only the end positions are important:
        #*#    # #     # #     # #
# #    #*#     # #     # #
# #    # #     #*#     # #
# #    # #     # #     #*#
      2. Extension 2: use constraint solving/programming to in coding the tactic level.
      3. Do not propose to the strategic level dead configurations, like with blocked barrels:
        **      #*
###      #
        Discover the dead configuration using a general mechanism rather than by hand-coding concrete cases: for example, by using constraint solving, or with a local A* search — limited to pushing a barrel around.
    4. Time-delimited Games. Real-Time Games.
      1. Basic version (a): implement a two-player game letting two different algorithms / sets of parameters play against each other.
      2. Basic version (b): implement an alpha-beta pruning algorithm so that it stops computation and returns the best move found so far, when it rounds out of “wallclock” time.
      3. Extension 2: propose / code a modification of — e.g. — alpha-beta pruning so that it worked in the limits of clock time on the entire game. If the sum of times spent on selecting a move by a given player exceeds this time, that player loses. You can simplify assuming, that a player “thinks” only during its move (when you do not want to use multithreading). The algorithm can see the times spent by the other player, playing with the same limit. Decide reasonably what portion of the time left to spend on the next move (try experimenting).
      4. Extension 3: code concurrent asynchronic players: each algorithm can make several moves in a row if the other player still computes its move. The rules of the game need to be interpretable in this case. If the games somehow stagnates, the players can propose a draw.
      5. Extension 4: propose / code a reasonable way to administer the time to compute a move in the context of extension 3, e.g. experiment with different strategies.
    5. General Game Playing. This exercise is not assigned to a particular deadline. You can submit it as from the later set.
      1. Basic version, option (a): Run the GGP system: the game server and clients, or connect a player to a running server (compile an existing player).
      2. Basic version, option (b): Formalize one of your favorite computer games, perhaps in a simplified version, in Game Description Language.
  8. Lab on games 2: refinements and heuristics
  9. The last set of projects: plan-space planning, rule engines / production systems, expert systems, agents, reinforcement learning, structured data sets: “relational learning”.
    1. Learning expert system. Perhaps you know the Twenty questions quiz. Perhaps you have even implemented it in the old times, a program guessing a word and building a decision tree, grown by asking the player “How would you ask to distinguish my answer from the thing you thought about?” Write an expert system being an improved version of such game. The system can have many uses, like in diagnostics.
      1. Basic version: write a Twenty questions game-inspired program that learns as above. Use forms with comments so as to acquire from the user well formed words-things to guess and “yes/no” questions about features of the considered thing. Instead of building the decision tree, for each known thing and each known question remember the answer: yes / no / unknown (when the question was not yet asked for that thing). When guessing the object, start from the set of all known objects. Select questions to quickly narrow the current set of objects considered (e.g. when restricted to the considered set, the question has as many “yes” as “no” answers). Discard the objects that disagree with the answer, but keep the objects with answer “unknown”. Record the questions of the system and the answers of the user, in order to update the answers from “unknown”, and also detect conflicts in knowledge (which means, that the player won, but perhaps by cheating).
      2. Extension 1: create and use association rules. Initially use only infallible rules: discard rules with at least one counterexample. An association rule says that when answers a set of (one, two, three, four, …) questions are as given, then an answer to yet another question will be as given. You can use one of the known algorithms for (Association rule learning). During the inquiry, as soon as a rule “fires” (its premises agree with the questions asked so far), test the question from its conclusion: if it was answered already differently, remove the association rule, if it was not answered, […]
      3. Rozszerzenie 2: wykorzystaj również zawodne reguły asocjacyjne, uwzględnij zarówno oszacowanie prawdopodobieństwa reguły (\frac{#(!X \wedge !Y)}{#(!X \wedge ?Y)} dla reguły X \Rightarrow Y, gdzie #!X zlicza, ile razy X jest prawdziwe, a #?Y zlicza, ile razy Y jest znane) jak i jakość tego oszacowania (jak często X jest znane oraz jak często Y jest znane gdy X jest prawdziwe).
      4. Rozszerzenie 3: zbuduj odpowiednio dużą bazę wiedzy dla jakiejś praktycznej dziedziny zastosowania systemu eksperckiego, wykorzystując “human computation”: zbuduj system, w którym wielu użytkowników może grać w twoją grę (i być wykorzystywać ją do rzeczywistej diagnostyki), działając na wspólnej bazie wiedzy. Możesz np. zaprogramować serwer http i odpowiedniego klienta.
    2. System ekspercki w zmiennym środowisku. Zaprogramuj w Soar (lub być może w CLIPS) system ekspercki uwzględniający, że obserwacja może wpływać na badany obiekt (może być de facto interwencją), oraz że badany obiekt jest procesem — zmienia się w czasie, z czasem ujawnia dodatkowe informacje.
    3. Programowanie indukcyjne. Typy algebraiczne (czyli warianty, sumy rozłączne produktów typów algebraicznych) dają bardzo wygodny sposób reprezentacji danych strukturalnych. Podejmiemy ambitne zadanie z maszynowego uczenia się: indukcję funkcji, czyli będziemy konstruować jak najoszczędniejszą funkcję, która dla zadanych danych wejściowych wygeneruje zadane dane wyjściowe. Zapoznaj się z artykułem Markusa Mottla Using Algebraic Datatypes as Uniform Representation for Structured Data, w szczególności z rozdziałem Generalizing Decision Tree Learning to Algebraic Datatypes i dokończ moją prototypową implementację funind.ml Δ.
      1. Wersja podstawowa:
        • Napisz test-zastosowanie (odpowiednik akapitu (* *** example *** *) z pliku źródłowego).
        • Wprowadź obsługę sytuacji, gdy dane nie opisują funkcji (tzn. gdy tym samym argumentom przypisane są różne wyniki — obecnie program wysypuje się wtedy).
        • Dopisz obsługę gałęzi domyślnych “ _ → “. Patrz: paragraf 3.3 artykułu.
        • Dopisz normalizację “lewej strony” (patrz paragraf 3.1.2 artykułu).
      2. Rozszerzenie 1: Rozszerz algorytm o obsługę zmiennych liczbowych (zapoznaj się z odpowiednimi mechanizmami budowy drzew decyzyjnych).
      3. Rozszerzenie 2: Możesz zmierzyć się z problemem indukcji funkcji rekurencyjnych.
    4. CLIPS i Sokoban.
      • Schemat projektu: zrealizuj projekt Sokoban z drugiej listy w języku CLIPS lub Soar.
    5. Agent 001. Zapoznaj się z tutorialem 2 (i być może również 3) do systemu Soar.
      1. Wersja podstawowa: zaprogramuj rozszerzenia programu “Eaters” zaproponowane na końcu tutoriala 2: punkty 1, 2, prosty mechanizm dla punktu 3.
      2. Rozszerzenie 1: zaprogramuj bardziej zaawansowany mechanizm dla punktu 3, punkt 4.
    6. Agent 002. Zapoznaj się z tutorialami 2 i 3 do systemu Soar.
      1. Wersja podstawowa: zaprogramuj rozszerzenia programu “SoarTanks” zaproponowane na końcu tutoriala 3: punkty 1, 2, któryś spośród punktów 3–5.
      2. Rozszerzenie 1: zaprogramuj punkty 1–5 (czyli o dwa więcej niż w wersji podstawowej).
      3. Rozszerzenie 2: zaprogramuj dodatkowo punkty 6 i 7.
      4. Rozszerzenie 3: zaprogramuj dodatkowo punkt 8.
    7. A* real-time beam search. Zaprogramuj algorytm A* z ograniczeniem na rozmiar frontu przeszukiwania (ang. “search fringe”), ale nie poprzez wyrzucanie stanów które się nie mieszczą i dalsze przeszukiwanie, a poprzez podjęcie decyzji co do kroku do podjęcia optymalnie względem posiadanej informacji (tzn. podjęcie akcji na ścieżce do najlepszego według A* stanu) i odrzucenie stanów których ocena była oparta na wybraniu innej ścieżki.
      1. Wersja podstawowa: Zaprogramuj algorytm kontrolujący agenta na bazie A* z następującą “pętlą główną”: przeszukujący aż do wypełnienia bufora “frontu przeszukiwania”, a następnie podejmujący akcje tak długo aż zwolni się miejsce we “froncie przeszukiwania”.
      2. Rozszerzenie 1: Zaprogramuj ten algorytm w systemie Soar w zgodzie z jego “filozofią”.
      3. Rozszerzenie 2: Zaprogramuj sytuację testową, w której opłaca się mniej planować wprzód przed rozpoczęciem działania i pomiędzy akcjami: np. współzawodnictwo agentów w “czasie rzeczywistym”, zmienne środowisko. Porównaj algorytm z tego zadania z algorytmem który po prostu wykonuje ustaloną ilość kroków algorytmu A* pomiędzy akcjami.
    8. Reinforcement Learning oraz zastosowanie systemów reguł produkcji do programowania agentów: Soar.
      1. Wersja podstawowa: Zapoznaj się z tutorialem RL w systemie Soar. Rozszerz agenta Eaters lub SoarTanks tak, aby wykorzystywał uczenie ze wzmocnieniem.
        • Rozszerzenie: Zademonstruj, że agent rzeczywiście z czasem (dzięki uczeniu ze wzmocnieniem) zdobywa coraz więcej punktów.
    9. Reinforcement Learning oraz zastosowanie systemów reguł produkcji do programowania agentów: RL-Competition i CLIPS.
      1. Wersja podstawowa: Zapoznaj się z dziedzinami Reinforcement Learning Competition 2009, zainstaluj oprogramowanie (kopia lokalna Δ). Wybierz jednego z dostępnych agentów i zapoznaj się z jego kodem źródłowym: C++ helicopter; Java mario, octopus, tetris; Python acrobot; Matlab tetris; (jest też dostępny interfejs dla Lispu ale nie ma dużego przykładowego agenta). Uruchom tego agenta i zademonstruj jego działanie.
        • Rozszerzenie 1: Zastosuj dla tego agenta uczenie ze wzmocnieniem (zaimplementuj wybrany algorytm). Zademonstruj, że agent rzeczywiście z czasem (dzięki uczeniu ze wzmocnieniem) zdobywa coraz więcej punktów.
        • Rozszerzenie 2: zanurz CLIPS i oprogramuj w nim inteligentne zachowanie twojego agenta (może nie mieć związku z uczeniem ze wzmocnieniem).
    10. Planowanie w przestrzeni planów.
    11. Statistical Relational Learning. System Alchemy. Modele graficzne którymi zajmowaliśmy się na pierwszej liście zadań wyrażały jedynie własności obiektów i zależności pomiędzy własnościami pojedynczego obiektu. W języku logiki byłyby to predykaty jednoargumentowe oraz formuły z jedną zmienną: da się je wyrazić w rachunku zdań. Alchemy pozwala wyrażać formuły pierwszego rzędu, relacje wiążące wiele obiektów i zależności pomiędzy tymi relacjami.
      • Schemat projektu: zrealizuj w Alchemy wybrany projekt z pierwszej listy zadań, ale z naciskiem na możliwości Alchemy których nie dają zwykłe sieci przekonań (sieci bayesowskie). Możesz np. wykorzystać skomplikowaną bazę danych z wieloma tabelami.
      • Literatura: 10-803: Markov Logic Networks (Machine Learning Department, Carnegie Mellon University)
  10. Pracownia Soar
    1. Soar Home
  11. Pracownia CLIPS
    1. CLIPS Home
  12. Pracownia Soar 2, uczenie ze wzmocnieniem
    1. Omówienie systemu Soar Δ (odp Δ)
    2. AGI/RL.pdf Δ
  13. Pracownia systemy bogate w wiedzę 1: wnioskowanie, Cyc, OpenCyc, Texai
    1. Cyc 101 Tutorial
      1. all PPT slides
    2. Foundations of Knowledge Representation in Cyc (Stephen Reed) OpenCycTut.pdf Δ
    3. Learning to Reason Knowledge Acquisition in Cyc (świetna prezentacja!)
    4. Indukcja, abdukcja.
    5. Parsowanie i generowanie języka naturalnego.
    6. The Texai English Bootstrap Dialog System
  14. Pracownia systemy bogate w wiedzę 2: RDF, SPARQL, OWL, DBpedia, Freebase
    1. RDF (Primer, Concepts, Syntax, Semantics, Vocabulary, and Test Cases) i SPARQL
      • RDF dostarcza struktury danych i narzędzi do przechowywania wiedzy, ale również zrębu ontologii do jej ustrukturowania
      1. SPARQL Tutorial przy Java Semantic Web framework Jena
      2. Innym enginem Javy do pracy z RDFami jest Sesame
    2. OWL2, OWL Features, OWL Guide, OWL Reference
      • Dopiero OWL dostarcza trochę semantyki dla wiedzy: zrąb ontologii zależności pomiędzy relacjami oraz narzędzia do wnioskowania.
      • OWL wprowadza ograniczenia na wyrażalność, by umożliwić szybkie wnioskowania (logiki deskryptywne). OWL 2 jest bardziej ekspresywny niż OWL-DL. OWL Full to wariant bardziej zgodny z RDF Schema, “nieznacznie” wykraczając poza logiki deskryptywne.
      • Solvery dla DL, Bossam: rule engine dla OWL
    3. DBpedia, DBpedia Project website to po pierwsze: Wikipedia przerobiona automatycznie na bazę RDFową, ma m.in. wstępy do wszystkich artykułów w kilku językach w tym po polsku, kategorie oraz infoboxy; po drugie: ma ambicję agregata ontologii dla LinkedData (ontologia samej DBpedia jest płytka, “organizuje infoboxy”)
      1. Dostęp do DBpedii
        1. LinkedData pozwala dobrać się do pojęcia poprzez http, np. http://dbpedia.org/resource/Busan, http://dbpedia.org/resource/The_Lord_of_the_Rings (zwraca jako RDFy “/resource/” lub jako html dla przeglądarki “/page/”)
        2. końcówka SPARQL, np. People who were born in Berlin before 1900
          • SPARQL jest poszerzony o “text search”, przydatne m.in. do abstraktów (wstępów artykułów)
        3. Download
      2. Integracja z innymi źródłami: zwróć uwagę na “owl:sameAs” oraz “dbpprop:wordnet_type”, np. http://dbpedia.org/page/Air_France
        • Integracja z (Open)Cyc
        • “owl:sameAs”=“is owl:sameAs of” (równość jest symetryczna), ale DBpedia i Freebase nie przeprowadzają wnioskowania; proste wnioskowania można zakodować jako kwerendy SPARQL
      3. Publikacje, wczesne blogi:
    4. Przeszukiwanie internetowych baz RDFowych: watson, Swoogle, razorbase, DBpedia URI Lookup
    5. Freebase (from Metaweb)
      • Freebase jest rozszerzana przez zarejestrowanych użytkowników jak Wikipedia, ale użytkownicy nie mogą modyfikować istniejących fragmentów (żeby nie zepsuć aplikacji — kompatybilność), co pogarsza jakość i zwiększa redundancję.
      • Kiepska (nieprzemyślana) obsługa negacji i braku wiedzy.
      1. Using the Query Editor
        • Metaweb Query Language Reference Guide
        • Patrz od strony 31.
        • Metaweb używa reprezentacji grafowej podobnej do RDF (ale swojej własnej przestrzeni nazw), z tym że po prawej stronie strzałki jest węzeł i/lub wartość, zamiast węzła lub wartości tak jak w RDF (czyli mamy czwórki a nie trójki).
        • MQL pozwala nie tylko czytać, ale też wstawiać do bazy (jak SQL).
        • MQL używa JSON.
        • Pola bez wartości w zapytaniu to odpowiedniki zmiennych wzorca.
        • Mocno bazuje na metaforze obiektu (hmm… JavaScrit?), pole “id”:null przechwytuje identyfikator obiektu (“subject” czyli pierwszy element trójki/czwórki).
          • Obiekt może mieć wiele identyfikatorów.
        • Są “dzikie karty” dla atrybutów, oraz operator inwersji biorący wartość i zwracający atrybut obiektu o tej wartości.
        • Inne więzy niż równość na atrybucie: “date_of_birth<” : “2000″ (od strony 78)
        • Wiele konstrukcji, ale nie mogę znaleźć zmiennych!
      2. Query Editor
      3. Freebase RDF (Linked Data)
      4. Przykładowa aplikacja: Sets (jej kod źródłowy)
      5. Download: Freebase Data Dumps
Edit · History · Print · Recent Changes · Search · Links
Page last modified on June 16, 2009, at 01:45 PM