Convolutional Neural Networks (CNNs) offer an alternative to the image cross-correlation methods used in Particle Image Velocimetry (PIV) to reconstruct the fluid velocity field from the experimental recording. Despite the flexibility of CNNs, the accuracy and robustness of the standard image processing remains unsurpassed for general PIV data. As CNNs are non-linear and typically entail up to millions of trainable parameters, they require large and carefully designed training datasets to avoid over-fitting and to obtain results that are accurate for a wide range of flow conditions and length scales. Most training datasets consist of PIV-like data that are generated from displacement fields resulting from numerical flow simulations, which, in addition of being computationally expensive, may be able to inform the network only about relatively few classes of flow problems. To overcome this issue and improve the accuracy of the velocity reconstructed by CNNs, we propose to train the networks with synthetic PIV-like data generated from random displacement fields. The underlying idea is that the training dataset simply needs to teach the network about the kinematic relationship between position and velocity. These kinematic training datasets are computationally inexpensive and may allow a much richer variability in terms of length scales by varying the generation parameters. By training a state-of-the-art CNN, we investigate the accuracy of the reconstructed displacement and velocity with synthetic and experimental test cases, such as a sinusoidal flow and wind-tunnel data from a turbulent-boundary-layer and a cylinder-wake experiment. We demonstrate that kinematic training can drastically improve the accuracy of the CNN and allows the network to outperform conventional cross-correlation methods, being more robust with respect to data noise and providing reconstructed velocity fields that have considerably higher spatial resolution (at pixel level).