Omówiliśmy problem uczenia się struktur sieci Bayesa z pełnymi danymi. Kiedy nieobserwowane zmienne wpływają na obserwowane dane, sprawy stają się trudniejsze. W najprostszym przypadku ekspert może powiedzieć algorytmowi uczącemu się, że istnieją pewne ukryte zmienne, pozostawiając algorytmowi znalezienie dla nich miejsca w strukturze sieci. Podobnie jak w przypadku kompletnych danych, cały algorytm ma zewnętrzną pętlę, która przeszukuje struktury i wewnętrzną pętlę, która pasuje do parametrów sieci danej struktury. Jeśli algorytm uczący nie jest informowany o tym, które ukryte zmienne istnieją, są dwie możliwości: albo udawać, że dane są naprawdę kompletne – co może zmusić algorytm do uczenia się modelu z dużą ilością parametrów, -lub wymyśl nowe ukryte zmienne, aby uprościć model. To drugie podejście może zostać zaimplementowane poprzez uwzględnienie w wyszukiwaniu struktury nowych opcji modyfikacji: oprócz modyfikowania linków algorytm może dodać lub usunąć ukrytą zmienną lub zmienić jej arność. Oczywiście algorytm nie będzie wiedział, że wymyślona przez niego nowa zmienna nazywa się HeartDisease; nie będzie też miał znaczących nazw dla wartości. Na szczęście nowo wynalezione ukryte zmienne będą zwykle połączone z wcześniej istniejącymi zmiennymi, więc ekspert może często sprawdzić lokalne rozkłady warunkowe dotyczące nowej zmiennej i ustalić jej znaczenie. Podobnie jak w przypadku pełnych danych, samo uczenie się struktury maksymalnego prawdopodobieństwa spowoduje powstanie całkowicie połączonej sieci (co więcej, takiej, w której nie ma ukrytych zmiennych), więc wymagana jest pewna forma kary za złożoność. Możemy również zastosować MCMC do próbkowania wielu możliwych struktur sieciowych, tym samym przybliżając uczenie bayesowskie. Na przykład możemy nauczyć się mieszanin Gaussów o nieznanej liczbie składników, próbując ponad liczbę; przybliżony rozkład a posteriori dla liczby Gaussów jest podany przez częstotliwości próbkowania procesu MCMC. W przypadku pełnych danych wewnętrzna pętla do nauki parametrów jest bardzo szybka wystarczy wyodrębnić częstotliwości warunkowe ze zbioru danych. Gdy istnieją ukryte zmienne, wewnętrzna pętla może obejmować wiele iteracji EM lub algorytmu opartego na gradiencie, a każda iteracja obejmuje obliczenie a posteriori w sieci Bayesa, co samo w sobie jest problemem NP-trudnym. Do tej pory takie podejście okazało się niepraktyczne w przypadku uczenia się złożonych modeli. Jednym z możliwych ulepszeń jest tak zwany algorytm strukturalny EM, który działa w bardzo podobny sposób jak zwykły (parametryczny) EM, z tą różnicą, że algorytm może aktualizować zarówno strukturę, jak i parametry. Tak jak zwykły EM używa bieżących parametrów do obliczenia oczekiwanych zliczeń w kroku E, a następnie stosuje te zliczenia w kroku M do wyboru nowych parametrów, strukturalny EM używa bieżącej struktury do obliczenia oczekiwanych zliczeń, a następnie stosuje te zliczenia w kroku M M-krok do oceny prawdopodobieństwa potencjalnych nowych struktur. (To kontrastuje z metodą pętli zewnętrznej/pętli wewnętrznej, która oblicza nowe oczekiwane liczby dla każdej potencjalnej struktury). W ten sposób strukturalna EM może dokonać kilku zmian strukturalnych w sieci bez ponownego obliczania oczekiwanych zliczeń i jest w stanie uczenie nietrywialnych struktur sieciowych Bayesa. Strukturalny EM ma raczej przestrzeń poszukiwań nad przestrzenią struktur niż przestrzenią struktur i parametrów. Niemniej jednak, wiele pozostaje do zrobienia, zanim będziemy mogli powiedzieć, że problem uczenia się struktury został rozwiązany.