Annotating videos manually is very costly and time consuming. Human being?s subjective and different understanding often lead to incomplete and inconsistent annotations and poor system performance. So it is an importance topic to annotate automatically semantic concepts for a video. Discovering the relationships among several concepts coexisting in the same video can help automatic semantic annotation. In this paper, we propose an improved K2 algorithm to learn the structure of the semantic network based Bayesian Network. Its advantage over Original K2 algorithm is no need for users to provide a complete node ordering. The system automatically determine the complete node ordering when users only can give a partial node ordering or even no prior at all. Experiment results show that our algorithm performs a little better than Original K2 algorithm in the application to automatic semantic annotation for video shots.