BC/NW 2013, №2 (23):6.2
СОВЕРШЕНСТВОВАНИЕ ТЕХНОЛОГИИ ПОИСКОВОГО ПРОЕКТИРОВАНИЯ ПОСРЕДСТВОМ ИСКЛЮЧЕНИЯ ЗАПРЕЩЕННЫХ КОМБИНАЦИЙ
Дзегеленок И.И., Вагнер Н.С.
(ФГБОУ ВПО «Национальный исследовательский университет «МЭИ», Москва, Россия)
Предпосылки к совершенствованию реализуемой технологии
Окружающий человека мир сложен и многообразен. Технический
прогресс ставит все новые и новые задачи. Разобраться в этом многообразии
нелегко. Пассивные наблюдения не позволяют принимать обоснованные решения не
только при создании сложных систем, но и при определении правил их грамотной
эксплуатации. А это значит, что ключевую роль должны играть процессы вовлечения
ЛПР–лица принимающего решения в технологию добывания новых знаний, составляющих
основу всякого осмысленного творения. Получаемое знание будет иметь ценность
тогда и только тогда, когда оно станет отражать реальное состояние дел в
настоящий период времени, то есть когда оно будет основано на актуальной
информации [16]. Собственно в этом и состоит проблема актуализации знаний. По
мере того как мы работаем с результатами наблюдения возникает вопрос о
корректности методики наблюдения. Если зафиксировать срез мира в виде конечного
набора количественно-качественных характеристик, то по мере изучения можно
поставить вопрос о значимости этих параметров. Зафиксируем значение
количественно-качественных характеристик в виде переменных 
, отображающих свойства
предметной области. Конкретным проявлением каждой характеристики будем
отображать качественные значения 
, где 
– номер предметной переменной, 
– индекс одного из
возможных значений предметной переменной 
. Определяемым таким образом предметным
переменным можно придать причинную интерпретацию 
обобщенного показателя качества. Для
определения степени принадлежности некоторого проявления окружающей среды можно
поставить вопрос о ранжировании этих параметров 
в зависимости от вклада этих параметров
в конечный результат.
При определенных ограничениях данная проблема может быть решена применением технологии поискового проектирования, направленной на открытие новых решений. В данном случае «открытие» рассматривается с позиций субъекта в виде ранее неизвестных ему областей существования эффективных и конкурентоспособных решений.
Негативное влияние запрещенных комбинаций
Для решения указанной проблемы на кафедре ВМСС разработан теоретический аппарат [2] и использующий его инструментарий [3], что позволяет целенаправленно приобретать необходимое эмпирическое знание. Однако при ближайшем рассмотрении полученных результатов этого оказалось мало. На самом деле при поисковом проектировании распределенных вычислительных систем, включая перспективные средства вычислительной техники и реализуемые на их основе корпоративные приложения [4] мы в большинстве случаев не можем получить однородное поисковое пространство из-за несовместимости отдельных значений различных параметров. Так, например, Microsoft Business Solutions Navision работает только под управлением ОС семейства Windows с собственной СУБД и Microsoft SQL Server. Данное приложение практически не поддерживает горизонтальную масштабируемость ввиду отсутствия встроенных средств синхронизации. Поэтому неизбежно появятся сочетания значений, называемые «абсурдными», которые принципиально нереализуемы при текущем состоянии информационных технологий. И, как следствие, возникает вопрос, не менее важный, чем решение самой задачи, а что следует делать с «абсурдными» комбинациями значений предметных переменных? Ведь пустоты в поисковом пространстве и их скопления приводят к лишним вычислениям при формировании искомого знания, представляемого в искаженном, чаще всего нелинейном виде.
Традиционная технология постановки и решения открытых задач
Открытая задача – это конструкция, включающая:
1. жестко не фиксированный набор предметных переменных , определяющих
свойства изучаемого мира объекта x, как правило, в виде разрозненных фактов;
2. имеющиеся в наличии примеры удачных, неудачных и
«абсурдных», возможно разрозненных фактов, индуктивное обобщение которых
приводит к получению искомого причинно – следственного знания ;
3. свободно задаваемое правило качественной оценки 
эмпирических
гипотез, выдвижение и оценка которых работает на повышение достоверности
искомого знания;
Таблица 1
Укрупнённая схема технологии поискового проектирования
|
1 |
Концептуализация |
|
2 |
Структуризация |
|
3 |
Характеризация |
|
4 |
Формальный синтез |
|
5 |
Аргументация |
Концептуализация «отвечает» за определение прагматики поискового проектирования в виде ответа на вопросы «Зачем?», «Для кого?» и «Почему?».
Структуризация нужна для выделения, хотя бы в общих чертах, внешних показателей качества и возможных ограничений на область существования искомой модели. От человека также требуется указание конкретных правил качественного (не обязательно количественного) оценивания возможных фактов, представляющих модель.
Характеризация предусматривает фиксацию конкретных свойств, определяющих существование альтернативных решений в виде фактов и мыслимых объектов. В дополнение определяется семантика поискового проектирования в виде физически и/или логически невозможных сочетаний конкретных проявлений рассматриваемых свойств. Работа блока завершается заданием начального обучающего множества фактов.
Первые три названных блока поддаются лишь частичной автоматизации, поскольку здесь по большей части работает человеческий фактор. Иное дело последующие блоки.
Формализованный синтез может быть осуществлён автоматически и в этом состоит основное преимущество данной методологии. Именно в этом блоке вырабатывается искомая модель на основе индуктивного обобщения изначально разрозненных фактов.
Аргументация предусматривает обоснование решений, вырабатываемых построенной моделью искомого знания. Это могут быть лучшие решения – «открытия» за пределами начальных представлений, а также рейтинговые оценки возможных альтернатив.
Каждый из пяти представленных блоков идейно и конструктивно опирается на Принцип структурного дополнения. Его суть состоит в привнесении, выявлении и использовании структурных свойств, направляющих исследователя к открытию нового [11]. В частности, этому принципу соответствует основной постулат актуализации знаний об упорядоченности изучаемого мира фактов. Именно этот принцип работает на реализуемые механизмы индуктивного обобщения фактов и выдвижения эмпирических гипотез [9,10].
Принципы и приемы исключения запрещенных комбинаций
Для борьбы с ними был разработан новый более совершенный
механизм, позволяющий преобразовать поисковое пространство таким образом, чтобы
в идеале не оставалось «абсурдных» точек. Его суть состоит в анализе
закономерностей среди «абсурдов», выявлении «запрещенных» комбинаций значений и
уменьшении размерности поискового пространства путем его свертки по параметрам,
входящим в эти комбинации. В результате последующего удаления значений,
соответствующих «запрещенным» комбинациям, происходит переход к решению
уточненной задачи поискового проектирования. Проведенные эксперименты
подтвердили повышение содержательной емкости поискового пространства и, как
следствие, увеличение качества приобретаемого знания. При этом качество
обучения определяется экспертом исходя из числа оцененных гипотез, адекватности
оценки фактов правилом . Следующим шагом перед принятием
решения о перепостановке является попытка объяснить полученные результаты.
Решение принимает эксперт, решатель может только подсказать возможный путь к
решению. Принципиальное отличие заключается в том, что при априорном подходе
предметные переменные, участвующие в создании новой переменной, заранее
определяются экспертом, а при апостериорном подходе переменные кандидаты
подбираются исходя из «соображений» решателя, не учитывающего семантику. В этом
случае решатель может не увидеть связь с дополнительной переменной и
перепостановка не на полном наборе определяющий переменных уменьшит
достоверность решения задачи. Например, при недостаточной степени исследования
поискового пространства всё может указывать на перепостановку по двум
переменным, а на самом деле, абсурдность определяется значениями трех
переменных. Для сведения этой проблемы к минимуму необходимо достаточное
исследование поискового пространства и семантическая оценка экспертом
результатов, полученных решателем.
Иллюстрация эффекта исключения запрещенных комбинаций
Модельная задача: поисковое проектирование web-сервера
Параметры:
• Платформа (x86, Sun)
• Операционная система (Windows, Unix)
• Программное обеспечение web-сервера (Internet Information Services, Apache)
• Используемая технология(PHP, ASP)
Это четырехмерное поисковое пространство можно представить в следующем виде:
Рис. 1. Исходное поисковое пространство модельной задачи
Запрещенные комбинации:
1. Windows на платформе Sun не работает
2. IIS не работает под Unix
Таким образом, список запрещенных комбинаций следующий:
Win – Sun – IIS
Win – Sun – Apache
Unix – Sun – IIS
Unix – x86 – IIS
Образуем декартово произведение значений 3-х «конфликтующих» переменных: 1. Операционная система, 2. Аппаратная платформа, 3. Веб-сервер и получаем двумерную плоскость (рис.2)
Рис. 2. Искомое поисковое пространство
Как видно на рис. 2, запрещенные комбинации сгруппировались (выделено пунктиром) по переменной PHP–ASP и теперь их можно исключить из заново сформированного 2-х мерного пространства. Следует, однако, заметить, что не всегда удается исключить абсолютно все «абсурдные» точки (запрещенные комбинации).
При оптимизации поискового пространства не стоит исключать «неабсурдные» точки, особенно положительные, так как можно выбросить открытие.
В результате из задачи с четырьмя переменными получилась задача с двумя переменными, но часть переменных у нее свернута. По числу оставшихся точек емкость полученного поискового пространства составляет 50% от первоначального пространства.
Направления дальнейшего развития реализуемой технологии
На протяжении ряда лет на кафедре ВМСС ведутся исследования
по применению и дальнейшему развитию данной технологии. Задачи ставятся
различные: и по мерности поискового пространства, и по сложности решающего
правила , и
по виду запрещенных комбинаций. Запрещенные комбинации могут возникать
спонтанного по мере тестирования окружающей среды, так и иметь семантические
предпосылки. В открытых задачах поискового проектирования можно выделить два
класса наиболее часто встречаемых задач: задачи выбора и задачи собственно
проектирования.
В настоящий момент сосредоточено внимание на возможности качественной оценки результатов решения открытых задач. Для этого применяются различные показатели качества, такие как коэффициент новизны получаемого знания, показывающий степень удаленности полученных результатов от начального знания в поисковом пространстве, глубина целеполагания, коэффициент достоверности, и коэффициент ранговой корреляции[9,10]. Можно оценить как отдельные решения, так и построенную модель искомого знания в целом.
Литература
1. Chakrebarti S . Mining the Web: Discovering Knowledge from Hypertext... Publisher: Morgan Kaufmann 2003.–345 p.
2. Cooley R., Mobasher B., and Srivastava J., Web mining: Information and pattern discovery on the World Wide Web// Proc. 9th IEEE Int. Conf. Tools with Artificial Intelligence, pp.558–567, Nov. 1997.
3. Kosla R. and Blockeel H. Web mining research a survey, SIG KDD Explorations, vol. 2, pp. 1–15, July 2000.
4. Ланде Л.В. Поиск знаний в Internet. Профессиональная работа. – М.: Диалектика.–272 с.
5. Бизнес-аналитика: от данных к знаниям / Н.Б.Паклин, В.И.Орешков – СПб.: Питер, 2010.–704 с.
6. Анализ данных и процессов / А.А.Барсегян, М.С.Куприанов, М.Д.Тэсс, С.И.Елизаров. – СПб.: БХВ-Петербург, 2009.–512
7. Chakrebarti S. Mining the Web: Discovering Knowledge from Hypertext... Publisher: Morgan Kaufmann 2003.–345 p.
8. Техническое творчество: теория, методология, практика. Энциклопедический словарь справочник / Под редакцией А.И.Половинкина и В.В. Попова–М.: Издательство «Информ-система», 1995, 408 с.
9. Дзегеленок И.И. Логика поиска проектных решений – М.: Моск. энерг. ин-т, 1984. – 64с.
10. Дзегеленок И.И. Открытые задачи поискового проектирования – М.: Моск. энерг. ин-т, 1991 . – 66с.
11. АРГОНАВТ – система приобретения эмпирических знаний. -В кн. Справочно-практическое издание "СОФТЕЛЬ – Сто компьютерных программ для бизнеса". Вып. 1997-1998. -М.: Издательство «ХАМТЕК ПАБЛИШЕР», 1997, с. 117-125
12. Дзегеленок И.И. Методология поискового проектирования вычислительных систем/ /Информационная математика.– Изд-во РАЕН АСТ- Физматлит, № 1(4), 2004, с.110–119
13. Дзегеленок И.И. Сетевые образовательные технологии актуализации знаний. «Информационные технологии в проектировании и производстве»: Науч.-технич. журн./ФГУП «Всероссийский институт межотраслевой информации», 2003. №3, с.10–15
14. Дзегеленок И.И., Филипьев И.В. Подход к созданию интеллектуального агента согласованного информационного поиска в Интернет/9-я Национальная конференция по искусственному интеллекту. Труды конференции. Том 2.-М.: Физматлит, 2004, с. 715–722
15. Дзегеленок И.И., Аляева Ю.В., Кузнецов А.Ю. Инструментальные средства поискового проектирования. Лабораторные работы №1–3: методическое пособие.– М.: Издательский дом МЭИ, 2007.– 40 с.
16. Становление и развитие научной школы искусственного интеллекта в московском энергетическом институте / Вагин В.Н., Еремеев А.П., Колосов О.С., Дзегеленок И.И., Фролов А.Б.// Программные продукты и системы.– Тверь , 2010. –№3. С.3–16
17. Дзегеленок И.И. На пути к преобразованию информационных ресурсов Интернет в актуальное знание // Информационные ресурсы России, №2, 2011
18. Дзегеленок И.И.,Кондратьев М.А.,Аляева Ю.В. Применение решателя открытых задач: методическое пособие – М. : Издательский дом МЭИ, 2012.–– 48.с.