Do tej pory zakładaliśmy, że struktura sieci Bayesa jest podana i próbujemy tylko nauczyć się parametrów. Struktura sieci reprezentuje podstawową wiedzę przyczynową na temat domeny, którą ekspert, a nawet naiwny użytkownik może łatwo dostarczyć. Jednak w niektórych przypadkach model przyczynowy może być niedostępny lub podlegać dyskusji – na przykład niektóre korporacje od dawna twierdzą, że palenie nie powoduje raka, a inne korporacje twierdzą, że stężenie CO2 nie ma wpływu na klimat – dlatego ważne jest, aby zrozumieć jak na podstawie danych można nauczyć się struktury sieci Bayesa. Ta sekcja zawiera krótki szkic głównych pomysłów. Najbardziej oczywistym podejściem jest poszukiwanie dobrego modelu. Możemy zacząć od modelu nie zawierającego linków i rozpocząć dodawanie rodziców dla każdego węzła, dopasowując parametry do metod, które właśnie omówiliśmy i mierząc dokładność wynikowego modelu. Alternatywnie, możemy zacząć od wstępnego zgadywania konstrukcji i użyć wspinaczki lub symulowanego wyszukiwania wyżarzania, aby dokonać modyfikacji, dostrajając parametry po każdej zmianie w konstrukcji. Modyfikacje mogą obejmować odwracanie, dodawanie lub usuwanie łączy. Nie wolno nam wprowadzać cykli w procesie, więc wiele algorytmów zakłada, że dla zmiennych podane jest porządkowanie i że węzeł może mieć rodziców tylko wśród tych węzłów, które pojawiają się wcześniej w porządkowaniu . Dla pełnej ogólności musimy też przeszukać możliwe zamówienia. Istnieją dwie alternatywne metody decydowania o znalezieniu dobrej struktury. Pierwszym z nich jest sprawdzenie, czy warunkowe zapewnienia niezależności zawarte w strukturze są rzeczywiście spełnione w danych. Na przykład użycie naiwnego modelu Bayesa dla problemu restauracji zakłada, że:
P(Głodny,Bar |WillWait) = P(Głodny|WillWait)P(Bar | WillWait)
i możemy sprawdzić w danych, czy to samo równanie zachodzi między odpowiednimi częstotliwościami warunkowymi. Ale nawet jeśli struktura opisuje prawdziwą przyczynową naturę dziedziny, statystyczne fluktuacje w zbiorze danych oznaczają, że równanie nigdy nie zostanie dokładnie spełnione, więc musimy przeprowadzić odpowiedni test statystyczny, aby sprawdzić, czy istnieją wystarczające dowody na to, że hipoteza niezależności zostało naruszone. Złożoność powstałej sieci będzie zależeć od progu zastosowanego w tym teście — im bardziej rygorystyczny test niezależności, tym więcej dodanych łączy i tym większe niebezpieczeństwo przepełnienia. Podejściem bardziej zgodnym z pomysłami zawartymi w tym rozdziale jest ocena stopnia, w jakim proponowany model wyjaśnia dane (w sensie probabilistycznym). Musimy jednak uważać, jak to mierzymy. Jeśli spróbujemy znaleźć hipotezę maksymalnego prawdopodobieństwa, otrzymamy w pełni połączoną sieć, ponieważ dodanie większej liczby rodziców do węzła nie może zmniejszyć prawdopodobieństwa (Ćwiczenie 21.MLPA). Jesteśmy zmuszeni w pewien sposób karać złożoność modelu. Podejście MAP (lub MDL) po prostu odejmuje karę od prawdopodobieństwa każdej struktury (po dostrojeniu parametrów) przed porównaniem różnych struktur. Podejście bayesowskie stawia wspólne pierwszeństwo nad strukturami i parametrami. Zazwyczaj jest zbyt wiele struktur, aby można je było zsumować (superwykładniczy w liczbie zmiennych), więc większość praktyków używa MCMC do próbkowania struktur. Penalizowanie złożoności (czy to metodą MAP, czy metodą bayesowską) wprowadza ważny związek pomiędzy optymalną strukturą a charakterem reprezentacji dla rozkładów warunkowych w sieci. W przypadku rozkładów tabelarycznych kara złożoności dla rozkładu węzła rośnie wykładniczo wraz z liczbą rodziców, ale w przypadku, powiedzmy, zaszumionych rozkładów OR, rośnie tylko liniowo. Oznacza to, że uczenie się za pomocą modeli z zaszumionym OR (lub innymi zwartymi parametrami) ma tendencję do tworzenia wyuczonych struktur z większą liczbą rodziców niż uczenie się z rozkładami tabelarycznymi.