Point defects in solids are important because they can have a large influence on the mechanical, electronic, and optical properties. One of the most ubiquitous defects in metals is oxygen. Here, we use DFT to show that all three stable phases of cobalt display complex defect structures in the presence of oxygen. We calculate defect formation energies and migration barriers to elucidate the dominant diffusion mechanisms in these systems. In close packed hcp and fcc cobalt, we find that oxygen interstitials strongly reacts with vacancies to form split-vacancy centers, which provide an alternate diffusion mechanism for vacancies and oxygen. Diffusion in epsilon-cobalt follows a completely different route, occurring via a concerted indirect-exchange mechanism. We also present a machine learning approach for quick and accurate prediction of formation energies of compounds in the context of crystal structure predictions. Typical methods such as genetic algorithms often rely on DFT codes to perform such calculations at a relatively high computational cost. We illustrate a new means of representing crystal structures using radial and angular distribution functions and demonstrate two machine learning models capable of yielding low prediction errors of a few meV across the entire composition and phase space in binary systems. The high predictive accuracies make our models excellent candidates for the exploration of energy landscapes.