Network virtualization has become a promising paradigm for supporting diverse vertical services in Software Defined Networks (SDNs). Each vertical service is carried by a virtual network (VN), which normally has a chaining structure. In this way, a Service Function Chain (SFC) is composed by an ordered set of virtual network functions (VNFs) to provide tailored network services. Such new programmable flexibilities for future networks also bring new network management challenges: how to collect and analyze network measurement data, and further predict and diagnose the performance of SFCs? This is a fundamental problem for the management of SFCs, because the VNFs could be migrated in case of SFC performance degradation to avoid Service Level Agreement (SLA) violation. Despite the importance of the problem, SFC performance analysis has not attracted much research attention in the literature. In this current paper, enabled by a novel detailed network debugging technology, In-band Network Telemetry (INT), we propose a learning based framework for early SFC fault prediction and diagnosis. Based on the SFC traffic flow measurement data provided by INT, the framework firstly extracts SFC performance features. Then, Long Short-Term Memory (LSTM) networks are utilized to predict the upcoming values for these features in the next time slot. Finally, Support Vector Machine (SVM) is utilized as network fault classifier to predict possible SFC faults. We also discuss the practical utilization relevance of the proposed framework, and conduct a set of network emulations to validate the performance of the proposed framework.