Вероятностные модели в информатике доклад

Обновлено: 17.05.2024

Пусть в результате проведения эксперимента наступило некоторое случайное событие. Совокупность Z всех случайных событий, связанных с данным экспериментом, играет основную роль в нашем дальнейшем рассмотрении основ этго курса. Понятие случайного события имеет абстрактный характер, т.к. конкретная природа события не имеет значения. Существенно лишь то, что случайное событие А есть совокупность описаний w только тех элементарных событий, которые могут одновременно наступать с исходом А, и что событие А с w происходит или нет при осуществлении комплекса условий У поэтому между событий множества Z если и могут существовать соотношения, то только, в первую очередь, логического и теоретико-множественного характера. Если описание w некоторого элементарного события принадлежит пространству W, то будем писать wcW . Запись A=Z означает, что случайное событие А принадлежит совокупности Z . Противоположные утверждения, состоящие в том, что описание w элементарного события и случайное событие А не принадлежат соответственно пространству W и множеству Z, записываются в следующем виде.

Задача. Сколько различных пятизначных чисел н можно составить из чисел 1,2,3,4,5,6,7.если еть одна цифра, которая повторяется в числе ровно 2 раза а все другие цифры разные. Процесс составления числа, удовлетворяющего условию задачи представим в виде последовательного выполнения следующих трех действий:1. А1 есть выбор цифры которая будет повторяться 2 раза; 2.А2 Суть выбор 2-х мест в пятизначном числе для повторяющейся цифры;3.А3 означает выбор и расстановка трех разных цифр из оставшихся на три свободные места в пятизначном числе. Здесь получаем н1=7,н2=С….. н3=…. , следовательно н=7*10*120=8400.

2. Понятие сочетаний.

Любое размещение предметов, порядок которых не имеет значения, называется сочетанием. Из набора чисел 1, 2, 3, 4, 5 можно извлечь десятью различными способами любые два числа, если мы условимся не различать пары, состоящие из одних и тех же чисел, взятых в различном порядке, т.е., например, не различать 1, 2 и 2, 1. Если из двенадцати человек нужно выбрать комитет в составе девяти членов, то это можно сделать столькими способами, сколько сочетаний из двенадцати по девять мы можем составить. Это, естественно, относится к случаю, когда сам порядок размещения членов внутри комитета несуществен. Рассмотрим множество В =2 . ;B_M >, где B_t — различные множества, составленные из элементов множества G. Множества B_t , i = 1, 2,…M называются различными сочетаниями из N элементов по к, если каждое из них содержит ровно к различных элементов множества G, и все B_t различаются между собой хотя бы одним элементом. Число различных сочетаний из N элементов по к элементов обозначают через и М = =N!/(k!(N-k)!) где к=. Рассмотрим пример составления различных сочетаний. Пусть множество G есть группа из семи студентов. Пронумеруем всех студентов, тогда G =. Различные неупорядоченные наборы по три студента будут являться примерами различных сочетаний из семи по три. Например, множества , (1, 2, 4>, , , есть различные сочетания из семи по три. Всего можно составить ровно М -| = 7!/(3! (7 - 3)!) = 35 различных сочетаний из семи элементов по три. Если перед нами стоит задача вычисления числа различных способов, которыми можно выбрать трех студентов для дежурства по столовой, то ответом будет число М = 35

Сочетанием с повторениями называются наборы, в которых каждый элемент может участвовать несколько раз. Число сочетаний с повторениями из N по K равно =

3. Доказательство непрерывности вероятностной функции P(.):→ F[0;1]снизу

Вероятностной функции P(.):→F[0;1] непрерывна снизу, т.е.

для любой последовательности <> случайных событий.

Доказательство: Доказательство этого утверждения проведем в два этапа. Сначала покажем ,что

Итак, =и, следовательно

На втором этапе покажем, что

Ряд сходится, так как его сумма равна P()-P(),

А это конечное число. Поэтому остаток →0 при n→.

переходя к пределу во втором равенстве для P(),непосредственно получаем:

1. Служебный автобус и один из его пассажиров подходят к остановке в случайный момент времени от 6 часов до 6 часов 20 минут. Автобус стоит на остановке в течение пяти минут, а затем уезжает. Найти вероятность того, что пассажир опоздает на автобус.

Пусть х- время прихода автобуса, у- человека.

1) у х: человек пришел раньше и ждет до конца.

2) автобус пришел раньше, а человек пришел не позже чем на пять минут

2. В генуэзской лотерее разыгрываются 90 номеров, из которых выигрывают 5. По условию можно ставить ту или иную сумму на любой номер или на любую совокупность 2-х,3-х,4-х или 5 номеров, при чем для получения выигрыша должны быть угаданы все выбранные номера. Какова вероятность выигрыша в каждом из пяти случаев?

Построение информационной модели с использованием метода Монте-Карло

Метод статистических испытаний, численный метод решения математических задач при помощи моделирования случайных процессов и событий.

