Пользователь
0,0
рейтинг
16 октября 2012 в 13:33

Разное → Как я решил потихоньку учить питон, а попал в дебри CS188.1x Artificial Intelligence из песочницы

Привет Хабр, или введение


image

Расскажу свою небольшую предысторию.

Как то в очередной раз надоело ковырять очередной контроллер, схему и pcb, и удрученный средней по рынку зарплатой рядового электронщика решил — хочу опять в программисты.

Не могу сказать, что я уже был в программистах, но образование получил 3 года назад по специальности «Информационные системы и технологии» в Военмехе. А судьба занесла в схемотехники-электронщики еще во времена универа. Раньше спасали частые командировки на объекты (пока молод и холост — интересно), а последний год все окончательно надоело.
Читая Хабр, выбрал себе Python.

Эти первая вторая недавние статьи помогли определится как и что начинать.

Собственно, по рекомендации и начал в начале сентября с изучения: Марк Лутц. Изучаем Python, 4-е издание. Стиснув зубы и сжав в кулак все что сжималось — на остатке мотивации дочитал до 803-й страницы, сделав попутно все упражнения. На середине ООП меня скрючило окончательно. Книга хороша, но муторна — нет сил.

Просто бросать не хотелось, и дальше попробовал курс Google’s python class. Ух, как же классно оказалось решить финальную задачку! Два вечера пролетели за мгновенье.

Тут я понял, что дожимать через силу книгу, возможно не лучший вариант. И вспомнил, что видел пост про курсы западных университетов. Раньше останавливало знание разговорного английского, но ведь Ника Парланте я же понял!

Сказано — сделано, и вот я уже записан на два курса. Про первый уже писали тут, про второй — тут. А то, что в одном python 2.7, в другом 3.2 — еще и лучше, подумалось мне. После дотошного Лутца первые 2 недели обоих курсов щелкнулись как орешки. Отдельное спасибо progress bar за мотивацию. И кликая по ссылкам был найден он — CS188.1x: Artificial Intelligence. Что пишут?

PREREQUISITES
  • Programming
    1. Object-Oriented Programming
    2. Recursion
    3. Python or the ability to learn Python quickly (short referesher provided)
  • Data Structures
    1. Lists vs. Sets (Arrays, Hashtables)
    2. Queuing (Stacks, Queues, Priority Queues)
    3. Trees vs. Graphs (Traversal, Backpointers)
  • Math
    1. Probability, Random Variables, and Expectations (Discrete)
    2. Basic Asymptotic Complexity (Big-O)
    3. Basic Counting (Combinations and Permutations)



Классно! Вспомню матан, потренирую своего маленького пока еще питона, и ничего что курс идет уже 2ю неделю.

Полная программа курса
Introduction to AI
  • Overview
  • Agents: Perception, Decisions, and Actuation

Search and Planning
  • Uninformed Search (Depth-First, Breadth-First, Uniform-Cost)
  • Informed Search (A*, Greedy Search)
  • Heuristics and Optimality

Constraint Satisfaction Problems
  • Backtracking Search
  • Constraint Propagation (Forward Checking, Arc Consistency)
  • Exploiting Graph Structure

Game Trees and Decision Theory
  • Decision Theory
    Preferences, Rationality, and Utilities
    Maximum Expected Utility

  • Game Trees and Tree-Structured Computation
    Minimax, Expectimax, Combinations
    Evaluation Functions and Approximations
    Alpha-Beta Pruning

Markov Decision Processes (MDPs)
  • Policies, Rewards, and Values
  • Value Iteration
  • Policy Iteration

Reinforcement Learning (RL)
  • TD/Q Learning
  • Exploration
  • Approximation

Conclusion and Wrap-Up
No Lecture, Final Exam Week


Первое столкновение с действительностью

Расскажу про курс подробнее. Вводная лекция произвела очень благоприятное впечатление. Приятно говорящий (а главное, не бородатый!) дядька, хорошо оформленные слайды (потом узнал, что над картинками трудился отдельный дизайнер). Лекции записаны из реальной аудитории, слышно реакцию студентов (в основном смех). Рассказали, что понимают под AI сегодня, что изменилось с 50-х годов, показали видео из машин Google, а также своего робота, который аккуратно складывает рубашки и футболки. Мда, в моем ВУЗе передача знаний про AI началась и закончилась рассказом о тесте Тьюринга.

