До сих пор рассматриваемый процесс обучения состоял из внешнего цикла, который представлял собой процесс поиска структуры, и внутреннего цикла, представляющего собой процесс оптимизации параметров. В случае полных данных внутренний цикл выполняется очень быстро, поскольку при этом достаточно лишь извлечь информацию об условных частотах из набора данных. Если же имеются скрытые переменные, то для выполнения внутреннего цикла может потребоваться применить много итераций алгоритма ЕМ или алгоритма на основе градиента, а каждая итерация потребует вычисления распределений апостериорных вероятностей в байесовской сети, что само представляет собой NP-трудную задачу. К настоящему времени доказано, что такой подход является практически не применимым для определения в процессе обучения сложных моделей. Одно из возможных усовершенствований состоит в использовании так называемого алгоритма структурного ЕМ, который действует во многом таким же образом, как и обычный (параметрический) алгоритм ЕМ, за исключением того, что этот алгоритм может обновлять не только параметры, но и структуру. Так же как в обычном алгоритме ЕМ используются текущие параметры для вычисления ожидаемых количеств в Е-шаге, а затем эти количества применяются в М-шаге для выбора новых параметров, так и в алгоритме структурного ЕМ используется структура для вычисления ожидаемых количеств, после чего эти количества применяются в М-шаге для оценки правдоподобия потенциальных новых структур (в этом состоит отличие данного метода от метода внешнего цикла/внутреннего цикла, в котором вычисляются новые ожидаемые количества для каждой потенциальной структуры). Таким образом, структурный алгоритм ЕМ позволяет вносить в сеть несколько структурных изменений без каких-либо повторных вычислений ожидаемых количеств и обладает способностью определять в процессе обучения нетривиальные структуры байесовских сетей. Тем не менее необходимо проделать еще очень много работы, прежде чем можно будет утверждать, что задача определения структуры в процессе обучения окончательно решена.