Монте-Карло (княжество Монако)

В удобной бухте Монако расположен очень живописный и довольно крупный (на 700 швартовочных мест) порт, куда заходят самые роскошные яхты со всего мира. Милостивый князь Монако не собирает налоги со своих подданных. Наоборот, заботится, чтобы их жизнь проходила как в сказке. Ведь все они – миллионеры и знаменитости. Нет, это не сценарий голливудского фильма. Просто самый настоящий рай на земле. Очень часто его так и называют – звездный Эдем…

Крохотное княжество Монако расположено на юге Европы, на побережье Средиземного моря, на стыке Приморских Альп и знаменитого Лазурного берега. По суше граничит только с Францией. На сегодняшний день страна занимает одно из первых мест в мире по плотности населения.

Вычисление числа Пи

Построим формальную модель для вычисления площади круга радиуса R, центр которого совпадает с началом координат. Круг вписан в квадрат со стороной 2R, площадь которого вычисляется как 4R 2

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

Наивный байесовский классификатор

Начну с того, что кратко повторю прошлый текст: мы уже говорили о наивном байесовском классификаторе в этом блоге. В наивном байесе делается дополнительное предположение об условной независимости атрибутов (слов) при условии темы:

В результате сложное апостериорное распределение удалось переписать как

И вот какая картинка этой модели соответствует:

Всё в точности как мы говорили в прошлый раз: отдельные слова в документе связаны с переменной категории расходящейся связью; это показывает, что они условно независимы при условии данной категории. Обучение наивного байеса заключается в том, чтобы обучить параметры отдельных факторов: априорного распределения на категориях p(C) и условных распределений отдельных параметров .

А общая модель всех документов (без плашек мы её не рисовали) будет состоять из нескольких копий этого графа и, соответственно, выглядеть так:

Здесь я явным образом нарисовал параметры распределения на категориях α и параметры – вероятности слов в каждой категории β. Поскольку у этих параметров нет отдельного фактора в разложении, им не соответствует узел сети, но часто удобно их тоже изобразить для наглядности. В данном случае картинка означает, что разные копии переменной C были порождены из одного и того же распределения p(C), а разные копии слов порождались из одного и того же распределения, параметризованного ещё и значением категорий (т.е. β – это матрица вероятностей разных слов в разных категориях).

Линейная регрессия

Продолжим ещё одной моделью, которую вы, возможно, смутно припоминаете из курсов матстатистики – линейной регрессией. Суть модели проста: мы предполагаем, что переменная y, которую мы хотим предсказать, получается из вектора признаков x как некоторая линейная функция с весами w (жирный шрифт будет обозначать векторы – это и общепринято, и в html мне это будет удобнее, чем каждый раз рисовать стрелочку) и нормально распределённым шумом:

В модели предполагается, что нам доступен некоторый набор данных, датасет D. Он состоит из отдельных реализаций этой самой регрессии, и (важно!) предполагается, что эти реализации были порождены независимо. Кроме того, в линейной регрессии часто вводят априорное распределение на параметры – например, нормальное распределение

Тогда мы приходим к вот такой картинке:

Здесь я явным образом нарисовал параметры априорного распределения μ₀ и Σ₀. Обратите внимание – линейная регрессия очень похожа по структуре на наивный байес.

С плашками то же самое будет выглядеть ещё проще:

Какие основные задачи, которые решаются в линейной регрессии? Первая задача – найти апостериорное распределение на w, т.е. научиться пересчитывать распределение w при имеющихся данных (x,y) из D; математически мы должны посчитать параметры распределения

В графических моделях обычно заштриховывают переменные, значения которых известны; таким образом, задача состоит в том, чтобы по вот такому графу со свидетельствами пересчитать распределение w:

Вторая основная задача (в чём-то даже более основная) – посчитать предсказательное распределение, оценить новое значение y в какой-то новой точке. Математически эта задача выглядит существенно сложнее, чем предыдущая – теперь надо интегрировать по апостериорному распределению

А графически как раз меняется не так много – мы рисуем новую переменную, которую хотим предсказывать, а задача по-прежнему та же: с некоторыми свидетельствами (из датасета) пересчитать распределение некоторой другой переменной в модели, только теперь это не w, а y * :

Скрытые марковские модели

Ещё один широко известный и популярный класс вероятностных моделей – скрытые марковские модели (hidden Markov models, HMM). Они применяются в распознавании речи, для нечёткого поиска подстрок и в других тому подобных приложениях. Скрытая марковская модель – это марковская цепь (последовательность случайных величин, где каждая величина x_t+1 зависит только от предыдущей x_t и при условии x_t условно независима с предыдущими x_t-k), в которой мы не можем наблюдать скрытые состояния, а видим только некоторые наблюдаемые y_t, которые зависят от текущего состояния. Например, в распознавании речи скрытые состояния – это фонемы, которые вы хотите сказать (это некоторое упрощение, на самом деле каждая фонема – это целая модель, но для иллюстрации сойдёт), а наблюдаемые – это собственно звуковые волны, которые доходят до распознающего устройства. Картинка получается вот какая:

Этой картинки достаточно, чтобы решать задачу применения уже готовой скрытой марковской модели: по имеющейся модели (состоящей из вероятностей перехода между скрытыми состояниями A, начального распределения цепи π и параметров распределений наблюдаемых B) и данной последовательности наблюдаемых найти наиболее вероятную последовательность скрытых состояний; т.е., например, в уже готовой системе распознавания речи распознать новый звуковой файл. А если нужно обучить параметры модели, лучше явно нарисовать их и на картинке, чтобы было понятно, что одни и те же параметры участвуют во всех переходах:

SVD и PMF

В целой серии постов (1, 2, 3, 4) мы говорили об одном из главных инструментов коллаборативной фильтрации – сингулярном разложении матриц, SVD.

Мы искали SVD-разложение методом градиентного спуска: конструировали функцию ошибки, считали от неё градиент, спускались по нему. Однако можно сформулировать и общую вероятностную постановку задачи, которая обычно называется PMF (probabilistic matrix factorization). Для этого нужно ввести априорные распределения на векторы признаков пользователей и продуктов:

(где I – единичная матрица), а затем, как в обычном SVD, представить рейтинги как зашумленные линейные комбинации признаков пользователей и продуктов:

где произведение берётся по рейтингам, присутствующим в обучающей выборке. Получается вот такая картинка (картинка взята из статьи [Salakhutdinov, Mnih, 2009]):

Можно добавить ещё один уровень байесовского вывода и обучать заодно и гиперпараметры распределений признаков для пользователей и продуктов; я сейчас не буду в это углубляться, а просто приведу соответствующую картинку (из той же статьи) – возможно, ещё доведётся поговорить об этом подробнее.

Байесовские рейтинг-системы

Поведение интернет-пользователей

И закончу ещё одним близким мне примером – моделями поведения интернет-пользователей в поисковых системах. Опять же, подробно вдаваться не буду – может быть, ещё вернёмся к этому, а пока можно почитать, например, нашу с Александром Фишковым обзорную статью – просто рассмотрю одну такую модель для примера. Мы пытаемся смоделировать, что делает пользователь, когда получает поисковую выдачу. Просмотр ссылки и клик трактуются как случайные события; для конкретной запросной сессии переменная E_i обозначает просмотр описания ссылки на документ, показанный на позиции i, C_i – клик на этой позиции. Введём упрощающее предположение: предположим, что процесс просмотра описаний всегда начинается с первой позиции и строго линеен. Позиция просматривается, только если все предыдущие позиции были просмотрены. В итоге наш виртуальный пользователь читает ссылки сверху вниз, если ему понравился (что зависит от релевантности ссылки), кликает, и, если документ действительно оказывается релевантным, пользователь уходит и больше не возвращается; любопытно, но факт: для поисковой системы хорошее событие – это когда пользователь как можно быстрее ушёл и не вернулся, а если он возвращается к выдаче, значит, не смог найти то, что искал.

В результате получается так называемая каскадная клик-модель (cascading click model, CCM); в ней пользователь следует вот такой блок-схеме:

Заключение и выводы

Помогите другим пользователям — будьте первым, кто поделится своим мнением об этой презентации.

Аннотация к презентации

Содержание

Вероятностные модели

Слайд 2

Содержание

Слайд 3

Что такое модель?

Модель — это искусственно создаваемый объект, заменяющий некоторый объект реального мира (объект моделирования) и воспроизводящий ограниченное число его свойств. Понятие модели относится к фундаментальным общенаучным понятиям, а моделирование — это метод познания действительности, используемый различными науками.

Слайд 4

Вероятностные модели

Вероятностные модели базируются на использовании больших серий испытаний параметрами, причём точность полученных результатов зависит от количества проведённых опытов. Воспользуемся методом Монте-Карло для исследования вероятностной модели бросания монеты.

Слайд 5

Вероятностная модель бросания монеты

Слайд 6

Сначала построим качественную вероятностную модель бросания монеты:

Слайд 7

Формальная модель

Пусть N – количество точек, которые случайным образом генерируются внутри квадрата. Случайный выбор координат точек, которые попадают внутрь квадрата (N точек), должен производиться так, чтобы координаты точек x и y удовлетворяли условиям: -1

Слайд 8

Компьютерная модель

Слайд 9

Проект «Бросание монеты

Метод Монте-Карло Х - . . . . . . . . . . . .. .. .. .. . . . . Количество бросани Количество бросаний 100 Орёл Решка 46 54 Пуск -1 1 1 -1

Слайд 10

Исследование модели

Слайд 11

Презентация была сделана ученицами 11Б класса Красниковой Мариной Тарасовой Ангелиной

Читайте также: