vadim_kataev (vadim_kataev) wrote,
vadim_kataev
vadim_kataev

Categories:

Интеллектуальные агенты. Часть 1


Найти и распарсить


Некоторые соглашения:

Агент
Сущность, взаимодействующая со своей окружающей средой. Это не просто пассивный наблюдатель, но инициатор действия. Если рассматривать агента как объект наблюдения Y в момент времени t, то можно сказать, что будущее поведение объекта Y хотя и продиктовано прошлым (t-dt) , без знания конкретной структуры конкретного объекта Y мы не сможем сделать достаточно точный прогноз о поведении объекта Y в будущем. Даже полное знание описания класса к которому принадлежит объект Y не позволит нам иметь гарантию точного предсказания поведения объекта в момент времени (t+dt) без возможности наблюдателя иметь информацию о внутреннем состоянии системы "объект Y" в момент t.

Отличия агентов от объектов
Выделим среди класса "объекты" некотрой системы все объекты, к которым не принадлежат агенты. Назовём их пассивными объектами и посмотрим на их отличия от агентов. Главное отличие состоит в том, что пассивные объекты в системе не являются сами инициаторами действий по изменению своего поведения в окружающей среде*. Так же у пассивных объектов отсутствуют механизмы защиты внутреннего состояния.

Впрочем, всё это звучит абстрактно и давайте посмотрим на примеры.
Пусть у нас есть два объекта, Камень и Жук.
Class Stone:
    states
    percept

Class Beatle:
    states
    percept


В states хранятся физические состояния объекта и на них может повлиять либо percept либо ограниченный класс законов (в случае для всех объектов это гравитация, для камня это ещё и например внутренняя радиоактивность)

percept является внешней поверхностью объекта, реагирующей на определённый класс законов (например, на свет, температуру, влажность). Таким образом, percept есть просто первый взаимодействующий слой объекта с окружающим миром.

Теперь конкретно про отличия. Скажем, мы пронаблюдали за объектами-представителями обоих этих классов и приходим к следующим выводам:

1) объект класса Beatle не поддаётся изменению своей внутренней структуры под действием некоторых воздействий на его percept. Исследуя класс Beatle, мы замечаем интересную особенность его структуры - она построена таким образом, что в state сохраняется информация о percept в моменты времени (t¹-dt¹, t¹) и имеется механизм позволяющий в момент времени t²-dt² при "похожем" состоянии percept "знать" состояние state в ещё не состоявшемся времени t², то есть образно говоря:
    if  percept[t¹-dt¹] == shadow   and  state[t¹] == low_energy:
        if percept[t²] == shadow:
            state[future(t² + dt²)] = low_energy

    if state[future(t² + dt²)] == low_energy:
        go()
    if state[future(t² + dt²)] == comfortable:
        stay()

такой объект всегда инициирует действие - избегать тени. Реализация механизма в структуре тела объекта.
Пусть вас не вводят в заблуждения обозначения low_energy и comfortable - это сделано для наглядности.
Пассивные объекты могут имеють такое поведение, но система Beatle сочетает в себе множество реакций и не только на освещённость.

2)а как выглядит поведение объекта Stone ?
    if  percept[t¹-dt¹] == temperature_up 
        state[t¹] = temperature_up
    ...
    if  percept[t¹-dt¹] == shadow
        state[t¹] = temperature_down

отличие камня от жука в таком случае есть отсутствие внутреннего сохранения информации о прошлом и использования этой информации для изменения своего поведения.

Рациональный агент
Агент, выбирающий наилучший вариант поведения среди множества альтернатив для удовлетворения определённой цели. Уровень рациональности поведения тем выше, чем лучше удовлетворяется цель.
Например, поисковый агент, который может находить более нужную информацию для пользователя за более короткое время чем другие агенты при одинаковой формулировке условий поиска для множества агентов, является более рациональным среди других агентов применительно к цели - поиску определённой информации.

Интеллектуальный программный агент
Программа, имеющая свойства рационального агента, запоминающая состояния окружающей среды, умеющая распозновать состояния окружающей среды на основе накопленной информации, делать прогнозы развития окружающей среды. Как правило, для окружающей среды используется информационное пространство Internet, а программа состоит из потока исполнения.