image

Минус для меня — это невозможность скачать видео с субтитрами себе локально.

Лекции хорошо, а практика? Ага на первой неделе имеем (Optional) Math Self Diagnostic, (Optional) Python Refresher.
Приведу здесь пример вопроса из раздела Math:

You are playing a solitaire game in which you are dealt three cards without replacement from a simplified deck of 10 cards (marked 1 through 10). You win if one of your cards is a 10 or if all of your cards are odd.
How many winning hands are there if different orders are different hands?
What is your chance of winning?


Собственно высшее техническое образование шепчет: «Где-то это уже было...» С помощью википедии математика вспомнилась. В python refresher было заглянул, но уверенность в своих силах, которая поселилась после Лутца и двух курсов, дала волю лени, и делать задачку я не стал, решив перейти к недели второй.

Поиск и деревья

С понятием графов и раскрытием поискового дерева был ознакомлен в ВУЗе. Поэтому ожидал, что будет скучновато. Но показанный преподавателем желтый старина Пэкмен удержал интерес. Depth First, Breadth First, Uniform Cost, Greedy, A*(with heuristic) Search — все это последовательно объяснялось, а в качестве примера служил Пэкмен, весело бегающий по лабиринту за точками в соответствии с алгоритмом поиска. И ни строчки кода в лекциях. Мне понравилось.

В тот же день с лекциями была осилена домашняя работа — графы и общие вопросы про жуков в лабиринте
А вот дальнейшая вкладка project 1 повергла в ступор. Скачайте архив (подробнее тут, спасибо Nbooo), запустите под python 2.7 pacman.py — поиграйте (можно запустить также с ключем -h для help). А теперь пишите свои функции в модуле search.py, ваш пэкмен должен найти еду в углу лабиринта. Вот так это выглядит.

image

Как же так, ведь как это написать нас не учили. Но раз уж взялся. Работа отставлена в сторону. В первый день было написано несколько кривых реализаций Depth First Search, пэкмен регулярно начал добираться до еды. Но они безжалостно удалялись, оказалось количество вскрытых поиском ветвей и оптимальность пути жестко контролируется. Тестируются ваши функции и методы автоматически, после загрузки исходных текстов на сервер. В очередной раз стерев страницу кода, бросил свой меч и взялся за орало. Листочки бумаги покрывались деревьями, рисунками пэкмена и лабиринта. Коллеги-электронщики считали своим долгом ухмыльнуться, проходя мимо. В итоге реализация была найдена. Кто хочет поучится — стоит помучаться самостоятельно. От тех кто на ты с питоном и алгоритмами, буду рад услышать замечания по делу.

Код
Думаю тут все понятно, util.Stack() и utilQueue() — фактически списки, обернутые в классы для удобства учащихся, с методами push и pop, FIFO и LIFO соответственно:

def depthFirstSearch(problem):
    """
    Search the deepest nodes in the search tree first

    Your search algorithm needs to return a list of actions that reaches
    the goal.  Make sure to implement a graph search algorithm

    To get started, you might want to try some of these simple commands to
    understand the search problem that is being passed in:

    print "Start:", problem.getStartState()
    >>> Start: (4, 3)
    print "Is the start a goal?", problem.isGoalState(problem.getStartState())
    >>> Is the start a goal? False
    print "Start's successors:", problem.getSuccessors(problem.getStartState())
    >>> Start's successors: [((4, 4), 'North', 1), ((4, 2), 'South', 1), ((5, 3), 'East', 1), ((3, 3), 'West', 1)]
    """
    def fromXYtoXY(coord1, coord2):
        '''
        tuple(int,int), tuple(int,int) -> str
        Takes near coord1 coord2 tuples, returns string way, or error
        sample for tinyMaze:
        >>>fromXYtoXY((5,5),(4,5))
        >>>'West'

        >>>fromXYtoXY((1,3),(2,3))
        >>>'East'
        '''
        if coord1[0]==coord2[0]:
            if coord1[1]-coord2[1]==1:
                return 'South'
            else:
                return 'North'
        elif coord1[1]==coord2[1]:
            if coord1[0]-coord2[0]==1:
                return 'West'
            else:
                return 'East'
        else:
            return ('Path not found from %s to %s' % (coord1, coord2))

    Fringe = util.Stack()
    currState=problem.getStartState()
    Fringe.push([currState])
    while True:
        currState=Fringe.pop()
        if problem.isGoalState(currState[-1]):
            listWays=[]
            fromState=currState[0]       # формируем выходной список с путями
            for state in currState[1:]:  # ex: ['South', 'West']
                listWays.append(fromXYtoXY(fromState,state))
                fromState=state
            return listWays
            break
        for State, Way, Price in problem.getSuccessors(currState[-1]):
            if not State in currState:
                nextPath=currState[:]
                nextPath.append(State)
                Fringe.push(nextPath)



Реализация Breadth First Search, по-моему, вышла уже немного красивее.

Код
def breadthFirstSearch(problem):
    """
    Search the shallowest nodes in the search tree first.
    """
    fringe=util.Queue()
    visitedNodes=[]
    fringe.push([problem.getStartState(),[]]) # сохраним стартовые координаты + нулевой путь

    while not fringe.isEmpty(): #пока в очереди есть чтото
        currNode = fringe.pop() #берем последний
        if currNode[0] not in visitedNodes: #если не было посещено
            visitedNodes.append(currNode[0])   #добавим
            for State, Way, Price in problem.getSuccessors(currNode[0]):
                path=currNode[1][:] #сделаем путь для дочерней ветки
                path.append(Way)
                if problem.isGoalState(State):
                    return path
                else:
                    fringe.push([State, path])



Потом были уже относительно легко реализованы Uniform Cost Search и A* Search (с Евклидовым расстоянием до еды в качестве heuristic-функции)

Код
def uniformCostSearch(problem):
    "Search the node of least total cost first. "
    fringe=util.PriorityQueue()
    visitedNodes=[]
    fringe.push([problem.getStartState(),[],0],0)
    while not fringe.isEmpty():
        currNode = fringe.pop()
        if problem.isGoalState(currNode[0]):
            return currNode[1]
        if currNode[0] not in visitedNodes: #если не было посещено
            visitedNodes.append(currNode[0])   #добавим
            for State, Way, Price in problem.getSuccessors(currNode[0]):
                path=currNode[1][:] #сделаем путь к дочерней ветке
                totalCost=currNode[2]+Price
                path.append(Way)
                fringe.push([State, path, totalCost],totalCost)

def aStarSearch(problem, heuristic=nullHeuristic):
    "Search the node that has the lowest combined cost and heuristic first."
    "*** YOUR CODE HERE ***"
    fringe=util.PriorityQueue()
    visitedNodes=[]
    fringe.push([problem.getStartState(),[],0],0)
    while not fringe.isEmpty():
        currNode = fringe.pop()
        if problem.isGoalState(currNode[0]):
            print 'Success!!', currNode[1]
            return currNode[1]
        if currNode[0] not in visitedNodes: #если не было посещено
            visitedNodes.append(currNode[0])   #добавим
            for State, Way, Price in problem.getSuccessors(currNode[0]):
                #print 'succ', State, Way, Price
                path=currNode[1][:] #сделаем путь к дочерней ветке
                totalCost=currNode[2]+Price
                path.append(Way)
                fringe.push([State, path, totalCost],totalCost+heuristic(State,problem))



Во второй части project 1 учащимся предлагалось видоизменить проблемы поиска в модуле searchAgents.py, адаптировав методы дочерних классов. Если раньше был один Пэкмен и одна еда, то теперь один Пэкмен и еда в 4-х углах, пройтись по которым нужно по оптимальному пути. А также придумать heuristic-функцию для A* Search, который призван сократить затраты на раскрытие ветвей дерева поиска (система оценки следующая: inconsistent heuristics will get no credit. 1 point for any non-trivial consistent heuristic. 1 point for expanding fewer than 1600 nodes. 1 point for expanding fewer than 1200 nodes.).

Закончился project 1 решением проблемы оптимального поедания множества точек в лабиринте.

image

В итоге почти 3 рабочих дня я потратил на решение этих задач, хорошо на работе было некоторое затишье. Поломать голову было интересно и, надеюсь, что полезно в перспективе.

Закончить хочу шутливыми словами преподавателя в одной из лекций:

Anything you want to do, NP-hard. Sorry, this is an AI class. Everything is hard.
Надеюсь, обзор немного помог кому-то. Курс (или просто порешать задачи) советую всем начинающим знакомится с python, а сам с нетерпением жду project 2.

upd. часть 2
Глеб @smartass111
карма
30,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разное

Комментарии (30)

  • +2
    В итоге почти 3 рабочих дня я потратил на решение этих задач

    Да, я вот тоже думала сначала, ну откуда там взяться 15-ти заявленным часам в неделю?
    Потом проколбасилась полтора выходных с кодом, успела сделать четверть (Python мне до этого был вовсе незнаком), осознала. Теперь буду приступать к проекту сразу после его релиза)
  • 0
    Ух, прям жалею что не потяну сейчас вместе с 6.00x еще 188.1x))
    • +1
      Кстати, судя по 6.00x syllabus, эти вещи про графы и поиск там будут в 19, 20 лекциях.
      Я сейчас еще попробовал этот python курс, там уклон в сторону визуализации
      программа
      Week Topics Mini-project
      1. Expressions, variables, functions, conditionals. «Rock-Paper-Scissors-Lizard-Spock» game
      2. Event-driven programming, local and global variables, buttons and input fields. «Guess the Number» game
      3. The canvas, static drawing, timers, interactive drawing. Stopwatch: The Game
      4. Lists, keyboard input, motion, positional/velocity control. «Pong» game
      5. Mouse input, more lists, dictionaries, images. «Memory» game
      6. Classes, tiled images. «Blackjack» game
      7. Acceleration and friction, spaceship class, sprite class, sound. Spaceship from «RiceRocks» game
      8. Sets, groups of sprites, collisions, sprite animation. Full «RiceRocks» game
      • 0
        Да, я видела)
        Спасибо за ссылку на курс)
        В целом, мне очень нравится как подают материал. Прям жалко, что у нас в вузе некому так качественно преподавать.
        Хех, на Сoursera я сейчас подписалась на эти два курса.
  • +4
    «Искал книжки и статьи по питону. Теперь Яндекс в контекстной рекламе предлагает купить питона, недорого, с доставкой.» ©
    • 0
      Потому что надо было писать «пайтон»!
  • +3
    Здорово, но код задач ( даже под спойлером) всё же не стоило выкладывать до окончания курса. ИМХО, конечно.

    P.S. Если не ошибаюсь, уже были прецеденты по поводу решений, выложенных на гитхабе.
    • +1
      Вдогонку — Раз, два.

    • 0
      Ну не до окончания курса, а хотя бы до дедлайна по домашнему заданию. Который вроде бы завтра.
      А Дэн Кляйн как лектор шикарен! Самое главное его отличие от всех вузовских преподов моей студенческой жизни — его реально интересно слушать. И хочется слушать. И при этом еще и понимаешь, что слышишь.
      • 0
        Про код — смотрите ссылки. Про лектора — согласен, огромное удовольствие смотреть и слушать! Очень увлекательно и увлечённо рассказывает :)
    • 0
      Дедлайн на project 1 был 14 числа, потом его продлили до 15го. Поэтому я не публиковал до 16го.
      • 0
        Еще раз — в Honor code написано «не публиковать», про дату это уже я написал. Впрочем, дело Ваше и совесть тоже :)
        • +1
          Да, я не прав, почему то отпечаталось в голове что до окончания приема заданий. Ну теперь уже менять ничего не буду.
        • 0
          Вроде, в обсуждении где-то было, что после всех дедлайнов можно выкладывать и обсуждать уже с кодом?
  • +12
    Потренировать своего питона!
    • +6
      Изучить ИИ поглубже!
      • +6
        Найти точку в лабиринте!
  • +2
    Хорошо излагаете, запитонил рассказ с лету.
  • 0
    "… удрученный средней по рынку зарплатой рядового электронщика"
    Не драматизируйте, человек который умеет программировать контроллеры и разрабатывать PCB зарабатывает достаточно на жизнь.
    • 0
      На жизнь хватает, но ведь тянет сравнивать.
      Например hh.ru дает совершенно разные результаты на запрос «схемотехник or электронщик» и на запрос «java». Да и бывает в одной и той же фирме соседние позиции «электронщик» «embedded программист» представлены с разницей до 2х раз.
      Плюс, на мой взгляд, в software development в России есть серьезные фирмы с интересными задачами, а с hardware все значительно хуже, большие и интересные проекты мне известны лишь в оборонке, с ее глупостями, зарплатами и прочим набором ньюансов.
      Хотя я не исключаю возможной кривизны собственных рук и ущербности подхода. Рад за тех коллег по электронному цеху, у кого все лучше чем у меня :)
  • 0
    deleted (промазал)
  • 0
    Да, в первом задании первого проекта чувствуешь себя несколько беспомощным :) Но стоит начать — сразу затягивает.
    Прекрасные задания.
  • 0
    Я ленивый, поэтому код поиска написал один для всех алгоритмов (и стоимость не хранил, а каждый раз вызывал getCostOfActions — да-да, я настолько ленивый):

    def genericSearch(problem, pushFn, popFn):
        closed = set()
        pushFn([], problem.getStartState())
        while True:
            actions, state = popFn()
            if problem.isGoalState(state):
                return actions
            if not state in closed:
                closed.add(state)
                for succ, action, cost in problem.getSuccessors(state):
                    pushFn(actions + [action], succ)
    

    Ну и дальше просто вызывал с нужными функциями push/pop:

    def breadthFirstSearch(problem):
        fringe = deque()
        return genericSearch(problem,
            lambda actions, state: fringe.append((actions, state)),
            lambda: fringe.popleft())
    
    def aStarSearch(problem, heuristic=nullHeuristic):
        fringe = []
        return genericSearch(problem,
            lambda actions, state: heapq.heappush(fringe, (problem.getCostOfActions(actions) + heuristic(state, problem), actions, state)),
            lambda: heapq.heappop(fringe)[1:])
    

    Сначала попробовал всё реализовать через очередь с приоритетами, но этот подход не понравился автопроверялке — она ожидала конкретных решений, для гарантии которых с PQ недостаточно голого приоритета, нужно пихать доп. данные. В общем, маразм выходит, да ещё и тормозной. А так всё оптимально, с самыми подходящими коллекциями.

    P.S. Советую не пользоваться самопальным util.Queue. У него стоимость push = O(len). :)
  • +1
    «Минус для меня — это невозможность скачать видео с субтитрами себе локально.» — Вполне можно, с помощью программы youtube-dl, например.
    Параметр --write-srt
    Только, как я вижу, для 6й лекции например субтитров вообще нету.
    • 0
      Есть субтитры нормальные (когда они есть), написанные специально обученными людьми, они на сайте EdX. Есть субтитры автогенеренные тытрубкой с помощью распознавания речи, они на тытрубке, соответственно. Нормальные субтитры на тытрубку никто не заливал, вроде, поэтому подобные качалки выдернут бесполезные автогенеренные.

      Вот пример субтитров с тытрубки:

      How about chess? = how much ass
      Deep Blue = demons = depots
      There've been huge advances in Go = their computer dances and go
      • 0
        Это от какой лекции? У меня на edx — html5 проигрыватель, с кнопкой CC — по нажатию на нее справа появляются субтитры. Для первых лекций они были, потом я их отключил, сейчас для 6 смотрю их нет. У вас не так?
        • 0
          Субтитры не отключали, их просто (ещё) не сделали. Вроде, от пятой лекции. Не помню точно.
          • 0
            Ну, качаю 5-А-Segment 6, --write-srt — начало — DAN KLEIN: тырпыр, т.е. то что на edX, явно не распознавание речи.
  • 0
    Я всего лишь хотел посмотреть, что посоветует хабр почитать по матану, чтобы изучить преобразование Фурье и запилить синтезатор на arduino, а теперь у меня два новых курса на питоне, с которым я незнаком.
  • 0
    Кстати, можно ещё сдать первое домашнее задание CS188.1x?

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.