The variable network conditions of end-users demand different resolutions, formats, and bitrate versions of videos to be delivered over the network. Fetching each video from the Content Delivery Network (CDN) burdens all network layers. A promising solution is to leverage Mobile Edge Computing (MEC). This paper presents a Machine Learning based caching and transcoding model, which helps release the burden on the backhaul links of the network. The purposed scheme contains a task scheduler and time estimator. The time estimator predicts the job's transcoding time based on the Virtual Machines (VMs) load. The task scheduler maps the transcoding task to different VMs regarding the cost feasibility, Quality of Service (QoS) of the users, and the cost-to-performance ratio of VMs. For this purpose, we prepare a dataset of 500 videos and transcode each video in every lower representation using Amazon Elastic Compute Cloud (EC2). The time estimator is trained on 77% of the video dataset containing more than 80,000 transcoding time data of different videos. The simulation results show that the proposed scheme outperforms its counterparts in terms of cost, average delay perceived by the user, and backhaul burden.