Посмотрим на типичную реализацию интеллектуального программного агента.
Работа агента представлена на рисунке жёлтыми прямоугольниками:



Как видим, искусственный интеллект агента базируется на обработке информационных потоков, изначально инициатором которых является человек. Данная схема так же может быть соотнесена со схемой работы службы google answers, где множество агентов-людей работая по этой схеме получают деньги от человека, задавающего вопросы.
Давайте подробно рассмотрим первую часть работы агента:

Понять и найти
Сначала человек инициирует запрос, скажем на обычном натуральном языке.
Лингвистическая конструкция сначала приводится к нормальному виду, где объекты запроса (слова), выстраивают дерево взаимосвязей have, is_a, part_of etc. Таким образом, переделанный запрос агент передаёт поисковым машинам и получает ответ либо в форме веб-страницы, либо в форме программных объектов. Например google позволяет вам бесплатно делать до 1000 запросов в сутки при подключении вашего агента через SOAP интерфейс:
import google
data = google.doGoogleSearch(search_terms)
total_results = len(data.results)
for d in data:
    print d

но я предпочитаю другую схему - самую надёжную, т.к. она не имеет ограничений на количество запросов и обрабатывает результаты которые расчитанны на клиента-человека а не на агента. Самым простым решением в таком случае становится парсинг страницы уже готовыми инструментами, например следующая комманда возвращает нам список URL на наш запрос:
lynx -dump "http://www.google.com/search?
num=10&hl=en&lr=&q=$1&btnG=Search" | 
grep '. http' | grep -v 'google'  | awk -F '. ' '{print $3}'


Не поленитесь и создайте скрипт search.sh состоящий всего из одной вышеприведённой комманды - она нам очень пригодится позднее при создании "умного" агента.

Есть ещё лучший способ:
    [...]
    req = urllib2.Request('http://www.google.com/search?lr=&ie=UTF-8&oe=UTF-8&q=' + Req)
    req.add_header('User-Agent', 'Mozilla/5.0 (X11; compatible; MSIE 5.5; Linux i666)')
    try:
        f = urllib2.urlopen(req)
    except IOError, e:
        if hasattr(e, 'reason'):
        print 'Error with reason : ';  print e.reason
    BUFSIZE = 8192 * 2
    while True:
        data = f.read(BUFSIZE)
        if not data: break
    [...]

в такой программе легко собрать необходимый парсер например с помощью наследования от класса sgmllib.SGMLParser (вспомните как работает LinuxOrgRu агент о котором я писал здесь)

Следующим шагом является просмотр страниц, к которым ведут ссылки со страницы результата поиска:
    a=open('from_google').readlines()
    a = [x[:-1] for x in a]
    x=0
    for URL in a:
        links -source ${URL} > result${x}
        x+=1


теперь посмотрим в наш директорий:
globalsearch: ls
google-search.py   result0    result12  result15  result18  result3  result6  result9
gsearch.py             result1    result13  result16  result19  result4  result7
numbers                result11   result14  result17  result2   result5  result8

у нас есть непропарсенных 20 результатов в виде html страниц. Следите за рисунком - сейчас мы в точке, где начинается кластеризация информации на relevant/irrelevant блоки.

Если вы внимательно следите за повествованием, то заметите, что всё что мы делаем поддаётся автоматизации и от человека зависят только условия запроса, поэтому мы смело можем делать все наши операции в форме скрипта.

Теперь наша задача распарсить эти страницы таким образом, что бы выделить из их тел необходимую нам информацию, проанализировать её и если нужно, выявить зависимости, изменить состояние локальной памяти, воспользоваться услугами других поисковых систем, сравнить результаты и т.д. Об этом я расскажу во второй части.

Рекомендуемое чтение для этой части:
M.E. Bratman
Intention, Plans and Practical Reason Harvard University Press: Cambridge, MA, 1987

S.Brin, L.Page
The Anatomy of a Large-Scale Hypertextual Web Search Engine Computer Science Department, Stanford, 2000

G.Wooldridge
Reasoning about rational agents Massachusets Institute of Technology, 2000

Продолжение следует.
Subscribe

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 17 comments